[答1118] 階段を昇る場合の数

'


[答1118] 階段を昇る場合の数


　階段を１歩で１段昇ることを｢１段昇り｣、１歩で２段昇ることを｢２段昇り｣と言うことにします。

　１段昇りの直前か直後は２段昇り、２段昇りの直前か直後は１段昇りになるように、

　32段の階段を昇る方法は何通り？

　なお、「直前か直後」の意味は、最初は「直前」がないので「直後」、最後は「直後」がないので「直前」、

　最初と最後以外は「直前」「直後」の片方でも両方でも良いものとします。


[解答]

　昇り始めも最後も 1＋2 または 2＋1 で、途中に 1＋1＋1 も 2＋2＋2 もない昇り方になります。

　ｎ段の階段を昇る方法は a_n 通り、そのうち、

　最初昇り始めが 1＋2 あるものを b_n 通り、 2＋1 あるものを c_n 通りとします。

　3＝1＋2＝2＋1 ，4＝1＋2＋1 ，5＝2＋1＋2 ，6＝1＋2＋1＋2＝1＋2＋2＋1＝2＋1＋1＋2＝2＋1＋2＋1 ，

　a₁＝a₂＝0 ，a₃＝2 ，a₄＝a₅＝1 ，a₆＝4 です。

　n≧7 として、

　ｎ段の階段を昇る方法のうち、1＋2 で始まるものは、次に 1＋2 が現れる前は、

　1＋2 ，1＋2＋1 ，1＋2＋2 ，1＋2＋2＋1 ですので、b_n＝b_n-3＋b_n-4＋b_n-5＋b_n-6 ……(1) 、

　ｎ段の階段を昇る方法のうち、2＋1 で始まるものは、次に 1＋2 が現れる前は、

　2＋1 ，2＋1＋1 ，2＋1＋2 ，2＋1＋1＋2 ですので、c_n＝c_n-3＋c_n-4＋c_n-5＋c_n-6 ……(2) 、

　a_n＝b_n＋c_n だから、(1)＋(2) より、a_n＝a_n-3＋a_n-4＋a_n-5＋a_n-6 です。

　a₇＝a₄＋a₃＋a₂＋a₁＝3 で、以下、電卓を使っての計算を簡単にするために、n≧8 のときは、

　a_n＝a_n-3＋a_n-4＋a_n-5＋a_n-6 から a_n-1＝a_n-4＋a_n-5＋a_n-6＋a_n-7 を減じて、

　a_n－a_n-1＝a_n-3－a_n-7 、a_n＝a_n-1＋a_n-3－a_n-7 になります。

　a₈＝a₇＋a₅－a₁＝4 ，以下同様に、a₉＝8 ，a₁₀＝9 ，a₁₁＝12 ，a₁₂＝19 ，a₁₃＝24 ，a₁₄＝33 ，a₁₅＝48 ，

　a₁₆＝64 ，a₁₇＝88 ，a₁₈＝124 ，a₁₉＝169 ，a₂₀＝233 ，a₂₁＝324 ，a₂₂＝445 ，a₂₃＝614 ，a₂₄＝850 ，

　a₂₅＝1171 ，a₂₆＝1616 ，a₂₇＝2233 ，a₂₈＝3080 ，a₂₉＝4251 ，a₃₀＝5870 ，a₃₁＝8100 ，a₃₂＝11180 です。

.