ブログ

家庭科・調理 フィボナッチ数列の出現例

1ドル札と2ドル札のみを使い,n(整数)ドルを払う方法の数B(n)を求めましょう.

1.n=1のとき:2ドル札は0枚で,1ドル札1枚出すしか方法はありません:
  方法{1}のみで,方法の数はB(1)=1
2.n=2のとき:2ドル札0枚なら{1,1},2ドル札1枚なら{2}で,
  方法の数は B(2)=2
3.n=3のとき:2ドル札0枚なら{1,1,1},2ドル札1枚なら{2,1},{1,2}で,
  方法の数は B(3)=3
4.n=4のとき:2ドル札0枚なら{1,1,1,1},2ドル札1枚なら{2,1,1},{1,2,1},{1,1,2},2ドル札2枚なら{2,2}で,
  方法の数は B(4)=5
(ただし,同じ種類の札は区別していません)

これらの結果を考察すると,
B(n)はB(n-1)の方法に1ドル追加したものと,B(n-2)の方法に2ドル追加するものとの和になる.
2ドル追加の方法に{1,1}を追加する方法があると思う人がいるかもしれないが,
追加する2つの1のうちの始めの1は,B(n-1)個の方法に繰り込まれ,すでに存在し,それに1を追加することは,すでに前者の項に含まれている.ゆえに.
B(n)=B(n-1)+B(n-2)
かくして,この方法でnドル支払う方法の数の再帰的な定義が得られました.
これはフィボナッチ数列
1,2,3,5,8,13,21,34,55,・・・・・
の定義と同じです.

1,2,3の3つの数字を和の構成因子として,正の整数nを表現したとき,異なる表現数をb(n)とする.以下は例です.
1.1=1 b(1)=1
2.2=1+1=2 b(2)=2
3. 3=(1+1)+1=(2)+1=3 b(3)=3
4. 4=(1+1+1)+1=(2+1)+1=(3)+1=2+2 b(4)=4
5. 5=(1+1+1+1)+1=(2+1+1)+1=(3+1)+1=(2+2)+1=2+3 b(5)=5
6.6=(1+1+1+1+1)+1=(2+1+1+1)+1=(3+1+1)+1=(2+2+1)+1=(2+3)+1=3+3 b(6)=6
7.7=(1+1+1+1+1+1)+1=(2+1+1+1+1)+1=(3+1+1+1)+1=(2+2+1+1)+1=(2+3+1)+1=(3+3)+1=3+2+2 b(7)=7

n-1の展開表現の各々に1づつ加えてnの展開表現を得るが,これに加えて,新しい表現が1つできる.従って,
b(n)=b(n-1)+1=n

タグ