右の図のような道がある街において、以下の問いに答えます。 (1) AからBへ行く最短経路は何通りあるか。 (2) AからBへ行く最短経路のうち、Cを通るものは何通りあるか。 (3) AからBへ行く最短経路のうち、Cを通りDを通らないものは何通りあるか。

1. 問題の内容

右の図のような道がある街において、以下の問いに答えます。

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

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

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

2. 解き方の手順

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

AからBへ行くには、右に5回、上に4回移動する必要があります。

したがって、最短経路の総数は、9回の移動のうち、右への移動5回を選ぶ組み合わせの数に等しくなります。これは二項係数で表すことができ、

$\binom{9}{5} = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$ 通りです。

(2) Cを通る経路

AからCへ行くには、右に2回、上に1回移動する必要があります。その経路数は

$\binom{3}{2} = \frac{3!}{2!1!} = 3$ 通りです。

CからBへ行くには、右に3回、上に3回移動する必要があります。その経路数は

$\binom{6}{3} = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$ 通りです。

したがって、AからCを経由してBへ行く経路数は、 $3 \times 20 = 60$ 通りです。

(3) Cを通りDを通らない経路

まず、Cを通る経路の総数は60通りでした。

次に、Cを通り、かつDも通る経路の数を求めます。

CからDへ行くには、右に1回、上に2回移動する必要があります。その経路数は

$\binom{3}{1} = \frac{3!}{1!2!} = 3$ 通りです。

DからBへ行くには、右に2回、上に1回移動する必要があります。その経路数は

$\binom{3}{2} = \frac{3!}{2!1!} = 3$ 通りです。

したがって、AからCを経由し、Dも経由してBへ行く経路数は、 $3 \times 3 \times 3 = 27$ 通りです。

Cを通り、Dを通らない経路数は、Cを通る経路の総数からCを通りDも通る経路数を引けばよいので、 $60 - 27 = 33$ 通りです。

3. 最終的な答え

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

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

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