This site is supported by donations to The OEIS Foundation.

 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) 14
 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, 70, 76, 82, 88, 98, 104, 114, 120, 130, 140, 150, 160, 170, 180, 195, 205, 220, 230, 245, 260, 275, 290, 305, 320, 341, 356, 377, 392, 413, 434, 455, 476, 497, 518, 546 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS Number of partitions of n into parts 1, 2, 5, and 10. 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 REFERENCES R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 316. G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1. J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 152. N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS William Boyles, Table of n, a(n) for n = 0..10000 (terms 0...1000 from T. D. Noe) X. Gourdon and B. Salvy, Effective asymptotics of linear recurrences with rational coefficients, Discrete Mathematics, vol. 153, no. 1-3, 1996, pages 145-163. INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 174 Gerhard Kirchner, Derivation of formulas Index entries for linear recurrences with constant coefficients, signature (1,1,-1,0,1,-1,-1,1,0,1,-1,-1,1,0,-1,1,1,-1). FORMULA G.f.: 1 / ((1 - x) * (1 - x^2) * (1 - x^5) * (1 - x^10)). - Michael Somos, Nov 17 1999 a(n) - a(n-1) = A025810(n). - Michael Somos, Dec 15 2002 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 a(n) = -a(-18-n). - Michael Somos, Apr 01 2003 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 EXAMPLE 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 + ... MAPLE 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 # second Maple program: 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 MATHEMATICA a[ n_] := SeriesCoefficient[ 1 / ((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)), {x, 0, n}] 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 *) Table[Length[FrobeniusSolve[{1, 2, 5, 10}, n]], {n, 0, 70}] (* Harvey P. Dale, Apr 02 2012 *) 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 *) 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 *) Table[Length@IntegerPartitions[n, All, {1, 2, 5, 10}], {n, 0, 70}] (* Giorgos Kalogeropoulos, May 07 2019 *) PROG (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 */ (PARI) Vec( 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)) + O(x^66) ) \\ Joerg Arndt, Oct 02 2013 (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 */ (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 */ (Haskell) a000008 = p [1, 2, 5, 10] where    p _          0 = 1    p []         _ = 0    p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m -- Reinhard Zumkeller, Dec 15 2013 (MAGMA) [#RestrictedPartitions(n, {1, 2, 5, 10}):n in [0..60]]; // Marius A. Burtea, May 07 2019 CROSSREFS Cf. A001299, A025810. Cf. A001300, A169718. Sequence in context: A290807 A121385 A029015 * A001312 A182086 A001301 Adjacent sequences:  A000005 A000006 A000007 * A000009 A000010 A000011 KEYWORD nonn,easy,nice AUTHOR STATUS approved

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

Last modified September 17 12:45 EDT 2019. Contains 327131 sequences. (Running on oeis4.)