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
Keywords
Examples
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 + ...
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.
Programs
-
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 *)
Formula
G.f.: 1/((1-x)*(1-x^2)*(1-x^4)*(1-x^10)*(1-x^20)*(1-x^40)*(1-x^100)).
Comments