図のような道のある地域で、以下の最短経路の数を求めます。 (1) AからBまでの経路数 (2) AからCを通ってBまでの経路数 (3) AからCを通って、×印の道を通らずにBまでの経路数

1. 問題の内容

図のような道のある地域で、以下の最短経路の数を求めます。

(1) AからBまでの経路数

(2) AからCを通ってBまでの経路数

(3) AからCを通って、×印の道を通らずにBまでの経路数

2. 解き方の手順

(1) AからBまでの経路数

AからBへ行くには、右に5回、上に3回移動する必要があります。

したがって、全移動回数は8回です。

このうち、右への移動を5回選ぶ組み合わせの数が経路数となります。

これは、8回の移動の中から右への移動5回を選ぶ組み合わせ数に等しいので、

${}_8 \mathrm{C}_5 = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$通り

(2) AからCを通ってBまでの経路数

AからCへ行くには、右に2回、上に2回移動する必要があります。

したがって、全移動回数は4回です。

このうち、右への移動を2回選ぶ組み合わせの数が経路数となります。

これは、4回の移動の中から右への移動2回を選ぶ組み合わせ数に等しいので、

${}_4 \mathrm{C}_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通り

CからBへ行くには、右に3回、上に1回移動する必要があります。

したがって、全移動回数は4回です。

このうち、右への移動を3回選ぶ組み合わせの数が経路数となります。

これは、4回の移動の中から右への移動3回を選ぶ組み合わせ数に等しいので、

${}_4 \mathrm{C}_3 = \frac{4!}{3!1!} = 4$通り

したがって、AからCを通ってBまでの経路数は、

$6 \times 4 = 24$通り

(3) AからCを通って、×印の道を通らずにBまでの経路数

AからCまでの経路数は(2)より6通り。

CからBまでの全経路数は(2)より4通り。

Cから×印を通ってBへ行く経路数を求める。

Cから×印へは右に1回、上に0回移動するため、1通り。

×印からBへは右に2回、上に1回移動する必要があるため、経路数は ${}_3 \mathrm{C}_2 = 3$通り

したがって、Cから×印を通ってBへ行く経路数は、$1 \times 3 = 3$通り。

したがって、Cから×印を通らずにBへ行く経路数は、$4 - 3 = 1$通り。

したがって、AからCを通って、×印の道を通らずにBまでの経路数は、$6 \times 1 = 6$通り

3. 最終的な答え

(1) 56通り

(2) 24通り

(3) 6通り