A001312 -id:A001312 - cp's OEIS frontend

A000008 Number of ways of making change for n cents using coins of 1, 2, 5, 10 cents.

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

Offset: 0

N. J. A. Sloane

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

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

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

William Boyles, Table of n, a(n) for n = 0..10000 (terms 0...1000 from T. D. Noe)
Henry 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
Gerhard Kirchner, Derivation of formulas
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).

Cf. A001299, A025810.

Cf. A001300, A169718.

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

[#RestrictedPartitions(n,{1,2,5,10}):n in [0..60]]; // Marius A. Burtea, May 07 2019

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

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

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 */

{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 */

Vec( 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)) + O(x^66) ) \\ Joerg Arndt, Oct 02 2013

{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 */

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
a(n) = floor((2*n^3 + 54*n^2 + 421*n + 15*n*(-1)^n + 24*n * ((-1)^[(n mod 5)>2] - [(n mod 5)=1]) + 1248)/1200). - Hoang Xuan Thanh, Jun 27 2025

A001313 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 20, 50 cents.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 11, 12, 15, 16, 19, 22, 25, 28, 31, 34, 41, 44, 51, 54, 61, 68, 75, 82, 89, 96, 109, 116, 129, 136, 149, 162, 175, 188, 201, 214, 236, 249, 271, 284, 306, 328, 350, 372, 394, 416, 451, 473, 508, 530, 565, 600, 635, 670, 705, 740

Offset: 0

N. J. A. Sloane

Number of partitions of n into parts 1, 2, 5, 10, 20, and 50. - Joerg Arndt, Sep 05 2014

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.

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 182
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, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1).

Cf. A001319.

CoefficientList[Series[1/((1 - x) (1 - x^2) (1 - x^5) (1 - x^10) (1 - x^20) (1 - x^50)), {x, 0, 50}], x]
Table[Length[FrobeniusSolve[{1,2,5,10,20,50},n]],{n,0,60}] (* (very slow) Harvey P. Dale, Dec 25 2011 *)

Vec(1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50))+O(x^99)) \\ Charles R Greathouse IV, Jan 24 2022

G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)).

A001301 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 25 cents.

Original entry on oeis.org

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, 65, 71, 78, 84, 91, 102, 109, 120, 127, 138, 151, 162, 175, 186, 199, 217, 230, 248, 261, 279, 300, 318, 339, 357, 378, 406, 427, 455, 476, 504, 536, 564, 596, 624, 656

Offset: 0

N. J. A. Sloane

nonn

Number of partitions of n into parts 1, 2, 5, 10, and 25. - Joerg Arndt, Sep 05 2014

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.

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 177
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, 0, 0, 0, 0, 0, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1).
Index entries for sequences related to making change.

M := Matrix(43, (i,j)-> if (i=j-1) or (j=1 and member(i, [1, 2, 5, 8, 10, 13, 16, 17, 25, 28, 31, 32, 36, 37, 40, 43])) then 1 elif j=1 and member(i, [3, 6, 7, 11, 12, 15, 18, 26, 27, 30, 33, 35, 38, 41, 42]) then -1 else 0 fi); a := n -> (M^(n))[1,1]; seq (a(n), n=0..51); # Alois P. Heinz, Jul 25 2008

CoefficientList[ Series[ 1 / ((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)(1 - x^25)), {x, 0, 55} ], x ]
Table[Length[FrobeniusSolve[{1,2,5,10,25},n]],{n,0,60}] (* Harvey P. Dale, Jan 19 2020 *)

Vec(1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^25)) + O(x^100)) \\ Michel Marcus, Sep 05 2014

G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^25)).

A001302 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 25, 50 cents.

Original entry on oeis.org

Offset: 0

N. J. A. Sloane

nonn

Number of partitions of n into parts 1, 2, 5, 10, 25, and 50. - Joerg Arndt, Sep 05 2014

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.

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 178
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, 0, 0, 0, 0, 0, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, 0, 0, 0, 0, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, 0, 0, 0, 0, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1).

CoefficientList[ Series[ 1 / ((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)(1 - x^25)(1 - x^50)), {x, 0, 55} ], x ]
Array[Length@IntegerPartitions[#, All, {1, 2, 5, 10, 25, 50}]&, 100, 0] (* Giorgos Kalogeropoulos, Apr 24 2021 *)

Vec(1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^25)*(1-x^50))+ O(x^100)) \\ Michel Marcus, Sep 05 2014

G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^25)*(1-x^50)).

a(n) = Sum_{k=0..floor(n/2)} A001300(n-2*k). - Christian Krause, Apr 24 2021

A182086 Number of ways of making change for n Pfennig using Deutschmark coins.

Original entry on oeis.org

Offset: 0

Reinhard Zumkeller, Apr 11 2012

nonn

The Pfennig was the subunit of the Deutsche Mark, the currency of Germany until the adoption of the Euro in 2002; the coins were (business strike): 1 Pfg, 2 Pfg, 5 Pfg, 10 Pfg, 50 Pfg, 1 DM = 100 Pfg, 2 DM and 5 DM;
a(n) = A000008(n) for n < 50; a(50) = A000008(50) + 1 = 342;
a(n) = A001312(n) for n < 200; a(200) = A001312(200) + 1 = 26905.
Number of partitions of n into parts 1, 2, 5, 10, 50, 100, 200, and 500. - Joerg Arndt, Jul 08 2013

			Number of partitions of coin values into coin values:
a(1) = #{1} = 1;
a(2) = #{2, 1+1} = 2;
a(5) = #{5, 2+2+1, 2+1+1+1, 1+1+1+1+1} = 4;
a(10) = #{10, 5+5, 5+2+2+1, 5+2+1+1+1, 5+5x1, 2+2+2+2+2, 2+2+2+2+1+1, 2+2+2+1+1+1+1, 2+2+6x1, 2+8x1, 10x1} = 11;
a(50) = #{50,10+10+10+10+10, 10+10+10+10+5+5, 10+10+10+10+5+2+2+1, 10+10+10+10+5+2+1+1+1, 10+10+10+10+5+10x1, ...} = 342;
a(100) = 2499;
a(200) = 26905;
a(500) = 1229587.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Deutsche Bundesbank, Umlaufmuenzen
Wikipedia, Deutsche Mark, Coins
Index entries for sequences related to making change.
Index entries for linear recurrences with constant coefficients, order 868.

Cf. A001364, A067996, A082593.

a182086 = p [1,2,5,10,50,100,200,500] where
   p  0 = 1; p []  = 0
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

CoefficientList[Series[1/((1 - x)*(1 - x^2)*(1 - x^5)*(1 - x^10)*(1 - x^50)*(1 - x^100)*(1 - x^200)*(1 - x^500)), {x, 0, 50}], x] (* G. C. Greubel, Aug 20 2017 *)

Vec(1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^50)*(1-x^100)*(1-x^200)*(1-x^500))+O(x^566)) \\ Joerg Arndt, Jul 08 2013

G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^50)*(1-x^100)*(1-x^200)*(1-x^500)). - Joerg Arndt, Jul 08 2013

A367253 The number of ways of making change for 5n cents with Canadian coins (5, 10, 25, 100, 200).

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 16, 18, 20, 22, 24, 26, 30, 32, 36, 38, 42, 46, 50, 54, 58, 62, 68, 72, 78, 82, 88, 94, 100, 106, 112, 118, 128, 134, 144, 150, 160, 170, 180, 190, 200, 210, 224, 234, 248, 258, 272, 286, 300, 314, 328, 342, 362

Offset: 0

Johann Peters, Nov 11 2023

Since 2012 the Canadian penny has been discontinued. The coins now commonly used are the nickel (5 cents), the dime (10 cents), the quarter (25 cents), the loonie (100 cents), and the toonie (200 cents).

Number of partitions of n into parts 1, 2, 5, 20, 40. - Alois P. Heinz, Nov 11 2023

Ray Chandler, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1, 1, -1, 0, 1, -1, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, -1, 1, 0, -1, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 1, -1, 0, 1, -1, -1, 1).
Index entries for sequences related to making change.

Cf. A000008, A001312, A182086, A307849.

a[n_]:=Length[FrobeniusSolve[{5,10,25,100,200},5*n]]; a/@Range[0,100] (* Ivan N. Ianakiev, Nov 21 2023 *)
CoefficientList[Series[1/((1-x)*(1-x^2)*(1-x^5)*(1-x^20)*(1-x^40)),{x,0,1000}],x] (* Ray Chandler, Nov 22 2023 *)

From Alois P. Heinz, Nov 11 2023: (Start)
G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^20)*(1-x^40)).
a(20*n) = A307849(n). (End)

A339094 Number of (unordered) ways of making change for n US Dollars using the current US denominations of $1, $2, $5, $10, $20, $50 and $100 bills.

Original entry on oeis.org

Offset: 0

Robert G. Wilson v, Nov 25 2020

Not the same as A001313. First difference appears at A001313(100) being 4562, whereas a(100) is 4563; obviously one more than A001313(100).
Not the same as A057537.
Number of partitions of n into parts 1, 2, 5, 10, 20, 50 and 100.

			a(5) is 4 because 1+1+1+1+1 = 2+1+1+1 = 2+2+1 = 5.

Cf. A000008, A001299, A001300, A001301, A001306, A001302, A001306, A001310, A001312, A001313, A001314, A001319, A001343, A001362, A001364, A057537, A067996, A067997, A073031, A085502, A112024, A124146, A160551, A169718, A181934, A187243.

f[n_] := Length@ IntegerPartitions[n, All, {1, 2, 5, 10, 20, 50, 100}]; Array[f, 75, 0] (* or *)
CoefficientList[ Series[1/((1 - x) (1 - x^2) (1 - x^5) (1 - x^10) (1 - x^20) (1 - x^50) (1 - x^100)), {x, 0, 75}], x] (* or *)
Table[ Length@ FrobeniusSolve[{1, 2, 5, 10, 20, 50, 100}, n], {n, 0, 75}] (* much slower *)

coins(v[..])=my(x='x); prod(i=1, #v, 1/(1-x^v[i]))
Vec(coins(1, 2, 5, 10, 20, 50, 100)+O(x^99)) \\ Charles R Greathouse IV, Jan 24 2022

G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)).

cp's OEIS Frontend

A000008 Number of ways of making change for n cents using coins of 1, 2, 5, 10 cents.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

Formula

A001313 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 20, 50 cents.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A001301 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 25 cents.

Views

Author

Keywords

Comments

References

Links

Programs

Maple

Mathematica

PARI

Formula

A001302 Number of ways of making change for n cents using coins of 1, 2, 5, 10, 25, 50 cents.

Views

Author

Keywords

Comments

References

Links

Programs

Mathematica

PARI

Formula

A182086 Number of ways of making change for n Pfennig using Deutschmark coins.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A367253 The number of ways of making change for 5n cents with Canadian coins (5, 10, 25, 100, 200).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A339094 Number of (unordered) ways of making change for n US Dollars using the current US denominations of $1, $2, $5, $10, $20, $50 and $100 bills.

Views