フィボナッチ数列の組み合せ論的解釈
フィボナッチ数列の組み合せ論的解釈
(1)
\(n\)段の階段を1段または2段ずつ登るときの登り方は\(F_{n+1}\)通り。(2)
○と×を\(n\)個1列に並べるとき、×が連続にならないように並べる方法は\(F_{n+2}\)通り(1)
4段の階段を1段または2段ずつ登るときの登り方は\(F_{4+1}=F_{5}=5\)通りあり、それは\(\left(1,1,1,1\right),\)\(\left(1,1,2\right),\left(1,2,1\right),\left(2,1,1\right),\left(2,2\right)\)の5通りである。(2)
○と×を3個並べるときに×が連続にならないように並べる方法は\(F_{3+2}=F_{5}=5\)通りあり、それは\(○○○,○○\times,○\times○,\times○○,\times○\times\)の5通りである。(1)
\(n\)段を登る方法が\(W(n)\)とする。\(n\)段目にたどり着くには\(n-2\)段目から\(2\)段登るか、\(n-1\)段目から\(1\)段登るかなので、\(W(n)=W\left(n-1\right)+W\left(n-2\right)\)となる。\(W(1)=1,W(2)=2\)なので\(W(n)=F_{n+1}\)となる。(2)
\(n\)個並べる方法が\(W\left(n\right)\)とする。\(n\)個並べるのを1個と\(n-1\)個に分ける。このとき最初の1個が○なら残りのn-1個は\(W\left(n-1\right)\)通り、最初の1個が×なら次は○でないといけないので\(W\left(n-2\right)\)通りとなる。すなわち\(W\left(n\right)=W\left(n-1\right)+W\left(n-2\right)\)となる。\(W\left(1\right)=2,W\left(2\right)=3\)なので\(W(n)=F_{n+2}\)となる。
ページ情報
| タイトル | フィボナッチ数列の組み合せ論的解釈 |
| URL | https://www.nomuramath.com/xagestqa/ |
| SNSボタン |
フィボナッチ数列の定義
\[
F_{n+2}=F_{n+1}+F_{n}
\]
フィボナッチ数列の商の極限
\[
\lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_{n}}=\phi
\]
フィボナッチ数列の一般項(ビネの公式)
\[
F_{n}=\frac{1}{\sqrt{5}}\left\{ \left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right\}
\]
フィボナッチ数列同士の最大公約数
\[
\gcd\left(F_{m},F_{n}\right)=F_{\gcd\left(m,n\right)}
\]