数学A / 場合の数

通行止めのある最短経路

★★★ 応用最短経路余事象

問題

横に4区画、縦に3区画の格子状の道路がある。左下の A から右上の B まで、右または上にだけ進んで最短で行く。ただし、A から右へ2区画・上へ1区画進んだ交差点 P から、その右どなりの交差点 Q(P から右へ1区画)へ向かう道が工事中で通れない。この工事区間を通らない最短経路は何通りあるか。

ヒントを見る

『 $P \to Q$ の道が通れない』は、全経路から『 $P \to Q$ を通ってしまう経路』を引く。その経路数は $A \to P$ と $Q \to B$ の経路数の積。

解答・解説

方針

「ある道(辺)を通れない」問題は、裏返して数えるのが速い。

全体の最短経路から、「その工事区間を通ってしまう経路」を引けばよい。

工事区間 P→Q を通る経路は、P で必ずこの1歩を踏むので、A→P の経路と Q→B の経路を自由に組み合わせたものすべてだ。このかけ算を全体から引く。

解答

⓪ 発想 — どう考え始めるか。 通れない辺がある問題だ。

その辺を避ける経路を正面から数えると、回り道の場合分けが増える。逆に、全体から「その辺を通る経路」を引くほうが速い。

その辺を通る経路は、 $P \to Q$ の $1$ 歩を必ず踏む。だから前半 $A \to P$ と後半 $Q \to B$ に切れて、かけ算で数えられる。

禁止条件を、補集合と分割のかけ算で処理する合わせ技だ。

A→B の最短経路。工事中の区間 P→Q(赤破線)は通れない

公式特定の点を通る経路 = (前半の経路数) × (後半の経路数)

全経路数: A から B へは右4区画・上3区画なので

$\frac{7 !}{4 ! \times 3 !} = 35 (通り)$

工事区間 P→Q を通る経路: この道を通る経路は、必ず「A→P と進み、P→Q の1歩を踏み、Q→B と進む」形になる。P は A から右2・上1、Q は右3・上1の場所だ。

A → P: 右2区画・上1区画なので $\frac{3 !}{2 ! 1 !} = 3$ 通り
Q → B: 残り右1区画・上2区画なので $\frac{3 !}{1 ! 2 !} = 3$ 通り

P→Q の1歩は決まっているので、前半3通りと後半3通りの組合せで $3 \times 3 = 9$ 通りがこの工事区間を通る。

工事区間を通らない経路: 全体から引いて

$35 - 9 = 26 (通り)$

まとめ:「特定の道を通らない」を最初から数えると、その道を避ける回り道を場合分けすることになって大変だ。『通ってしまう経路』のほうが(1歩が決まっているぶん)数えやすいので、裏返して引くのが得だ。

発展 — 一歩先へ。 別解では、全経路を「列 $x = 2$ から $x = 3$ へどの高さで移るか」で分類して足した。この足し算は、二項係数の積の和 $(2 2) (1 4) + (2 3) (1 3) + (2 4) (1 2) + (2 5) (1 1)$ になり、値は全経路 $(3 7) = 35$ に等しい。

二項係数の積を足すと $1$ つの二項係数にまとまる、というヴァンデルモンド型の恒等式(畳み込み)の一例だ。経路を途中の $1$ か所で切って前後に分けるたびに、この形が現れる。

禁止された $1$ 本の辺は、この和からちょうど $1$ 項( $(2 3) (1 3) = 9$ )を落とすことに当たる。数え上げを和の形にしておくと、禁止や条件を「項を消す」操作として扱える。

答

26通り

別解

別解 — 列の境目を「どの高さで越えるか」で数える(直接足し上げるルート)。 引き算を使わず、通ってよい経路を正面から足し上げる。

どの経路も、 $x = 2$ の列から $x = 3$ の列へ移る右向きの $1$ 歩を、ちょうど一度だけ踏む。その $1$ 歩の高さ $y$ は $0, 1, 2, 3$ のどれかだ。

工事中なのは高さ $y = 1$ の $1$ 歩、すなわち $P \to Q$ 。だから $y = 0, 2, 3$ で越える経路だけを数えればよい。

高さ $y$ で越える経路の数は、 $A \to (2, y)$ と $(3, y) \to B$ の積になる。

$y = 0$ : $(2 2) \times (1 4) = 1 \times 4 = 4$
$y = 2$ : $(2 4) \times (1 2) = 6 \times 2 = 12$
$y = 3$ : $(2 5) \times (1 1) = 10 \times 1 = 10$

足すと

$4 + 12 + 10 = 26.$

全体から引く本解と同じ $26$ 通りに、こんどは足し算だけでたどり着く。

ポイント

「特定の道(辺)を通れない」→ 全体 − その道を通る経路(裏返して数える)
辺 P→Q を通る経路 = (A→P) × (Q→B)(その1歩は決まっている)
避けて数える(正面)より、通る場合を引くほうが速い

よくある間違い

工事を「点 $P$ を通らない」と読み違える(通れないのは辺で、点 $P$ 自体は通ってよい)。
$A \to P$ (右 $2$ ・上 $1$ )や $Q \to B$ (右 $1$ ・上 $2$ )の区画数を数え違えて経路数を誤る。
禁止された辺を避ける回り道を正面から場合分けし始め、場合が増えて収拾がつかなくなる。