A067997 Number of (unordered) ways of making change for n cents using coins of 1/2, 1, 2, 3, 5, 10, 20, 25, 50, 100 cents (all historical U.S.A. coinage denominations up to 100 cents).

1, 2, 4, 7, 11, 17, 25, 35, 48, 64, 85, 110, 141, 178, 222, 275, 337, 409, 493, 589, 702, 830, 977, 1144, 1333, 1549, 1792, 2065, 2372, 2714, 3100, 3528, 4005, 4534, 5119, 5769, 6485, 7273, 8140, 9089, 10135, 11276, 12524, 13885, 15366, 16983, 18738

Offset: 0

Author

Rick L. Shepherd, Feb 08 2002

Keywords

• easy
• nonn

Comments

The U.S.A. issued the following unusual denomination coins during the 18th and 19th centuries: 1/2-cent pieces, 1793-1857; 2-cent pieces, 1864-1873; 3-cent pieces, 1851-1889; and 20-cent pieces, 1875-1878. This sequence is also the number of ways of making change for n cents using coins of 1 (two types, say, old pre-1858 "large cents" and 1856-to-present "small cents"), 2, 3, 5, 10, 20, 25, 50, 100 cents. For present purposes, one of the two types of 1-cent piece is actually taken to be two 1/2-cent pieces.

Examples

			a(2)=4 because change can be made for 2 cents in these 4 ways: (1) 4 1/2-cent coins, (2) 2 1/2-cent, 1 1-cent, (3) 2 1-cent, (4) 1 2-cent coin.
		

References

• R. S. Yeoman, A Guide Book of United States Coins, Ed. Kenneth Bressett, 53rd Edition (2000). New York: St. Martin's Press, 1999. pp. 72-77, 92-93, 104-106, 135. (also known as The Official Red Book of United States Coins)

Links

• Ron Guth, Your Online Reference For U.S. Coins
• Mitch Hight, United States Coinage History
• Clint Leland, U.S. Coins Quantities Minted
• Index entries for sequences related to making change.
• Index entries for linear recurrences with constant coefficients, order 217.

Crossrefs

Cf. A067996, A067995, A001314 (two kinds of nickels), A028291 (analog for 1/2, 1, 2, 3, 5 only, or 1(two types), 2, 3, 5 only).

Programs

Mathematica

CoefficientList[ Series[1 / ((1 - x)^2(1 - x^2)(1 - x^3)(1 - x^5)(1 - x^10)(1 - x^20)(1 - x^25)(1 - x^50)(1 - x^100)), {x, 0, 50} ], x]

PARI

a(n)=polcoeff(1/((1-x)^2*(1-x^2)*(1-x^3)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^25)*(1-x^50)*(1-x^100)+x*O(x^n)), n)

Formula

G.f.: 1/((1-x)^2*(1-x^2)*(1-x^3)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^25)*(1-x^50)*(1-x^100))