碁盤の目状の道路網の最短経路は何通り？ ~ 数学について考えてみる

「上図のように碁盤の目状の道路網の左下のスタート地点から右上のゴール地点へ最短で進むことができる経路は何通りあるか？」

　このような問題はどのように解けばよいでしょうか？

　問題の道路網の場合、交差点から次の交差点までの移動を1回とするとスタートからゴールまでの最短経路はどれも上へ4回、右へ5回進むことになります。

したがって、この問題の場合「最短経路が何通りあるか？」は「上へ4回、右へ5回の移動の順番を組み替えていくつの道順をつくることができるか？」ということになります。

　1から9までの番号が割り振られた丸と上矢印4個、右矢印5個を用意します。上矢印は上への移動、右矢印は右への移動を表します。
9つの丸の中に上矢印か右矢印を入れてすべての丸を埋めることで最短経路が完成します。

まず、上矢印から入れていきます。9つの丸から上矢印を入れる丸を4つを選ぶので、その組み合わせの数は

${_9C_4}=\frac{9!}{4! 5!}=126\ (\text{通り})$

となります。

次に右矢印を入れます。空いている丸の数は5つ、右矢印の数も5つなので組み合わせの数は

${_5C_5}=\frac{5!}{5! 0!}=1\ (\text{通り})$

となります。

したがって、最短経路は

$\begin{align*}{_9C_4}\cdot{_5C_5}&=\frac{9!}{4!5!}\cdot\frac{5!}{5!0!}\\[0.5em] &=\frac{9!}{4!5!}\quad(={_9C_4})\\[0.5em] &=126\ (\text{通り})\end{align*}$

となります。

このことから最短経路が何通りあるのかを求めるには

$\begin{align*}{_p C_q}&={_p C_r}=\frac{p!}{q!r!}\\[1em] &\begin{aligned}&p:移動の合計回数\\[0.3em]&q:上方向への移動回数\\[0.3em]&r:右方向への移動回数\end{aligned}\end{align*}$

で計算すれば良いことがわかります。

　次は条件付きの場合を考えてみます。

交差点

　同じ道路網で上図の位置にある交差点

$\text{A}$ を必ず通る場合の最短経路は何通りかを考えます。

最短経路となるのはスタートから交差点

$\text{A}$ までの赤の部分と交差点

$\text{A}$ からゴールまでの青の部分を通るものだけです。
なので、まずは赤と青の部分それぞれ最短経路は何通りあるのかを計算します。

・赤の部分

最短経路はどれも上へ2回、右へ2回の移動なので

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

・青の部分

最短経路はどれも上へ2回、右へ3回の移動なので

${_5C_2}=\frac{5!}{2! 3!}=10(\text{通り})$

赤の部分の最短経路

$6$ 通りの1つ1つにはそれぞれ青の部分の最短経路

$10$ 通りの通り方があるので、交差点

$\text{A}$ を通る最短経路は

$6×10=60\ (\text{通り})$

となります。

　逆に交差点 $\text{A}$ を通らない最短経路の数は、通る場所に制限がない場合の最短経路の数から交差点 $\text{A}$ を通る場合の最短経路の数を引くことで求められます。
上で求めたように制限がない場合の最短経路は $126$ 通り、交差点 $\text{A}$ を通る場合の最短経路は $60$ 通りなので