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