図のような道のある町で、点Aから点Bまでの最短経路の総数、点Qを通る最短経路の総数、点Pまたは点Qを通る最短経路の総数をそれぞれ求める問題です。

1. 問題の内容

図のような道のある町で、点Aから点Bまでの最短経路の総数、点Qを通る最短経路の総数、点Pまたは点Qを通る最短経路の総数をそれぞれ求める問題です。

2. 解き方の手順

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

AからBまでの最短経路は、右に5回、上に4回進む経路です。したがって、9回の移動のうち、右に進む5回を選ぶ組み合わせの数で計算できます。

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

AからBまでの最短経路は126通りです。

(2) AからQを通る最短経路の総数

AからQまでの最短経路は、右に3回、上に2回進む経路です。

$${_5C_3 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10}$$

QからBまでの最短経路は、右に2回、上に2回進む経路です。

$${_4C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6}$$

したがって、AからQを経由してBまでの最短経路は、AからQまでの経路数とQからBまでの経路数の積で計算できます。

$$10 \times 6 = 60$$

AからQを通る最短経路は60通りです。

(3) AからPを通る最短経路の総数

AからPまでの最短経路は、右に2回、上に1回進む経路です。

$${_3C_2 = \frac{3!}{2!1!} = 3}$$

PからBまでの最短経路は、右に3回、上に3回進む経路です。

$${_6C_3 = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20}$$

したがって、AからPを経由してBまでの最短経路は、AからPまでの経路数とPからBまでの経路数の積で計算できます。

$$3 \times 20 = 60$$

AからPを通る最短経路は60通りです。

(4) AからPまたはQを通る最短経路の総数

Pを通る経路数とQを通る経路数を足し、PとQの両方を通る経路数を引きます。

AからPを通ってQを通ることは不可能なので、PとQの両方を通る経路数は0です。したがって、

$$60 + 60 = 120$$

PまたはQを通る最短経路は120通りです。

3. 最終的な答え

* AからBまでの最短経路の総数は126通り

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

* AからPまたはQを通る最短経路の総数は120通り

サシス：126

セソタ：60

チッテ：120