A001312 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 50, 100 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, 64, 70, 76, 82, 88, 98, 104, 114, 120, 130, 140, 150, 160, 170, 180, 195, 205, 220, 230, 245, 260, 275, 290, 305, 320, 342, 357, 379, 394, 416, 438, 460, 482, 504, 526
Offset: 0
Examples
1 + x + 2*x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 5*x^6 + 6*x^7 + 7*x^8 + 8*x^9 + 11*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
- H. Bottomley, Initial terms of A000008, A001301, A001302, A001312, A001313
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 181
- Index entries for linear recurrences with constant coefficients, order 168.
- Index entries for sequences related to making change.
Programs
-
Mathematica
a[ n_] := SeriesCoefficient[1/((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)(1 - x^50)(1 - x^100)), {x, 0, n}] Table[Length[FrobeniusSolve[{1,2,5,10,50,100},n]],{n,0,60}] (* Harvey P. Dale, Dec 29 2017 *)
Formula
G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^50)*(1-x^100)).
Comments