右の図のような道がある町で、A地点からB地点までの最短経路の総数を求める問題です。ただし、P地点とQ地点を通る経路のみを考えます。

1. 問題の内容

右の図のような道がある町で、A地点からB地点までの最短経路の総数を求める問題です。ただし、P地点とQ地点を通る経路のみを考えます。

2. 解き方の手順

最短経路は、右と上に進むことによってのみ実現されます。

まず、A地点からP地点までの最短経路の数を求めます。

次に、P地点からQ地点までの最短経路の数を求めます。

最後に、Q地点からB地点までの最短経路の数を求めます。

それらの数をすべて掛け合わせることで、AからBまでのPとQを通る最短経路の総数が得られます。

AからPまでの最短経路：右に2回、上に1回移動する必要があるので、経路数は $_3C_2 = \frac{3!}{2!1!} = 3$通りです。

PからQまでの最短経路：右に1回、上に2回移動する必要があるので、経路数は $_3C_1 = \frac{3!}{1!2!} = 3$通りです。

QからBまでの最短経路：右に1回、上に1回移動する必要があるので、経路数は $_2C_1 = \frac{2!}{1!1!} = 2$通りです。

したがって、AからPを通ってQを通ってBへ行く最短経路の総数は $3 \times 3 \times 2 = 18$通りです。

3. 最終的な答え

18