右図のような道路のある町で、A地点からB地点まで最短経路で行くとき、以下の問いに答える。 (1) A地点からB地点までの最短経路は何通りあるか。 (2) A地点からB地点まで、C地点を通る最短経路は何通りあるか。

1. 問題の内容

右図のような道路のある町で、A地点からB地点まで最短経路で行くとき、以下の問いに答える。

(1) A地点からB地点までの最短経路は何通りあるか。

(2) A地点からB地点まで、C地点を通る最短経路は何通りあるか。

2. 解き方の手順

(1) A地点からB地点まで行くには、右に6回、上に3回移動する必要がある。したがって、最短経路の総数は、9回の移動のうち、右方向への移動6回を選ぶ組み合わせの数である。これは組み合わせの公式で計算できる。

$$$$

\binom{9}{6} = \frac{9!}{6!3!} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 3 \times 4 \times 7 = 84

$$$$

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

その経路数は、5回の移動のうち、右方向への移動3回を選ぶ組み合わせの数である。

$$$$

\binom{5}{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10

$$$$

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

その経路数は、4回の移動のうち、右方向への移動3回を選ぶ組み合わせの数である。

$$$$

\binom{4}{3} = \frac{4!}{3!1!} = \frac{4}{1} = 4

$$$$

したがって、A地点からC地点を経由してB地点まで行く最短経路数は、A地点からC地点までの経路数と、C地点からB地点までの経路数の積で求められる。

$10 \times 4 = 40$

3. 最終的な答え

(1) A地点からB地点までの最短経路は84通り。

(2) A地点からB地点まで、C地点を通る最短経路は40通り。