A000064 Partial sums of (unordered) ways of making change for n cents using coins of 1, 2, 5, 10 cents. (Formerly M1002 N0375)

1, 2, 4, 6, 9, 13, 18, 24, 31, 39, 50, 62, 77, 93, 112, 134, 159, 187, 218, 252, 292, 335, 384, 436, 494, 558, 628, 704, 786, 874, 972, 1076, 1190, 1310, 1440, 1580, 1730, 1890, 2060, 2240, 2435, 2640, 2860, 3090, 3335, 3595, 3870, 4160, 4465, 4785, 5126

Offset

0,2

Comments

Number of partitions of n into two kinds of part 1 and one kind of parts 2, 5, and 10. - Joerg Arndt, May 10 2014

References

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 152.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Christian G. Bower, Table of n, a(n) for n = 0..1000

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

Formula

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

a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) + a(n-5) - 2*a(n-6) + 2*a(n-8) - a(n-9) + a(n-10) - 2*a(n-11) + 2*a(n-13) - a(n-14) - a(n-15) + 2*a(n-16) - 2*a(n-18) + a(n-19). - Fung Lam, May 07 2014

a(n) ~ n^4 / 2400 as n->oo. - Daniel Checa, Jul 11 2023

Maple

1/(1-x)^2/(1-x^2)/(1-x^5)/(1-x^10)
a:= proc(n) local m, r; m := iquo(n, 10, 'r'); r:= r+1; (55+(119+(95+ 25*m) *m) *m) *m/6+ [1, 2, 4, 6, 9, 13, 18, 24, 31, 39][r]+ [0, 26, 61, 99, 146, 202, 267, 341, 424, 516][r]*m/6+ [0, 10, 21, 33, 46, 60, 75, 91, 108, 126][r]*m^2/2+ (5*r-5) *m^3/3 end: seq(a(n), n=0..100); # Alois P. Heinz, Oct 05 2008

Mathematica

CoefficientList[Series[1/((1-x)^2(1-x^2)(1-x^5)(1-x^10)), {x, 0, 100}], x] (* Vladimir Joseph Stephan Orlovsky, Jan 25 2012 *)

Prog

(PARI) a(n)=if(n<0, 0, polcoeff(1/((1-x)^2*(1-x^2)*(1-x^5)*(1-x^10))+x*O(x^n), n))
(PARI) a(n)=floor((n^4+38*n^3+476*n^2+2185*n+3735)/2400+(n+1)*(-1)^n/160+(n\5+1)*[0, 0, 1, 0, -1][n%5+1]/10) \\ Tani Akinari, May 10 2014

Crossrefs

Cf. A000008.

Sequence in context: A114830 A177239 A001304 * A001305 A088575 A177189

Adjacent sequences: A000061 A000062 A000063 * A000065 A000066 A000067

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Corrected and extended by Simon Plouffe

Status

approved