A001313 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 20, 50 cents.
1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 11, 12, 15, 16, 19, 22, 25, 28, 31, 34, 41, 44, 51, 54, 61, 68, 75, 82, 89, 96, 109, 116, 129, 136, 149, 162, 175, 188, 201, 214, 236, 249, 271, 284, 306, 328, 350, 372, 394, 416, 451, 473, 508, 530, 565, 600, 635, 670, 705, 740
Offset: 0
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
- H. Bottomley, Initial terms of A000008, A001301, A001302, A001312, A001313
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 182
- Index entries for sequences related to making change.
- Index entries for linear recurrences with constant coefficients, signature (1, 1, -1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1).
Crossrefs
Cf. A001319.
Programs
-
Mathematica
CoefficientList[Series[1/((1 - x) (1 - x^2) (1 - x^5) (1 - x^10) (1 - x^20) (1 - x^50)), {x, 0, 50}], x] Table[Length[FrobeniusSolve[{1,2,5,10,20,50},n]],{n,0,60}] (* (very slow) Harvey P. Dale, Dec 25 2011 *) -
PARI
Vec(1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50))+O(x^99)) \\ Charles R Greathouse IV, Jan 24 2022
Formula
G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)).
Comments