右の図のような道がある街において、以下の3つの問いに答える。 (ア) AからBへ行く最短経路は何通りあるか。 (イ) AからBへ行く最短経路のうち、Cを通るものは何通りあるか。 (ウ) AからBへ行く最短経路のうち、Cを通りDを通らないものは何通りあるか。

1. 問題の内容

右の図のような道がある街において、以下の3つの問いに答える。

(ア) AからBへ行く最短経路は何通りあるか。

(イ) AからBへ行く最短経路のうち、Cを通るものは何通りあるか。

(ウ) AからBへ行く最短経路のうち、Cを通りDを通らないものは何通りあるか。

2. 解き方の手順

(ア) AからBへの最短経路

AからBへ行くには、右に5回、上に3回移動する必要がある。したがって、最短経路の総数は、8回の移動のうち、右への移動を5回選ぶ組み合わせの数に等しい。これは、組み合わせの公式を用いて計算できる。

$_8C_5 = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$

(イ) AからCを通ってBへ行く最短経路

AからCへ行くには、右に2回、上に1回移動する必要がある。その経路数は、$_3C_2 = \frac{3!}{2!1!} = 3$通りである。

CからBへ行くには、右に3回、上に2回移動する必要がある。その経路数は、$_5C_3 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$通りである。

したがって、AからCを通ってBへ行く最短経路数は、 $3 \times 10 = 30$通りである。

(ウ) AからCを通りDを通らずにBへ行く最短経路

AからCを通る経路は(イ)で30通りと求めた。

このうち、Dを通る経路を求める。

AからCを通りDを通る経路は、AからCまでの経路数($3$通り)とCからDまでの経路数($_2C_1 = 2$通り)とDからBまでの経路数($_3C_2 = 3$通り)を掛けて$3 \times 2 \times 3 = 18$通りとなる。

したがって、AからCを通りDを通らない経路は、$30 - 18 = 12$通りとなる。

3. 最終的な答え

(ア) 56通り

(イ) 30通り

(ウ) 12通り