FC2ブログ

Welcome to my blog

[答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 です。

.

スポンサーサイト



Comments 8

There are no comments yet.
ひとりしずか  
No title

我が家のカノコユリ6輪目が開花、タカサゴユリはまだ蕾
ユリは清楚で優雅でおくゆかしい感じが好きです

ニリンソウ  
No title

おはようございます。
小雨の朝ですよ、賑やかで忙しかった昨日が嘘のように
静かです。

タカサゴユリが目立ってきました
庭に来たのは抜いてるんだけどよそで見ると姿がいい花です。

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!をありがとうございます。
私は今年はカノコユリと縁がなく、見ていません。
タカサゴユリが咲くと、今年のユリの見納めだと思います。

ヤドカリ  
No title

ニリンソウさん、早速のコメントとナイス!をありがとうございます。
お盆になって、こちらも少し朝晩の気温が少し下がってきました。
このタカサゴユリは、檀那寺に咲いていたものです。

アキチャン  
No title

おはようございます。
清楚…この言葉は白い百合のお花が一番似合うような気がします(o^-^o)

ヤドカリ  
No title

アキチャンさん、コメントとナイス!をありがとうございます。
白百合は百合のなかでも清楚な感じがします。
もちろん、大きな花は立派ですね。

スモークマン  
No title

グーテンアーベント ^^
最初数えかけたのですが…断念 ^^;
漸化式ってのはとっても便利だのに...
この手はどうも苦手だなぁ…Orz...

ヤドカリ  
No title

スモークマンさん、コメントをありがとうございます。
漸化式は慣れるしかないです。
簡単な場合からどうすればよいのかを考えることになります。