A001300 Number of ways of making change for n cents using coins of 1, 5, 10, 25, 50 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

Offset

0,6

Comments

Number of partitions of n into parts 1, 5, 10, 25, and 50. - Joerg Arndt, May 10 2014

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

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, Problems 1 and 2.

Links

T. D. Noe, Table of n, a(n) for n = 0..10000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 176

Index entries for sequences related to making change.

Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 1, -1, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1).

Formula

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

Maple

1/((1-x)*(1-x^5)*(1-x^10)*(1-x^25)*(1-x^50));

Mathematica

CoefficientList[ Series[ 1 / ((1 - x)(1 - x^5)(1 - x^10)(1 - x^25)(1 - x^50)), {x, 0, 65} ], x ]

Prog

(Haskell)
a001300 = p [1, 5, 10, 25, 50] 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
(PARI) a(n)=floor(((n\5)^4+38*(n\5)^3+476*(n\5)^2+2185*(n\5)+3735)/2400+(n\5+1)*(-1)^(n\5)/160+(n\5\5+1)*[0, 0, 1, 0, -1][n\5%5+1]/10) \\ Tani Akinari, May 10 2014

Crossrefs

Cf. A001299, A169718, A000008.

Sequence in context: A130496 A187243 A001299 * A169718 A001306 A260984

Adjacent sequences: A001297 A001298 A001299 * A001301 A001302 A001303

Keyword

nonn,easy

Author

N. J. A. Sloane, Mar 15 1996

Status

approved