A001302 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 25, 50 cents.
1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 11, 12, 15, 16, 19, 22, 25, 28, 31, 34, 40, 43, 49, 52, 58, 65, 71, 78, 84, 91, 102, 109, 120, 127, 138, 151, 162, 175, 186, 199, 217, 230, 248, 261, 279, 300, 318, 339, 357, 378, 407, 428, 457, 478, 507, 540, 569, 602, 631, 664
Offset: 0
Keywords
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 178
- 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, 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, 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, 0, 0, 0, 0, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1).
Programs
-
Mathematica
CoefficientList[ Series[ 1 / ((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)(1 - x^25)(1 - x^50)), {x, 0, 55} ], x ] Array[Length@IntegerPartitions[#, All, {1, 2, 5, 10, 25, 50}]&, 100, 0] (* Giorgos Kalogeropoulos, Apr 24 2021 *) -
PARI
Vec(1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^25)*(1-x^50))+ O(x^100)) \\ Michel Marcus, Sep 05 2014
Formula
G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^25)*(1-x^50)).
a(n) = Sum_{k=0..floor(n/2)} A001300(n-2*k). - Christian Krause, Apr 24 2021
Comments