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

- Jun 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? - Jun 13th 2008, 06:13 AMPaulRS
Okay, let's call $\displaystyle a_n$ 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 $\displaystyle a_n$ ways, now if we want to add a coin of 2 dollars this can be done in $\displaystyle a_{n-1}$ ways (since we need n-1 dollars), and so on...

Summing all the possibilities:

$\displaystyle a_{n+1}=a_{n}+a_{n-1}+2a_{n-4}+2a_{n-9}+a_{n-19}+a_{n-49}+a_{n-99}$ (1)

Now for this to always make sense we define $\displaystyle a_n=0$ if $\displaystyle n<0$ and $\displaystyle a_{0}=1$ (there's only one way of paying nothing) and then $\displaystyle a_{n+1}$ is defined by (1) if $\displaystyle n\geq{0}$ - Jun 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 $\displaystyle a_{n-1}$ ways (since we need n-1 dollars), and so on...

I think it is about assumption that to pay a bill of $\displaystyle n$ we need $\displaystyle a_{n}$ so we need $\displaystyle a_{n-1}$ ways to pay a bill of $\displaystyle n-1$

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

cheers... - Jun 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 $\displaystyle a_n$ ways, thus if the thing you want to hand in last is a 1 dollar coin you can do this in $\displaystyle a_n$ 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