右の図のような街路において、AからBへ行く最短経路のうち、以下の条件を満たす経路が何通りあるかを求めます。 (1) Pを通る経路 (2) Qを通る経路 (3) PとQを通る経路 (4) PもQも通らない経路

## 問題54の解答

1. 問題の内容

右の図のような街路において、AからBへ行く最短経路のうち、以下の条件を満たす経路が何通りあるかを求めます。

(1) Pを通る経路

(2) Qを通る経路

(3) PとQを通る経路

(4) PもQも通らない経路

2. 解き方の手順

最短経路の総数を求める際には、同じ方向に進む必要のある回数に注目し、組合せの考え方を用います。

例えば、AからBへ行く場合、右に4回、上に3回進む必要があります。したがって、7回の移動のうち、右に進む4回を選ぶ方法の数が総経路数となります。これは ${}_7C_4 = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$通りです。

(1) Pを通る経路

AからPへの経路数は ${}_3C_1 = \frac{3!}{1!2!} = 3$通りです。

PからBへの経路数は ${}_4C_3 = \frac{4!}{3!1!} = 4$通りです。

したがって、Pを通る経路数は $3 \times 4 = 12$通りです。

(2) Qを通る経路

AからQへの経路数は ${}_5C_3 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$通りです。

QからBへの経路数は ${}_2C_1 = \frac{2!}{1!1!} = 2$通りです。

したがって、Qを通る経路数は $10 \times 2 = 20$通りです。

(3) PとQを通る経路

AからPへの経路数は ${}_3C_1 = 3$通りです。

PからQへの経路数は ${}_2C_2 = 1$通りです。

QからBへの経路数は ${}_2C_1 = 2$通りです。

したがって、PとQを通る経路数は $3 \times 1 \times 2 = 6$通りです。

(4) PもQも通らない経路

AからBへの総経路数から、Pを通る経路数、Qを通る経路数を引き、PとQの両方を通る経路数を足し戻すことで、PもQも通らない経路数を求めます。

PまたはQを通る経路数は、Pを通る経路数 + Qを通る経路数 - PとQを通る経路数 = $12 + 20 - 6 = 26$通りです。

したがって、PもQも通らない経路数は、AからBへの総経路数 - PまたはQを通る経路数 = $35 - 26 = 9$通りです。

3. 最終的な答え

(1) Pを通る経路: 12通り

(2) Qを通る経路: 20通り

(3) PとQを通る経路: 6通り

(4) PもQも通らない経路: 9通り