図のような道がある街で、以下の問いに答える問題です。 (ア) AからBへ行く最短経路の総数を求める。 (イ) AからBへ行く最短経路のうち、Cを通る経路の数を求める。 (ウ) AからBへ行く最短経路のうち、Cを通り、Dを通らない経路の数を求める。

1. 問題の内容

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

(ア) AからBへ行く最短経路の総数を求める。

(イ) AからBへ行く最短経路のうち、Cを通る経路の数を求める。

(ウ) AからBへ行く最短経路のうち、Cを通り、Dを通らない経路の数を求める。

2. 解き方の手順

(ア) 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へ行く最短経路は、右に2回、上に1回進む必要があります。したがって、全3回の移動のうち、右への移動を2回選ぶ組み合わせの数が最短経路の数となります。

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

CからBへ行く最短経路は、右に3回、上に2回進む必要があります。したがって、全5回の移動のうち、右への移動を3回選ぶ組み合わせの数が最短経路の数となります。

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

したがって、AからCを経由してBへ行く最短経路の数は、AからCへの経路数とCからBへの経路数の積で求められます。

$3 \times 10 = 30$

(ウ) AからCへ行く経路は3通り(上記(イ)より)。CからBへ行く経路は10通り(上記(イ)より)。

AからDへ行く最短経路は、右に3回、上に2回進む必要があります。したがって、全5回の移動のうち、右への移動を3回選ぶ組み合わせの数が最短経路の数となります。

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

DからBへ行く最短経路は、右に2回、上に1回進む必要があります。したがって、全3回の移動のうち、右への移動を2回選ぶ組み合わせの数が最短経路の数となります。

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

AからCを経由してBへ行く最短経路数は30通り(上記(イ)より)。

AからDを経由してBへ行く最短経路数は、 $10 \times 3 = 30$通り。

Cを通りDも通る経路の数を求める。AからCへ行く経路は3通り。CからDへ行く経路は、右に1回上に1回なので2通り。DからBへ行く経路は3通り。したがってCもDも通る経路は、$3 \times 2 \times 3 = 18$通り。

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

3. 最終的な答え

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

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

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