図のような道がある街で、以下の3つの最短経路の数を求める問題です。 (1) AからBへ行く最短経路 (2) AからBへ行く最短経路のうち、Cを通るもの (3) AからBへ行く最短経路のうち、Cを通りDを通らないもの

1. 問題の内容

図のような道がある街で、以下の3つの最短経路の数を求める問題です。

(1) AからBへ行く最短経路

(2) AからBへ行く最短経路のうち、Cを通るもの

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

2. 解き方の手順

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

AからBへ行くには、右に5マス、上に3マス進む必要があります。したがって、全部で8マス進むうち、右に5マス進む方向の選び方を考えればよいので、

$_{8}C_{5} = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$ 通り

(2) AからBへの最短経路のうち、Cを通るもの

AからCへの最短経路は、右に2マス、上に1マス進むので、

$_{3}C_{2} = \frac{3!}{2!1!} = 3$ 通り

CからBへの最短経路は、右に3マス、上に2マス進むので、

$_{5}C_{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$ 通り

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

$3 \times 10 = 30$ 通り

(3) AからBへの最短経路のうち、Cを通りDを通らないもの

AからCへは3通り。CからDへの最短経路は右に1マス、上に1マス進むので、

$_{2}C_{1} = 2$ 通り。DからBへの最短経路は右に2マス、上に1マス進むので、

$_{3}C_{2} = 3$ 通り。

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

$3 \times 2 \times 3 = 18$ 通り

Cを通る経路が30通りあり、そのうちDを通る経路が18通りあるので、Cを通りDを通らない経路は、

$30 - 18 = 12$ 通り

3. 最終的な答え

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

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

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