Change for a Dollar

Date: 01/22/2001 at 17:35:06
From: maria E. Lacey
Subject: Coins used to change one dollar

Could you please tell me the two hundred plus ways in which coins are 
used to make change for one dollar?

Date: 01/23/2001 at 11:43:55
From: Doctor Greenie
Subject: Re: Coins used to change one dollar

Hi, Maria -

It wouldn't do you any good for us to tell you the 292 different ways 
to make change for a dollar. We are here to teach mathematics - that 
is, to help you learn ways to answer questions like this for yourself.

I will provide a sketch below of how I would go about enumerating all 
of the different ways to make change for a dollar. You can also find 
several pages in the Dr. Math archives where this problem is discussed 
(using slightly different approaches). To find these pages, click on 
the "Search the Archives" link on the main Dr. Math page and enter 
"change for a dollar" as the phrase to look for. (Be sure to click on 
the button that makes the search engine look for the entire phrase 
instead of the individual words.)

The key to answering this question correctly and completely is to 
organize your list of ways to make change for a dollar in such a way 
that you make sure that you (a) count every possibility, and (b) don't 
count any possibilities more than once. With this goal in mind, there 
are two key features to my approach to this problem:

(1) Break the problem into smaller parts. I will enumerate all the 
possible combinations I can have for the numbers of half dollars and 
quarters; then for each of those combinations I will enumerate the 
number of ways I can make up the remaining part of a dollar using 
dimes, nickels, and pennies.

(2)  Keep the list in either strictly ascending or strictly descending 
order in terms of the numbers of coins of different denominations. I 
personally prefer to order my list with the largest numbers of 
largest-denomination coins at the top. I hope this will be clear from 
my outline below.

So here is a list of all the possible combinations I can have of half 
dollars and quarters.  The list also shows, for each combination of 
half dollars and quarters, the remaining amount to made up using 
dimes, nickels, and pennies.

                      remaining
    half                amount
   dollars  quarters   (cents)
 -------------------------------
      2        0          0

      1        2          0
      1        1         25
      1        0         50

      0        4          0
      0        3         25
      0        2         50
      0        1         75
      0        0        100

Notice the arrangement of this list. The first entry is the one that 
uses the maximum number (2) of the largest-denomination coin (half 
dollars).  The next three entries are those that use the next largest 
number (1) of half dollars; these three entries are arranged with the 
one using the largest number of quarters (2) first and the smallest 
number of quarters (0) last. Similarly, the last five entries use the 
smallest number (0) of half dollars; and they are arranged with the 
entry having the largest number of quarters (4) first and the smallest 
number of quarters (0) last.

To complete the answer to the problem, you now need to find the 
numbers of different ways to make either 0, 25, 50, 75, or 100 cents 
using only dimes, nickels, and pennies. Once you have done that, you 
can find the total number of ways to make change for a dollar by 
adding a column to the table above showing the number of ways to make 
change for a dollar using each of the possible combinations of half 
dollars and quarters. Then your table will look like this:

                      remaining     number of ways to make
    half                amount      remaining amount using
   dollars  quarters   (cents)    dimes, nickels, and pennies
 -------------------------------------------------------------
      2        0          0              1

      1        2          0              1
      1        1         25             12
      1        0         50             36

      0        4          0              1
      0        3         25             12
      0        2         50             36
      0        1         75             72
      0        0        100            121
                                      -----
        Total number of ways to make   292
               change for a dollar

I have filled in the numbers in the last column for you. Clearly if 
the amount to be made up using dimes, nickels, and pennies is 0 (i.e., 
the whole dollar is made up using half dollars and/or quarters) then 
there is exactly one way to make up the remaining "0 cents": 0 dimes, 
0 nickels, and 0 pennies. To determine the other numbers in the last 
column, you can make an organized list of all the possibilities, as I 
have done for the first part of the problem above.

For example, below is an outline of the organized list showing that 
there are 36 ways to make change for 50 cents using dimes, nickels, 
and pennies. In this list, I have not listed all the possible 
combinations. Instead, I have only indicated, for each possible number 
of dimes, the possible numbers of nickels I can use. I can do this 
because, since any amount of money can be made using all pennies, I am 
able to choose any number of nickels and make up the remaining amount 
with pennies. Notice again the arrangement of the entries, with the 
largest possible number of dimes first and the smallest possible 
number of dimes last.

Number of Ways to Make Change for 50 Cents Using Dimes, Nickels, 
Pennies:

                choices for
    dimes    number of nickels    number of choices
   -------------------------------------------------
      5              0                 1
      4          0, 1, or 2            3
      3            0 to 4              5
      2            0 to 6              7
      1            0 to 8              9
      0            0 to 10            11
                                     ----
    Total number of ways to make      36
        change for 50 cents using
        dimes, nickels, and pennies

See if you can build the tables showing that the numbers of ways to 
make change for 25 cents, 75 cents, and 100 cents using dimes, 
nickels, and pennies are as shown in the table above (12, 72, and 121, 
respectively). When you have done so, you will have enumerated all 292 
possible ways for making change for a dollar.

Your original question asked for us to show you all the possible ways 
to make change for a dollar.  As you can see, doing so would be very 
tedious. But at this point, you should know what the 292 different 
ways are, without having to write them out.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/