Mathacadabra
Home > Advanced Problems > Combinatorics
Note: this page uses MathJax for formatting, so may take a few seconds to load.


Ordered Change For A Dollar

How many ways can you make change for a dollar if the order of the coins is important? Suppose that the available coins are pennies, nickels, dimes, quarters, and fifty-cent pieces.

For example, two different ways to make change for a dollar are \[ 5+25+25+25+10+10 \quad \mbox{and} \quad 10+25+25+25+10+5. \]

Solution
Let $a(n)$ be the number of ways to make change for $n$, where $n \geq 1$. The sequence is $\{a(n)\}=\{1,1,1,1,2,3,4,5,6,9,\ldots\}$. A recurrence formula follows from the observation that in a given way to change a specific amount, the first unit can be a penny, nickel, dime, quarter, or fifty-cent piece. This leaves the remaining amount of money to be changed. If we set $a(0)=1$, and $a(n)=0$ when $n$ is negative, we get \begin{align*} &a(0)=1; \quad a(n)=0, \; \mbox{for} \; n<0;\\ &a(n)=a(n-1)+a(n-5)+a(n-10)+a(n-25)+a(n-50), \quad \mbox{for} \; n > 0. \end{align*} The recurrence gives (via computer) \[ a(100)=8{,}577{,}874{,}824{,}928 \] a bit over eight trillion.

What if we ask the same question, but where the order of the units does not matter? The answer is a bit smaller: 292. You may be entertained solving this problem. It is the last problem in George Pólya's famous book, How to Solve It.