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?

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.