与えられた図の道順において、以下の3つの場合における最短経路の数を求める。 (1) PからQまでの最短経路の数 (2) PからRを通ってQまでの最短経路の数 (3) PからX印の箇所を通らずにQまでの最短経路の数

1. 問題の内容

与えられた図の道順において、以下の3つの場合における最短経路の数を求める。

(1) PからQまでの最短経路の数

(2) PからRを通ってQまでの最短経路の数

(3) PからX印の箇所を通らずにQまでの最短経路の数

2. 解き方の手順

(1) PからQまでの最短経路の数

PからQへ行くには、右に6回、下に5回移動する必要がある。これは、合計11回の移動のうち、右への移動6回を選ぶ組み合わせと同じである。

したがって、経路の数は、

$_{11}C_6 = \frac{11!}{6!5!} = \frac{11 \times 10 \times 9 \times 8 \times 7}{5 \times 4 \times 3 \times 2 \times 1} = 11 \times 3 \times 2 \times 7 = 462$

(2) PからRを通ってQまでの最短経路の数

PからRへの最短経路の数は、右に2回、下に1回移動する必要があるので、

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

RからQへの最短経路の数は、右に4回、下に4回移動する必要があるので、

$_{8}C_4 = \frac{8!}{4!4!} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 2 \times 7 \times 5 = 70$

したがって、PからRを通ってQまでの最短経路の数は、

$3 \times 70 = 210$

(3) PからX印の箇所を通らずにQまでの最短経路の数

PからQへの最短経路の総数は462通り。（1）より。

PからXを通ってQへの最短経路の数を考える。

PからXへの最短経路の数は、右に5回、下に2回移動する必要があるので、

$_{7}C_5 = \frac{7!}{5!2!} = \frac{7 \times 6}{2 \times 1} = 21$

XからQへの最短経路の数は、右に1回、下に3回移動する必要があるので、

$_{4}C_1 = \frac{4!}{1!3!} = 4$

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

$21 \times 4 = 84$

PからX印の箇所を通らずにQまでの最短経路の数は、

$462 - 84 = 378$

3. 最終的な答え

(1) 462通り

(2) 210通り

(3) 378通り

Provided answer (3) is wrong in this case, which should be 378 instead of

3

6

2. I will edit the solution accordingly.

1. 問題の内容

与えられた図の道順において、以下の3つの場合における最短経路の数を求める。

(1) PからQまでの最短経路の数

(2) PからRを通ってQまでの最短経路の数

(3) PからX印の箇所を通らずにQまでの最短経路の数

2. 解き方の手順

(1) PからQまでの最短経路の数

PからQへ行くには、右に6回、下に5回移動する必要がある。これは、合計11回の移動のうち、右への移動6回を選ぶ組み合わせと同じである。

したがって、経路の数は、

$_{11}C_6 = \frac{11!}{6!5!} = \frac{11 \times 10 \times 9 \times 8 \times 7}{5 \times 4 \times 3 \times 2 \times 1} = 11 \times 3 \times 2 \times 7 = 462$

(2) PからRを通ってQまでの最短経路の数

PからRへの最短経路の数は、右に2回、下に1回移動する必要があるので、

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

RからQへの最短経路の数は、右に4回、下に4回移動する必要があるので、

$_{8}C_4 = \frac{8!}{4!4!} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 2 \times 7 \times 5 = 70$

したがって、PからRを通ってQまでの最短経路の数は、

$3 \times 70 = 210$

(3) PからX印の箇所を通らずにQまでの最短経路の数

PからQへの最短経路の総数は462通り。（1）より。

PからXを通ってQへの最短経路の数を考える。

PからXへの最短経路の数は、右に5回、下に2回移動する必要があるので、

$_{7}C_5 = \frac{7!}{5!2!} = \frac{7 \times 6}{2 \times 1} = 21$

XからQへの最短経路の数は、右に1回、下に3回移動する必要があるので、

$_{4}C_1 = \frac{4!}{1!3!} = 4$

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

$21 \times 4 = 84$

PからX印の箇所を通らずにQまでの最短経路の数は、

$462 - 84 = 378$

3. 最終的な答え

(1) 462通り

(2) 210通り

(3) 378通り