Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Try to find the generating function first. –  Mhenni Benghorbal Dec 1 '12 at 22:43
    
try breaking up the problem by supposing that you are using $k$ 5's. Then figure out how many such $k$ are possible, which is something akin to $[n/5]$ (floor function). You can account for multiplicities in each configuration by figuring out how many elements you have: $N=(n-5k)+k$, and looking at $N$ choose $k$. Perhaps you can find a simpler recursion by considering how the number of ways goes up from $n$ to $n+1$... –  Alex R. Dec 1 '12 at 22:43
    
@MhenniBenghorbal: since it’s clear from the OP’s example that different orderings are counted as distinct, generating functions are surely overkill here — this problem could well come up in a course that doesn’t even mention generating functions. –  Peter LeFanu Lumsdaine Dec 1 '12 at 23:24
    
@PeterLeFanuLumsdaine: It is a suggestion! –  Mhenni Benghorbal Dec 1 '12 at 23:32
    
I appended some of my attempt so far.. –  xiamx Dec 1 '12 at 23:32

1 Answer 1

up vote 2 down vote accepted

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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