階段の下り方

  $~n~$ 段の階段を下りるときに、一段下りるか、二段下りる(一段飛ばし)かを組み合わせると、全部で何通りの下り方があるのか?
この問いが「浜村渚」シリーズで出てきたので、実際に計算してみました。
Ⅰ 問題
Ⅱ 解法


目次

Ⅰ 問題

 今回考えるのはこんな問題です。

問題

  $~n~$ 段の階段がある。この階段を下りていく際、

 ①1段下りる
 ②2段下りる(1段飛ばし)

の2通りを自由に組み合わせるとき、何通りの下り方があるか?

 『浜村渚の計算ノート』第1巻の、第3話($\log{1000}$. ちごうた計算)のp179には次のような文があります。

 取調質室を出てすぐ脇の階段を下り始めると同時に、浜村渚は何か考え込みながら、不規則な歩き方をした。一段下りたかと思うと、次の一段をとばして下りてみたり、とにかく不規則な、不思議な下り方だ。━━一段下りるか、一段とばして二段下りるか、この二通りの下り方を組み合わせたら、$n$段下りるのに何通りの下り方がありますか?

 渚の数学好きを示すかのような描写ですが、この話とふか~い関わりがありました。

浜村渚の計算ノート (講談社文庫) [ 青柳碧人 ]


Ⅱ 解法

 まずは $~n=1~$ から考えていきましょう。

$n=1~$ のとき


 図からわかる通り、①(1段下りる)の1通り。

 続いて、 $~n=2~$ のときです。

$n=2~$ のとき



 こちらは、を2回繰り返すか、②(2段下りる)で一気に下りるかの2通り。

 もう1つ、 $~n=3~$ のときも数えてみます。

$n=3~$ のとき




を3回繰り返すか、で1段2段と下りていくか、で2段1段と下りていくかの3通り。

 ここで気づくのが、

 3段目は1段目と2段目を合わせたものである

ということ。
 3段階段の最初の2つの下り方については、1段下ってから $~n=2~$ の考え方を使ってます。最後の1つの下り方については、2段下ってから $~n=1~$ の考え方を使ってます。
 すなわち、

\begin{align}
&3段階段の下り方 \\
&=2段階段の下り方+1段階段の下り方
\end{align}


\begin{equation}
3段階段の下り方=2段階段の下り方+1段階段の下り方
\end{equation}

ということになります。
 
 もう、ピンと来ましたね。本題の $~n~$ 段についても考えてみましょう。

解説

  $~n~$ 段の階段の下り方は $~a_{n}~$ 通りあるとする。
 階段を3段以上一気に下ることができないため、最初の一歩により、次のように場合分けできる。
(1) 最初に1段下った場合
 
 このとき、残りは $~(n-1)~$ 段である。よって、 $~a_{n-1}~$ 通り。
 
(2) 最初に2段下った場合

 このとき、残りは $~(n-2)~$ 段である。よって、 $~a_{n-2}~$ 通り。
 
 以上より、 $~n~$ 段の階段の下り方は
\begin{equation}
a_{n}=a_{n-1}+a_{n-2}
\end{equation}
と表せる。ただし、 $~a_{1}=1,a_{2}=2~$ である。

 ということで、フィボナッチ数列の考え方です。
 よく登場するフィボナッチ数列の定義とは、項が1つ分ズレていますが、本質は同じ↓↓

フィボナッチ数列

 次の漸化式で与えられる数列 $~\{F_n \}~$ をフィボナッチ数列という。
\begin{equation}
F_{n+2}=F_{n+1}+F_{n}
\end{equation}
ただし、 $~F_{1}=1,F_{2}=1~$ とする。

 ということで、フィボナッチ数列の一般項から、 $~n~$ 段階段の下り方の場合の数を求めると、

\begin{align}
&\displaystyle a_{n} \\
\\
&=\frac{1}{\sqrt{5}}\left\{ \left( \frac{1+\sqrt{5}}{2} \right)^{n+1}-\left( \frac{1-\sqrt{5}}{2} \right)^{n+1} \right\}
\end{align}


\begin{equation}
\displaystyle a_{n}=\frac{1}{\sqrt{5}}\left\{ \left( \frac{1+\sqrt{5}}{2} \right)^{n+1}-\left( \frac{1-\sqrt{5}}{2} \right)^{n+1} \right\}
\end{equation}

 という答えが出てきます。階段も黄金比につながっているんですね。


 数えるとキリがない $~n~$ 段階段も、漸化式の考え方を使うと簡単に解けてしまうのがすごいですね。しかも、フィボナッチ数列。この世はフィボナッチ数列に溢れています。

   


◇参考文献等
・青柳碧人(2014)『浜村渚の計算ノート』,p.179,新潮社.

浜村渚の計算ノート (講談社文庫) [ 青柳碧人 ]

よかったらシェアしてね!

コメント

コメントする

CAPTCHA


目次
閉じる