AからBまでの最短経路のうち、PもQも通らない経路は何通りあるか。

1. 問題の内容

AからBまでの最短経路のうち、PもQも通らない経路は何通りあるか。

2. 解き方の手順

* AからBまでの最短経路の総数を求める。

AからBまでは、右に6回、下に2回移動する必要がある。したがって、最短経路の総数は、8回の移動のうち右に移動する6回を選ぶ組み合わせの数で計算できる。

$$$$

\binom{8}{6} = \frac{8!}{6!2!} = \frac{8 \times 7}{2 \times 1} = 28

$$$$

よって、AからBまでの最短経路は28通りである。

* AからBまでの最短経路のうち、Pを通る経路の数を求める。

AからPまでの最短経路の数は $\binom{3}{1} = 3$通りである。

PからBまでの最短経路の数は $\binom{5}{5} = \binom{5}{0} = 1$通りである。

したがって、Pを通る最短経路は $3 \times \binom{5}{5} = 3 \times 1 = 3$通りである。

* AからBまでの最短経路のうち、Qを通る経路の数を求める。

AからQまでの最短経路の数は $\binom{5}{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$通りである。

QからBまでの最短経路の数は $\binom{3}{3} = 1$通りである。

したがって、Qを通る最短経路は $10 \times 1 = 10$通りである。

* AからBまでの最短経路のうち、PとQの両方を通る経路の数を求める。

AからPまでの最短経路の数は $\binom{3}{1} = 3$通りである。

PからQまでの最短経路の数は $\binom{2}{2} = 1$通りである。

QからBまでの最短経路の数は $\binom{3}{3} = 1$通りである。

したがって、PとQの両方を通る最短経路は $3 \times 1 \times 1 = 3$通りである。

* PまたはQを通る経路の数を求める。

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

$3 + 10 - 3 = 10$通り

* PもQも通らない経路の数を求める。

PもQも通らない経路の数は、AからBまでの最短経路の総数 - PまたはQを通る経路の数で計算できる。

$28 - 10 = 18$通り

3. 最終的な答え

18通り