Home > Advanced Problems > Combinatorics

Note: this page uses MathJax for formatting, so may take a few seconds to load.

MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
function showSolution() {
if (document.getElementById('divSolution').style.display == "none")
{ document.getElementById('divSolution').style.display = "block"; }
else
{ document.getElementById('divSolution').style.display = "none"; }
}
document.getElementById('divSolution').style.display = "none";

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*.