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

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, 342, 357, 379, 394, 416, 438, 460, 482, 504, 526

Offset

0,3

Comments

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

Links

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.

Formula

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

Example

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.

Mathematica

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

Prog

(Haskell)
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
(PARI) 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

Crossrefs

Cf. A001364, A067996, A082593.

Sequence in context: A029015 A000008 A001312 * A001301 A001302 A001313

Adjacent sequences: A182083 A182084 A182085 * A182087 A182088 A182089

Keyword

nonn

Author

Reinhard Zumkeller, Apr 11 2012

Status

approved