■コイン問題(その2)

【2】漸化式

A0+A1x+A2x^2+・・・=(B0+B1x+B2x^2+・・・)(1−x^5)

より

  Bn=An+Bn-5

同様に

  Cn=Bn+Cn-10

  Dn=Cn+Dn-50

  A0=B0=C0=D0=1

  A1=A2=A3=・・・=1

という漸化式の問題となる.

  Dn=Cn+Dn-50

すなわち,50円を使わない,50円を使う両替の仕方に分けることができる.

===================================

n  0 5 10 15 20 25 30 35 40 45 50

An  1 1 1 1 1 1 1 1 1 1 1

Bn  1 2 3 4 5 6 7 8 9 10 11

Cn  1 2 4 6 9 12 16 20 25 30 36

Dn  1 2 4 6 9 12 16 20 25 30 37

===================================

n  50 55 60 65 70 75 80 85 90 95 100

An  1 1 1 1 1 1 1 1 1 1 1

Bn  11 12 13 14 15 16 17 18 19 20 21

Cn  36 42 49 56 64 72 81 90 100 110 121

Dn  37 44 53 62 73 84 97 110 125 140 158

158通り

===================================