A169718 -id:A169718 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9, 13, 13, 13, 13, 13, 18, 18, 18, 18, 18, 24, 24, 24, 24, 24, 31, 31, 31, 31, 31, 39, 39, 39, 39, 39, 49, 49, 49, 49, 49, 60, 60, 60, 60, 60, 73, 73, 73, 73, 73, 87, 87, 87, 87, 87, 103, 103, 103, 103, 103

Offset: 0

N. J. A. Sloane, Mar 15 1996

a(n) = A001300(n) = A169718(n) for n < 50. - Reinhard Zumkeller, Dec 15 2013

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

			G.f. = 1 + x + x^2 + x^3 + x^4 + 2*x^5 + 2*x^6 + 2*x^7 + 2*x^8 + 2*x^9 + 4*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.

T. D. Noe, Table of n, a(n) for n = 0..10000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 175
Gerhard Kirchner, Derivation of formulas
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]
Index entries for sequences related to making change.
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 1, -1, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1).

Cf. A001300, A169718, A000008.

a001299 = p [1,5,10,25] 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

CoefficientList[ Series[ 1 / ((1 - x)(1 - x^5)(1 - x^10)(1 - x^25)), {x, 0, 65} ], x ]
Table[Length[FrobeniusSolve[{1,5,10,25},n]],{n,0,80}] (* Harvey P. Dale, Dec 01 2015 *)
a[ n_] := With[ {m = Quotient[n, 5] / 10}, Round[ (4 m + 3) (5 m + 1) (5 m + 2) / 6]]; (* Michael Somos, Feb 23 2017 *)

a(n)=floor((n\5+1)*((n\5+2)*(2-n%5)/100+[54,27,-2,-33,-66][n%5+1]/500)+(2-5*(n%5%2))*(-1)^n/40+(2*n^3+123*n^2+2146*n+16290)/15000) \\ Tani Akinari, May 09 2014

{a(n) = my(m=n\5 / 10); round((4*m + 3) * (5*m + 1) * (5*m + 2) / 6)}; /* Michael Somos, Feb 23 2017 */

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

a(n) = round((100*x^3 + 135*x^2 +53*x)/6) + 1 with x= floor(n/5)/10. See link "Derivation of formulas". - Gerhard Kirchner, Feb 23 2017

A000008 Number of ways of making change for n cents using coins of 1, 2, 5, 10 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, 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

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

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9, 13, 13, 13, 13, 13, 18, 18, 18, 18, 18, 24, 24, 24, 24, 24, 31, 31, 31, 31, 31, 39, 39, 39, 39, 39, 50, 50, 50, 50, 50, 62, 62, 62, 62, 62, 77, 77, 77

Offset: 0

N. J. A. Sloane, Mar 15 1996

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

a(n) = A001299(n) for n < 50; a(n) = A169718(n) for n < 100. - Reinhard Zumkeller, Dec 15 2013

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, Problems 1 and 2.

T. D. Noe, Table of n, a(n) for n = 0..10000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 176
Index entries for sequences related to making change.
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 1, -1, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1, 0, 0, 0, 1, -1, 0, 0, 0, -1, 1).

Cf. A001299, A169718, A000008.

a001300 = p [1,5,10,25,50] 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

1/((1-x)*(1-x^5)*(1-x^10)*(1-x^25)*(1-x^50));

CoefficientList[ Series[ 1 / ((1 - x)(1 - x^5)(1 - x^10)(1 - x^25)(1 - x^50)), {x, 0, 65} ], x ]

a(n)=floor(((n\5)^4+38*(n\5)^3+476*(n\5)^2+2185*(n\5)+3735)/2400+(n\5+1)*(-1)^(n\5)/160+(n\5\5+1)*[0,0,1,0,-1][n\5%5+1]/10) \\ Tani Akinari, May 10 2014

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

A187243 Number of ways of making change for n cents using coins of 1, 5, and 10 cents.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9, 12, 12, 12, 12, 12, 16, 16, 16, 16, 16, 20, 20, 20, 20, 20, 25, 25, 25, 25, 25, 30, 30, 30, 30, 30, 36, 36, 36, 36, 36, 42, 42, 42, 42, 42, 49, 49, 49, 49, 49, 56, 56, 56, 56, 56, 64, 64, 64, 64, 64, 72, 72, 72, 72, 72

Offset: 0

T. D. Noe, Mar 07 2011

a(n) is the number of partitions of n into parts 1, 5, and 10. - Joerg Arndt, Feb 02 2017
From Gerhard Kirchner, Jan 25 2017: (Start)
There is a simple recurrence for solving such problems given coin values 1 = c(1) < c(2) < ... < c(k).
Let f(n, j), 1 < j <= k, be the number of ways of making change for n cents with coin values c(i), 1 <= i <= j. Then any number m of c(j)-coins with 0 <= m <= floor(n/c(j)) can be used, and the remaining amount of change to be made using coins of values smaller than c(j) will be n - m*c(j) cents. This leads directly to the recurrence formula with a(n) = f(n, k).
For k = 3 with c(1) = 1, c(2) = 5, c(3) = 10, the recurrence can be reduced to an explicit formula; see link "Derivation of formulas".
By the way, a(n) is also the number of ways of making change for n cents using coins of 2, 5, 10 cents and at most one 1-cent coin. That is because any coin combination is, as in the original problem, fixed by the numbers of 5-cent and 10-cent coins.
(End)

			From _Gerhard Kirchner_, Jan 25 2017: (Start)
Recurrence:
a(11)  = f(11, 3) = f(11 - 0, 2) + f(11 - 10, 2)
       = f(11 - 0, 1) + f(11 - 5, 1) + f(11 - 10, 1) + f(1, 2)
       = 1 + 1 + 1 + 1 = 4.
Explicitly: a(79) = (7 + 1)*(7 + 1 + 1) = 72.
(End)

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

Cf. A001299, A001300, A001306, A169718, A002266, A002620, A245573.

CoefficientList[ Series[ 1 / ((1 - x)(1 - x^5)(1 - x^10)), {x, 0, 75} ], x ]

Vec( 1/((1-x)*(1-x^5)*(1-x^10))+O(x^99)) \\ Charles R Greathouse IV, Aug 22 2011

a(n)=(n^2+16*n+97+10*(n\5+1)*(5*(n\5)+2-n))\100 \\ Tani Akinari, Sep 10 2015

a(n) = {my(q=n\10, s=(n%10)\5); (q+1)*(q+1+s); } \\ (Kirchner's explicit formula) Joerg Arndt, Feb 02 2017

G.f.: 1/((1-x)*(1-x^5)*(1-x^10)).
From Gerhard Kirchner, Jan 25 2017: (Start)
General recurrence: f(n, 1) = 1; j > 1: f(0, j) = 1 or f(n, j) = Sum_{m=0..floor(n/c(j))} f(n-m*c(j), j-1);
a(n) = f(n, k).
Note: f(n, j) = f(n, j-1) for n < c(j) => f(1, j) = 1.
Explicit formula:
a(n) = (q+1)*(q+1+s) with q = floor(n/10) and s = floor((n mod 10)/5). (End)
a(n) = A002620(A002266(n)+2) = floor((floor(n/5) + 2)^2 / 4). - Hoang Xuan Thanh, Jun 26 2025

A208217 Number of ways of making change for n cents using coins of 1, 5, 10, 25, 50, and 100 cents, where each coin that appears is used a different number of times.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 4, 3, 3, 4, 4, 5, 5, 5, 4, 5, 8, 7, 6, 8, 7, 12, 9, 11, 11, 12, 14, 14, 15, 14, 14, 20, 16, 18, 18, 20, 25, 24, 23, 24, 24, 32, 27, 30, 31, 30, 40, 38, 37, 40, 38, 48, 44, 48, 46, 49, 57, 54, 54, 58, 59, 72, 63, 68, 67, 70, 83, 80

Offset: 0

Matthew C. Russell, Apr 24 2012

nonn

			For n=6 the a(6)=1 solution is six copies of the 1-cent coin. (Taking one 1-cent coin and one 5-cent coin is not allowed, as those two coins have the same nonzero multiplicity.)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Doron Zeilberger, Using Generatingfunctionology to enumerate distinct-multiplicity partitions.

Cf. A169718, A208216.

# for a g.f. in Maple format see the Doron Zeilberger link.

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

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, 793, 828, 881, 916

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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

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

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A187243 Number of ways of making change for n cents using coins of 1, 5, and 10 cents.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A208217 Number of ways of making change for n cents using coins of 1, 5, 10, 25, 50, and 100 cents, where each coin that appears is used a different number of times.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

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

Author

Keywords

Comments

Examples

Links

Crossrefs