碁盤の目状の道路網の最短経路は何通り？(2)

図1　道路網の最短経路

「図1のような道路網のスタートからゴールまでの最短経路は何通りあるか？」

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

図2　道路網の補完

　まずは碁盤の目のようになるように図2のように線を書き足します。
補完された交差点を交差点$\text{A}$、道路を$\text{B}$地点とします。すると、問題文を「$\text{A}$と$\text{B}$どちらも通らない」場合の最短経路は何通りか？というように解釈することができます。

　ここで、「$\text{A}$と$\text{B}$どちらも通らない」という条件の否定について考えます。
「$\text{A}$と$\text{B}$どちらも通らない」すなわち「$\text{A}$を通らずかつ$\text{B}$を通らない」の否定は「$\text{A}$を通るまたは$\text{B}$を通る」です。これをベン図で表すと以下の図3のようになります。

図3　「$\text{A}$を通るまたは$\text{B}$を通る」のベン図

「$\text{A}$を通る」は左の楕円部分、「$\text{B}$を通る」は右の楕円部分です。2つの楕円が重なった緑の部分は「$\text{A}$、$\text{B}$両方を通る」となります。
そして「$\text{A}$を通る、または$\text{B}$を通る」は赤と緑、青をあわせたものになります。

このことから「$\text{A}$を通るまたは$\text{B}$を通る（赤、緑、青）」を求めるには、

「$\text{A}$を通る（赤、緑）」+「$\text{B}$を通る（青、緑）」-「$\text{A}$、$\text{B}$両方を通る（緑）」

を考えれば良いということになります。

　また、「$\text{A}$も$\text{B}$も通らない」場合の最短経路の数を求めるには、「補完した状態のすべて」の最短経路の数から「$\text{A}$を通る、または$\text{B}$を通る」場合の最短経路の数を引くことで求めることができます。

基本的な最短経路の数の求め方は以下に掲載しています。

関連：碁盤の目状の道路網の最短経路は何通り？

　以上から、「補完した状態のすべて」の場合、「$\text{A}$を通る」場合、「$\text{B}$を通る」場合、「$\text{A}$、$\text{B}$両方を通る」場合それぞれの最短経路が何通りあるのかを計算します。

補完した状態のすべての最短経路

　補完した状態の道路網は縦5マス×横7マスなので、

$$\frac{12!}{5! 7!}=792\ (通り)$$

となります。

「$\text{A}$を通る」場合

図4　「$\text{A}$を通る」場合

　図4のように考えると、

赤い部分は

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

紫の部分は

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

したがって、

$$3× 126=378\ (通り)$$

「$\text{B}$を通る」場合

図5　「$\text{B}$を通る」場合

　図5のように考えると、

紫の部分は

$$\frac{8!}{3! 5!}=56\ (通り)$$

青の部分は

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

したがって、

$$56× 3=168\ (通り)$$

「$\text{A}$、$\text{B}$両方を通る」場合

図6　「$\text{A}$、$\text{B}$両方を通る」場合

　図6のように考えると、

赤の部分は

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

緑の部分は

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

青の部分は

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

したがって、

$$3× 10× 3=90\ (通り)$$

よって、「$\text{A}$を通る、または$\text{B}$を通る」場合の最短経路の数は

$$378+168-90=456\ (通り)$$

であるから、求めたい「$\text{A}$と$\text{B}$どちらも通らない」場合の最短経路の数は

$$792-456=\mathbf{336}\ (通り)$$

となります。

関連：碁盤の目状の道路網の最短経路は何通り？