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

1, 1, 2, 3, 4, 6, 8, 10, 13, 16, 21, 25, 31, 37, 44, 53, 62, 72, 84, 96, 113, 128, 147, 167, 189, 216, 243, 273, 307, 342, 386, 428, 477, 529, 585, 650, 716, 788, 867, 949, 1046, 1141, 1248, 1361, 1481, 1617, 1755, 1904, 2065, 2232, 2424, 2614, 2824, 3045, 3278

Offset: 0

Author

Rick L. Shepherd, Feb 07 2002

Keywords

• easy
• nonn

Comments

The U.S.A. issued the following unusual denomination coins during the 19th century: 2-cent pieces, 1864-1873; 3-cent pieces, 1851-1889; and 20-cent pieces, 1875-1878.

Examples

			a(5)=6 because change can be made for 5 cents in these 6 ways: (1) 5 1-cent coins, (2) 3 1-cent, 1 2-cent, (3) 2 1-cent, 1 3-cent, (4) 1 1-cent, 2 2-cent, (5) 1 2-cent, 1 3-cent, (6) 1 5-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. 104-106, 135. (also known as The Official Red Book of United States Coins)

Links

• Index entries for sequences related to making change.
• Index entries for linear recurrences with constant coefficients, order 216.

Crossrefs

Cf. A067995, A067997, A000008.

Programs

Mathematica

CoefficientList[ Series[1/((1 - x)(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, 55} ], x ]

PARI

a(n)=polcoeff(1/((1-x)*(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)*(1-x^2)*(1-x^3)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^25)*(1-x^50)*(1-x^100))

Extensions

Offset corrected to 0 by Ray Chandler, Dec 04 2023