与えられた道のある町で、A地点からD地点まで最短経路で行く場合の数を、以下の条件で求める問題です。 (1) A地点からB地点を通ってD地点まで行く場合の数 (2) A地点からC地点を通ってD地点まで行く場合の数 (3) A地点からD地点まで行く場合の数

1. 問題の内容

与えられた道のある町で、A地点からD地点まで最短経路で行く場合の数を、以下の条件で求める問題です。

(1) A地点からB地点を通ってD地点まで行く場合の数

(2) A地点からC地点を通ってD地点まで行く場合の数

(3) A地点からD地点まで行く場合の数

2. 解き方の手順

最短経路の総数は、右に進む回数と上に進む回数が決まれば一意に定まります。これは組み合わせの問題として解くことができます。

(1) A地点からB地点を通ってD地点まで行く場合

* A地点からB地点までの最短経路の数を求めます。AからBへは右に3回、上に1回移動するので、合計4回の移動のうち、右方向への移動を3回選ぶ組み合わせを考えます。これは $_4C_3 = \frac{4!}{3!1!} = 4$ 通りです。

* B地点からD地点までの最短経路の数を求めます。BからDへは右に1回、上に2回移動するので、合計3回の移動のうち、右方向への移動を1回選ぶ組み合わせを考えます。これは $_3C_1 = \frac{3!}{1!2!} = 3$ 通りです。

* A地点からB地点を通ってD地点まで行く最短経路の数は、AからBまでの経路数とBからDまでの経路数を掛け合わせたものです。

(2) A地点からC地点を通ってD地点まで行く場合

* A地点からC地点までの最短経路の数を求めます。AからCへは右に2回、上に2回移動するので、合計4回の移動のうち、右方向への移動を2回選ぶ組み合わせを考えます。これは $_4C_2 = \frac{4!}{2!2!} = 6$ 通りです。

* C地点からD地点までの最短経路の数を求めます。CからDへは右に2回、上に2回移動するので、合計4回の移動のうち、右方向への移動を2回選ぶ組み合わせを考えます。これは $_4C_2 = \frac{4!}{2!2!} = 6$ 通りです。

* A地点からC地点を通ってD地点まで行く最短経路の数は、AからCまでの経路数とCからDまでの経路数を掛け合わせたものです。

(3) A地点からD地点まで行く場合

* A地点からD地点までの最短経路の数を求めます。AからDへは右に4回、上に4回移動するので、合計8回の移動のうち、右方向への移動を4回選ぶ組み合わせを考えます。これは $_8C_4 = \frac{8!}{4!4!} = 70$ 通りです。

3. 最終的な答え

(1) A地点からB地点を通ってD地点まで行く最短経路は $4 \times 3 = 12$ 通り。

(2) A地点からC地点を通ってD地点まで行く最短経路は $6 \times 6 = 36$ 通り。

(3) A地点からD地点まで行く最短経路は $70$ 通り。