A057537 Number of ways of making change for n Euro-cents using the Euro currency.

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

Offset: 0

Author

Thomas Brendan Murphy (murphybt(AT)tcd.ie), Sep 06 2000

Keywords

• nonn
• easy

Comments

Euro currency has coins and bills of size 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000 cents.

Differs from A001313 first at n=100. - Georg Fischer, Oct 06 2018

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.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..65536
• AFP, 500-euro note gets last print run, (2019)
• Index entries for sequences related to making change.
• Index entries for linear recurrences with constant coefficients, order 88888.

Crossrefs

Cf. A001313.

Programs

Maple

gf:= 1/expand((1-x) * (1-x^2) * (1-x^5) * (1-x^10) * (1-x^20) * (1-x^50) * (1-x^100) * (1-x^200) * (1-x^500) * (1-x^1000) * (1-x^2000) * (1-x^5000) * (1-x^10000) * (1-x^20000) * (1-x^50000)):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..100);

Mathematica

f = 1/Times@@(1 - x^{1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000}); a[n_] := SeriesCoefficient[f, {x, 0, n}]; Table[a[n], {n, 1, 61}] (* Jean-François Alcover, Nov 28 2013, after Maple *)

PARI

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

Formula

G.f.: 1/((1-x) * (1-x^2) * (1-x^5) * (1-x^10) * (1-x^20) * (1-x^50) * (1-x^100) * (1-x^200) * (1-x^500) * (1-x^1000) * (1-x^2000) * (1-x^5000) * (1-x^10000) * (1-x^20000) * (1-x^50000)).