右の図のような道がある街において、AからBへ行く最短経路の総数、そのうちCを通る経路の数、そしてCを通るがDを通らない経路の数をそれぞれ求める問題です。

1. 問題の内容

右の図のような道がある街において、AからBへ行く最短経路の総数、そのうちCを通る経路の数、そしてCを通るがDを通らない経路の数をそれぞれ求める問題です。

2. 解き方の手順

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

AからBへ行くには、右に5回、上に3回移動する必要があります。したがって、最短経路の総数は、8回の移動のうち、右への移動5回を選ぶ組み合わせの数に等しくなります。

$$\binom{8}{5} = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$$

(2) AからBへの最短経路のうち、Cを通るものの数

AからCへの最短経路は、右に2回、上に1回移動する必要があります。したがって、その経路の数は

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

CからBへの最短経路は、右に3回、上に2回移動する必要があります。したがって、その経路の数は

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

したがって、AからBへの最短経路のうち、Cを通るものの数は、$3 \times 10 = 30$

(3) AからBへの最短経路のうち、Cを通り、Dを通らないものの数

まず、AからBへの最短経路のうち、CとDの両方を通るものの数を求めます。

AからCへの経路は先ほど求めたように3通りです。

CからDへの最短経路は、右に1回、上に1回移動する必要があるので、その経路数は

$$\binom{2}{1} = 2$$

DからBへの最短経路は、右に2回、上に1回移動する必要があります。したがって、その経路の数は

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

したがって、AからBへの最短経路のうち、CとDの両方を通るものの数は、$3 \times 2 \times 3 = 18$

よって、AからBへの最短経路のうち、Cを通り、Dを通らないものの数は、

(Cを通る経路の数) - (CとDの両方を通る経路の数) = $30 - 18 = 12$

3. 最終的な答え

* AからBへ行く最短経路は 56 通り。

* そのうち、Cを通るものは 30 通り。

* また、AからBへ行く最短経路のうち、Cを通りDを通らないものは 12 通り。