右図のような道がある街において、以下の問いに答える問題です。 (ア) AからBへ行く最短経路は何通りあるか。 (イ) AからBへ行く最短経路のうち、Cを通るものは何通りあるか。 (ウ) AからBへ行く最短経路のうち、Cを通りDを通らないものは何通りあるか。

1. 問題の内容

右図のような道がある街において、以下の問いに答える問題です。

(ア) AからBへ行く最短経路は何通りあるか。

(イ) AからBへ行く最短経路のうち、Cを通るものは何通りあるか。

(ウ) AからBへ行く最短経路のうち、Cを通りDを通らないものは何通りあるか。

2. 解き方の手順

(ア) AからBへ行く最短経路の総数を求めます。AからBへは、右に5回、上に3回移動する必要があります。したがって、全8回の移動のうち、右への移動を5回選ぶ場合の数、つまり$_{8}C_{5}$が最短経路の総数となります。

$_{8}C_{5} = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$

(イ) AからCへ行く最短経路の数と、CからBへ行く最短経路の数をそれぞれ求め、それらを掛け合わせることで、AからBへCを通る最短経路の数が求められます。

AからCへは、右に2回、上に1回移動する必要があります。したがって、全3回の移動のうち、右への移動を2回選ぶ場合の数、つまり$_{3}C_{2}$が最短経路の総数となります。

$_{3}C_{2} = \frac{3!}{2!1!} = 3$

CからBへは、右に3回、上に2回移動する必要があります。したがって、全5回の移動のうち、右への移動を3回選ぶ場合の数、つまり$_{5}C_{3}$が最短経路の総数となります。

$_{5}C_{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$

よって、AからBへCを通る最短経路は$3 \times 10 = 30$通りとなります。

(ウ) AからBへ行く最短経路のうち、Cを通りDを通るものを計算します。

AからCへ行く経路は(イ)より3通りです。

CからDへ行く経路は、右に1回、上に1回なので、2通りです。

DからBへ行く経路は、右に2回、上に1回なので、$_{3}C_{2}=3$通りです。

したがって、AからBへCとDを通る経路は$3 \times 2 \times 3 = 18$通りです。

AからBへ行く最短経路のうち、Cを通りDを通らない経路は、Cを通る経路の総数からCとDの両方を通る経路の総数を引けば求まります。

よって、$30 - 18 = 12$通りとなります。

3. 最終的な答え

(ア) 56通り

(イ) 30通り

(ウ) 12通り