I went into the bank to get change for a dollar. The teller said, "How do you want the change, buddy? I mean, there are 292 ways involving pennies, nickels, dimes, quarters, and half-dollars to give change for a dollar!"

Since I didn't like her attitude, I didn't answer her question. I simply said, "Well, I certainly don't want any pennies."

How many ways are there for her to give me change now?

(Note: Americans, always shunning simplicity have chosen to name their coins in the following easy-to-remember manner: Penny=1 cent, Nickel=5 cents, Dime=10 cents, Quarter=25 cents, Half Dollar=50 cents)

(In reply to Solution (After all that) by Lewis)

The problem with combining all pairs of ways of getting 50 cents is that some pairs add up to the same number of quarters, dimes and nickels as a completely different pair.

For example (0 q 0 d 10 n) combined with (0 q 5 d 0 n) gives 0 q 5 d 10 n, but so does (0 q 1 d 8 n) & (0 q 4 d 2 n), as well as (0 q 2 d 6 n) & (0 q 3 d 4 n). If this one way of changing a dollar (5 dimes and 10 nickels) could be counted three times under different arrangements, then it could be counted 3003 times for all its permutations (15!/(5!10!)). Counting all the permutations of all the ways would produce 27,517 arrangements.

Posted by Charlie on 2003-06-20 08:55:20