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

1. 問題の内容

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

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

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

2. 解き方の手順

(1) A地点からB地点までの最短経路の総数を求める。

AからBへ行くには、右に6回、下に3回移動する必要がある。したがって、移動の総数は9回。このうち右への移動が6回、下への移動が3回なので、経路の総数は、9回の移動から右への移動6回を選ぶ組み合わせの数、または下への移動3回を選ぶ組み合わせの数で求められる。組み合わせの公式を用いると、

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

または、

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

(2) A地点からC地点を経由してB地点までの最短経路の数を求める。

AからCへ行くには、右に3回、下に1回移動する必要がある。したがって、移動の総数は4回。このうち右への移動が3回、下への移動が1回なので、経路の総数は、4回の移動から右への移動3回を選ぶ組み合わせの数、または下への移動1回を選ぶ組み合わせの数で求められる。組み合わせの公式を用いると、

$_{4}C_{3} = \frac{4!}{3!1!} = \frac{4 \times 3 \times 2}{3 \times 2 \times 1} = 4$

または、

$_{4}C_{1} = \frac{4!}{1!3!} = \frac{4 \times 3 \times 2}{3 \times 2 \times 1} = 4$

CからBへ行くには、右に3回、下に2回移動する必要がある。したがって、移動の総数は5回。このうち右への移動が3回、下への移動が2回なので、経路の総数は、5回の移動から右への移動3回を選ぶ組み合わせの数、または下への移動2回を選ぶ組み合わせの数で求められる。組み合わせの公式を用いると、

$_{5}C_{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$

または、

$_{5}C_{2} = \frac{5!}{2!3!} = \frac{5 \times 4}{2 \times 1} = 10$

したがって、AからCを経由してBへ行く経路の数は、$4 \times 10 = 40$ 通り。

3. 最終的な答え

(1) 84通り

(2) 40通り