与えられた図のような道路網において、地点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までの最短経路は、右に5回、上に4回移動する必要があるため、総経路数は、

$_{5+4}C_5 = {}_9C_5 = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$ 通りです。

PからRまでの最短経路数は、右に2回、上に1回移動する必要があるため、

$_{2+1}C_2 = {}_3C_2 = \frac{3!}{2!1!} = 3$ 通りです。

RからQまでの最短経路数は、右に3回、上に3回移動する必要があるため、

$_{3+3}C_3 = {}_6C_3 = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$ 通りです。

したがって、PからRを通りQまで行く経路数は $3 \times 20 = 60$ 通りです。

(2)

PからSまでの最短経路数は、右に4回、上に3回移動する必要があるため、

$_{4+3}C_4 = {}_7C_4 = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ 通りです。

SからQまでの最短経路数は、右に1回、上に1回移動する必要があるため、

$_{1+1}C_1 = {}_2C_1 = \frac{2!}{1!1!} = 2$ 通りです。

したがって、PからSを通りQまで行く経路数は $35 \times 2 = 70$ 通りです。

Rを通ってSを通る経路数は、PからRまでの経路数が3通り、RからSまでの経路数が、右に2回、上に2回移動する必要があるので、$_{2+2}C_2 = {}_4C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ 通り、SからQまでの経路数が2通りなので、$3 \times 6 \times 2 = 36$通りです。

したがって、Rを通らずSを通る経路数は、$70 - 36 = 34$ 通りです。

(3)

PからQへの最短経路の総数から、Rを通る経路数とSを通る経路数を引き、RとSの両方を通る経路数を足します。

PからQへの総経路数: 126通り

Rを通る経路数: 60通り

Sを通る経路数: 70通り

RとSの両方を通る経路数: 36通り

RもSも通らない経路数は、$126 - 60 - 70 + 36 = 32$ 通りです。

3. 最終的な答え

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

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

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