cp's OEIS Frontend

A000008 Number of ways of making change for n cents using coins of 1, 2, 5, 10 cents.

%I A000008 M0280 N0099 #126 Jun 27 2025 04:27:38
%S A000008 1,1,2,2,3,4,5,6,7,8,11,12,15,16,19,22,25,28,31,34,40,43,49,52,58,64,
%T A000008 70,76,82,88,98,104,114,120,130,140,150,160,170,180,195,205,220,230,
%U A000008 245,260,275,290,305,320,341,356,377,392,413,434,455,476,497,518,546
%N A000008 Number of ways of making change for n cents using coins of 1, 2, 5, 10 cents.
%C A000008 Number of partitions of n into parts 1, 2, 5, and 10.
%C A000008 There is a unique solution to this puzzle: "There are a prime number of ways that I can make change for n cents using coins of 1, 2, 5, 10 cents; but a semiprime number of ways that I can make change for n-1 cents and for n+1 cents." There is a unique solution to this related puzzle: "There are a prime number of ways that I can make change for n cents using coins of 1, 2, 5, 10 cents; but a 3-almost prime number of ways that I can make change for n-1 cents and for n+1 cents." - _Jonathan Vos Post_, Aug 26 2005
%D A000008 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 316.
%D A000008 G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1.
%D A000008 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 152.
%D A000008 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000008 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000008 William Boyles, <a href="/A000008/b000008.txt">Table of n, a(n) for n = 0..10000</a> (terms 0...1000 from T. D. Noe)
%H A000008 Henry Bottomley, <a href="/A000008/a000008.gif">Initial terms of A000008, A001301, A001302, A001312, A001313</a>
%H A000008 X. Gourdon and B. Salvy, <a href="http://dx.doi.org/10.1016/0012-365X(95)00133-H">Effective asymptotics of linear recurrences with rational coefficients</a>, Discrete Mathematics, vol. 153, no. 1-3, 1996, pages 145-163.
%H A000008 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=174">Encyclopedia of Combinatorial Structures 174</a>
%H A000008 Gerhard Kirchner, <a href="/A187243/a187243_1.pdf">Derivation of formulas</a>
%H A000008 <a href="/index/Mag#change">Index entries for sequences related to making change.</a>
%H A000008 <a href="/index/Rec#order_18">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).
%F A000008 G.f.: 1 / ((1 - x) * (1 - x^2) * (1 - x^5) * (1 - x^10)). - _Michael Somos_, Nov 17 1999
%F A000008 a(n) - a(n-1) = A025810(n). - _Michael Somos_, Dec 15 2002
%F A000008 a(n) = a(n-2) + a(n-5) - a(n-7) + a(n-10) - a(n-12) - a(n-15) + a(n-17) + 1. - _Michael Somos_, Apr 01 2003
%F A000008 a(n) = -a(-18-n). - _Michael Somos_, Apr 01 2003
%F A000008 a(n) = (q+1)*(h(n) - q*(3n-10q+7)/6) with q = floor(n/10) and h(n) = A000115(n) = round((n+4)^2/20). See link "Derivation of formulas". - _Gerhard Kirchner_, Feb 10 2017
%F A000008 a(n) = floor((2*n^3 + 54*n^2 + 421*n + 15*n*(-1)^n + 24*n * ((-1)^[(n mod 5)>2] - [(n mod 5)=1]) + 1248)/1200). - _Hoang Xuan Thanh_, Jun 27 2025
%e A000008 G.f. = 1 + x + 2*x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 5*x^6 + 6*x^7 + 7*x^8 + 8*x^9 + 11*x^10 + ...
%p A000008 M:= Matrix(18, (i,j)-> if(i=j-1 and i<17) or (j=1 and member(i, [2,5,10,17,18])) or (i=18 and j=18) then 1 elif j=1 and member(i, [7,12,15]) then -1 else 0 fi); a:= n-> (M^(n+1))[18,1]; seq(a(n), n=0..51); # _Alois P. Heinz_, Jul 25 2008
%p A000008 # second Maple program:
%p A000008 a:= proc(n) local m, r; m := iquo(n, 10, 'r'); r:= r+1; ([23, 26, 35, 38, 47, 56, 65, 74, 83, 92][r]+ (3*r+ 24+ 10*m) *m) *m/6+ [1, 1, 2, 2, 3, 4, 5, 6, 7, 8][r] end: seq(a(n), n=0..100); # _Alois P. Heinz_, Oct 05 2008
%t A000008 a[ n_] := SeriesCoefficient[ 1 / ((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)), {x, 0, n}]
%t A000008 a[n_, d_] := SeriesCoefficient[1/(Times@@Map[(1-x^#)&, d]), {x, 0, n}] (* general case for any set of denominations represented as a list d of coin values in cents *)
%t A000008 Table[Length[FrobeniusSolve[{1,2,5,10},n]],{n,0,70}] (* _Harvey P. Dale_, Apr 02 2012 *)
%t A000008 LinearRecurrence[{1, 1, -1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1}, {1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 11, 12, 15, 16, 19, 22, 25, 28}, 100] (* _Vincenzo Librandi_, Feb 10 2016 *)
%t A000008 a[ n_] := Quotient[ With[{r = Mod[n, 10, 1]}, n^3 + 27 n^2 + (191 + 3 {4, 13, 0, 5, 8, 9, 8, 5, 0, 13}[[r]]) n + 25], 600] + 1; (* _Michael Somos_, Mar 06 2018 *)
%t A000008 Table[Length@IntegerPartitions[n,All,{1,2,5,10}],{n,0,70}] (* _Giorgos Kalogeropoulos_, May 07 2019 *)
%o A000008 (PARI) {a(n) = if( n<-17, -a(-18-n), if( n<0, 0, polcoeff( 1 / ((1 - x) * (1 - x^2) * (1 - x^5) * (1 - x^10)) + x * O(x^n), n)))}; /* _Michael Somos_, Apr 01 2003 */
%o A000008 (PARI) Vec( 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)) + O(x^66) ) \\ _Joerg Arndt_, Oct 02 2013
%o A000008 (PARI) {a(n) = my(r = (n-1)%10 + 1); (n^3 + 27*n^2 + (191 + 3*[4, 13, 0, 5, 8, 9, 8, 5, 0, 13][r])*n + 25)\600 + 1}; /* _Michael Somos_, Mar 06 2018 */
%o A000008 (Maxima) a(n):=floor(((n+17)*(2*n^2+20*n+81)+15*(n+1)*(-1)^n+120*((floor(n/5)+1)*((1+(-1)^mod(n,5))/2-floor(((mod(n,5))^2)/8))))/1200); /* _Tani Akinari_, Jun 21 2013 */
%o A000008 (Haskell)
%o A000008 a000008 = p [1,2,5,10] where
%o A000008    p _          0 = 1
%o A000008    p []         _ = 0
%o A000008    p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
%o A000008 -- _Reinhard Zumkeller_, Dec 15 2013
%o A000008 (Magma) [#RestrictedPartitions(n,{1,2,5,10}):n in [0..60]]; // _Marius A. Burtea_, May 07 2019
%Y A000008 Cf. A001299, A025810.
%Y A000008 Cf. A001300, A169718.
%K A000008 nonn,easy,nice
%O A000008 0,3
%A A000008 _N. J. A. Sloane_