右図のような道のある地域で、以下の条件におけるA地点からB地点までの最短経路の数を求める問題です。 (1) AからBまで行く。 (2) AからCを通ってBまで行く。 (3) AからCを通らずにBまで行く。

1. 問題の内容

右図のような道のある地域で、以下の条件におけるA地点からB地点までの最短経路の数を求める問題です。

(1) AからBまで行く。

(2) AからCを通ってBまで行く。

(3) AからCを通らずにBまで行く。

2. 解き方の手順

(1) AからBまで行く場合

AからBまでの最短経路は、右に4回、上に3回移動することで構成されます。したがって、7回の移動のうち、右への移動を4回選ぶ場合の数、または上への移動を3回選ぶ場合の数を計算すればよいです。これは組み合わせの考え方で求められます。

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

(2) AからCを通ってBまで行く場合

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

AからCまでは、右に1回、上に1回移動するので、最短経路は2回中1回の右移動を選ぶことで求まります。

$${}_2C_1 = \frac{2!}{1!1!} = 2$$

CからBまでは、右に3回、上に2回移動するので、最短経路は5回中3回の右移動を選ぶことで求まります。

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

したがって、AからCを通ってBまで行く最短経路は、

$2 \times 10 = 20$ 通りです。

(3) AからCを通らずにBまで行く場合

AからBまでの最短経路から、AからCを通ってBまで行く最短経路を引けばよいです。

(1)より、AからBまでの最短経路は35通りです。

(2)より、AからCを通ってBまで行く最短経路は20通りです。

したがって、AからCを通らずにBまで行く最短経路は、

$35 - 20 = 15$ 通りです。

3. 最終的な答え

(1) AからBまで行く最短経路は35通り。

(2) AからCを通ってBまで行く最短経路は20通り。

(3) AからCを通らずにBまで行く最短経路は15通り。