A001310 Number of ways of making change for n cents using coins of 1, 2, 4, 10, 20, 40, 100 cents.

1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 13, 13, 18, 18, 24, 24, 31, 31, 39, 39, 50, 50, 62, 62, 77, 77, 93, 93, 112, 112, 134, 134, 159, 159, 187, 187, 218, 218, 252, 252, 293, 293, 337, 337, 388, 388, 442, 442, 503, 503, 571, 571, 646, 646, 728, 728, 817, 817, 913

Offset

0,3

Comments

Number of partitions of n into parts 1, 2, 4, 10, 20, 40, 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..1000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 180

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

Index entries for sequences related to making change.

Formula

G.f.: 1/((1-x)*(1-x^2)*(1-x^4)*(1-x^10)*(1-x^20)*(1-x^40)*(1-x^100)).

Example

1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 6*x^6 + 6*x^7 + 9*x^8 + 9*x^9 + 13*x^10 + ...

Mathematica

a[n_] := SeriesCoefficient[1/((1 - x)(1 - x^2)(1 - x^4)(1 - x^10)(1 - x^40)(1 - x^100)), {x, 0, n}]
Table[Length[FrobeniusSolve[{1, 2, 4, 10, 20, 40, 100}, n]], {n, 0, 60}] (* Harvey P. Dale, Nov 13 2013 *)

Crossrefs

Sequence in context: A060027 A001362 A358206 * A328422 A029009 A340280

Adjacent sequences: A001307 A001308 A001309 * A001311 A001312 A001313

Keyword

nonn

Author

N. J. A. Sloane

Status

approved