# 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?

• Yes, it can be done without brute force. It's a decent exercise in mental arithmetic. – David K Jan 21 '15 at 5:14
• So the only way is brute force then – suomynonA Jan 21 '15 at 5:43

## 3 Answers

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.

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$.

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).