碁盤の目の道路を最短で進む経路の数は、「同じものを含む順列」として一発で計算できます。
なぜ経路と順列が対応するのか、その原理を理解すれば、通過点の指定や通行止めにも自在に対応できます。
碁盤の目状（格子状）の道路を、A地点からB地点まで最短で進むことを考えます。 ここで「最短」とは、遠回りしないことです。 つまり、目的地から離れる方向（左や下）には一切進みません。
たとえば、AからBまで右に4区画、上に3区画の距離があるとしましょう。 最短経路では、必ず右に4回、上に3回、合計7回の移動を行います。 どの経路を通っても「右4回・上3回」という内訳は変わりません。 違うのは右と上の順序だけです。
ここで、右に1区画進むことを「$\rightarrow$」、上に1区画進むことを「$\uparrow$」と記号で表してみましょう。 1つの最短経路は、たとえば次のような7文字の列に対応します。
$$\rightarrow \ \rightarrow \ \uparrow \ \rightarrow \ \uparrow \ \uparrow \ \rightarrow$$この文字列は「$\rightarrow$ が4個、$\uparrow$ が3個」の並べ方の1つです。 逆に、$\rightarrow$ 4個と $\uparrow$ 3個のどんな並べ方も、最短経路1つに対応します。 これこそが、最短経路問題の核心です。
右に $m$ 区画、上に $n$ 区画進む最短経路の数は、「$\rightarrow$ が $m$ 個、$\uparrow$ が $n$ 個」の同じものを含む順列の数と一致します。
なぜ一致するのでしょうか？ それは以下の2つの事実からです。
事実1：最短経路は必ず「右 $m$ 回、上 $n$ 回」の移動からなる（回数は固定）。
事実2：文字列と経路が1対1に対応する（異なる文字列は異なる経路を表す）。
つまり最短経路の数え上げは、「右」と「上」という2種類の文字の並べ替え問題に完全に帰着するのです。
右に $m$ 区画、上に $n$ 区画進む最短経路の総数：
$$\frac{(m+n)!}{m! \cdot n!} = {}_{m+n}C_m = {}_{m+n}C_n$$合計 $(m+n)$ 個の文字を一列に並べることを考えます。 もしすべての文字が異なれば、並べ方は $(m+n)!$ 通りです。
しかし実際は、$\rightarrow$ が $m$ 個あって互いに区別できません。 $\rightarrow$ 同士を入れ替えても同じ配列なので、$m!$ 通りの重複があります。 同様に $\uparrow$ も $n$ 個あるので $n!$ 通りの重複があります。
よって、異なる並べ方は $\dfrac{(m+n)!}{m! \cdot n!}$ 通りです。
これは ${}_{m+n}C_m$（$(m+n)$ 個の位置から $m$ 個を「$\rightarrow$ の位置」として選ぶ）とも一致します。
右に3区画、上に2区画の場合、最短経路の数は
$$\frac{5!}{3! \cdot 2!} = \frac{120}{6 \times 2} = 10 \text{ (通り)}$$これは ${}_{5}C_2 = 10$ とも一致します。5つの移動のうち「上」を置く2箇所を選べばよいのです。
✕ 誤：「最短経路は1本だけ（直線で結ぶ経路）では？」
○ 正：格子点上では、すべて右か上にしか進まない経路はどれも同じ距離（$(m+n)$ 区画分）です。 「最短」＝「遠回りしない」であり、「1本しかない」わけではありません。その「同じ距離の経路が何通りあるか」を数えるのがこの問題です。
✕ 誤：「右に3、上に2のとき ${}_{5}C_3$ と ${}_{5}C_2$ で答えが違うかも？」
○ 正：${}_{5}C_3 = {}_{5}C_2 = 10$ です。${}_{n}C_r = {}_{n}C_{n-r}$ が成り立つので、$m$ と $n$ のどちらを選んでも同じ答えです。 計算のしやすさでは、小さい方を下に書くのがコツです。
格子の各交差点に「そこに到達する最短経路の数」を書き込むと、パスカルの三角形が現れます。 各点の数は「左の点の数 ＋ 下の点の数」で求まります。 これは ${}_{n}C_r = {}_{n-1}C_{r-1} + {}_{n-1}C_r$ という組合せの漸化式そのものです。
この考え方は、大学のグラフ理論やコンピュータサイエンスの動的計画法（DP）の基礎です。 カーナビの最短経路探索も、「1歩前の結果を使って次を計算する」という本質は同じです。
「AからBまでの最短経路のうち、途中の点Cを必ず通るものは何通りか」という問題を考えましょう。 入試でも非常によく出題されるパターンです。
Cを必ず通るということは、経路を「AからC」と「CからB」の2区間に分けられるということです。 各区間はそれぞれ独立に最短経路を選べるので、積の法則が使えます。
点Cを必ず通る最短経路の数は：
$$(\text{A→Cの最短経路数}) \times (\text{C→Bの最短経路数})$$
なぜ「積」になるのか？ AからCまでの経路の選び方と、CからBまでの経路の選び方は互いに独立だからです。 AからCまでどの経路を選んでも、CからBへはすべての最短経路が選べます。これが積の法則の条件を満たしています。
右に5区画、上に4区画の格子で、A$(0,0)$からB$(5,4)$まで、途中の点C$(2,1)$を通る最短経路の数を求めましょう。
Step 1：A→Cの最短経路。右に2、上に1なので ${}_{3}C_1 = 3$ 通り。
Step 2：C→Bの最短経路。右に $5-2=3$、上に $4-1=3$ なので ${}_{6}C_3 = 20$ 通り。
Step 3：積の法則により、$3 \times 20 = 60$ 通り。
「CとDの両方を通る」場合は、CとDの順序に注意します。 最短経路ではCの方がAに近い位置にあるなら、必ずA→C→D→Bの順に通ります。 このとき：
$$(\text{A→Cの数}) \times (\text{C→Dの数}) \times (\text{D→Bの数})$$✕ 誤：「CとDの両方を通る」→「(A→Cの数) $\times$ (A→Dの数)」として、Aから各点への経路数をそれぞれ掛ける。
○ 正：経路はA→C→D→Bと一本につながるので、区間ごとに分割します。 「A→C」「C→D」「D→B」の3区間の経路数をそれぞれ求めて掛けます。
「A→Cの数」と「A→Dの数」を掛けるのは、2つの独立な経路を同時に考えていることになり、意味が違います。 1本の経路を区間に分割するのが正しい考え方です。
「CまたはDを通る」場合は、和の法則を使います。ただし、CもDも両方通る経路が重複するので、包除原理を適用します。
$$(\text{Cを通る数}) + (\text{Dを通る数}) - (\text{CもDも通る数})$$「AからBへの最短経路からランダムに1つ選ぶとき、Cを通る確率は？」── これは「Cを通る経路の数 $\div$ 全経路の数」です。 通過点指定の問題は、場合の数だけでなく、第7章の確率問題としても出題されます。
格子上のランダムウォーク（各交差点でランダムに右か上を選ぶ）は、統計力学やファイナンス理論（株価のランダムウォークモデル）の基礎になっています。
格子上に「通れない点（通行止め）」がある場合の最短経路を数える問題は、入試で特に好まれるパターンです。 解法の基本は余事象の考え方、つまり「全体から、ダメなものを引く」です。
特定の点Cを通らない最短経路の数は：
$$(\text{A→Bの全最短経路数}) - (\text{Cを通るA→Bの最短経路数})$$「Cを通る最短経路数」は、Section 2で学んだ方法で「$(\text{A→Cの数}) \times (\text{C→Bの数})$」と求められます。
数え上げで「〜でないもの」を直接数えるのが難しいときは、余事象を使います。
$$(\text{条件を満たす数}) = (\text{全体}) - (\text{条件を満たさない数})$$
最短経路問題では「通れない点を避ける経路」を直接数えるのは面倒ですが、「通る経路」は積の法則で簡単に出せます。 だから「全体 $-$ 通る」が有効なのです。
右に4区画、上に3区画の格子で、C$(2,1)$ を通らないA$(0,0)$→B$(4,3)$ の最短経路の数を求めましょう。
Step 1：全体（A→B）：右4上3で ${}_{7}C_3 = 35$ 通り。
Step 2：Cを通る経路：A→C（右2上1）$\times$ C→B（右2上2）$= {}_{3}C_1 \times {}_{4}C_2 = 3 \times 6 = 18$ 通り。
Step 3：Cを通らない：$35 - 18 = 17$ 通り。
通れない点が2つ（C, D）ある場合は、包除原理を使います。
$$(\text{全体}) - (\text{Cを通る}) - (\text{Dを通る}) + (\text{CもDも通る})$$「CもDも通る」を足し戻すのは、「Cを通る経路」を引くときに「CもDも通る経路」も引かれ、 「Dを通る経路」を引くときにも再び引かれているので、二重に引きすぎた分を補正するためです。
CとDの位置関係によっては、最短経路でCとDの両方を通ることが不可能な場合があります。
たとえば、C$(2,3)$、D$(3,1)$なら、CからDに行くには「右に1、下に2」進む必要があり、最短経路（上にしか進まない）では不可能です。 また、DからCに行くにも「左に1」が必要で不可能です。
○ 正：「CもDも通る」が0通りなら、式は単に $(\text{全体}) - (\text{Cを通る}) - (\text{Dを通る})$ となります。 2点の位置関係を図で確認してから計算に入りましょう。
通れないのが「点」ではなく「辺」や「領域」の場合は、格子の各交差点に「そこへの最短経路の数」を書き込む方法が有効です。 出発点Aの値を1とし、各点の値を「左の点の値 ＋ 下の点の値」で順に求めます。 通れない点や辺があれば、その部分の値を0として計算を続けます。
格子書き込み法は、コンピュータサイエンスの動的計画法（Dynamic Programming, DP）の典型例です。 DPとは、大きな問題を小さな部分問題に分割し、部分問題の結果を記憶しながら全体の答えを構成する手法です。
点 $(i, j)$ への経路数を $f(i,j)$ とすると、漸化式は $f(i,j) = f(i-1,j) + f(i,j-1)$（左と下から来る）。 この漸化式をプログラムで実装すれば、通行止めがどんなに複雑でも経路数を計算できます。
格子に「右上への対角線（斜めの道）」が一部加わった場合を考えます。 斜めの道を1回通ると、右に1かつ上に1の移動が「1手」で済むため、通常より1手少ない合計移動回数でBに到達できます。
この場合、3種類の移動「$\rightarrow$（右）」「$\uparrow$（上）」「$\nearrow$（右上）」が登場します。 ただし、$\nearrow$ が使えるのは斜めの道がある特定の場所だけなので、注意が必要です。
対角線を含む最短経路問題の基本方針は、場合分けです。
場合1：斜めの道を使わない → 通常の最短経路と同じ計算。
場合2：斜めの道を使う → 斜めの道の入口を必ず通るので、「A→入口」「斜めの道」「出口→B」の区間分割。
この2つの場合は排反（斜めを使うか使わないか）なので、和の法則で足し合わせます。
右に3、上に2の格子で、$(1,0)$ から $(2,1)$ への対角線の道が1本だけある場合を考えましょう。
場合1：斜めの道を使わない。A$(0,0)$→B$(3,2)$ の通常の最短経路数は ${}_{5}C_2 = 10$ 通り。
場合2：斜めの道を使う。斜めの道の入口 $(1,0)$ と出口 $(2,1)$ を経由する。
・A$(0,0)$→$(1,0)$：右1上0で $1$ 通り
・$(1,0)$→$(2,1)$：斜めの道で $1$ 通り
・$(2,1)$→B$(3,2)$：右1上1で ${}_{2}C_1 = 2$ 通り
・積の法則：$1 \times 1 \times 2 = 2$ 通り
ただし注意：場合1には、$(1,0)$→$(2,1)$ を斜めでなく「右＋上」で通る経路も含まれています。しかし場合1は「斜めを使わない」場合なので、$(1,0)$を通っていても斜め道を使わなければ場合1に含まれます。場合1と場合2は「斜めの道を使うか否か」で排反です。
合計：$10 + 2 = 12$ 通り。
✕ 誤：「右2回、上1回、斜め1回の順列 $= \frac{4!}{2! \cdot 1! \cdot 1!} = 12$」
○ 正：この計算がたまたま正解と一致する場合もありますが、一般には間違いです。 斜めの道は特定の場所にしか存在しないので、「斜め」を文字列の任意の位置に自由に置くことはできません。
一括処理が正しいのは、すべての格子点間に斜めの道がある場合のみです。 実際の問題では斜めの道は一部にしかないので、「使う/使わない」の場合分けが安全な方法です。
最短経路問題の各パターンを整理しましょう。
| パターン | 問題の特徴 | 解法のポイント |
|---|---|---|
| A：基本 | 制約なしのA→B | ${}_{m+n}C_m$（同じものを含む順列） |
| B：通過点指定 | 途中の点を必ず通る | 区間分割 → 各区間の経路数の積 |
| C：通れない点 | 特定の点を通れない | 全体 $-$ その点を通る経路数 |
| D：通れない領域 | 区画が通行止め | 格子書き込み法（各点への経路数を順に計算） |
| E：対角線あり | 斜めの道がある | 「斜めを使う/使わない」で場合分け |
| F：複合 | B〜Eの組合せ | 上記を組み合わせて段階的に処理 |
どのパターンも、根底にある原理は同じです： 「最短経路 ＝ 同じものを含む順列」。 この対応関係を理解していれば、条件がどう変わっても、積の法則・余事象・場合分けを組み合わせて対応できます。
Q1. 右に4区画、上に2区画の格子で、A（左下）からB（右上）への最短経路は何通りですか？
Q2. 最短経路の数え方が「同じものを含む順列」と一致する理由を一言で説明してください。
Q3. 右に3、上に3の格子で、点C（右2、上1の位置）を必ず通る最短経路は何通りですか？
Q4. 上のQ3の設定で、点Cを通らない最短経路は何通りですか？
Q5. 対角線を含む経路の問題で、「3種類の文字の順列」として一括処理してはいけないのはなぜですか？
この記事で学んだ内容を、入試形式の問題で確認しましょう。
格子状の道路において、A地点からB地点に最短経路で行く道順は何通りあるか。ただし、AからBまで横に5区画、縦に3区画とする。
$56$ 通り
方針：右5回・上3回の「同じものを含む順列」として求める。
最短経路は右に5回、上に3回の合計8回の移動からなり、その順序で経路が決まる。
$${}_{8}C_3 = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 \text{ (通り)}$$
横に4区画、縦に3区画の格子状の道路がある。A$(0,0)$からB$(4,3)$に最短経路で行くとき、次の各場合の道順は何通りあるか。
(1) 途中でC$(2,1)$を通る場合
(2) C$(2,1)$を通らない場合
(1) $18$ 通り (2) $17$ 通り
方針：(1)は区間分割して積の法則。(2)は全体からCを通る経路を引く。
(1) A→C：右2上1で ${}_{3}C_1 = 3$ 通り。C→B：右2上2で ${}_{4}C_2 = 6$ 通り。
積の法則：$3 \times 6 = 18$ 通り
(2) A→Bの全経路数：${}_{7}C_3 = 35$ 通り。
Cを通らない：$35 - 18 = 17$ 通り
横に5区画、縦に4区画の格子状の道路がある。A$(0,0)$からB$(5,4)$に最短経路で行くとき、途中でC$(2,1)$とD$(4,3)$の両方を通る道順は何通りあるか。
$36$ 通り
方針：C$(2,1)$はD$(4,3)$より左下にあるので、最短経路ではA→C→D→Bの順に通る。3区間に分割して積の法則を使う。
・A$(0,0)$→C$(2,1)$：右2上1で ${}_{3}C_1 = 3$ 通り
・C$(2,1)$→D$(4,3)$：右 $4-2=2$、上 $3-1=2$ で ${}_{4}C_2 = 6$ 通り
・D$(4,3)$→B$(5,4)$：右 $5-4=1$、上 $4-3=1$ で ${}_{2}C_1 = 2$ 通り
積の法則：$3 \times 6 \times 2 = 36$ 通り
横に4区画、縦に4区画の格子状の道路がある。A$(0,0)$からB$(4,4)$に最短経路で行くとき、C$(2,2)$を通らない道順は何通りあるか。
$34$ 通り
方針：余事象を使う。全体からCを通る経路を引く。
全体：A$(0,0)$→B$(4,4)$の最短経路数は ${}_{8}C_4 = 70$ 通り。
Cを通る経路：A$(0,0)$→C$(2,2)$の経路数は ${}_{4}C_2 = 6$ 通り。C$(2,2)$→B$(4,4)$の経路数も ${}_{4}C_2 = 6$ 通り。
積の法則：$6 \times 6 = 36$ 通り。
Cを通らない：$70 - 36 = 34$ 通り。
※ C$(2,2)$は格子のちょうど中央にあり、多くの経路がここを通ることがわかります。全経路70のうち36（半分以上）がC経由です。