右図のような道のある町で、以下の各場合に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地点までの最短経路の数と、B地点からD地点までの最短経路の数をそれぞれ求め、それらを掛け合わせることで、A地点からB地点を通ってD地点まで行く最短経路の総数を求めます。

A地点からB地点へは、右に2回、上に5回移動するので、合計7回の移動でB地点に到達します。

経路数は、7回の移動のうち、右への移動2回を選ぶ組み合わせなので、$_7C_2 = \frac{7!}{2!5!} = \frac{7 \times 6}{2 \times 1} = 21$ 通りです。

B地点からD地点へは、右に3回、上に0回移動するので、最短経路は1通りです。

したがって、A地点からB地点を通ってD地点まで行く最短経路は $21 \times 1 = 21$ 通りです。

(2) A地点からC地点までの最短経路の数と、C地点からD地点までの最短経路の数をそれぞれ求め、それらを掛け合わせることで、A地点からC地点を通ってD地点まで行く最短経路の総数を求めます。

A地点からC地点へは、右に2回、上に3回移動するので、合計5回の移動でC地点に到達します。

経路数は、5回の移動のうち、右への移動2回を選ぶ組み合わせなので、$_5C_2 = \frac{5!}{2!3!} = \frac{5 \times 4}{2 \times 1} = 10$ 通りです。

C地点からD地点へは、右に3回、上に2回移動するので、合計5回の移動でD地点に到達します。

経路数は、5回の移動のうち、右への移動3回を選ぶ組み合わせなので、$_5C_3 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$ 通りです。

したがって、A地点からC地点を通ってD地点まで行く最短経路は $10 \times 10 = 100$ 通りです。

(3) A地点からD地点までの最短経路の数を求めます。

A地点からD地点へは、右に5回、上に5回移動するので、合計10回の移動でD地点に到達します。

経路数は、10回の移動のうち、右への移動5回を選ぶ組み合わせなので、$_{10}C_5 = \frac{10!}{5!5!} = \frac{10 \times 9 \times 8 \times 7 \times 6}{5 \times 4 \times 3 \times 2 \times 1} = 252$ 通りです。

3. 最終的な答え

(1) 21通り

(2) 100通り

(3) 252通り