Find a recurrence relation for the number of ways to pay a bill of n dollars if the order in which the coins and bills are paid matters.

We have "coins" of 1, 2, 5, 10$ and "bills" of 5, 10, 20, 50 and 100$.

How to begin doing this sum?

Printable View

- June 4th 2008, 08:59 AMrobocop_911find a recurrence relation
Find a recurrence relation for the number of ways to pay a bill of n dollars if the order in which the coins and bills are paid matters.

We have "coins" of 1, 2, 5, 10$ and "bills" of 5, 10, 20, 50 and 100$.

How to begin doing this sum? - June 13th 2008, 06:13 AMPaulRS
Okay, let's call the number of ways in which you can the bill of n dollars.

Note that if we want to pay a bill of n+1 dollars we can add a coin of a dollar to n dollars, this can be done in ways, now if we want to add a coin of 2 dollars this can be done in ways (since we need n-1 dollars), and so on...

Summing all the possibilities:

(1)

Now for this to always make sense we define if and (there's only one way of paying nothing) and then is defined by (1) if - June 13th 2008, 09:17 AMnatarajchakraborty
Wow, but I got some doubts.... the derivation is quite tough for me....

How this works?

Quote:

now if we want to add a coin of 2 dollars this can be done in ways (since we need n-1 dollars), and so on...

I think it is about assumption that to pay a bill of we need so we need ways to pay a bill of

but still I need some explanation.... am I right in my thinking....

cheers... - June 13th 2008, 09:32 AMPaulRS
Forget about the bill, the only thing you want is to know in how many ways you can hand in n+1 dollars using that type of coins and notes.

If we want to GIVE A $1 coin at the end (for we care about the order), we need to have $N otherwise will NOT be giving $N+1, but we can give $N dollars in ways, thus if the thing you want to hand in last is a 1 dollar coin you can do this in ways

Now the other cases (according to what you want to give last) are very similar and so, by the sum rule we have what I'd posted