number of ways to make $2.00

How many different ways can you make $2.00 using only 1 cent, 5 cent, 10 cent, and 25 cent pieces, and 1 and 2 dollar bills (there are 100 cents in a dollar)? I have worked out an equation:

$$p + 5n + 10d + 25q + 100l + 200t = 200$$

Where all variables are non-negative integers. But I don't know what to do from here to figure out how many different sets of non-negative integers there are that satisfy this equation. What do I do next?

Solution 1:

Recursive algorithm for general monetary systems:

Let $f(x;a_0,a_1...a_k)$ be the number of ways to make $x$c with coins/notes of value $a_i$.

$f(200;1,5,10,25,100,200)=1+f(200;1,5,10,25,100)$

$f(200;1,5,10,25,100)=1+f(100;1,5,10,25)+f(200;1,5,10,25)$

$f(200;1,5,10,25)=1+f(25;1,5,10)+...+f(200;1,5,10)$

Carry on like this, using $f(0;...)=1$ and

$f(x;a_0..a_k)=1+f(a_k;...a_{k-1})+...+ f(na_k;...a_{k-1})$

where $n$ is the greatest integer such that $na_k \leq x$.

Solution 2:

Use generating functions. All you have to do is find the coefficient of $x^{200}$ in the formula $$ (1 + x + x^2 + \cdots)(1 + x^5 + x^{10} + \cdots)(1 + x^{10} + x^{20} + \cdots) $$ $$ \cdot (1 + x^{25} + x^{50} + \cdots)(1 + x^{100} + x^{200} + \cdots)(1 + x^{200} + x^{400} + \cdots) $$

The problem is inherently quite computation-heavy, but reducing it to the question above makes the computation much more straightforward, and also very easy to do with a computer.