1
$\begingroup$

How to find a recurrence relation for F(n) the number of ways to make n cents change using only pennies, nickels(5cents), and dimes(10cents)... So for 9 cents, there are 6 ways, which are

1 1 1 1 1 1 1 1 1 ( 9 pennies) 5 1 1 1 1 (1 nickel followed by 4 pennies) 1 5 1 1 1 1 1 5 1 1 1 1 1 5 1  1 1 1 1 5 

My attempt so far:

I tried cases up to n=9 just to see how the numbers change

n=0: 1 way (0,0,0) where each element in this vector represent                     number of penny, nickel and dime respectively n=1  1 * (1,0,0)  1 way n=2  1 * (2,0,0)  1 way n=3  1 * (3,0,0)  1 way n=4  1 * (4,0,0)  1 way n=5  1 * (5,0,0)        1 * (0,1,0)  2 ways n=6  1 * (6,0,0)      2 * (1,1,0)  3 ways n=7  1 * (7,0,0)      3 * (2,1,0)  4 ways n=8  1 * (8,0,0)      4 * (3,1,0)  5 ways n=9  1 * (9,0,0)      5 * (4,1,0)  6 ways 

But I still can't seem to find any sort of subroutine which I can use to build my recurrence.

  • 0
    @xiamx: Ok, then you need to solve the problem using the tools that you have been taught.2012-12-01

1 Answers 1

3

If I’m specifying a way to make change for n cents, I have three options: start with a dime, and then make change for the remaining $(n-10)$ cents; or start with a nickel, then make change for the remaining $(n-5)$ cents; or start with a penny, then do the remaining $(n-1)$ cents.

So there are:

  • $F(n-10)$ ways starting with a dime;
  • $F(n-5)$ ways starting with a nickel;
  • $F(n-1)$ ways starting with a penny.

Adding these up gives: $ F(n) = F(n-1) + F(n-5) + F(n-10) $

Is this the sort of recurrence relation you were looking for?