与えられた道のある町において、地点Pから地点Qまでの最短経路について、以下の問いに答える。 (1) PからQまでの最短経路は何通りあるか。また、そのうちRを通る経路は何通りあるか。 (2) PからQまでの最短経路のうち、Rを通らずSを通る経路は何通りあるか。 (3) PからQまでの最短経路のうち、RもSも通らない経路は何通りあるか。

1. 問題の内容

与えられた道のある町において、地点Pから地点Qまでの最短経路について、以下の問いに答える。

(1) PからQまでの最短経路は何通りあるか。また、そのうちRを通る経路は何通りあるか。

(2) PからQまでの最短経路のうち、Rを通らずSを通る経路は何通りあるか。

(3) PからQまでの最短経路のうち、RもSも通らない経路は何通りあるか。

2. 解き方の手順

(1)

* PからQまでの最短経路の総数を求める。PからQへは右に5回、上に4回移動する必要がある。したがって、最短経路の総数は、9回の移動のうち右への移動を5回選ぶ組み合わせの数に等しい。これは ${}_9 C_5$ で計算できる。

* PからRを通ってQへ行く最短経路の数を求める。これはPからRへの最短経路の数と、RからQへの最短経路の数を掛け合わせることで求められる。PからRへは右に2回、上に1回移動する必要があるため、${}_3 C_2$ 通りの経路がある。RからQへは右に3回、上に3回移動する必要があるため、${}_6 C_3$ 通りの経路がある。したがって、PからRを通ってQへ行く最短経路の数は、${}_3 C_2 \times {}_6 C_3$ で計算できる。

(2)

* PからSを通ってQへ行く最短経路の数を求める。PからSへは右に4回、上に2回移動する必要があるため、${}_6 C_4$ 通りの経路がある。SからQへは右に1回、上に2回移動する必要があるため、${}_3 C_1$ 通りの経路がある。したがって、PからSを通ってQへ行く最短経路の数は、${}_6 C_4 \times {}_3 C_1$ で計算できる。

* PからRを通ってSを通りQへ行く最短経路の数を求める。これはPからRへの最短経路の数、RからSへの最短経路の数、SからQへの最短経路の数を掛け合わせることで求められる。PからRへは右に2回、上に1回移動する必要があるため、${}_3 C_2$ 通りの経路がある。RからSへは右に2回、上に1回移動する必要があるため、${}_3 C_2$ 通りの経路がある。SからQへは右に1回、上に2回移動する必要があるため、${}_3 C_1$ 通りの経路がある。したがって、PからRを通ってSを通りQへ行く最短経路の数は、${}_3 C_2 \times {}_3 C_2 \times {}_3 C_1$ で計算できる。

* Rを通らずSを通る経路の数は、PからSを通ってQへ行く経路の数から、PからRを通ってSを通りQへ行く経路の数を引くことで求められる。

(3)

* PからQへの最短経路の総数から、Rを通る経路の数とSを通る経路の数を足し合わせる。

* 重複して引いたRとSの両方を通る経路の数を引く。すなわち、PからQへの最短経路の総数から、Rを通る経路の数とSを通る経路の数を足し合わせ、RとSの両方を通る経路の数を引く。

$P$から$Q$への最短経路の数 - ($P$から$R$を通って$Q$に行く経路の数 + $P$から$S$を通って$Q$に行く経路の数 - $P$から$R$と$S$を通って$Q$に行く経路の数)

${}_9 C_5 - ({}_3 C_2 \times {}_6 C_3 + {}_6 C_4 \times {}_3 C_1 - {}_3 C_2 \times {}_3 C_2 \times {}_3 C_1)$

3. 最終的な答え

(1)

* PからQまでの最短経路の総数: ${}_9 C_5 = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$ 通り

* Rを通る経路の数: ${}_3 C_2 \times {}_6 C_3 = 3 \times \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 3 \times 20 = 60$ 通り

(2)

* Sを通る経路の数: ${}_6 C_4 \times {}_3 C_1 = {}_6 C_2 \times {}_3 C_1 = \frac{6 \times 5}{2 \times 1} \times 3 = 15 \times 3 = 45$ 通り

* RとSを通る経路の数: ${}_3 C_2 \times {}_3 C_2 \times {}_3 C_1 = 3 \times 3 \times 3 = 27$ 通り

* Rを通らずSを通る経路の数: $45 - 27 = 18$ 通り

(3)

* RもSも通らない経路の数: $126 - (60 + 45 - 27) = 126 - 78 = 48$ 通り

最終的な答え：

(1) PからQまでの最短経路は126通り、Rを通る経路は60通り。

(2) Rを通らずSを通る経路は18通り。

(3) RもSも通らない経路は48通り。