与えられた図の道路において、以下の問いに答える。 (1) PからQまで行く最短経路は何通りあるか。 (2) Rを通ってPからQまで行く最短経路は何通りあるか。 (3) Xを通らずにPからQまで行く最短経路は何通りあるか。

1. 問題の内容

与えられた図の道路において、以下の問いに答える。

(1) PからQまで行く最短経路は何通りあるか。

(2) Rを通ってPからQまで行く最短経路は何通りあるか。

(3) Xを通らずにPからQまで行く最短経路は何通りあるか。

2. 解き方の手順

(1) PからQまで行く場合、右に4回、上に3回移動する必要がある。したがって、7回の移動のうち右に4回行く組み合わせを考えれば良いので、

$_{7}C_{4} = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ 通り。

(2) Rを通ってPからQまで行く場合、PからRまで行き、RからQまで行く必要がある。

PからRまで行くには、右に2回、上に1回移動する必要がある。したがって、3回の移動のうち右に2回行く組み合わせを考えれば良いので、

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

RからQまで行くには、右に2回、上に2回移動する必要がある。したがって、4回の移動のうち右に2回行く組み合わせを考えれば良いので、

$_{4}C_{2} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ 通り。

よって、Rを通ってPからQまで行く最短経路は $3 \times 6 = 18$ 通り。

(3) Xを通らずにPからQまで行く場合、PからQまでの最短経路からXを通る最短経路の数を引けばよい。

Xを通るPからQへの最短経路は、PからXへ行き、XからQへ行く。

PからXへは、右に1回、上に2回移動する必要がある。したがって、3回の移動のうち右に1回行く組み合わせを考えれば良いので、

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

XからQへは、右に3回、上に1回移動する必要がある。したがって、4回の移動のうち右に3回行く組み合わせを考えれば良いので、

$_{4}C_{3} = \frac{4!}{3!1!} = 4$ 通り。

よって、Xを通ってPからQまで行く最短経路は $3 \times 4 = 12$ 通り。

したがって、Xを通らずにPからQまで行く最短経路は $35 - 12 = 23$ 通り。

3. 最終的な答え

(1) 35通り

(2) 18通り

(3) 23通り