右図のような道のある地域で、以下の問いに答える問題です。 (1) AからBまで行く最短の道順は何通りあるか。 (2) AからCを通ってBまで行く最短の道順は何通りあるか。 (3) AからCを通らずにBまで行く最短の道順は何通りあるか。

1. 問題の内容

右図のような道のある地域で、以下の問いに答える問題です。

(1) AからBまで行く最短の道順は何通りあるか。

(2) AからCを通ってBまで行く最短の道順は何通りあるか。

(3) AからCを通らずにBまで行く最短の道順は何通りあるか。

2. 解き方の手順

(1) AからBまで行く最短の道順

AからBへ行くには、右に3回、上に4回移動する必要があります。合計7回の移動のうち、右への移動を3回選ぶ組み合わせの数が、AからBへの最短経路の数になります。これは、組み合わせの記号を用いて $_7C_3$ と表すことができます。

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

(2) AからCを通ってBまで行く最短の道順

AからCへの最短経路と、CからBへの最短経路の数をそれぞれ求め、それらを掛け合わせます。

AからCへは、右に2回、上に1回移動する必要があります。合計3回の移動のうち、右への移動を2回選ぶ組み合わせの数が、AからCへの最短経路の数になります。これは、組み合わせの記号を用いて $_3C_2$ と表すことができます。

$_3C_2 = \frac{3!}{2!1!} = \frac{3 \times 2 \times 1}{2 \times 1 \times 1} = 3$

CからBへは、右に1回、上に3回移動する必要があります。合計4回の移動のうち、右への移動を1回選ぶ組み合わせの数が、CからBへの最短経路の数になります。これは、組み合わせの記号を用いて $_4C_1$ と表すことができます。

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

したがって、AからCを通ってBへ行く最短の道順は、$3 \times 4 = 12$ 通りです。

(3) AからCを通らずにBまで行く最短の道順

AからBへのすべての最短経路から、AからCを通ってBへ行く最短経路の数を引けば、AからCを通らずにBへ行く最短経路の数が求められます。

AからBへの最短経路は35通り、AからCを通ってBへ行く最短経路は12通りであるため、AからCを通らずにBへ行く最短経路は、$35 - 12 = 23$ 通りです。

3. 最終的な答え

(1) AからBまで行く最短の道順は35通り。

(2) AからCを通ってBまで行く最短の道順は12通り。

(3) AからCを通らずにBまで行く最短の道順は23通り。