右図のような道において、以下の問いに答えます。 (1) AからBまでの最短経路は何通りあるか。 (2) AからBまでの最短経路のうち、Pを通らないものは何通りあるか。

1. 問題の内容

右図のような道において、以下の問いに答えます。

(1) AからBまでの最短経路は何通りあるか。

(2) AからBまでの最短経路のうち、Pを通らないものは何通りあるか。

2. 解き方の手順

(1) AからBまでの最短経路の総数を求めます。

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

したがって、最短経路の総数は、7回の移動のうち、右への移動4回を選ぶ組み合わせの数に等しくなります。

これは、組み合わせの公式を用いて計算できます。

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

(2) Pを通る経路の数を求め、(1)から引くことでPを通らない経路の数を求めます。

AからPまでの最短経路は、右に2回、上に1回移動する必要があります。

したがって、AからPまでの最短経路の数は、3回の移動のうち、右への移動2回を選ぶ組み合わせの数に等しくなります。

${}_3 C_2 = \frac{3!}{2!1!} = 3$

PからBまでの最短経路は、右に2回、上に2回移動する必要があります。

したがって、PからBまでの最短経路の数は、4回の移動のうち、右への移動2回を選ぶ組み合わせの数に等しくなります。

${}_4 C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$

したがって、AからPを経由してBまでの最短経路の数は、AからPまでの経路の数とPからBまでの経路の数を掛け合わせたものになります。

$3 \times 6 = 18$

Pを通らないAからBへの最短経路の数は、AからBへの最短経路の総数からPを通る経路の数を引いたものです。

$35 - 18 = 17$

3. 最終的な答え

(1) 35通り

(2) 17通り