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

AからBまでは、右に5回、上に2回移動するので、合計7回の移動が必要です。このうち、上への移動を2回選ぶ組み合わせの数が経路の数となります。

AからBへの経路数は、

$_7C_2 = \frac{7!}{2!5!} = \frac{7 \times 6}{2 \times 1} = 21$ 通り

BからDまでは、右に1回、上に4回移動するので、合計5回の移動が必要です。このうち、上への移動を4回選ぶ組み合わせの数が経路の数となります。

BからDへの経路数は、

$_5C_4 = \frac{5!}{4!1!} = \frac{5}{1} = 5$ 通り

よって、AからBを通ってDまで行く経路数は、

$21 \times 5 = 105$ 通り

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

A地点からC地点までの最短経路の数と、C地点からD地点までの最短経路の数をそれぞれ求め、それらを掛け合わせます。

AからCまでは、右に4回、上に3回移動するので、合計7回の移動が必要です。このうち、上への移動を3回選ぶ組み合わせの数が経路の数となります。

AからCへの経路数は、

$_7C_3 = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ 通り

CからDまでは、右に2回、上に1回移動するので、合計3回の移動が必要です。このうち、上への移動を1回選ぶ組み合わせの数が経路の数となります。

CからDへの経路数は、

$_3C_1 = \frac{3!}{1!2!} = \frac{3}{1} = 3$ 通り

よって、AからCを通ってDまで行く経路数は、

$35 \times 3 = 105$ 通り

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

A地点からD地点までは、右に6回、上に5回移動するので、合計11回の移動が必要です。このうち、上への移動を5回選ぶ組み合わせの数が経路の数となります。

AからDへの経路数は、

$_{11}C_5 = \frac{11!}{5!6!} = \frac{11 \times 10 \times 9 \times 8 \times 7}{5 \times 4 \times 3 \times 2 \times 1} = 11 \times 3 \times 2 \times 7 = 462$ 通り

3. 最終的な答え

(1) A地点からB地点を通ってD地点まで行く経路数は、105通りです。

(2) A地点からC地点を通ってD地点まで行く経路数は、105通りです。

(3) A地点からD地点まで行く経路数は、462通りです。