|
| |
|
|
A000008
|
|
Number of ways of making change for n cents using coins of 1, 2, 5, 10 cents.
(Formerly M0280 N0099)
|
|
10
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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
|
|
|
REFERENCES
| X. Gourdon and B. Salvy, Effective asymptotics of linear recurrences with rational coefficients, Discrete Math., 153 (1996), 145-163.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 316.
G. P\'{o}lya and G. Szeg\"{o}, 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
| T. D. Noe, Table of n, a(n) for n = 0..1000
H. Bottomley, Initial terms of A000008, A001301, A001302, A001312, A001313
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 174
Index entries for sequences related to making change.
|
|
|
FORMULA
| 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).
a(n) = term (18,1) in a certain 18x18 matrix (see Maple code). - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jul 25 2008
|
|
|
MAPLE
| 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10));
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
Contribution from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Oct 05 2008: (Start)
# even more efficient:
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)
|
|
|
MATHEMATICA
| a[n_] := SeriesTerm[1/((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)), {x, 0, n}]
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).
|
|
|
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)))
|
|
|
CROSSREFS
| Cf. A001299. a(n)-a(n-1)=A025810(n).
Sequence in context: A029016 A121385 A029015 * A001312 A001301 A001302
Adjacent sequences: A000005 A000006 A000007 * A000009 A000010 A000011
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
