login
Number of ways of making change for n cents using coins of 1, 5, 10, 25, 50 and 100 cents.
7

%I #31 Jan 26 2021 05:59:38

%S 1,1,1,1,1,2,2,2,2,2,4,4,4,4,4,6,6,6,6,6,9,9,9,9,9,13,13,13,13,13,18,

%T 18,18,18,18,24,24,24,24,24,31,31,31,31,31,39,39,39,39,39,50,50,50,50,

%U 50,62,62,62,62,62,77,77,77,77,77,93,93,93,93,93,112,112,112,112,112,134,134

%N Number of ways of making change for n cents using coins of 1, 5, 10, 25, 50 and 100 cents.

%C a(n) = A001300(n) for n < 100; a(n) = A001299(n) for n < 50. - _Reinhard Zumkeller_, Dec 15 2013

%C Number of partitions of n into parts 1, 5, 10, 25, 50, 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="/A169718/b169718.txt">Table of n, a(n) for n = 0..10000</a>

%H M. Erickson, <a href="http://www.jstor.org/stable/10.4169/194762110X489224">Change for a dollar, change for a million</a>, Math. Horizons, Feb 2010, pp. 22-25.

%H B. Polster, <a href="https://www.youtube.com/watch?v=VLbePGBOVeg">Explaining the bizarre pattern in making change for a googol dollars (infinite generating functions)</a>, Mathologer video (2021).

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

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

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

%t Table[Length[FrobeniusSolve[{1,5,10,25,50,100},n]],{n,0,80}] (* or *) CoefficientList[Series[1/((1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100)),{x,0,80}],x] (* _Harvey P. Dale_, Dec 25 2011 *)

%o (Haskell)

%o a169718 = p [1,5,10,25,50,100] where

%o p _ 0 = 1

%o p [] _ = 0

%o p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

%o -- _Reinhard Zumkeller_, Dec 15 2013

%Y Cf. A001299, A001300, A000008.

%K nonn

%O 0,6

%A _N. J. A. Sloane_, Apr 20 2010