図に示す道路網において、O地点から出発し、以下の条件を満たす最短経路の数を求める。 (1) A地点を通りP地点へ行く経路の数 (2) B地点を通りP地点へ行く経路の数 (3) A地点とB地点の両方を通りP地点へ行く経路の数 ただし、C地点は通れない。

1. 問題の内容

図に示す道路網において、O地点から出発し、以下の条件を満たす最短経路の数を求める。

(1) A地点を通りP地点へ行く経路の数

(2) B地点を通りP地点へ行く経路の数

(3) A地点とB地点の両方を通りP地点へ行く経路の数

ただし、C地点は通れない。

2. 解き方の手順

各地点へ到達する最短経路の数を、左下から順に各地点に書き込んでいく。

ある地点への最短経路数は、その地点の左と下の地点への最短経路数の和となる。

C地点は通れないことに注意する。

(1) O地点からA地点へ行く最短経路数は15通り。

A地点からP地点へ行く最短経路数は $\frac{(7-3)!}{(7-3-1)!(1)!} = \frac{4!}{3!1!} = \frac{4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1)(1)} = 4$

O地点からA地点を通り、P地点へ行く最短経路数は $15 \times 4 = 60$ 通り。

(2) O地点からB地点へ行く最短経路数は6通り。

B地点からP地点へ行く最短経路数を求める。C地点は通れないことに注意すると、

B地点からP地点までの最短経路数は $\frac{(7-2)!}{(7-2-4)!(4)!} - \frac{(7-3)!}{(7-3-3)!(3)!} = \frac{5!}{1!4!} - \frac{4!}{1!3!} = 5 - 4 = 1$

B地点からP地点までの最短経路数は35通り。

O地点からB地点を通り、P地点へ行く最短経路数は $6 \times 35 = 210$ 通り。

(3) O地点からA地点へ行く最短経路数は15通り。A地点からB地点へ行くには、C地点を通らずには行けないので、A地点からB地点へは行けない。

O地点からB地点へ行く最短経路数は6通り。B地点からA地点へ行くには、C地点を通らずには行けないので、B地点からA地点へは行けない。

したがって、A地点とB地点の両方を通る最短経路は存在しない。 よって、0通り。

A地点からB地点へ行く最短経路数は0通り。

B地点からA地点へ行く最短経路数は0通り。

A地点とB地点の両方を通る最短経路の数は0通り。

(1) OからAへ行くのは15通り。AからPへ行くのは4通り。よって、 $15 \times 4 = 60$通り。

(2) OからBへ行くのは6通り。BからPへ行くのは35通り。よって、$6 \times 35 = 210$通り。

(3) OからAを経由してBに行くのは、Cを通るので0通り。OからBを経由してAに行くのも、Cを通るので0通り。よって0通り。

3. 最終的な答え

(1) 60通り

(2) 210通り

(3) 0通り