[答595] 17段の階段の上がり方

'


[答595] 17段の階段の上がり方


　階段を上がるとき、１段上がるか２段上がるかを組み合わせて 17段の階段を上がる方法は何通り？

　ただし、連続して２段上がれないものとします。


[解答1]

　２段上がる回数は 0，1，2，3，4，5，6 回のいずれかです。

　例えば、２段上がる回数が４回の場合、１段上がる回数は９回で、

　｜
｜
｜
｜
｜
｜
｜
｜
｜
｜　のうちの、

　縦線の所４ヶ所に
を入れれば上がり方を示せるから、その総数は、₁₀Ｃ₄ になります。

　従って、問題の総数は、

　₁₈Ｃ₀＋₁₆Ｃ₁＋₁₄Ｃ₂＋₁₂Ｃ₃＋₁₀Ｃ₄＋₈Ｃ₅＋₆Ｃ₆＝1＋16＋91＋220＋210＋56＋1＝595 になります。


[解答2]

　２段上がる回数は 0，1，2，3，4，5，6 回のいずれかです。

　例えば、２段上がる回数が４回の場合、１段上がる回数は９回で、

　｜

｜

｜

｜
｜　のうちの、

　５本の縦線の所のうち重複可で６ヶ所に
を入れれば上がり方を示せるから、その総数は、₅Ｈ₆ になります。

　従って、問題の総数は、

　₁Ｈ₁₈＋₂Ｈ₁₅＋₃Ｈ₁₂＋₄Ｈ₉＋₅Ｈ₆＋₆Ｈ₃＋₇Ｈ₀＝1＋16＋91＋220＋210＋56＋1＝595 になります。


[解答3]

　ｎ段の階段を上がる方法を a_n 通りとします。

　17段の階段を上がるとき、最後に１段上がる場合は a₁₆ 通り、

　最後に２段上がる場合は、その前は１段上がることになり a₁₄ 通りだから、

　a₁₇＝a₁₆＋a₁₄ で、一般に、a_n＝a_n-1＋a_n-3 が成り立ちます。

　a₁＝1，a₂＝2，a₃＝3 だから、　a₄＝a₃＋a₁＝4 ，a₅＝a₄＋a₂＝6 ， a₆＝a₅＋a₃＝9 ，a₇＝a₆＋a₄＝13 ，

　a₈＝a₇＋a₅＝19 ， a₉＝a₈＋a₆＝28 ，a₁₀＝a₉＋a₇＝41 ，a₁₁＝a₁₀＋a₈＝60 ， a₁₂＝a₁₁＋a₉＝88 ，

　a₁₃＝a₁₂＋a₁₀＝129 ，a₁₄＝a₁₃＋a₁₁＝189 ， a₁₅＝a₁₄＋a₁₂＝277 ，a₁₆＝a₁₅＋a₁₃＝406 ，

　a₁₇＝a₁₆＋a₁₄＝595　になります。


☆ 漸化式 a_n＝pa_n-1＋qa_n-2＋ra_n-3 について、

　特性方程式 x³＝px²＋qx＋r が異なる解α，β，γをもつとき、

　定数 A，B，C を使って、a_n＝Aαⁿ＋Bβⁿ＋Cγⁿ　と表されることが知られています。

　本問では、K＝³√{(29－3√93)/2}，L＝³√{(29－3√93)/2} とすれば、

　特性方程式 x³＝x²＋1 の解は、

　(1＋K＋L)/3，{2－(1－i√3)K－(1＋i√3)L}/6，{2－(1＋i√3)K－(1－i√3)L}/6 になり、

　これを α，β，γ として、a_n＝Aαⁿ＋Bβⁿ＋Cγⁿ 、

　ここで、a₁＝1，a₂＝2，a₃＝3 となるように、定数 A，B，C を決めれば、一般式を得ることはできますが、

　計算は困難です。

.