A001301 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 25 cents.

1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 11, 12, 15, 16, 19, 22, 25, 28, 31, 34, 40, 43, 49, 52, 58, 65, 71, 78, 84, 91, 102, 109, 120, 127, 138, 151, 162, 175, 186, 199, 217, 230, 248, 261, 279, 300, 318, 339, 357, 378, 406, 427, 455, 476, 504, 536, 564, 596, 624, 656

Offset

0,3

Comments

Number of partitions of n into parts 1, 2, 5, 10, and 25. - 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

H. Bottomley, Initial terms of A000008, A001301, A001302, A001312, A001313

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 177

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

Index entries for sequences related to making change.

Formula

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

Maple

M := Matrix(43, (i, j)-> if (i=j-1) or (j=1 and member(i, [1, 2, 5, 8, 10, 13, 16, 17, 25, 28, 31, 32, 36, 37, 40, 43])) then 1 elif j=1 and member(i, [3, 6, 7, 11, 12, 15, 18, 26, 27, 30, 33, 35, 38, 41, 42]) then -1 else 0 fi); a := n -> (M^(n))[1, 1]; seq (a(n), n=0..51); # Alois P. Heinz, Jul 25 2008

Mathematica

CoefficientList[ Series[ 1 / ((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)(1 - x^25)), {x, 0, 55} ], x ]
Table[Length[FrobeniusSolve[{1, 2, 5, 10, 25}, n]], {n, 0, 60}] (* Harvey P. Dale, Jan 19 2020 *)

Prog

(PARI) Vec(1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^25)) + O(x^100)) \\ Michel Marcus, Sep 05 2014

Crossrefs

Sequence in context: A000008 A001312 A182086 * A001302 A001313 A057537

Adjacent sequences: A001298 A001299 A001300 * A001302 A001303 A001304

Keyword

nonn

Author

N. J. A. Sloane

Status

approved