login
This site is supported by donations 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)
15
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

T. D. Noe, Table of n, a(n) for n = 0..1000

H. Bottomley, Initial terms of A000008, A001301, A001302, A001312, A001313

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

Index entries for sequences related to making change.

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).

Gerhard Kirchner, Derivation of formulas

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(-18-n) = -a(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

# 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); # 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 *)

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

(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

CROSSREFS

Cf. A001299, A025810.

Cf. A001300, A169718.

Sequence in context: A029016 A121385 A029015 * A001312 A182086 A001301

Adjacent sequences:  A000005 A000006 A000007 * A000009 A000010 A000011

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 29 03:09 EDT 2017. Contains 288858 sequences.