右図のような道のある地域で、以下の問いに答える問題です。 (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までの最短経路は、右に5回、下に3回移動することで到達できます。

したがって、8回の移動のうち、右への移動を5回選ぶ組み合わせの数、または下への移動を3回選ぶ組み合わせの数を計算すればよいです。

組み合わせの公式は $nCr = \frac{n!}{r!(n-r)!}$ です。

AからBまでの最短経路数は、

$_8C_5 = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$ 通りです。

(2) AからCを通ってBまで行くには、まずAからCまで行き、次にCからBまで行く必要があります。

AからCまでは、右に1回、下に2回移動します。

したがって、3回の移動のうち、右への移動を1回選ぶ組み合わせの数、または下への移動を2回選ぶ組み合わせの数を計算すればよいです。

AからCまでの最短経路数は、

$_3C_1 = \frac{3!}{1!2!} = \frac{3 \times 2 \times 1}{1 \times 2 \times 1} = 3$ 通りです。

CからBまでは、右に4回、下に1回移動します。

したがって、5回の移動のうち、右への移動を4回選ぶ組み合わせの数、または下への移動を1回選ぶ組み合わせの数を計算すればよいです。

CからBまでの最短経路数は、

$_5C_4 = \frac{5!}{4!1!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{4 \times 3 \times 2 \times 1 \times 1} = 5$ 通りです。

したがって、AからCを通ってBまで行く最短経路数は、

$3 \times 5 = 15$ 通りです。

(3) AからCを通らずにBまで行く最短経路数は、AからBまでのすべての最短経路数から、AからCを通ってBまで行く最短経路数を引けば求められます。

したがって、AからCを通らずにBまで行く最短経路数は、

$56 - 15 = 41$ 通りです。

3. 最終的な答え

(1) 56通り

(2) 15通り

(3) 41通り