右図のような道路のある町で、A地点からB地点まで最短経路で行く場合について、以下の2つの問いに答える問題です。 (1) A地点からB地点までの最短経路は全部で何通りあるか。 (2) A地点からB地点までの最短経路のうち、C地点を通るものは何通りあるか。

1. 問題の内容

右図のような道路のある町で、A地点からB地点まで最短経路で行く場合について、以下の2つの問いに答える問題です。

(1) A地点からB地点までの最短経路は全部で何通りあるか。

(2) A地点からB地点までの最短経路のうち、C地点を通るものは何通りあるか。

2. 解き方の手順

(1) A地点からB地点までの最短経路の総数を求める。

AからBまでの移動は、右に6回、上に3回移動する必要がある。

したがって、全部で9回の移動のうち、右への移動を6回選ぶ場合の数に等しい。

これは組み合わせで計算できる。

$${9 \choose 6} = \frac{9!}{6!3!} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 3 \times 4 \times 7 = 84$$

(2) A地点からC地点を通ってB地点までの最短経路の数を求める。

まず、AからCまでの最短経路の数を求める。

AからCまでの移動は、右に2回、上に1回移動する必要がある。

したがって、全部で3回の移動のうち、右への移動を2回選ぶ場合の数に等しい。

$${3 \choose 2} = \frac{3!}{2!1!} = 3$$

次に、CからBまでの最短経路の数を求める。

CからBまでの移動は、右に4回、上に2回移動する必要がある。

したがって、全部で6回の移動のうち、右への移動を4回選ぶ場合の数に等しい。

$${6 \choose 4} = \frac{6!}{4!2!} = \frac{6 \times 5}{2 \times 1} = 15$$

AからCを通ってBへ行く経路の数は、AからCへの経路の数とCからBへの経路の数を掛け合わせたものになる。

$$3 \times 15 = 45$$

3. 最終的な答え

(1) A地点からB地点までの最短経路は全部で84通り

(2) A地点からB地点までの最短経路のうち、C地点を通るものは45通り