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

1. 問題の内容

右図のような道のある町で、以下の条件でA地点からD地点まで行く最短経路の数を求める。

(1) A地点からB地点を通ってD地点まで行く。

(2) A地点からC地点を通ってD地点まで行く。

(3) A地点からD地点まで行く。

2. 解き方の手順

最短経路の数を求めるには、各交差点に到達する経路の数を書き込んでいく方法が有効です。

(1) A地点からB地点を通ってD地点まで行く場合

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

AからBへは、右に4回、上に1回移動します。したがって、経路の数は ${5 \choose 1} = 5$ 通りです。

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

BからDへは、上に2回移動します。したがって、経路の数は ${2 \choose 2} = 1$ 通りです。

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

$5 \times 1 = 5$ 通りです。

(2) A地点からC地点を通ってD地点まで行く場合

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

AからCへは、右に3回、上に2回移動します。したがって、経路の数は ${5 \choose 2} = \frac{5 \times 4}{2 \times 1} = 10$ 通りです。

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

CからDへは、右に1回、上に1回移動します。したがって、経路の数は ${2 \choose 1} = 2$ 通りです。

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

$10 \times 2 = 20$ 通りです。

(3) A地点からD地点まで行く場合

AからDへは、右に4回、上に3回移動します。したがって、経路の数は ${7 \choose 3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ 通りです。

3. 最終的な答え

(1) 5通り

(2) 20通り

(3) 35通り