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

Author

Reinhard Zumkeller, Apr 11 2012

Keywords

• nonn

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

Examples

			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.
		

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.

Crossrefs

Cf. A001364, A067996, A082593.

Programs

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

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

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

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