login
Number of ways of making change for n cents using coins of 1, 2, 4, 10, 20, 40, 100 cents.
3

%I #35 Feb 01 2022 01:28:47

%S 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,

%T 93,93,112,112,134,134,159,159,187,187,218,218,252,252,293,293,337,

%U 337,388,388,442,442,503,503,571,571,646,646,728,728,817,817,913

%N Number of ways of making change for n cents using coins of 1, 2, 4, 10, 20, 40, 100 cents.

%C Number of partitions of n into parts 1, 2, 4, 10, 20, 40, and 100. - _Joerg Arndt_, Sep 05 2014

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 316.

%D G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1.

%H T. D. Noe, <a href="/A001310/b001310.txt">Table of n, a(n) for n = 0..1000</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=180">Encyclopedia of Combinatorial Structures 180</a>

%H <a href="/index/Rec#order_177">Index entries for linear recurrences with constant coefficients</a>, order 177.

%H <a href="/index/Mag#change">Index entries for sequences related to making change.</a>

%F G.f.: 1/((1-x)*(1-x^2)*(1-x^4)*(1-x^10)*(1-x^20)*(1-x^40)*(1-x^100)).

%e 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 + ...

%t a[n_] := SeriesCoefficient[1/((1 - x)(1 - x^2)(1 - x^4)(1 - x^10)(1 - x^40)(1 - x^100)), {x, 0, n}]

%t Table[Length[FrobeniusSolve[{1,2,4,10,20,40,100},n]],{n,0,60}] (* _Harvey P. Dale_, Nov 13 2013 *)

%K nonn

%O 0,3

%A _N. J. A. Sloane_