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

1. 問題の内容

右の図のような道がある街において、以下の問題を解く。

(ア) AからBへ行く最短経路の総数を求める。

(イ) AからBへ行く最短経路のうち、Cを通るものの数を求める。

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

2. 解き方の手順

(ア) AからBへの最短経路は、右に5回、上に4回移動する必要がある。したがって、最短経路の総数は、9回の移動のうち右方向への移動を選ぶ回数に等しい。

これは組み合わせで計算できる。

$$$$

{}_{9}C_5 = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126

$$$$

(イ) AからCへ行く最短経路は、右に2回、上に1回移動する必要がある。

CからBへ行く最短経路は、右に3回、上に3回移動する必要がある。

したがって、AからCを経由してBへ行く最短経路の総数は、

(AからCへの経路数) × (CからBへの経路数)で求められる。

AからCへの経路数は ${}_3C_2 = \frac{3!}{2!1!} = 3$

CからBへの経路数は ${}_6C_3 = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$

したがって、AからCを経由してBへ行く最短経路の総数は、3 × 20 = 60

(ウ) AからBへ行く最短経路のうち、Cを通りDを通らない経路数を求める。これは、(Cを通る経路数) - (CとDの両方を通る経路数)で計算できる。

Cを通る経路数は(イ)で求めたように60通りである。

AからCへの経路数は ${}_3C_2 = 3$

CからDへの経路数は、右に1回、上に2回なので、${}_3C_1 = 3$

DからBへの経路数は、右に2回、上に1回なので、${}_3C_2 = 3$

したがって、AからC, Dを経由してBへ行く最短経路の総数は、3 × 3 × 3 = 27

したがって、Cを通りDを通らない経路数は、60 - 27 = 33

3. 最終的な答え

(ア) 126通り

(イ) 60通り

(ウ) 33通り