図のような道があるとき、以下の問いに答える問題です。 (1) PからQまで行く最短の道順は何通りあるか。 (2) Xを通らずにPからQまで行く最短の道順は何通りあるか。

1. 問題の内容

図のような道があるとき、以下の問いに答える問題です。

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

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

2. 解き方の手順

(1) PからQまで行く最短の道順は、右に5回、上に4回移動する必要があります。したがって、9回の移動のうち、右に移動する5回を選ぶ組み合わせの数を求めればよいです。

これは、9個の中から5個を選ぶ組み合わせなので、 $_9C_5$ で計算できます。

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

(2) Xを通る道順の総数を求め、(1)で求めた総数からそれを引けば、Xを通らない道順の総数が求められます。

まず、PからXまで行く最短経路は、右に2回、上に3回移動する必要があります。これは、5回の移動のうち、右に移動する2回を選ぶ組み合わせなので、 $_5C_2$ で計算できます。

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

次に、XからQまで行く最短経路は、右に3回、上に1回移動する必要があります。これは、4回の移動のうち、右に移動する3回を選ぶ組み合わせなので、 $_4C_3$ で計算できます。

$_4C_3 = \frac{4!}{3!(4-3)!} = \frac{4!}{3!1!} = \frac{4}{1} = 4$

したがって、PからXを通りQまで行く最短経路は、

$10 \times 4 = 40$ 通りです。

求めるXを通らずにPからQまで行く最短経路は、

$126 - 40 = 86$通りです。

3. 最終的な答え

(1) 126 通り

(2) 86 通り