A001362 Number of ways of making change for n cents using coins of 1, 2, 4, 10 cents.

1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 13, 13, 18, 18, 24, 24, 31, 31, 39, 39, 49, 49, 60, 60, 73, 73, 87, 87, 103, 103, 121, 121, 141, 141, 163, 163, 187, 187, 213, 213, 242, 242, 273, 273, 307, 307, 343, 343, 382, 382, 424, 424, 469, 469, 517, 517, 568, 568, 622, 622

Offset

0,3

Comments

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

Index entries for sequences related to making change.

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

Formula

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

Maple

1/(1-x)/(1-x^2)/(1-x^4)/(1-x^10): seq(coeff(series(%, x, n+1), x, n), n=0..80);

Mathematica

nn = 1000; CoefficientList[Series[1/((1 - x^1) (1 - x^2) (1 - x^4) (1 - x^10)), {x, 0, nn}], x] (* T. D. Noe, Jun 28 2012 *)
Table[Length[FrobeniusSolve[{1, 2, 4, 10}, n]], {n, 0, 60}] (* Harvey P. Dale, May 20 2021 *)

Prog

(PARI) a(n)=floor((n\2+8)*(2*(n\2)^2+11*(n\2)+18)/120) \\ Tani Akinari, May 14 2014

Crossrefs

Twice A001304.

Sequence in context: A001364 A029010 A060027 * A358206 A001310 A328422

Adjacent sequences: A001359 A001360 A001361 * A001363 A001364 A001365

Keyword

nonn

Author

N. J. A. Sloane

Status

approved