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?
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?
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}$
Wow, but I got some doubts.... the derivation is quite tough for me....
How this works?
well I got it about $\displaystyle 2a_{n-4}$ since there are two ways to pay a $\displaystyle 5$ dollar, by coin and a bill....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...
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