login
Number of ways of making change for n cents using coins of 1, 2, 5, 10, 20, 50 cents.
8

%I #37 Feb 01 2022 01:29:45

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

%T 75,82,89,96,109,116,129,136,149,162,175,188,201,214,236,249,271,284,

%U 306,328,350,372,394,416,451,473,508,530,565,600,635,670,705,740

%N Number of ways of making change for n cents using coins of 1, 2, 5, 10, 20, 50 cents.

%C Number of partitions of n into parts 1, 2, 5, 10, 20, and 50. - _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="/A001313/b001313.txt">Table of n, a(n) for n = 0..1000</a>

%H H. Bottomley, <a href="/A000008/a000008.gif">Initial terms of A000008, A001301, A001302, A001312, A001313</a>

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

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

%H <a href="/index/Rec#order_88">Index entries for linear recurrences with constant coefficients</a>, 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).

%F G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)).

%t CoefficientList[Series[1/((1 - x) (1 - x^2) (1 - x^5) (1 - x^10) (1 - x^20) (1 - x^50)), {x, 0, 50}], x]

%t Table[Length[FrobeniusSolve[{1,2,5,10,20,50},n]],{n,0,60}] (* (very slow) _Harvey P. Dale_, Dec 25 2011 *)

%o (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

%Y Cf. A001319.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_