Coin Combinations to Make a Dollar

Date: 11/12/96 at 07:42:16
From: The Rosol's
Subject: Dollars and coins

What is the number of combinations you need to get a dollar by using
pennies, nickles, dimes, quarters, and half dollars, and what is the
equation you use to get it from?

Date: 12/12/96 at 23:51:21
From: Doctor Donald
Subject: Re: Dollars and coins

It is possible to answer this question by systematically listing all 
the possibilities, but it is laborious. There is a fairly 
sophisticated solution to the problem in Introductory Combinatorics by 
Bogart, a 1983 text; it uses generating functions.  The discussion 
there is too elaborate to go into here; my guess is that there are
no substantially simpler approaches, though of course brute force 
enumeration is "simpler".

Apparently the problem is due to Polya, in an article in the American 
Mathematical Monthly, December 1956

Hope this helps.

-Doctor Donald,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 12/12/96 at 23:51:21
From: Doctor Donald
Subject: Re: Dollars and coins

There really isn't an equation for doing a problem like this.  But you
can use an organized way of counting.  For example:

Half-dollars    Quarters     Dimes     Nickels     Pennies    
   2                0          0          0           0
   1                2          0          0           0
   1                1          2          1           0
   1                1          1          3           0
   1                1          1          2           5
   1                1          1          1          10
   1                1          1          0          15
   1                1          0          5           0
   1                1          0          4           5
   1                1          0          3          10

You keep going this way.  If you can see patterns along the way,
you may not have to list every possibility.  

Another way to shorten the counting is to smaller amounts, then add
them up.  For example, what are the ways to make 25 cents?

Quarters    Dimes      Nickels      Pennies
   1          0            0            0
   0          2            1            0
   0          2            0            5
   0          1            3            0
   0          1            2            5
   0          1            1           10

Keep going.  When you get this, every time you see a quarter in the 
large table above, you can write this number in its place.  This way 
you don't keep repeating the dimes, nickels, and pennies every time.

Have fun.

-Doctor Gerald,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/