右のような街路で、点Pから点Qまで行く最短経路について、以下の問いに答えます。 (1) 総数は何通りあるか。 (2) 点Rを通る経路は何通りあるか。 (3) 点Rは通るが点Sは通らない経路は何通りあるか。

1. 問題の内容

右のような街路で、点Pから点Qまで行く最短経路について、以下の問いに答えます。

(1) 総数は何通りあるか。

(2) 点Rを通る経路は何通りあるか。

(3) 点Rは通るが点Sは通らない経路は何通りあるか。

2. 解き方の手順

(1) 総数について

点Pから点Qへ行く最短経路は、右に7回、上に4回移動する必要があります。

これは、合計11回の移動のうち、右への移動7回を選ぶ組み合わせの数に等しくなります。

したがって、総数は$_{11}C_7$で計算できます。

$_{11}C_7 = \frac{11!}{7!4!} = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1} = 11 \times 10 \times 3 = 330$

(2) 点Rを通る経路について

点Pから点Rへ行く最短経路は、右に2回、上に1回移動する必要があります。その経路数は$_{3}C_2=3$通りです。

点Rから点Qへ行く最短経路は、右に5回、上に3回移動する必要があります。その経路数は$_{8}C_5 = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$通りです。

したがって、点Rを通る経路の総数は、$3 \times 56 = 168$通りです。

(3) 点Rは通るが点Sは通らない経路について

点Rを通る経路の総数は168通りでした。

次に、点Rと点Sの両方を通る経路の数を計算します。

点Pから点Rへ行く経路数は3通りです。

点Rから点Sへ行く最短経路は、右に1回、上に1回移動する必要があります。その経路数は$_{2}C_1=2$通りです。

点Sから点Qへ行く最短経路は、右に4回、上に2回移動する必要があります。その経路数は$_{6}C_4 = \frac{6!}{4!2!} = \frac{6 \times 5}{2 \times 1} = 15$通りです。

したがって、点Rと点Sの両方を通る経路の総数は、$3 \times 2 \times 15 = 90$通りです。

点Rを通るが点Sは通らない経路の数は、点Rを通る経路の総数から点Rと点Sの両方を通る経路の数を引いたものです。

$168 - 90 = 78$通りです。

3. 最終的な答え

(1) 総数: 330通り

(2) Rを通る経路: 168通り

(3) Rは通るがSは通らない経路: 78通り