[答1118] 階段を昇る場合の数
'
[答1118] 階段を昇る場合の数
階段を1歩で1段昇ることを「1段昇り」、1歩で2段昇ることを「2段昇り」と言うことにします。
1段昇りの直前か直後は2段昇り、2段昇りの直前か直後は1段昇りになるように、
32段の階段を昇る方法は何通り?
なお、「直前か直後」の意味は、最初は「直前」がないので「直後」、最後は「直後」がないので「直前」、
最初と最後以外は「直前」「直後」の片方でも両方でも良いものとします。
[解答]
昇り始めも最後も 1+2 または 2+1 で、途中に 1+1+1 も 2+2+2 もない昇り方になります。
n段の階段を昇る方法は an 通り、そのうち、
最初昇り始めが 1+2 あるものを bn 通り、 2+1 あるものを cn 通りとします。
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 ,
a1=a2=0 ,a3=2 ,a4=a5=1 ,a6=4 です。
n≧7 として、
n段の階段を昇る方法のうち、1+2 で始まるものは、次に 1+2 が現れる前は、
1+2 ,1+2+1 ,1+2+2 ,1+2+2+1 ですので、bn=bn-3+bn-4+bn-5+bn-6 ……(1) 、
n段の階段を昇る方法のうち、2+1 で始まるものは、次に 1+2 が現れる前は、
2+1 ,2+1+1 ,2+1+2 ,2+1+1+2 ですので、cn=cn-3+cn-4+cn-5+cn-6 ……(2) 、
an=bn+cn だから、(1)+(2) より、an=an-3+an-4+an-5+an-6 です。
a7=a4+a3+a2+a1=3 で、以下、電卓を使っての計算を簡単にするために、n≧8 のときは、
an=an-3+an-4+an-5+an-6 から an-1=an-4+an-5+an-6+an-7 を減じて、
an-an-1=an-3-an-7 、an=an-1+an-3-an-7 になります。
a8=a7+a5-a1=4 ,以下同様に、a9=8 ,a10=9 ,a11=12 ,a12=19 ,a13=24 ,a14=33 ,a15=48 ,
a16=64 ,a17=88 ,a18=124 ,a19=169 ,a20=233 ,a21=324 ,a22=445 ,a23=614 ,a24=850 ,
a25=1171 ,a26=1616 ,a27=2233 ,a28=3080 ,a29=4251 ,a30=5870 ,a31=8100 ,a32=11180 です。
.