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$が知られる. 故に八十九通りが答.
問. $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}と表せる. 又別に自由に裏返すことのできる硬貨を用いると, 一列に並べられた$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$のとき$0$であると見ること.
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
