右図のような道のある町において、以下の条件を満たす最短経路の数を求める問題です。 (1) A地点からB地点を通ってD地点まで行く経路の数 (2) A地点からC地点を通ってD地点まで行く経路の数 (3) A地点からD地点まで行く経路の数

1. 問題の内容

右図のような道のある町において、以下の条件を満たす最短経路の数を求める問題です。

(1) A地点からB地点を通ってD地点まで行く経路の数

(2) A地点からC地点を通ってD地点まで行く経路の数

(3) A地点からD地点まで行く経路の数

2. 解き方の手順

各地点間の最短経路の数は、右方向への移動回数と上方向への移動回数が決まれば一意に定まります。組み合わせの考え方を利用します。

(1) A地点からB地点への最短経路の数は、右に4回、上に1回移動する必要があるので、

$\frac{5!}{4!1!} = 5$ 通り。

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

$\frac{4!}{1!3!} = 4$ 通り。

よって、A地点からB地点を通ってD地点まで行く最短経路の数は、

$5 \times 4 = 20$ 通り。

(2) A地点からC地点への最短経路の数は、右に3回、上に2回移動する必要があるので、

$\frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$ 通り。

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

$\frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ 通り。

よって、A地点からC地点を通ってD地点まで行く最短経路の数は、

$10 \times 6 = 60$ 通り。

(3) A地点からD地点への最短経路の数は、右に5回、上に4回移動する必要があるので、

$\frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 9 \times 2 \times 7 = 126$ 通り。

3. 最終的な答え

(1) 20通り

(2) 60通り

(3) 126通り