最短経路の数え方（同じものを含む順列）｜数A場合の数

最短経路の問題は、順列の問題に完全に翻訳できます。

右に進むを R、上に進むを U と書けば、経路は文字の並べ方

この見方をすれば、公式がそのまま使えます。

基本：右4・上3の格子

碁盤の目状の道を、A地点から東へ4区画・北へ3区画離れたB地点まで、最短で行く方法は何通りですか。

最短で行くには右に4回、上に3回進みます。合計7回。

その順番を決めれば経路が決まるので、RRRRUUU の並べ方の数が答えです。

35通りです。

【検算1】7か所のうちUを入れる3か所を選ぶと考えても同じです。

一致 ○

【検算2】書き込み法でも確かめます。各交点に「左の数＋下の数」を書いていきます。

3段目	1	4	10	20	35
2段目	1	3	6	10	15
1段目	1	2	3	4	5
0段目	1	1	1	1	1

右上が35 ○　公式と一致します。

必ず通る点があるとき

Aから東へ2・北へ1の地点Pを必ず通ってBへ行く方法は何通りですか。

2つに分けてかけ算します。

18通りです。

【検算】PからBは右2・上2で合計4回。 ○

途中の点で区切ってかける——これが基本の型です。

通れない点があるとき

東へ2・北へ2の地点Qが工事中で通れません。AからBへ行く方法は何通りですか。

全体から、Qを通る経路を引きます。

だから

17通りです。

【検算1】Qを通る18通りと通らない17通りを足すと

全体に戻ります ○

【検算2】書き込み法でも確かめられます。Qのところに0を書いて、そこから先へ数を伝えなければ、右上に17が出ます ○

通れない「道」があるとき

点(2,1)から点(2,2)へ向かう道が通行止めです。AからBへは何通りですか。

その道を通る経路の数を数えて引きます。

途中の1本道は1通りなので

26通りです。

【検算】点が通れない場合（18通りを引く）より、引く数が少ないのは自然です。道1本のほうが制限がゆるいからです ○

3つの型のまとめ

条件	やり方
制限なし
必ず通る点	区切ってかける
通れない点・道	全体から引く

「通る」はかけ算、「通れない」は引き算——この対応で整理できます。

学校の授業では、なぜここが飛ばされやすいのか

1. 「同じものを含む順列」との対応が示されにくいから

最短経路はRとUの並べ方そのものです。この翻訳ができれば、新しい公式は要りません。

ところが順列は文字や数の並べ方で導入されます。図形の問題と結びつける場面が作られにくいのです。

2. 書き込み法が「別の方法」に見えるから

交点に数を書いていく方法は、実はパスカルの三角形そのものです。二項係数と同じ数が並びます。

ところが公式と書き込み法が別々に紹介されると、同じものだと気づきにくい。両方を並べて確認する価値があります。

3. 「通れない」型は余事象の考え方だから

全体から引く——これは余事象の発想です。確率の単元でよく使いますが、場合の数の段階で意識される機会は多くありません。

結果として「引けばいい」と気づかず、通れる経路を直接数えようとして詰まります。

【検算】3つの方法

1. 公式と書き込み法の両方でやる

最も確実です。まったく別の手順で同じ数が出ます。

【検算】どちらも35 ○

2. 通る場合と通らない場合を足す

全体に戻るはずです。

【検算】 ○

3. 小さい格子で全部書き出す

右2・上2なら6通り——実際に書き出せます。

【検算】 ○

よくあるミス

ミス1：階乗で割り忘れる

同じ文字は区別しないので割ります。

ミス2：区画数と点の数を取り違える

進む回数を数えます。

ミス3：必ず通る点で足してしまう

かけ算です。

ミス4：通れない点の経路を引き忘れる

全体から引きます。

ミス5：点と道の禁止を同じに扱う

引く数が違います。

ミス6：書き込み法で足す向きを間違える

左と下の和です。

練習問題

1. 右4・上3の格子で、最短経路の総数を求めなさい。
2. 1を書き込み法でも確かめなさい。
3. 点(2,1)を必ず通る経路の数を求めなさい。
4. 点(2,2)を通れないときの経路の数を求めなさい。
5. 4で、通る場合と通らない場合の和を確かめなさい。
6. (2,1)から(2,2)への道が通れないときの経路の数を求めなさい。
7. 右2・上2の格子の経路数を求めなさい。

解答

1. 35通り
2. 書き込み法でも35 ○
3. 18通り
4. 17通り
5. ○
6. 26通り
7. 6通り

まとめ

• 最短経路はRとUの並べ方
• 公式は
• 必ず通る点は区切ってかける
• 通れない点・道は全体から引く
• 書き込み法は左と下の和（パスカルの三角形）
• 検算は2通りの方法／通る＋通らない／小さい格子で全書き出し

最短経路の問題は、図形に見えて実は並べ方の問題です。「見た目が違うだけで、やっていることは同じ」——この気づきが、場合の数を得意にする最短経路でもあります。