login
Number of ways of making change for n cents using coins of 1, 5, 10, 25 cents.
19

%I #54 Apr 18 2017 07:02:34

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

%U 49,60,60,60,60,60,73,73,73,73,73,87,87,87,87,87,103,103,103,103,103

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

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

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

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

%H Gerhard Kirchner, <a href="http://oeis.org/A187243/a187243_1.pdf">Derivation of formulas</a>

%H Ed Pegg, Jr., <a href="http://www.mathpuzzle.com/MAA/07-Sequence%20Pictures/mathgames_12_08_03.html">Sequence Pictures</a>, Math Games column, Dec 08 2003.

%H Ed Pegg, Jr., <a href="/A000043/a000043_2.pdf">Sequence Pictures</a>, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]

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

%H <a href="/index/Rec#order_41">Index entries for linear recurrences with constant coefficients</a>, signature (1, 0, 0, 0, 1, -1, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1).

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

%F a(n) = round((100*x^3 + 135*x^2 +53*x)/6) + 1 with x= floor(n/5)/10. See link "Derivation of formulas". - _Gerhard Kirchner_, Feb 23 2017

%e G.f. = 1 + x + x^2 + x^3 + x^4 + 2*x^5 + 2*x^6 + 2*x^7 + 2*x^8 + 2*x^9 + 4*x^10 + ...

%t CoefficientList[ Series[ 1 / ((1 - x)(1 - x^5)(1 - x^10)(1 - x^25)), {x, 0, 65} ], x ]

%t Table[Length[FrobeniusSolve[{1,5,10,25},n]],{n,0,80}] (* _Harvey P. Dale_, Dec 01 2015 *)

%t a[ n_] := With[ {m = Quotient[n, 5] / 10}, Round[ (4 m + 3) (5 m + 1) (5 m + 2) / 6]]; (* _Michael Somos_, Feb 23 2017 *)

%o (Haskell)

%o a001299 = p [1,5,10,25] 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

%o (PARI) a(n)=floor((n\5+1)*((n\5+2)*(2-n%5)/100+[54,27,-2,-33,-66][n%5+1]/500)+(2-5*(n%5%2))*(-1)^n/40+(2*n^3+123*n^2+2146*n+16290)/15000) \\ _Tani Akinari_, May 09 2014

%o (PARI) {a(n) = my(m=n\5 / 10); round((4*m + 3) * (5*m + 1) * (5*m + 2) / 6)}; /* _Michael Somos_, Feb 23 2017 */

%Y Cf. A001300, A169718, A000008.

%K nonn,easy

%O 0,6

%A _N. J. A. Sloane_, Mar 15 1996