右の図のような道がある。 (1) PからQまで行く最短の道順は何通りあるか。 (2) Rを通ってPからQまで行く最短の道順は何通りあるか。 (3) Xを通らずにPからQまで行く最短の道順は何通りあるか。

1. 問題の内容

右の図のような道がある。

(1) PからQまで行く最短の道順は何通りあるか。

(2) Rを通ってPからQまで行く最短の道順は何通りあるか。

(3) Xを通らずにPからQまで行く最短の道順は何通りあるか。

2. 解き方の手順

(1) PからQまで行くためには、右に5回、上に4回移動する必要がある。したがって、9回の移動のうち、右への移動を5回選ぶ場合の数を計算すればよい。これは、9個のものから5個を選ぶ組み合わせの数 $_9C_5$ で表される。

$_9C_5 = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$

(2) Rを通ってPからQまで行くためには、まずPからRまで行き、次にRからQまで行く必要がある。PからRへは右に2回、上に3回移動する必要がある。したがって、5回の移動のうち、右への移動を2回選ぶ場合の数を計算すればよい。これは、5個のものから2個を選ぶ組み合わせの数 $_5C_2$ で表される。

$_5C_2 = \frac{5!}{2!3!} = \frac{5 \times 4}{2 \times 1} = 10$

次に、RからQへは右に3回、上に1回移動する必要がある。したがって、4回の移動のうち、右への移動を3回選ぶ場合の数を計算すればよい。これは、4個のものから3個を選ぶ組み合わせの数 $_4C_3$ で表される。

$_4C_3 = \frac{4!}{3!1!} = 4$

よって、Rを通ってPからQまで行く最短の道順は、

$10 \times 4 = 40$ 通り。

(3) Xを通らずにPからQまで行く最短の道順は、PからQまでのすべての道順から、Xを通る道順を引けばよい。PからQまでの道順は(1)で計算した通り126通りである。

PからXまでは、右に1回、上に1回移動する必要がある。したがって、2回の移動のうち、右への移動を1回選ぶ場合の数を計算すればよい。これは、2個のものから1個を選ぶ組み合わせの数 $_2C_1$ で表される。

$_2C_1 = \frac{2!}{1!1!} = 2$

XからQまでは、右に4回、上に3回移動する必要がある。したがって、7回の移動のうち、右への移動を4回選ぶ場合の数を計算すればよい。これは、7個のものから4個を選ぶ組み合わせの数 $_7C_4$ で表される。

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

よって、Xを通るPからQまでの最短の道順は、

$2 \times 35 = 70$ 通り。

したがって、Xを通らずにPからQまで行く最短の道順は、

$126 - 30 = 96$ 通り。

126 - 70 = 56通り。

3. 最終的な答え

(1) 126通り

(2) 40通り

(3) 56通り