■コイン問題(その3)

[Q]1セント,5セント,10セント,50セントの5種類の硬貨で1ドル(100セント)を両替するには何通りの仕方があるか?

全部を1セントで両替の仕方をAn

1セントと5セントを使う両替の仕方をBn

1セントと5セントと10セントを使う両替の仕方をCn

1セントと5セントと10セントと25セントを使う両替の仕方をDn

1セントと5セントと10セントと25セントと50セントを使う両替の仕方をEnで表せば,

  En=Dn+En-50

  Dn=Cn+Dn-25

  Cn=Bn+Cn-10

  Bn=An+Bn-5

  A0=B0=C0=D0=1

目標はE100であるが,E100=292

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

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 13 18 24 31 39 49

En  1 2 4 6 9 13 18 24 31 39 50

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

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  49 60 73 87 103 121 141 163 187 213 242

En  50 62 77 93 112 134 159 187 218 252 292

目標はE100であるが,E100=292通り

4種類の硬貨25セント,10セント,5セント,1セントを用いて,1ドルを両替する方法は242通りあることもわかるだろう.

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

[Q]1ドルを25セント,10セント,5セントを用いて両替する方法は何通りあるか

29通り

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