Fibonacci 数の組みあわせ論的な性質とその応用
二項係数の斜め和
前提知識 : Fibonacci 数列, 二項係数
Fibonacci 数列 :
https://mathlog.info/articles/191
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
問題
Fibonacci 数列は, 以下のような組みあわせ論的な問題にも現れ, ときに Fibonacci 数に関する等式の導出にも用いることができる. 以下にその具体例を挙げる.
問. 十段の階段を, 一段上がりと二段上がりを用いて上る方法は何通り在るか ?
解. 一般の正なる整数$n$について, $n$段の階段を一段上がりと二段上がりを用いて上る方法の総数を$a_n$と表記する. $n\geqslant3$とする. $n$段の階段を一段上がりと二段上がりを用いて上るとき, 始めの一歩にて一段のみ上るのならば残りの段の上り方は$a_{n-1}$通り, 二段上るのならば残りの段の上り方は$a_{n-2}$通り在り, これらは重複せず, かつその外に場合は無いため
$$
\begin{align}
a_{n}=a_{n-1}+a_{n-2}
\end{align}
$$が恒に真なることを得る. $n<3$のとき$a_1=1,\ a_2=2$であるから
$$
\begin{align}
a_n=F_{n+1}
\end{align}
$$の成立が再帰的に判り, $a_{10}=F_{11}=89$と決定された. 八十九通り.
問. 「毎月一番いの兎が一番いの兎を生み, 生まれた一番いの兎が翌月から一番いの兎を生み始めるとすれば, 一番いの兎から始めて一年間に合計何番いの兎が生まれるか ? 」
この問題は, Leonardo Fibonacci (Leonardo Pisano) が著書『算盤の書』(Liber Abacī) に記した問題である.
解. 便宜のため, 生後一か月未満の兎を子供, そうでない兎を大供と言う. 一般の正なる整数$n$について, $n$か月後の子供, 大供の番いの数をそれぞれ$a_n,b_n$と表記する. $n\geqslant3$とする. 与えられた条件から考えて, $a_n,b_n$を表しかえれば
$$
\begin{align}
&a_n=b_{n-1},\\\\
&b_n=b_{n-1}+a_{n-1}
\end{align}
$$なる二つの恒等式が導かれ, 第一式を第二式に用いることによって
$$
\begin{align}
b_n=b_{n-1}+b_{n-2}
\end{align}
$$が恒に真なることを得る. $n<3$のとき$b_1=1,\ b_2=2$であるから
$$
\begin{align}
b_n=F_{n+1},\quad a_n=F_n
\end{align}
$$の成立が再帰的に判り, $a_{12}+b_{12}=F_{12}+F_{13}=377$と決定された. 三百七十七番い.
問. $1,2,3,4,5,6,7,8,9,10$の十数から内幾つかを選ぶ. 隣りあう二数を選んではならないとすれば, これらの選び方は何通り在るか ? ただし, 一つも選ばない場合も一通りと数える.
解. 一般の正なる整数$n$について, $1,2,3,\ldots,n$の中から内幾つかを選ぶ方法であって, 隣りあう二数を選ばないようなものの総数を$a_n$と表記する. $n\geqslant3$とする. $1,2,3,\ldots,n$の中から選ぶとき, $1$を選ぶのならば残りの選び方は$a_{n-2}$通り, $1$を選ばないのならば$a_{n-1}$通り在り, これらは重複せず, かつその外に場合は無いため
$$
\begin{align}
a_{n}=a_{n-2}+a_{n-1}
\end{align}
$$が恒に真なることを得る. $n<3$のとき$a_1=2,\ a_2=3$であるから
$$
\begin{align}
a_n=F_{n+2}
\end{align}
$$の成立が再帰的に判り, $a_{10}=F_{12}=144$と決定された. 百四十四通り.
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
等式の導出への応用
任意の$m,n\in\mathbb{Z}_{>0}$に対して, $F_{m+n+1}=F_{m+1}F_{n+1}+F_mF_n$が成りたつ.
$n$段の階段を一段上がりと二段上がりを用いて上る方法の総数を$a_n$と表記し, $a_{m+n}$を二通りに数える. 先ず, 第一の問題から
$$
\begin{align}
a_{m+n}=F_{m+n+1}
\end{align}
$$と表せる. 続いて, 階段の全体を始めの$m$段と終わりの$n$段に分割するとき, 始めの$m$段のうちの最後の段 ($m$段目)
を踏む場合と踏まない場合とが存在して, それぞれの総数を足しあわせると
$$
\begin{align}
a_{m+n}&=a_ma_n+a_{m-1}a_{n-1}\\
&=F_{m+1}F_{n+1}+F_mF_n
\end{align}
$$とも表せる. 以上の二つの等式から命題を得る. $\quad\Box$
任意の$n\in\mathbb{Z}_{>0}$に対して, $\displaystyle\sum_{0\leqslant j\leqslant i,\ i+j=n}\binom{i}{j}=F_{n+1}$が成りたつ.
$1,2,3,\ldots,n$の中から内幾つかを選ぶ方法であって, 隣りあう二数を選ばないようなものの総数を$a_n$と表記し, $a_n$を二通りに数える. 先ず, 第三の問題から
\begin{align}
a_{n}=F_{n+2}
\end{align}と表せる. 続いて, $1,2,3,\ldots,n$のそれぞれを選ぶものと選ばないものとに分類するという見方を取るとき, 自由に裏返すことのできる硬貨を用いると, 一列に並べられた$n$個の硬貨の表裏の配列であって, 表向きの硬貨の隣りあわないようなものの総数を代わりに数えれば善いことになる. 初めに裏向きに置く$k$個の硬貨を決めて並べておき, その後残りの$n-k$個の表向きの硬貨を挿入する位置を, 先の裏向きの硬貨どうしの間または両端から選ぶとすれば, $a_n$は
$$
\begin{align}
a_{n}&=\sum_{0\leqslant k\leqslant n}\binom{k+1}{n-k}\\
&=\sum_{0\leqslant j\leqslant n}\binom{n+1-j}{j}\quad(j=n-k)\\
&=\sum_{o\leqslant j\leqslant i,\ i+j=n+1}\binom{i}{j}
\end{align}
$$とも表せる. 以上の二つの等式から命題の$n\geqslant2$なる場合が得られ, $n=1$のときは容易に確かめられる. $\quad\Box$
$n,r\in\mathbb{Z}_{>0}$について, 二項係数$\displaystyle\binom{n}{r}$は$n\lt r$のとき零であるとして式変形を施している.
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
この記事を高評価した人
この記事に送られたバッジ
投稿者
