階段の下り方

数学B数列数学B

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


目次
  • 1. Ⅰ 問題
  • 2. Ⅱ 解法

Ⅰ 問題

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

問題

  \(~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,新潮社.

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

数学B数列数学B

Posted by Fuku