login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000008 Number of ways of making change for n cents using coins of 1, 2, 5, 10 cents.
(Formerly M0280 N0099)
16

%I M0280 N0099 #122 Jan 27 2023 15:35:20

%S 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 70,76,82,88,98,104,114,120,130,140,150,160,170,180,195,205,220,230,

%U 245,260,275,290,305,320,341,356,377,392,413,434,455,476,497,518,546

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

%C Number of partitions of n into parts 1, 2, 5, and 10.

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

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 152.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 Henry Bottomley, <a href="/A000008/a000008.gif">Initial terms of A000008, A001301, A001302, A001312, A001313</a>

%H 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 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=174">Encyclopedia of Combinatorial Structures 174</a>

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

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

%H <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 G.f.: 1 / ((1 - x) * (1 - x^2) * (1 - x^5) * (1 - x^10)). - _Michael Somos_, Nov 17 1999

%F a(n) - a(n-1) = A025810(n). - _Michael Somos_, Dec 15 2002

%F 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 a(n) = -a(-18-n). - _Michael Somos_, Apr 01 2003

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

%e 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 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 # second Maple program:

%p 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 a[ n_] := SeriesCoefficient[ 1 / ((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)), {x, 0, n}]

%t 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 Table[Length[FrobeniusSolve[{1,2,5,10},n]],{n,0,70}] (* _Harvey P. Dale_, Apr 02 2012 *)

%t 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 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 Table[Length@IntegerPartitions[n,All,{1,2,5,10}],{n,0,70}] (* _Giorgos Kalogeropoulos_, May 07 2019 *)

%o (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 (PARI) Vec( 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)) + O(x^66) ) \\ _Joerg Arndt_, Oct 02 2013

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

%o a000008 = p [1,2,5,10] 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 (Magma) [#RestrictedPartitions(n,{1,2,5,10}):n in [0..60]]; // _Marius A. Burtea_, May 07 2019

%Y Cf. A001299, A025810.

%Y Cf. A001300, A169718.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 08:22 EDT 2024. Contains 371236 sequences. (Running on oeis4.)