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までの最短経路の数は 通りである。
PからBまでの最短経路の数は 通りである。
したがって、Pを通る最短経路は 通りである。
* AからBまでの最短経路のうち、Qを通る経路の数を求める。
AからQまでの最短経路の数は 通りである。
QからBまでの最短経路の数は 通りである。
したがって、Qを通る最短経路は 通りである。
* AからBまでの最短経路のうち、PとQの両方を通る経路の数を求める。
AからPまでの最短経路の数は 通りである。
PからQまでの最短経路の数は 通りである。
QからBまでの最短経路の数は 通りである。
したがって、PとQの両方を通る最短経路は 通りである。
* PまたはQを通る経路の数を求める。
PまたはQを通る経路の数は、Pを通る経路の数 + Qを通る経路の数 - PとQの両方を通る経路の数で計算できる。
通り
* PもQも通らない経路の数を求める。
PもQも通らない経路の数は、AからBまでの最短経路の総数 - PまたはQを通る経路の数で計算できる。
通り
3. 最終的な答え
18通り