右図のような道があるとき、以下の問いに答えよ。 (1) AからBへ行く最短経路は何通りあるか。 (2) Cを通ってAからBへ行く最短経路は何通りあるか。 (3) Cを通らずにAからBへ行く最短経路は何通りあるか。

1. 問題の内容

右図のような道があるとき、以下の問いに答えよ。

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

(2) Cを通ってAからBへ行く最短経路は何通りあるか。

(3) Cを通らずにAからBへ行く最短経路は何通りあるか。

2. 解き方の手順

(1) AからBへ行く最短経路は、右に4回、下に3回移動する必要がある。

したがって、7回の移動のうち、右に移動する4回を選ぶ組み合わせの数で計算できる。

これは、組み合わせの公式を用いて ${}_7 C_4$ で計算できる。

${}_7 C_4 = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$

(2) Cを通ってAからBへ行く最短経路は、AからCへ行く最短経路とCからBへ行く最短経路の積で計算できる。

AからCへ行くには、右に1回、下に1回移動する必要がある。

したがって、2回の移動のうち、右に移動する1回を選ぶ組み合わせの数で計算できる。

これは、組み合わせの公式を用いて ${}_2 C_1$ で計算できる。

${}_2 C_1 = \frac{2!}{1!1!} = 2$

CからBへ行くには、右に3回、下に2回移動する必要がある。

したがって、5回の移動のうち、右に移動する3回を選ぶ組み合わせの数で計算できる。

これは、組み合わせの公式を用いて ${}_5 C_3$ で計算できる。

${}_5 C_3 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$

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

(3) Cを通らずにAからBへ行く最短経路は、AからBへ行くすべての最短経路から、Cを通ってAからBへ行く最短経路を引いた数で計算できる。

したがって、Cを通らずにAからBへ行く最短経路は $35 - 20 = 15$ 通りである。

3. 最終的な答え

(1) 35通り

(2) 20通り

(3) 15通り