フィボナッチ数列の組み合せ論的解釈
フィボナッチ数列の組み合せ論的解釈
(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ボタン |
フィボナッチ数列の行列表示
\[
\left(\begin{array}{cc}
F_{n+1} & F_{n}\\
F_{n} & F_{n-1}
\end{array}\right)=\left(\begin{array}{cc}
1 & 1\\
1 & 0
\end{array}\right)^{n}
\]
フィボナッチ数列の商の極限
\[
\lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_{n}}=\phi
\]
フィボナッチ数列の総和
\[
\sum_{k=0}^{n}F_{k}=F_{n+2}-1
\]
フィボナッチ数列の母関数
\[
\sum_{k=0}^{\infty}F_{k}x^{k}=\frac{x}{1-x-x^{2}}
\]