1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This recurrence is wrong for the usual variant in which we don't care about the order of coins, that is, a penny and a dime we consider the same as a dime and a penny. $\endgroup$ – Yuval Filmus Feb 7 '18 at 13:09
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If we consider the ordering then I think expression will be$ \frac{1}{(1-x^4)} + \frac{1}{(1-x^5)} + \frac{1}{(1-x^{10})} $ ? $\endgroup$ – Complexity Feb 7 '18 at 13:28
  • 1
    $\begingroup$ If you consider the ordering, it will be $1/(1-x^4-x^5-x^{10})$. $\endgroup$ – Yuval Filmus Feb 7 '18 at 13:35
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Complexity Experience and logic. Generally you try to state your solution in terms of a smaller problem and go from there. $\endgroup$ – orlp Feb 7 '18 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.