Maths IA · Algebra and functions · topic 4 of 40
Coin change: how fast does the count of ways grow? · IB Maths IA idea: guide, sample graph and step-by-step plan
easy to start, hard to finish wellHow many ways can you pay 50 cents? By hand it is easy, then hopeless. You're going to build a machine that counts for you, then ask how fast the count explodes.
- ✓ you like counting puzzles
- ✓ you can write a short loop or a spreadsheet formula
- ✓ you enjoy proving that a pattern is really true
The big idea
← the prediction is your hook!Each coin value gives a series that says how many of that coin you use: 1 + x^c + x^2c + … Multiply the series for your coin set and the coefficient of x^n is the number of ways to make n. One idea joins counting, recurrences and series. Generating functions are in neither course, so you introduce them yourself and explain every step. Predict first: how fast should the count grow, and what decides the rate? Then test your prediction against exact counts and prove what you can. At HL, spotting a pattern in small cases is not enough for criterion E: you need HL-level maths such as partial fractions and series, and a proof.
Make it yours: pick one twist
Copying a classic won't show your choices. Pick one of these (or invent your own) and your IA becomes yours.
Swipe for more twists →
Use real coins, a made-up set, or values with no common factor such as 3 and 5.
→ The generating function changes, and you can test whether the growth depends on the actual values or only on how many coins you have.Count sequences of coins (1 then 2 is different from 2 then 1) instead of combinations.
→ The generating function becomes one reciprocal and the recurrence is a single linear one. Predict how its growth compares with the unordered count, then test it.Allow at most a fixed number of each coin, as in a till that is running low.
→ Each infinite series becomes a polynomial, so you work with finite sums and a different kind of count.Test whether always taking the biggest coin gives the fewest coins, for several coin sets.
→ You move from counting to optimisation. You need a proof or a counterexample, which is a good test of rigour.Use partial fractions or a series expansion to explain why the count grows like it does, rather than only fitting a curve.
→ The core of your exploration becomes analytic, with a justified claim. This is the HL-level route.Vending machines, stamps, postage, or a game with point scores.
→ Gives your introduction a real purpose; the maths stays the same.Your Maths IA research question: run the check
can algebra answer it?Write your own question first. Then make sure it ticks every box:
- Names the coin set (or the family of sets) and says exactly what is counted: combinations or ordered payments.
- Says what you will describe about the count: a formula, a growth rate, or a comparison between coin sets.
- Can be answered by algebra that you show, not only by output from a program.
- Is narrow enough for 12 to 20 pages: one clear thread, not five coin systems touched lightly.
- At HL, needs a method beyond SL level (series, partial fractions, proof) to answer it.
The model
define every symbolThe generating-function idea in one picture. Draw yours with your own coin set and your own notation, and define every symbol.
How your Maths IA could be laid out
The usual order for a topic like this, what each part needs to show, and roughly how much of your 12 to 20 pages it takes. The words are all yours.
Your question, why counting change interests you (something real), and what you expect before you calculate anything.
Small cases listed in a systematic order so the reader sees the problem and your first pattern. Stop when it becomes repetitive.
Why a product of series counts the ways; every symbol defined; what x stands for and what it does not.
A recurrence or table that gives exact counts, how you computed it, and how you checked it against your hand counts.
Your claim about growth, the algebra behind it, and a graph of the exact counts against your model.
A justified argument, not an example. At HL this is where criterion E is won or lost.
A different set that tests whether your result is general or only true for your first choice.
Limits of the model, which assumptions mattered, what you would test next. Also place short reflections after surprises, not only here.
Go back to your aim and say whether it was met, using what you found.
Sources for the generating-function method and any code library used.
What your Maths IA graph could look like
Made-up data, to show you the form of a strong graph, not the answer. Your coin set and counts will differ. example only
- Axis labels say what n measures and in what unit, and what is being counted.
- Exact counts as points, the model as a curve. There is no error bar because the counts are exact; say so in your text.
- Two curves show the reader what the extra term in your model is doing.
- A log scale on the vertical axis would show the growth class (polynomial or exponential) more clearly.
- Another graph to consider: plot the ratio of your exact counts to the model, to show how the gap behaves as n grows.
Your game plan
hand counts first, then code!Tick steps off as you go. We'll remember on this device.
0 of 10 done
- Read and predictRead how generating functions count combinations. Before computing, write down what you expect: how fast should the count grow with one, two, three coin values?
- Trial run (1 lesson)Count the ways for small amounts by hand with a tiny coin set, in an order that avoids repeats. Write a short program or spreadsheet that gives the same numbers.
- Choose your coin setPick the set and say why. Decide whether you are counting combinations or ordered payments, and keep to it throughout.
- Build the generating functionWrite the product of series for your set. Explain in your own words why the coefficient of x^n counts the ways.
- Check it against the hand countsExpand the first few terms and compare with your trial run. If they disagree, find out why before moving on.
- Get exact countsProduce counts for a wide range of n by a recurrence or a table. Say how you checked a few of them independently.
- Describe the growthGraph the counts, decide what type of growth it is, and write down a claim about it with the reason you expect it to be true.
- Prove itJustify the claim with algebra: partial fractions, a series expansion, or a bound. If you cannot prove it all, prove part and say clearly what is left.
- Test a second coin setDoes the same argument work? Where does it need to change? Reflect on what this tells you about your first result.
- Write, cut, checkWrite in the layout order and keep repeated calculations to one worked example plus a table. Then run the checklist and get your question checked before your teacher reads a draft.
Maths you'll need
Traps to avoid in this Maths IA
- Spotting a formula from small cases and stating it as fact. Without a proof, rigour is missing.
- Counting ordered payments when you meant combinations (or the other way round) halfway through.
- Pasting program output or a computer algebra result as the maths, with no derivation of your own.
- At HL, an exploration that stays at SL level: listing cases and a simple recurrence will cap criterion E, even if it is all correct.
- Treating x as a number to be solved for. It is a placeholder; say so, and say what you do about convergence.
- Four coin systems done lightly instead of one or two done properly.
- Reflection only in the last paragraph. Put short reflections where something surprised you.
More Maths IA ideas like this
- Chords in a circle: which formula counts the regions?●●○
- Newton's method: how fast, and when does it fail?●●○
- Repeating decimals: what is the pattern in the digits?●●●
This guide shows how a topic like this is usually approached. It is not an IA. Your question, choices, data, analysis and words must be your own: change something, tell your teacher where the idea came from, and follow your school's rules on outside help.