|
| |
|
|
A000008
|
|
Number of ways of making change for n cents using coins of 1, 2, 5, 10 cents.
(Formerly M0280 N0099)
|
|
16
|
|
|
|
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
|
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-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) = (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 *)
|
|
|
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
(Magma) [#RestrictedPartitions(n, {1, 2, 5, 10}):n in [0..60]]; // Marius A. Burtea, May 07 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
