A001364 Number of ways of making change for n cents using coins of 1, 2, 4, 12, 24, 48, 96, 120 cents (based on English coinage of 1939).

1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 12, 12, 17, 17, 22, 22, 29, 29, 36, 36, 45, 45, 54, 54, 67, 67, 80, 80, 97, 97, 114, 114, 135, 135, 156, 156, 183, 183, 210, 210, 243, 243, 276, 276, 315, 315, 354, 354, 403, 403, 452, 452, 511, 511, 570, 570, 639, 639, 708, 708

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

More precisely number of ways of making change for n farthings. The coins were farthing, halfpenny, penny, threepence, sixpence, shilling, florin, half-crown.

Number of partitions of n into parts 1, 2, 4, 12, 24, 48, 96, and 120. - Joerg Arndt, Sep 05 2014

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 316.
• G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1.

Links

• T. D. Noe, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, order 307.
• Index entries for sequences related to making change.

Programs

Mathematica

nn = 60; CoefficientList[Series[1/((1 - x^1) (1 - x^2) (1 - x^4) (1 - x^12) (1 - x^24) (1 - x^48) (1 - x^96) (1 - x^120)), {x, 0, nn}], x]

Formula

G.f.: 1/((1-x)*(1-x^2)*(1-x^4)*(1-x^12)*(1-x^24)*(1-x^48)*(1-x^96)*(1-x^120)).