A001299 -id:A001299 - 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

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

A053344 Minimal number of coins needed to pay n cents using coins of denominations 1, 5, 10, 25 cents.

Original entry on oeis.org

1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 4

Offset: 1

Jean Fontaine (jfontain(AT)odyssee.net), Jan 06 2000

			a(57) = 5 because to pay 57 cents at least 5 coins are needed: 2 of 25 cents, 1 of 5 cents and 2 of 1 cent.

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

Cf. A011542, A001299.

I:=[1,2,3,4,1,2,3,4,5,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,1,2]; [n le 26 select I[n] else Self(n-1) +Self(n-25) - Self(n-26): n in [1..70]]; // G. C. Greubel, May 31 2018

f[n_]:=Floor[n/25]+Floor[Mod[n,25]/10]+Floor[Mod[Mod[n,25],10]/5]+Mod[Mod[Mod[n,25],10],5]; lst={};Do[AppendTo[lst,f[n]],{n,6!}];lst (* Vladimir Joseph Stephan Orlovsky, Sep 28 2009 *)
Table[Min[Total/@FrobeniusSolve[{1,5,10,25},n]],{n,100}] (* or *) LinearRecurrence[{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,-1},{1,2,3,4,1,2,3,4,5,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,1,2},100] (* Harvey P. Dale, Aug 14 2014 *)

Vec(-x*(5*x^24 -x^23 -x^22 -x^21 -x^20 +4*x^19 -x^18 -x^17 -x^16 -x^15 +3*x^14 -x^13 -x^12 -x^11 -x^10 +4*x^9 -x^8 -x^7 -x^6 -x^5 +3*x^4 -x^3 -x^2 -x -1) / ((x -1)^2*(x^4 +x^3 +x^2 +x +1)*(x^20 +x^15 +x^10 +x^5 +1)) + O(x^100)) \\ Colin Barker, Jan 10 2015

def A053344(n):
    a, b = divmod(n,25)
    c, d = divmod(b,10)
    return a+c+sum(divmod(d,5)) # Chai Wah Wu, Nov 08 2022

a(n) = floor(n/25) + floor([n mod 25]/10) + floor([{n mod 25} mod 10]/5) + ([n mod 25] mod 10) mod 5.

G.f.: -x*(5*x^24 -x^23 -x^22 -x^21 -x^20 +4*x^19 -x^18 -x^17 -x^16 -x^15 +3*x^14 -x^13 -x^12 -x^11 -x^10 +4*x^9 -x^8 -x^7 -x^6 -x^5 +3*x^4 -x^3 -x^2 -x -1) / ((x -1)^2*(x^4 +x^3 +x^2 +x +1)*(x^20 +x^15 +x^10 +x^5 +1)). - Colin Barker, Jan 10 2015

A169718 Number of ways of making change for n cents using coins of 1, 5, 10, 25, 50 and 100 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, 77, 77, 93, 93, 93, 93, 93, 112, 112, 112, 112, 112, 134, 134

Offset: 0

N. J. A. Sloane, Apr 20 2010

nonn

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

Number of partitions of n into parts 1, 5, 10, 25, 50, and 100. - 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..10000
M. Erickson, Change for a dollar, change for a million, Math. Horizons, Feb 2010, pp. 22-25.
B. Polster, Explaining the bizarre pattern in making change for a googol dollars (infinite generating functions), Mathologer video (2021).
Index entries for sequences related to making change.
Index entries for linear recurrences with constant coefficients, order 191.

Cf. A001299, A001300, A000008.

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

Table[Length[FrobeniusSolve[{1,5,10,25,50,100},n]],{n,0,80}] (* or *) CoefficientList[Series[1/((1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100)),{x,0,80}],x] (* Harvey P. Dale, Dec 25 2011 *)

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

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

A174140 Numbers congruent to k mod 25, where 10 <= k <= 24.

Original entry on oeis.org

10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 110, 111, 112, 113, 114, 115, 116

Offset: 1

Rick L. Shepherd, Mar 09 2010

Numbers whose partition into parts of sizes 1, 5, 10, and 25 having a minimal number of parts includes at least one part of size 10.
For each number the partition is unique.
Complement of A174141.
Amounts in cents requiring at least one dime when the minimal number of coins is selected from pennies, nickels, dimes, and quarters (whether usage of bills for whole-dollar amounts is permitted or not).

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

Cf. A174138, A174139, A174141, A047201 (requires at least one part of size 1 (penny)), A008587, A053344 (minimal number of parts), A001299 (number of all such partitions).

Flatten[Table[Range[10,24]+25n,{n,0,5}]] (* Harvey P. Dale, Jun 12 2012 *)

Vec(x*(10 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12 + x^13 + x^14 + x^15) / ((1 - x)^2*(1 + x + x^2)*(1 + x + x^2 + x^3 + x^4)*(1 - x + x^3 - x^4 + x^5 - x^7 + x^8)) + O(x^60)) \\ Colin Barker, Oct 25 2019

a(n+15) = a(n) + 25 for n >= 1.
From Colin Barker, Oct 25 2019: (Start)
G.f.: x*(10 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12 + x^13 + x^14 + x^15) / ((1 - x)^2*(1 + x + x^2)*(1 + x + x^2 + x^3 + x^4)*(1 - x + x^3 - x^4 + x^5 - x^7 + x^8)).
a(n) = a(n-1) + a(n-15) - a(n-16) for n>16.
(End)

A174141 Numbers congruent to k mod 25, where 0 <= k <= 9.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 150, 151, 152, 153, 154

Offset: 1

Rick L. Shepherd, Mar 09 2010

Numbers whose partition into parts of sizes 1, 5, 10, and 25 having a minimal number of parts does not include a part of size 10.
For each number the partition is unique.
Complement of A174140.
Amounts in cents not including a dime when the minimal number of coins is selected from pennies, nickels, dimes, and quarters (whether usage of bills for whole-dollar amounts is permitted or not).

Index entries for sequences related to making change.
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1).

Cf. A174138, A174139, A174140, A047201 (requires at least one part of size 1 (penny)), A008587, A053344 (minimal number of parts), A001299 (number of all such partitions).

LinearRecurrence[{1,0,0,0,0,0,0,0,0,1,-1},{0,1,2,3,4,5,6,7,8,9,25},70] (* Harvey P. Dale, May 30 2014 *)

a(n+10) = a(n) + 25 for n >= 1.

a(n)= +a(n-1) +a(n-10) -a(n-11). G.f. x^2*(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+16*x^9) / ( (1+x)*(1+x+x^2+x^3+x^4)*(x^4-x^3+x^2-x+1)*(x-1)^2 ). - R. J. Mathar, Oct 08 2011

A351725 Table T(n,k) read by rows: number of partitions of n into k parts of size 1, 5, 10 or 25.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1

Offset: 0

R. J. Mathar, Feb 17 2022

Multiset transform of the binary sequence b(n)=1,1,0,0,0,1,0,0,0,0,1,0,... with g.f. 1 + x + x^5 + x^10 + x^25, where b(.) is the Inverse Euler Transform of A001299.

			T(30,6)=2 counts the partitions 5+5+5+5+5+5 = 1+1+1+1+1+25.
The triangle starts at row n=0 and has columns k=0..n:
1
0 1
0 0 1
0 0 0 1
0 0 0 0 1
0 1 0 0 0 1
0 0 1 0 0 0 1
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 1
0 1 1 0 0 0 1 0 0 0 1
0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 0 1 1 0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
0 0 1 1 1 1 2 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1

Alois P. Heinz, Rows n = 0..360, flattened
Index entries for sequences related to making change.

Cf. A001299 (row sums), A351740.
Column k=0 gives A000007.
Main diagonal gives A000012.
T(2n,n) gives A351742.

b:= proc(n, i) option remember; `if`(n=0 or i=1, x^n, b(n, i-1)+
     (p-> `if`(p>n, 0, expand(x*b(n-p, i))))([1, 5, 10, 25][i]))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 4)):
seq(T(n), n=0..15);  # Alois P. Heinz, Feb 17 2022

b[n_, i_] := b[n, i] = If[n == 0 || i == 1, x^n, b[n, i - 1] +
     Function[p, If[p > n, 0, Expand[x*b[n-p, i]]]][{1, 5, 10, 25}[[i]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 4]];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 16 2022, after Alois P. Heinz *)

T(n,0) = 0 if k>0.
T(n,n) = 1.
Sum_{k=0..n} k * T(n,k) = A351740(n). - Alois P. Heinz, Feb 17 2022

A160551 Number of unordered ways of making change for n dollars using coins of denominations 1, 5, 10, and 25.

Original entry on oeis.org

1, 242, 1463, 4464, 10045, 19006, 32147, 50268, 74169, 104650, 142511, 188552, 243573, 308374, 383755, 470516, 569457, 681378, 807079, 947360, 1103021, 1274862, 1463683, 1670284, 1895465, 2140026, 2404767, 2690488, 2997989, 3328070, 3681531, 4059172, 4461793

Offset: 0

Lee A. Newberg, May 18 2009, Jun 15 2009

a(n) is the number of distinct quadruplets (p, k, d, q) of nonnegative integers satisfying p + 5k + 10d + 25q = 100n.

			There are four ways to make $0.10: (1) 10 pennies, (2) 5 pennies and 1 nickel, (3) 2 nickels, and (4) 1 dime.

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A001299.

f := 1/(1-x)/(1-x^5)/(1-x^10)/(1-x^25); a := n -> (convert(series(f,x,100*n+1),polynom)-convert(series(f,x,100*n),polynom)) /x^(100*n);
a := n -> (3 + 53*n + 270*n^2 + 400*n^3) / 3;

a(n) = {(3 + 53*n + 270*n^2 + 400*n^3) / 3} \\ Andrew Howroyd, Feb 02 2020

a(n) = [x^(100*n)] 1/((1-x)*(1-x^5)*(1-x^10)*(1-x^25)).
a(n) = (3 + 53*n + 270*n^2 + 400*n^3) / 3.
From Alois P. Heinz, Oct 08 2022: (Start)
a(n) = A001299(100*n).
G.f.: (60*x^3+501*x^2+238*x+1)/(x-1)^4. (End)

Terms a(21) and beyond from Andrew Howroyd, Feb 02 2020

A174138 Numbers congruent to {5,6,7,8,9,15,16,17,18,19} mod 25.

Original entry on oeis.org

5, 6, 7, 8, 9, 15, 16, 17, 18, 19, 30, 31, 32, 33, 34, 40, 41, 42, 43, 44, 55, 56, 57, 58, 59, 65, 66, 67, 68, 69, 80, 81, 82, 83, 84, 90, 91, 92, 93, 94, 105, 106, 107, 108, 109, 115, 116, 117, 118, 119, 130, 131, 132, 133, 134, 140, 141, 142, 143, 144, 155, 156, 157

Offset: 1

Rick L. Shepherd, Mar 09 2010

Numbers whose partition into parts of sizes 1, 5, 10, and 25 having a minimal number of parts includes a part of size 5.
For each number the partition is unique and exactly one part is of size 5.
Complement of A174139.
Amounts in cents requiring a nickel when the minimal number of coins is selected from pennies, nickels, dimes, and quarters (whether usage of bills for whole-dollar amounts is permitted or not).
For each n >= 0, floor(n/25) parts of size 25 (quarters) occur in the partition with minimal number of these parts (regardless of whether partition includes part of size 5).

			As 15 = 10 + 5, 15 is a term since 5 is included and all other candidate partitions have more than two parts. Similarly, as 30 = 25 + 5, 30 is a term. However, 45 = 25 + 10 + 10 is not a term as it contains no part of size 5.

Index entries for sequences related to making change.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,0,1,-1).

Cf. A174139, A174140, A174141, A047201 (requires at least one part of size 1 (penny)), A008587, A053344 (minimal number of parts), A001299 (number of all such partitions).

[n : n in [1..200] | n mod 25 in [5, 6, 7, 8, 9, 15, 16, 17, 18, 19]]; // Vincenzo Librandi, Mar 22 2015

Table[n + 9 + 5 Floor[(Floor[(n - 1)/5] - 1)/2] + 10 Floor[Floor[(n - 1)/5]/2], {n, 100}] (* Wesley Ivan Hurt, Mar 22 2015 *)

a(10+n) = a(n) + 25 for n >= 1.
a(n) = a(n-1) + a(n-10) - a(n-11). G.f.: x*(5+x+x^2+x^3+x^4+6*x^5+x^6+x^7+x^8+x^9+6*x^10)  / ( (1+x) *(x^4+x^3+x^2+x+1) *(x^4-x^3+x^2-x+1)*(x-1)^2 ). - R. J. Mathar, Oct 08 2011
a(n) = n+9+5*floor((floor((n-1)/5)-1)/2)+10*floor(floor((n-1)/5)/2). - Wesley Ivan Hurt, Mar 22 2015

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

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

A053344 Minimal number of coins needed to pay n cents using coins of denominations 1, 5, 10, 25 cents.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

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

A174140 Numbers congruent to k mod 25, where 10 <= k <= 24.

Views

Author

Keywords

Comments

Links

Crossrefs