Number of ways to make $n$ cents

Question

How to find a recurrence relation for $F(n)$ the number of ways to make n cents change using only pennies (4 cents), nickels(5cents), and dimes(10cents) and ordering matters.

There are three exclusive case here

1. Start with pennies then new subproblem is $F(n-4)$
2. Start with nickels then new subproblem is $F(n-5)$
3. Start with dimes then new subproblem is $F(n-10)$

$$F(n) = F(n-4)+ F(n-5) + F(n-10) $$

Is there any other way to solve this problem. The above method is ok but seems like magic to beginner. Is there any systematic approach to solve this problem?

Problem is also available on https://math.stackexchange.com/questions/248853/how-to-find-recurrence-relation-for-this-problem

Answer 1

If we try to apply your recurrence to $n = 9$ and add the base case $F(0) = 1$, then we get $F(9) = 2$. Now this might be the answer you want, since there are indeed two possibilities: penny+nickel and nickel+penny, but usually we consider these the same.

There are two ways to proceed if we want to compute the number of ways without regard to order. The first way is to consider three different functions $F,G,H$ which correspond to using all coins ($F$), only nickels and dimes ($G$), and only dimes ($H$). The recurrences are $$ F(n) = F(n-4) + G(n-5) + H(n-10), \\ G(n) = G(n-5) + H(n-10), \\ H(n) = H(n-10), $$ with initial conditions $F(0) = G(0) = H(0) = 1$ and $F(m) = G(m) = H(m) = 0$ for negative $m$. This gives a joint linear recurrence for the triplet $F(n),G(n),H(n)$.

The other approach is to use generating functions, which give us the following expression: $$ \sum_{n=0}^\infty F(n) x^n = \frac{1}{(1-x^4)(1-x^5)(1-x^{10})} = \frac{1}{1-x^4-x^5+x^9-x^{10}+x^{14}+x^{15}-x^{19}}. $$ This shows that the sequence $F(n)$ satisfies the recurrence $$ F(n) = F(n-4) + F(n-5) + F(n-10) \\- F(n-9) - F(n-14) - F(n-15) + F(n-19) $$ with initial conditions $F(0) = 1$ and $F(m) = 0$ for negative $m$.

This can be seen as a kind of inclusion/exclusion principle — I'll let you work out the details.

Answer 2

That is the systematic way of solving this kind of question. Generally trying to find a recurrence is one of the possible first steps of solving combinatoric problems.

Note that in order for the recurrence to be efficient you have to use memoization, remembering previous $F$ that you calculated, this is (somewhat poorly) called dynamic programming.