## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 94 combinatorics/coinage/combinations.p

Assuming you have enough coins of 1, 5, 10, 25 and 50 cents, how many

ways are there to make change for a dollar?

combinatorics/coinage/combinations.s

292. The table is shown below:

Amount 00 05 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Coins
.01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
.05 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
.10 1 2 4 6 9 12 16 20 25 30 36 42 49 56 64 72 81 90 100 110 121
.25 1 2 4 6 9 13 18 24 31 39 49 60 73 87 103 121 141 163 187 214 242
.50 1 2 4 6 9 13 18 24 31 39 49 62 77 93 112 134 159 187 218 253 292

The meaning of each entry is as follows:

If you wish to make change for 50 cents using only pennies, nickels and dimes,

go to the .10 row and the 50 column to obtain 36 ways to do this.

To calculate each entry, you start with the pennies. There is exactly one

way to make change for every amount. Then calculate the .05 row by adding

the number of ways to make change for the amount using pennies plus the number

of ways to make change for five cents less using nickels and pennies. This

continues on for all denominations of coins.

An example, to get change for 75 cents using all coins up to a .50, add the

number of ways to make change using only .25 and down (121) and the number of

ways to make change for 25 cents using coins up to .50 (13). This yields the

answer of 134.

Continue to: