A001343 Number of (unordered) ways of making change for n cents using coins of 5, 10, 20, 50, 100 cents.

1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4, 0, 0, 0, 0, 6, 0, 0, 0, 0, 6, 0, 0, 0, 0, 9, 0, 0, 0, 0, 9, 0, 0, 0, 0, 13, 0, 0, 0, 0, 13, 0, 0, 0, 0, 18, 0, 0, 0, 0, 18, 0, 0, 0, 0, 24, 0, 0, 0, 0, 24, 0, 0, 0, 0, 31, 0, 0, 0, 0

Offset

0,11

Comments

Number of partitions of n into parts 5, 10, 20, 50, 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 185

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

Index entries for sequences related to making change.

Formula

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

Maple

1/(1-x^5)/(1-x^10)/(1-x^20)/(1-x^50)/(1-x^100): seq(coeff(series(%, x, n+1), x, n), n=0..80);

Mathematica

nn = 100; CoefficientList[Series[1/((1 - x^5) (1 - x^10) (1 - x^20) (1 - x^50) (1 - x^100)), {x, 0, nn}], x] (* T. D. Noe, Jun 28 2012 *)
Table[Length[FrobeniusSolve[{5, 10, 20, 50, 100}, n]], {n, 0, 80}] (* very slow, Harvey P. Dale, May 19 2012 *)

Prog

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

Crossrefs

Sequence in context: A227189 A359327 A234859 * A022882 A171919 A000089

Adjacent sequences: A001340 A001341 A001342 * A001344 A001345 A001346

Keyword

nonn

Author

N. J. A. Sloane, Simon Plouffe

Status

approved