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

%I #16 Nov 27 2023 17:40:37

%S 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,

%T 70,76,82,88,98,104,114,120,130,140,150,160,170,180,195,205,220,230,

%U 245,260,275,290,305,320,342,357,379,394,416,438,460,482,504,526

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

%C 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;

%C a(n) = A000008(n) for n < 50; a(50) = A000008(50) + 1 = 342;

%C a(n) = A001312(n) for n < 200; a(200) = A001312(200) + 1 = 26905.

%C Number of partitions of n into parts 1, 2, 5, 10, 50, 100, 200, and 500. - _Joerg Arndt_, Jul 08 2013

%H G. C. Greubel, <a href="/A182086/b182086.txt">Table of n, a(n) for n = 0..1000</a>

%H Deutsche Bundesbank, <a href="http://www.bundesbank.de/bargeld/bargeld_faq_muenzendm.php#umlabb">Umlaufmuenzen</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Deutsche_Mark#Coins">Deutsche Mark, Coins</a>

%H <a href="/index/Mag#change">Index entries for sequences related to making change.</a>

%H <a href="/index/Rec#order_868">Index entries for linear recurrences with constant coefficients</a>, order 868.

%F 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

%e Number of partitions of coin values into coin values:

%e a(1) = #{1} = 1;

%e a(2) = #{2, 1+1} = 2;

%e a(5) = #{5, 2+2+1, 2+1+1+1, 1+1+1+1+1} = 4;

%e 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;

%e 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;

%e a(100) = 2499;

%e a(200) = 26905;

%e a(500) = 1229587.

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

%o (Haskell)

%o a182086 = p [1,2,5,10,50,100,200,500] where

%o p _ 0 = 1; p [] _ = 0

%o p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

%o (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

%Y Cf. A001364, A067996, A082593.

%K nonn

%O 0,3

%A _Reinhard Zumkeller_, Apr 11 2012