■シルベスターの公式・フロベニウス数(その18)

[Q]1円,5円,10円,50円で100円を両替するには何通りの仕方があるか?

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

 nに対する両替の仕方をDnであらわせば,

n  4 5 9 10 14 15 19 20 24 25

Dn  1 2 2 4 4 6 6 9 9 12

目標はD100であるが,

全部を1円で両替の仕方をAn

1円と5円を使う両替の仕方をBn

1円と5円と10円を使う両替の仕方をCn

1円と5円と10円と50円を使う両替の仕方をDnで表せば,

  Dn=Cn+Dn-50

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

  Cn=Bn+Cn-10

  Bn=An+Bn-5

  A0=B0=C0=D0=1

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

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

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 37・・・?

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

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