%I A000008 M0280 N0099
%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 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 (jvospost3(AT)gmail.com), Aug 26 
               2005
%D A000008 X. Gourdon and B. Salvy, Effective asymptotics of linear recurrences 
               with rational coefficients, Discrete Math., 153 (1996), 145-163.
%D A000008 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, 
               Reading, MA, 1990, p. 316.
%D A000008 G. P\'{o}lya and G. Szeg\"{o}, 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 T. D. Noe, <a href="b000008.txt">Table of n, a(n) for n = 0..1000</a>
%H A000008 H. Bottomley, <a href="a8.gif">Initial terms of A000008, A001301, A001302, 
               A001312, A001313</a>
%H A000008 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=174">
               Encyclopedia of Combinatorial Structures 174</a>
%H A000008 <a href="Sindx_Mag.html#change">Index entries for sequences related to 
               making change.</a>
%F A000008 G.f.: 1/((1-x)(1-x^2)(1-x^5)(1-x^10)). a(n)=a(n-2)+a(n-5)-a(n-7)+a(n-10)-a(n-12)-a(n-15)+a(n-17)+1. 
               a(-18-n)=-a(n).
%F A000008 a(n) = term (18,1) in a certain 18x18 matrix (see Maple code). - Alois 
               P. Heinz (heinz(AT)hs-heilbronn.de), Jul 25 2008
%p A000008 1/((1-x)*(1-x^2)*(1-x^5)*(1-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 (heinz(AT)hs-heilbronn.de), Jul 25 2008
%p A000008 Contribution from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Oct 05 2008: 
               (Start)
%p A000008 # even more efficient:
%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); (End)
%t A000008 a[n_] := SeriesTerm[1/((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)), {x, 0, n}]
%t A000008 a[n_, d_] := SeriesTerm[1/(Times@@Map[(1-x^#)&, d]), {x, 0, n}] (general 
               case for any set of denominations represented as a list of coin values 
               in cents).
%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)))
%Y A000008 a(n)-a(n-1)=A025810(n).
%Y A000008 Sequence in context: A029016 A121385 A029015 this_sequence A001312 A001301 
               A001302
%Y A000008 Adjacent sequences: A000005 A000006 A000007 this_sequence A000009 A000010 
               A000011
%K A000008 nonn,easy,nice
%O A000008 0,3
%A A000008 N. J. A. Sloane (njas(AT)research.att.com).