1. ## Recursive Relations...

I need help with this question...I have no idea how to start it.

A country uses as currency coins with values of 1 cent, 2 cents, 5 cents and 10 cents and bills with values of 5 cents, 10 cents, 20 cents and 100 cents. Find a recurrence relation for the number of ways to pay a bill of n cents if the order in which the coins and bills are paid matters.

ie a(17) = 9494

2. Originally Posted by chickeneaterguy
I need help with this question...I have no idea how to start it.

A country uses as currency coins with values of 1 cent, 2 cents, 5 cents and 10 cents and bills with values of 5 cents, 10 cents, 20 cents and 100 cents. Find a recurrence relation for the number of ways to pay a bill of n cents if the order in which the coins and bills are paid matters.

ie a(17) = 9494
Sorry I had a logic flaw at first.

for all n < 0: a(n) = 0
a(0) = 1
for all n > 0: a(n) = a(n-1) + a(n-2) + 2*a(n-5) + 2*a(n-10) + a(n-20) + a(n-100)

Now my answer agrees with the problem statement. Safe to ignore what I wrote below.

~~~~~~ Begin original response ~~~~~~~

This is common for the problem solving necessary for various computer science problems.

Say a(n) is the number of ways to pay. If you pay with a 1 cent coin, you're left with n-1 coins. If you pay with a 2 cent coin, you're left with n-2 coins.

Define: for all n $\displaystyle \le$ 0, a(n) = 0.

Define b(n) such that b(1) = 1; b(2..4) = 2 meaning b(2)=2, b(3)=2, b(4)=2; b(5..9) = 4; b(10..19) = 6; b(20..99) = 7; b(100..) = 8.

Then for all n > 0: a(n) = b(n) + a(n-1) + a(n-2) + 2*a(n-5) + 2*a(n-10) + a(n-20) + a(n-100).

Programmatically, we could implement with if-then statements;

if (n < 1) return 0;
s = 1 + a(n-1);
if (n > 1) s += 1 + a(n-2);
if (n > 4) s+= 2 + 2*a(n-5);
etc.

Edit: Hmm I'm getting a(17) = 14227, maybe I mistyped something. Edit 2: After fixing a bug, I now consistently get a(17)=21727 with the two different implementations given above. Can someone help decide whether this is right or the problem statement is right?

~~~~~~ End original response ~~~~~~~

3. Thanks a lot, I plugged in values to verify

a(0) = 1
a(1) = 1
a(2) = 2
a(3) = 3
a(4) = 5
a(5) = 10
a(6) = 10 + 5 + 2 = 17
a(7) = 17 + 10 + 4 = 31
a(8) = 31 + 17 + 6 = 54
a(9) = 54 + 31 + 10 = 95
a(10) = 95 + 54 + 20 + 2 = 171
a(11) = 171 + 95 + 34 + 2 = 302
a(12) = 302 + 171 + 62 + 4 = 539
a(13) = 539 + 302 + 108 + 6 = 955
a(14) = 955 + 539 + 190 + 10 = 1694
a(15) = 1694 + 955 + 342 + 20 = 3011
a(16) = 3011 + 1694 + 604 + 34 = 5343
a(17) = 5343 + 3011 + 1078 + 62 = 9494

It makes perfect sense as to why you did it the way you did. Thanks a lot!

4. Originally Posted by chickeneaterguy
Thanks a lot, I plugged in values to verify

a(0) = 1
a(1) = 1
a(2) = 2
a(3) = 3
a(4) = 5
a(5) = 10
a(6) = 10 + 5 + 2 = 17
a(7) = 17 + 10 + 4 = 31
a(8) = 31 + 17 + 6 = 54
a(9) = 54 + 31 + 10 = 95
a(10) = 95 + 54 + 20 + 2 = 171
a(11) = 171 + 95 + 34 + 2 = 302
a(12) = 302 + 171 + 62 + 4 = 539
a(13) = 539 + 302 + 108 + 6 = 955
a(14) = 955 + 539 + 190 + 10 = 1694
a(15) = 1694 + 955 + 342 + 20 = 3011
a(16) = 3011 + 1694 + 604 + 34 = 5343
a(17) = 5343 + 3011 + 1078 + 62 = 9494

It makes perfect sense as to why you did it the way you did. Thanks a lot!
You're welcome! If you're curious, my first solution calculated a different thing, which is: the sum of the number of coins/bills used for every possible way to pay.

5. That's cool. It seemed like that's what the question was asking for since it said "Find a recurrence relation for the number of ways to pay a bill of n cents if the order in which the coins and bills are paid matters." So I was a bit unsure there. I hate doing arithmetic on these...because if you screw one up, you screw all of them up.

6. Originally Posted by chickeneaterguy
That's cool. It seemed like that's what the question was asking for since it said "Find a recurrence relation for the number of ways to pay a bill of n cents if the order in which the coins and bills are paid matters." So I was a bit unsure there. I hate doing arithmetic on these...because if you screw one up, you screw all of them up.
The order mattering is simply a way of saying: paying a 3 cent bill with a 1 cent and then a 2 cent coin is different from paying with a 2 cent and then a 1 cent coin. It makes for a simple recursive solution.

I don't think there was any ambiguity in the question, I simply used wrong logic the first time around, due to not being careful enough. I agree it's quite easy to make a little mistake that throws everything off.

7. By the way, you might benefit from a CAS (computer algebra system) such as Pari/GP which I highly recommend (and is open source), I don't know about Mac but it's available in linux and windows distributions, (if google fails you can ask me how to set up), in it you can simply type

Code:
a(n)=if(n<0,0,if(n==0,1,a(n-1)+a(n-2)+2*a(n-5)+2*a(n-10)+a(n-20)+a(n-100)))
and then just type a(17) and it spits out the answer, can be somewhat spoiling..

8. Thanks, I have one already that I use for school(it's required) but for my discrete mathematics course I'll need to work problems out anyway. This problem was somewhat similar to the one I need to turn in.