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

A008616 Expansion of 1/((1-x^2)(1-x^5)).

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Number of partitions of n into parts of size two and five.

It appears that, for n >= 2, a(n-2) is also (1) the number of partitions of 3n that are 6-term arithmetic progressions and (2) floor(n/2) - floor(2n/5). - John W. Layman, Jun 29 2009

G. E. Andrews, K. Eriksson, Integer Partitions, Cambridge Univ. Press, 2004. page 30, Exercise 48.
D. J. Benson, Polynomial Invariants of Finite Groups, Cambridge, 1993, p. 100.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 213
M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (0, 1, 0, 0, 1, 0, -1).

Cf. A000217, A025810.

Cf. A008615. - John W. Layman, Jun 29 2009

m:=100; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(1/((1-x^2)*(1-x^5)))); // Wesley Ivan Hurt, Dec 27 2021

CoefficientList[Series[1 / ((1 - x^2) (1 - x^5)),{x, 0, 100}], x] (* Vincenzo Librandi, Jun 21 2013 *)

{a(n) = if( n<-6, -a(-7 - n), polcoeff( 1 / (1 - x^2) / (1 - x^5) + x * O(x^n), n))} /* Michael Somos, Jan 25 2005 */

a(n) = floor(n/10+(3+(-1)^n)/4) \\ Charles R Greathouse IV, Jun 19 2013

G.f.: 1/((1-x^2)(1-x^5)) = 1/((x-1)^2*(1+x)*(1+x+x^2+x^3+x^4)).
Euler transform of finite sequence [0, 1, 0, 0, 1].
a(n) = -a(-7 - n) = a(n - 10) + 1 = a(n - 2) + a(n - 5) - a(n - 7). - Michael Somos, Jan 25 2005
A000217(a(n)) = A025810(n). - Michael Somos, Dec 15 2002
a(n) = 7/20 + n/10 + (-1)^n/4 + (A105384(n) + 2*(A010891(n) + A105384(n+4)))/5. - R. J. Mathar, Jun 28 2009
a(n) = floor(n/10 + (3 + (-1)^n)/4). - Tani Akinari, Jun 20 2013

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

A008616 Expansion of 1/((1-x^2)(1-x^5)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula