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,3

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.

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

Table of n, a(n) for n=0..54.

Index entries for sequences related to making change.

Index entries for linear recurrences with constant coefficients, order 216.

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))

Example

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.

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 ]

Prog

(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)

Crossrefs

Cf. A067995, A067997, A000008.

Sequence in context: A062435 A171997 A020702 * A074715 A325350 A027585

Adjacent sequences: A067993 A067994 A067995 * A067997 A067998 A067999

Keyword

easy,nonn

Author

Rick L. Shepherd, Feb 07 2002

Extensions

Offset corrected to 0 by Ray Chandler, Dec 04 2023

Status

approved