Combinatorics Problem w/ money (exact purchase with XXX coins) Mr. Long Johns has 2 pennies, 3 nickels, 2 dimes, 3 quarters, and 8 dollar coins. For how many different amounts can John make an exact purchase? (no change required)


  
*
  
*A penny is 1 cent
  
*A nickel is 5 cents
  
*A dime is 10 cents
  
*A quarter is 25 cents
  
*A dollar coin is 100 cents

So....
1 cent
2 cents
5 cents
6 cents
7 cents
10 cents
11 cents
12 cents....
Any other way other than brute force?
 A: Count the amounts you can get that are under a dollar (we'll jigger the rest in momentarily).
If you do a few, you'll see them as ${0,1,2,5,6,7,10,11,12...}$ - three out of each five consecutive values.
There are $3/5*100 = 60$ such values (including zero - we'll get to that...)
For each of the nine possible dollars used (including zero), that gives $9*60 = 540$.
Now, drop the zero case, $540-1 = 539$.
Finally, add in the values where a dollar's worth of non-dollar coins and the eight dollar coins are combined with the remaining coins: $9.00, 9.01, 9.02, 9.05, 9.06, 9.07, 9.10, 9.11, 9.12$ - so nine of them.
That gives $539+9 = 548$ possible distinct amounts.
A: You can have $0,1$ or $2$ pennies, so work out how many ways without pennies and multiply by 3.
You can either make a full dollar or more with loose change, or not.
If not, you can make any multiple of $5c$ from $0c$ to $95c$, and any number of dollars from $0$ to $8$.
If you make at least a dollar with loose change, you can also make $9.00$, $9.05$ and $9.10$.
Put them together, and subtract $1$ from the final total for $0c$.
A: Based on http://ocw.mit.edu/courses/mathematics/18-310c-principles-of-applied-mathematics-fall-2007/lecture-notes/22_2_ln.pdf the generating function for the possible amounts is:
$$ \sum_{i=0}^2 x^i \sum_{j=0}^3 x^{5j} \sum_{k=0}^2 x^{10k} \sum_{l=0}^3 x^{25l} \sum_{m=0}^8 x^{100m}$$
which can be expanded and the possible amounts are the exponents of $x$ in that expanded form (possible ways to make them are the coefficients of these terms).
