右図のような道のある町で、AからBまでの最短経路の総数を求め、さらに最短経路のうちQを通るものの総数、PまたはQを通るものの総数を求める問題です。

1. 問題の内容

右図のような道のある町で、AからBまでの最短経路の総数を求め、さらに最短経路のうちQを通るものの総数、PまたはQを通るものの総数を求める問題です。

2. 解き方の手順

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

AからBまで行くには、右に5回、上に4回移動する必要があります。合計9回の移動のうち、右への移動を5回選ぶ場合の数なので、組み合わせの式で計算できます。

$_{9}C_{5} = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$

(2) Qを通る最短経路の総数：

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

$_{5}C_{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$ 通りです。

QからBまでの最短経路は、右に2回、上に2回移動する必要があるので、

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

したがって、Qを通る最短経路の総数は $10 \times 6 = 60$ 通りです。

(3) Pを通る最短経路の総数：

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

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

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

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

したがって、Pを通る最短経路の総数は $3 \times 20 = 60$ 通りです。

(4) PとQの両方を通る最短経路の総数：

AからPまでの最短経路の総数は3通りです。

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

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

QからBまでの最短経路の総数は6通りです。

したがって、PとQの両方を通る最短経路の総数は $3 \times 2 \times 6 = 36$ 通りです。

(5) PまたはQを通る最短経路の総数：

PまたはQを通る最短経路の総数は、Pを通る最短経路の総数 + Qを通る最短経路の総数 - PとQの両方を通る最短経路の総数で求められます。

したがって、$60 + 60 - 36 = 84$ 通りです。

3. 最終的な答え

* 最短経路の総数は 126 通り

* Qを通る最短経路の総数は 60 通り

* PまたはQを通る最短経路の総数は 84 通り