Combinatorics: Number of ways to make 1500 dollars

Question

I have 50 bills of 20\$ and 20 bills of 50\$ and 10 bills of 100\$. With how many ways a bank machine could make the 1500\$ ?

what I think is :as the cofficient of $x^{1500}$ in $(1+x+x^2+\ldots+x^{1000})^3$

Answer 1

First note that you can't have a lone \$50 bill - they must always be paired with another to make a multiple of \$100. Then the same applies to \$20 bills, except they need to appear in packs of $5$, again to make a \$100 bundle.

This simplifies the issue considerably, since now you have 3 stacks of $10$ items: \$100 bills, \$50 pairs, \$20 bundles, with each item worth \$100.

So now it's a division with limits. We can enumerate picking $15$ items from $3$ classes with $\binom {15+2}2$. Then we can remove all cases when we pick more of than one class than the $10$ allowed by allocating $11$ items to each class in turn and counting how we can divide the remaining $4$ items.

So the result is $\binom {17}{2}-3\binom {6}{2}$.

Answer 2

To keep numbers small let's divide the note values by $10$ so we have $50$ of $2$, $20$ of $5$ and $10$ of $10$ and want to make $150$. Because the other two denominations and the target amount are divisible by $5$, in all ways of making $150$ the number of $2$ notes must be a multiple of $5$, so effectively we have $10$ notes of $10$ but in a different kind – think different series of notes. Then, by the same logic, the number of $5$ notes used must be even, so it is like $10$ notes of $10$ in a third kind. Now we can divide note values by $10$ again, leading to the ultimate reduced question:

What is the number of integer solutions to $a+b+c=15$ where $0\le a,b,c\le10$?

We count the number of ways with no upper limit on the variables, which is $\binom{15+3-1}{3-1}=136$, then subtract the number of ways where one of the variables is at least $10$: three times the number of nonnegative integer solutions to $a+b+c=4$, equalling $45$. Thus the final answer is $91$: there are $91$ ways for the ATM to dispense \$1500.