A169718 Number of ways of making change for n cents using coins of 1, 5, 10, 25, 50 and 100 cents.

1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9, 13, 13, 13, 13, 13, 18, 18, 18, 18, 18, 24, 24, 24, 24, 24, 31, 31, 31, 31, 31, 39, 39, 39, 39, 39, 50, 50, 50, 50, 50, 62, 62, 62, 62, 62, 77, 77, 77, 77, 77, 93, 93, 93, 93, 93, 112, 112, 112, 112, 112, 134, 134

Offset: 0

Author

N. J. A. Sloane, Apr 20 2010

Keywords

• nonn

Comments

a(n) = A001300(n) for n < 100; a(n) = A001299(n) for n < 50. - Reinhard Zumkeller, Dec 15 2013

Number of partitions of n into parts 1, 5, 10, 25, 50, and 100. - 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..10000
• M. Erickson, Change for a dollar, change for a million, Math. Horizons, Feb 2010, pp. 22-25.
• B. Polster, Explaining the bizarre pattern in making change for a googol dollars (infinite generating functions), Mathologer video (2021).
• Index entries for sequences related to making change.
• Index entries for linear recurrences with constant coefficients, order 191.

Crossrefs

Cf. A001299, A001300, A000008.

Programs

Haskell

a169718 = p [1,5,10,25,50,100] where
   p _          0 = 1
   p []         _ = 0
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Dec 15 2013

Mathematica

Table[Length[FrobeniusSolve[{1,5,10,25,50,100},n]],{n,0,80}] (* or *) CoefficientList[Series[1/((1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100)),{x,0,80}],x] (* Harvey P. Dale, Dec 25 2011 *)

Formula

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