東西に6本、南北に7本の道がある。O地点から出発し、P地点まで最短距離で行く経路について、以下の3つの場合に経路の数を求める。ただし、C地点は通れない。 (1) A地点を通る場合 (2) B地点を通る場合 (3) A地点とB地点の両方を通る場合

1. 問題の内容

東西に6本、南北に7本の道がある。O地点から出発し、P地点まで最短距離で行く経路について、以下の3つの場合に経路の数を求める。ただし、C地点は通れない。

(1) A地点を通る場合

(2) B地点を通る場合

(3) A地点とB地点の両方を通る場合

2. 解き方の手順

各地点への最短経路数を順に計算していく。ある地点への経路数は、その地点に到達できる左または下の地点への経路数の和となる。C地点は通れないことに注意する。

(1) A地点を通る場合

O地点からA地点までの最短経路数を求める。A地点までには、右に2回、上に3回移動する必要がある。したがって、経路数は$_{2+3}C_2 = {}_5C_2 = \frac{5!}{2!3!} = \frac{5 \times 4}{2 \times 1} = 10$通り。

A地点からP地点までの最短経路数を求める。P地点までには、右に3回、上に4回移動する必要がある。したがって、経路数は$_{3+4}C_3 = {}_7C_3 = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$通り。

したがって、O地点からA地点を通りP地点までの最短経路数は、$10 \times 35 = 350$通り。

(2) B地点を通る場合

O地点からB地点までの最短経路数を求める。B地点までには、右に0回、上に4回移動する必要がある。したがって、経路数は$_{0+4}C_0 = {}_4C_0 = 1$通り。

B地点からP地点までの最短経路数を求める。P地点までには、右に5回、上に3回移動する必要がある。したがって、経路数は$_{5+3}C_5 = {}_8C_5 = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$通り。

したがって、O地点からB地点を通りP地点までの最短経路数は、$1 \times 56 = 56$通り。

(3) A地点とB地点の両方を通る場合

A地点とB地点の両方を通るためには、O地点からA地点へ行き、そこからB地点へ行くか、またはO地点からB地点へ行き、そこからA地点へ行く必要がある。ただし、O地点からA地点、B地点の順に行くことはできないため、AからBを経由してPに行くしかない。

O地点からA地点までの経路数は10通り(上記参照)。

A地点からB地点までの最短経路数を求める。この時、C地点は通れないことに注意する。

AからBまでには、左に2回、下に1回移動する必要があるが、C地点を通らない経路を考える必要がある。

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

A地点からB地点へC地点を通らずにたどり着くルートは、A地点からC地点を通ってB地点へたどり着くルートを除けば良い。しかし、AからBへの最短経路は、Cを通らずにBへ行ける。そのため、最短経路をそのまま計算できる。

B地点からP地点までの経路数は56通り(上記参照)。

したがって、O地点からA地点とB地点を通りP地点までの最短経路数は、$10 \times 2 \times 56 = 1120$通り。

3. 最終的な答え

(1) 350通り

(2) 56通り

(3) 1120通り