数学A / 場合の数

指定の点を通る最短経路

★★ 標準最短経路同じものを含む順列

問題

横に4区画、縦に3区画の格子状の道路がある。左下の A から右上の B まで、右または上にだけ進んで最短で行く。途中の交差点 P(A から右へ2区画、上へ1区画進んだ点)を必ず通る経路は何通りあるか。

ヒントを見る

『 $P$ を必ず通る』は、経路を $A \to P$ と $P \to B$ の2区間に分けて考える。各区間の最短経路数を求めてかける。

解答・解説

「指定の点 P を通る」経路は、A→P と P→B の2つに分けて考える。

それぞれの区間の経路数を求めて、かけ合わせればよい。P で必ず1回通るので、前半の道と後半の道を自由に組み合わせられるからだ。

各区間は、ふつうの最短経路(同じものを含む順列)として数える。

⓪ 発想 — どう考え始めるか。 「指定の点 P を通る」経路は、A→P と P→B の2つの区間に分けて考える。

どの経路も P を必ず1回だけ通るから、前半の道と後半の道は自由に組み合わせられる。だから区間ごとの経路数の掛け算になる。

各区間は、ふつうの最短経路として数える。右への移動と上への移動の並べ方、つまり同じものを含む順列だ。

A から B への最短経路で、点 P(右2・上1)を通る

P を通る経路は「A から P へ行き、続けて P から B へ行く」経路だ。だから2区間の経路数をかけ合わせて求める。

A → P: 右へ2区画、上へ1区画進むので

$\frac{3 !}{2 ! \times 1 !} = 3 (通り)$

P → B: 残りは右へ2区画、上へ2区画進むので

$\frac{4 !}{2 ! \times 2 !} = 6 (通り)$

前半3通りのそれぞれに対して後半6通りが選べるので、かけ算して

$3 \times 6 = 18 (通り)$

まとめ:「点を通る」をかけ算に分けられるのは、P で必ず1回通り、前半と後半を別々に選べるからだ。逆に「点 P を通らない」経路がほしいなら、全経路 $\frac{7 !}{4 ! 3 !} = 35$ からこの18を引いて17通り、と裏返して求められる。

発展 — 一歩先へ。 全経路は $\frac{7 !}{4 ! 3 !} = 35$ 通りで、P を通るのはそのうち $18$ 通り。この比 $\frac{18}{35}$ は、「でたらめに最短経路を選んだとき P を通る確率」として、確率の単元でそのまま再登場する。

書き込み法の数の並びはパスカルの三角形で、組合せの数 $_{n} C_{k}$ の足し算の関係( $_{n} C_{k} =_{n - 1} C_{k - 1} +_{n - 1} C_{k}$ )を目で見ていることになる。

答

18通り

図に数を書き込む「足し算ルート」も、確実で分かりやすい。

各交差点に「A からそこまで行く経路の数」を書き込んでいく。どの交差点へも、左か下からしか来られないので、「左の数+下の数」を書けばよい。

A の行(下端)と列(左端)はすべて $1$ 。あとは足し算を繰り返すだけで、P には $3$ が入る。

P を通る経路だけを数えたいので、次は P を新しい出発点( $P$ に $3$ を置いたまま)にして、同じ足し算を B まで続ける。B に入る数が答えの $18$ になる。

計算式を立てずに機械的な足し算だけで進むので、途中に通行止めや複数の指定点がある複雑な問題ほど、この書き込み法が強い。書き込まれる数の並びは、実はパスカルの三角形そのものだ。