[答595] 17段の階段の上がり方
'
[答595] 17段の階段の上がり方
階段を上がるとき、1段上がるか2段上がるかを組み合わせて 17段の階段を上がる方法は何通り?
ただし、連続して2段上がれないものとします。
[解答1]
2段上がる回数は 0,1,2,3,4,5,6 回のいずれかです。
例えば、2段上がる回数が4回の場合、1段上がる回数は9回で、
|
|
|
|
|
|
|
|
|
| のうちの、
縦線の所4ヶ所に
を入れれば上がり方を示せるから、その総数は、10C4 になります。
従って、問題の総数は、
18C0+16C1+14C2+12C3+10C4+8C5+6C6=1+16+91+220+210+56+1=595 になります。
[解答2]
2段上がる回数は 0,1,2,3,4,5,6 回のいずれかです。
例えば、2段上がる回数が4回の場合、1段上がる回数は9回で、
|
|
|
|
| のうちの、
5本の縦線の所のうち重複可で6ヶ所に
を入れれば上がり方を示せるから、その総数は、5H6 になります。
従って、問題の総数は、
1H18+2H15+3H12+4H9+5H6+6H3+7H0=1+16+91+220+210+56+1=595 になります。
[解答3]
n段の階段を上がる方法を an 通りとします。
17段の階段を上がるとき、最後に1段上がる場合は a16 通り、
最後に2段上がる場合は、その前は1段上がることになり a14 通りだから、
a17=a16+a14 で、一般に、an=an-1+an-3 が成り立ちます。
a1=1,a2=2,a3=3 だから、 a4=a3+a1=4 ,a5=a4+a2=6 , a6=a5+a3=9 ,a7=a6+a4=13 ,
a8=a7+a5=19 , a9=a8+a6=28 ,a10=a9+a7=41 ,a11=a10+a8=60 , a12=a11+a9=88 ,
a13=a12+a10=129 ,a14=a13+a11=189 , a15=a14+a12=277 ,a16=a15+a13=406 ,
a17=a16+a14=595 になります。
☆ 漸化式 an=pan-1+qan-2+ran-3 について、
特性方程式 x3=px2+qx+r が異なる解α,β,γをもつとき、
定数 A,B,C を使って、an=Aαn+Bβn+Cγn と表されることが知られています。
本問では、K=3√{(29-3√93)/2},L=3√{(29-3√93)/2} とすれば、
特性方程式 x3=x2+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 になり、
これを α,β,γ として、an=Aαn+Bβn+Cγn 、
ここで、a1=1,a2=2,a3=3 となるように、定数 A,B,C を決めれば、一般式を得ることはできますが、
計算は困難です。
.