全然わからないのでお願いします

１５段の階段があります
一段ずつ上がる方法と一段飛ばしで上がる方法を組み合わせる場合
階段を上りきるまでの組み合わせは全部で何通りあるでしょうか

計算式を書いていただけると助かります

No.2 ベストアンサー 回答者： alice_44 回答日時： 2011/01/29 22:30

学習参考書などによく載っている解法としては…

n 段を、その方法で上がる上がり方を a[n] 通りとします。
最後の一歩が一段である上がり方は a[n-1] 通り、
最後の一歩が一段飛ばしである上がり方は a[n-2] 通りなので、
a[n] = a[n-1] + a[n-2].
また、初期条件として、
a[1] = 1,　←「一歩１回」のみ
a[2] = 2.　←「一歩２回」と「一歩飛ばし１回」の２通り
以上で a[n] が決まります。
いわゆるフィボナッチ数列ですね。

漸化式を解いて一般項を求めることもできますが、
n = 15 程度なら、順に各項を計算して、
a[3] = 2 + 1 = 3,
a[4] = 3 + 2 = 5,
a[5] = 5 + 3 = 8,
a[6] = 8 + 5 = 13,
a[7] = 13 + 8 = 21,
a[8] = 21 + 13 = 34,
a[9] = 34 + 21 = 55,
a[10] = 55 + 34 = 89,
a[11] = 89 + 55 = 144,
a[12] = 144 + 89 = 233,
a[13] = 233 + 144 = 377,
a[14] = 377 + 233 = 610,
a[15] = 610 + 377 = 987.
としても一瞬でしょう。

この回答へのお礼

ありがとうございました。

お礼日時：2011/02/01 06:55

No.1 回答者： noname#157574 回答日時： 2011/01/29 21:35

1段上がる回数をm回，2段上がる回数をn回とおくと，(m，n)の組合せは

(15，0)，(13，1)，(11，2)，(9，3)，(7，4)，(5，5)，(3，6)，(1，7)の8通りある。
(15，0)のとき1通り
(13，1)のとき14C1＝14(通り)
(11，2)のとき13C2＝(13・12)/(2・1)＝78(通り)
(9，3)のとき12C3＝(12・11・10)/(3・2・1)＝220(通り)
(7，4)のとき11C4＝(11・10・9・8)/(4・3・2・1)＝330(通り)
(5，5)のとき10C5＝(10・9・8・7・6)/(5・4・3・2・1)＝252(通り)
(3，6)のとき９C6＝９C3＝(9・8・7)/(3・2・1)＝84(通り)
(1，7)のとき8C7＝8C1＝8(通り)
よって1＋14＋78＋220＋330＋252＋84＋8＝987(通り)

この回答へのお礼

解答ありがとうございます
ちょっと質問なのですが途中の計算式にでてくるcの意味がわかりません

教えていただけると助かります

お礼日時：2011/01/29 21:43