順に足し上げて数える場合の数

階段ののぼり方（1 段か 2 段ずつ、使えない段がある場合をふくむ）や、通れない点がある道順の数を、手前までの数を順に足し上げて求められる

前提

道順の数（算数場合の数）

この技能までの道筋（3 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
道順の数（算数場合の数）

説明

階段を 1 段ずつか 2 段ずつのぼるときののぼり方の数を、下の段から順に「その段まで何通りで来られるか」を求めて足し上げることで数えられるようになります。使えない段（ふんではいけない段）があっても、同じ方法でそのまま数えられます。道順の数を交差点ごとに書きこんでいく方法と同じ考え方で、樹形図をかくと枝が多くなりすぎる場合に役立ちます。

なぜそうしてよいのか

たとえば 1 段か 2 段ずつのぼるとき、5 段目に着く直前にいる場所は「4 段目」か「3 段目」のどちらかです。4 段目から 1 段のぼって 5 段目に着くのぼり方と、3 段目から 2 段のぼって 5 段目に着くのぼり方は、最後の一歩がちがうので重なりません。また、この 2 つ以外の来方はありません。だから和の法則により、(5 段目までの数) = (4 段目までの数) + (3 段目までの数) となります。これは碁盤の目の道順で「ある交差点までの行き方の数 = 左どなりまでの数 + 下どなりまでの数」とした考え方とまったく同じです。

使えない段があるときは、その段に立つことができないので、その段までの数を $0$ とします。すると、その段から次へ進むのぼり方は数に入らず、使えない段をとびこえるのぼり方だけが自然に数えられます。通れない交差点に $0$ を書きこんだのと同じです。

スタートの地面（0 段目）にいる方法は「まだ何もしない」の 1 通りなので、0 段目を $1$ として始めます。

手順

0 段目（地面）を $1$ 通りとし、使えない段にはあらかじめ $0$ と書いておく
1 段目は 0 段目から 1 段のぼるしかないので、1 段目の数は 0 段目の数と同じ（1 段目が使えない段なら $0$ ）
2 段目から上は、下から順に「1 つ下の段の数 + 2 つ下の段の数」を計算して書く（使えない段は計算せず $0$ のまま）
目的の段まで足し上げたら、そこに書いた数が答え

例題

8 段の階段を、1 回に 1 段か 2 段ずつのぼります。ただし、4 段目はこわれているのでふむことができません。8 段目までのぼるのぼり方は何通りあるか求めよ。

例題の解答

手順 1: 0 段目を $1$ 、使えない 4 段目を $0$ とします。
手順 2: 1 段目は 0 段目から来るしかないので $1$ 通り。
手順 3: 下から順に、1 つ下と 2 つ下の数を足します。
2 段目: $1 + 1 = 2$
3 段目: $2 + 1 = 3$
4 段目: 使えないので $0$
5 段目: $0 + 3 = 3$ （4 段目からは来られず、3 段目から 2 段のぼる来方だけ）
6 段目: $3 + 0 = 3$
7 段目: $3 + 3 = 6$
8 段目: $6 + 3 = 9$
手順 4: 8 段目の数は $9$ なので、のぼり方は 9 通り。
（確かめ: 4 段目をふまないには 3 段目から 5 段目へ 2 段のぼるしかありません。3 段目までが 3 通り、5 段目から 8 段目までの 3 段が 3 通りなので $3 \times 3 = 9$ で一致します。）

答え: $9$

よくある誤り

0 段目を数に入れず、1 段目と 2 段目をともに $1$ として始めてしまう誤り。2 段目へは「1 段+1 段」と「2 段」の 2 通りあるので、正しくは 0 段目を $1$ として 2 段目は $1 + 1 = 2$ 。
使えない段を飛ばして計算せず、その段にも「1 つ下 + 2 つ下」を書いてしまう誤り。4 段目が使えないのに 4 段目を $3 + 2 = 5$ とすると 5 段目が $5 + 3 = 8$ と大きくなりすぎる。正しくは 4 段目は $0$ で、5 段目は $0 + 3 = 3$ 。
使えない段の数を「書かない（空欄）」にして、次の段で 1 つ下だけ足したり、さらに下の段を足したりしてしまう誤り。正しくは使えない段は $0$ として、どの段も必ず「1 つ下 + 2 つ下」だけを足す（5 段目は $0 + 3$ 、6 段目は $3 + 0$ ）。
足すのではなくかけてしまう誤り。2 つの来方（1 つ下からと 2 つ下から）は最後の一歩がちがって重ならないので和の法則で、3 段目は $2 \times 1 = 2$ ではなく $2 + 1 = 3$ 。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（教科書の例題レベル）
6 段ある階段を、1 回に 1 段または 2 段ずつのぼります。下の床から 6 段目までのぼるのぼり方は、全部で何通りありますか。ただし、1 段ずつと 2 段ずつを混ぜてもよく、のぼる順番がちがうものは別ののぼり方として数えます。

この技能を使う問題

難易度 4（公立高校入試の難問・私立高校入試レベル）
$12$ 段ある階段を、 $0$ 段目（いちばん下の床）から $12$ 段目（いちばん上）までのぼる。1 回に $1$ 段または $2$ 段のぼることができるが、 $5$ 段目と $9$ 段目はこわれているので、そこに足をつくことはできない。 $12$ 段目にちょうど着くようなのぼり方は全部で何通りあるか求めよ。ただし、のぼり方は、1 回ごとに $1$ 段のぼるか $2$ 段のぼるかの並び方で区別する。