Fibonacci数と組み合わせ論

はじめに

本稿では，漸化式$F_1=1,F_2=1,F_{n+2}=F_{n+1}+F_n(n=1,2,\cdots )$で与えられるFibonacci数について，その華麗な性質のいくつかを，問題を通して組み合わせ論的な側面から眺めてみます．
なお，本稿では上記のように，$n$番目のFibonacci数を$F_n$で表すものとします．

問題をいくつか

例えば$n=4$のとき，以下の5通りである．

問題1 $n=4$の例

例えば$n=3$のとき，以下の5通りである．

問題2 $n=3$の例

それでは解答を書いていきます．考えたい人は考えてください．(答え自体は容易に想像つくけど……)

問題1の解答

■$n=1,2$のとき
このとき，それぞれ1通り，2通り．
■$n\ge 3$のとき
最後の一歩として，「$n-1$段目から$1$段登る」か「$n-2$段目から$2$段登る」の$2$通りが考えられる．よって求める登り方の通り数は($n-1$段の通り数)$+$($n-2$段の通り数)．
以上より，$F_{n+1}$通りが求める答えである．

問題2の解答

問題1の階段で，$n+1$段のものを考える．
この階段の$1$段目から$n$段目までをマス目とみなし，段を踏んで登ることをマスを黒く塗ることを$1$対$1$に対応付けることが出来る．

以上より，$F_{n+2}$通りが求める答えである．

1対1対応

問題1，問題2を踏まえて，これらは次のように一般化することができる．

さらに，これから他にも次のような系も考えることができる．

拡張してみよう

問題1の拡張

まずは問題1を拡げてみる．問題1を再掲しておこう．

$m+n$段の階段を考える．問題1の解答を用いてこれの登り方の通り数を求める．
まず，問題$1$の解答より，登り方の通り数は$F_{m+n+1}$通り．
さて，次に，登り方には$m$段目を踏むか$m$段目を踏まないの$2$通りがあることを考える．
前者は($m$段の登り方)$\times$($n-1$段の登り方)通り，後者は($m-1$段の登り方)$\times$($n$段の登り方)通りである．
以上より，次がいえる：
$$F_{m+n+1}=F_{m+1}{F}_{n+1}+F_m{F}_n$$

添字を書き換えて，

これは加法定理と呼ばれる．

これはよくFibonacci数列の一般項を表すBinetの公式を用いて示されることが多いが，このような組み合わせ論的な証明を見出すことができた．

また，この加法定理については こちらの記事 もぜひご覧ください．

問題2の拡張

次に問題2について．これも再掲しておく．

$n$個のマスのうち，$k$個を白で塗ることを考えよう．

このときの塗り方は，黒マスを$n-k$個用意し，その両端と間の$n-k+1$か所の中から白マスが入るところを選ぶ場合の数に等しいので${}_{n-k+1}{\mathrm{C}}_k$通り．

ここで，$k$は$0$から$\lfloor {\displaystyle \frac{n+1}{2}}\rfloor$までの値をとることから，次を得る：

$$F_{n+2}=\sum _{k=0}^{\lfloor (n+1)/2\rfloor }{}_{n-k+1}{\mathrm{C}}_k$$
添字を書き換えて，

が成り立つ．

ここからさらに，Pascalの三角形を考えよう．

Pascalの三角形

これは，次に示す補題2から，二項係数を用いて次のように書くことができる：

Pascalの三角形

さて，先ほど得た$F_{n+1}=\sum _{k=0}^{\lfloor n/2\rfloor }{}_{n-k}{\mathrm{C}}_k$の式について考えよう．右辺の二項係数の和の部分は，Pascalの三角形では直線上に現れる．例えば，$n=4$のときは下図のところに現れ，これらの和が$F_4$になっている．

Pascalの三角形

以上のことより，Pascalの三角形を下図のように斜めに足すと，Fibonacci数列が現れる．

Pascalの三角形