図のような経路において、点Pから出発して点Qを通らずに点Rへ行く最短経路は何通りあるかを求める問題です。

1. 問題の内容

図のような経路において、点Pから出発して点Qを通らずに点Rへ行く最短経路は何通りあるかを求める問題です。

2. 解き方の手順

まず、点Pから点Rへ行くすべての最短経路を求めます。次に、点Pから点Qを経由して点Rへ行く最短経路を求めます。最後に、すべての最短経路から点Qを経由する最短経路を引くことで、点Qを通らない最短経路の数を求めます。

点Pから点Rへの最短経路は、右に4回、上に3回進む必要があります。したがって、全経路の数は、7回の移動のうち右に進む4回を選ぶ組み合わせで求められ、$\binom{7}{4} = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$通りです。

点Pから点Qへの最短経路は、右に2回、上に1回進む必要があります。したがって、経路の数は、$\binom{3}{2} = \frac{3!}{2!1!} = 3$通りです。

点Qから点Rへの最短経路は、右に2回、上に2回進む必要があります。したがって、経路の数は、$\binom{4}{2} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通りです。

点Pから点Qを経由して点Rへ行く最短経路は、点Pから点Qへの経路数と点Qから点Rへの経路数を掛け合わせることで求められます。したがって、$3 \times 6 = 18$通りです。

点Pから点Rへのすべての最短経路から点Qを経由する最短経路を引くと、点Qを通らない最短経路の数が得られます。$35 - 18 = 17$通りです。

3. 最終的な答え

17通り