図のような道のある町で、点Aから点Bまで最短経路で行く場合の数を以下の3つについて求める問題です。 (1) AからBまでの最短経路の総数 (2) AからBまでの最短経路のうち、点Qを通るものの総数 (3) AからBまでの最短経路のうち、点Pまたは点Qを通るものの総数

1. 問題の内容

図のような道のある町で、点Aから点Bまで最短経路で行く場合の数を以下の3つについて求める問題です。

(1) AからBまでの最短経路の総数

(2) AからBまでの最短経路のうち、点Qを通るものの総数

(3) AからBまでの最短経路のうち、点Pまたは点Qを通るものの総数

2. 解き方の手順

(1) AからBまでの最短経路の総数

AからBまで行くには、右に5回、上に3回移動する必要があります。したがって、最短経路の総数は、8回の移動のうち、右への移動を5回選ぶ組み合わせの数に等しくなります。これは、組み合わせの記号を用いて ${}_8 \mathrm{C}_5$ と表されます。

${}_8 \mathrm{C}_5 = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 8 \times 7 = 56$

したがって、AからBまでの最短経路の総数は56通りです。

(2) AからBまでの最短経路のうち、点Qを通るものの総数

AからQまでの最短経路の総数は、右に4回、上に1回移動する必要があるので、${}_5 \mathrm{C}_4 = \frac{5!}{4!1!} = 5$ 通りです。

QからBまでの最短経路の総数は、右に1回、上に2回移動する必要があるので、${}_3 \mathrm{C}_1 = \frac{3!}{1!2!} = 3$ 通りです。

したがって、AからQを通ってBまで行く最短経路の総数は $5 \times 3 = 15$ 通りです。

(3) AからBまでの最短経路のうち、点Pまたは点Qを通るものの総数

AからPまでの最短経路の総数は、右に2回、上に2回移動する必要があるので、${}_4 \mathrm{C}_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ 通りです。

PからBまでの最短経路の総数は、右に3回、上に1回移動する必要があるので、${}_4 \mathrm{C}_3 = \frac{4!}{3!1!} = 4$ 通りです。

したがって、AからPを通ってBまで行く最短経路の総数は $6 \times 4 = 24$ 通りです。

PとQの両方を通る経路を重複して数えないように、PとQの両方を通る経路の数を計算します。AからPまでの経路は6通り、PからQまでの経路は右に2回、上に-1回なので存在しないため0通りです。

そのためPとQの両方を通る経路は0通りです。

PまたはQを通る経路の総数は、Pを通る経路の数+Qを通る経路の数-PとQの両方を通る経路の数で計算できます。

$24 + 15 - 0 = 39$

したがって、PまたはQを通る経路の総数は39通りです。

3. 最終的な答え

- セ：56

- チ：15

- テ：39