880
30 確率 ⑩0
題30
★★☆ 15分
1歩で1段または2段のいずれかで階段を昇るとき1歩で2段昇
ることは連続しないものとする。 15段の階段を昇る昇り方は何通り
あるか。
(京大・理系・07)
0
(理解
試行のヒント①
1段昇りでも2段昇りでも1歩進むと「“階段の一番
下の段”という状態にリセットされる」と見ることができるので,再
帰的な構造です。n段の昇り方を an 通りとして漸化式を立てましょ
う。
・・・(*) の条件がなけ
「1歩で2段昇ることは連続しないものとする」
れば有名問題なので,一度くらいやった経験があるのではないでしょう
か? まずはこれを考えてみましょう。
試行のヒント② 再帰的な構造をもつ問題の場合,最初の操作で場合
分けするか,最後の操作で場合分けします。最初の操作を「1段昇
り」と「2段昇り」で場合分けしてみてください。
ように
遷移的な構造をもつ問題で漸化式を立てるときは、 28 29でやった
遷移的な構造をもつ
問題の漸化式の立て方
n番目の状態で場合分けをして,
n+1番目の状態との関係を考える
ということになりますが、 再帰的な構造をもつ問題では, 「n番目の状態
で場合分け」が難しいことが多いです。 このようなときは,
確率 ⑩ 195