図のような道のある町で、PからQまで最短経路で行く場合の数を、以下の条件でそれぞれ求める問題です。 (1) Rを通って行く。 (2) ×印の箇所は通らないで行く。 (3) Rを通り、×印の箇所は通らないで行く。

1. 問題の内容

図のような道のある町で、PからQまで最短経路で行く場合の数を、以下の条件でそれぞれ求める問題です。

(1) Rを通って行く。

(2) ×印の箇所は通らないで行く。

(3) Rを通り、×印の箇所は通らないで行く。

2. 解き方の手順

(1) Rを通って行く場合

PからRまでの最短経路の数と、RからQまでの最短経路の数をそれぞれ計算し、それらを掛け合わせます。

PからRへは、右に2回、下に1回移動する必要があります。したがって、PからRへの最短経路の数は、

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

RからQへは、右に3回、下に3回移動する必要があります。したがって、RからQへの最短経路の数は、

$\frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$

よって、PからRを通ってQへ行く最短経路の数は、

$3 \times 20 = 60$

(2) ×印の箇所は通らないで行く場合

まず、PからQまでのすべての最短経路の数を計算します。次に、×印の箇所を通る最短経路の数を計算します。

最後に、すべての最短経路の数から×印の箇所を通る最短経路の数を引きます。

PからQへは、右に5回、下に4回移動する必要があります。したがって、PからQへの最短経路の総数は、

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

Pから×印の箇所へは、右に3回、下に2回移動する必要があります。したがって、Pから×印の箇所への最短経路の数は、

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

×印の箇所からQへは、右に2回、下に2回移動する必要があります。したがって、×印の箇所からQへの最短経路の数は、

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

したがって、Pから×印の箇所を通ってQへ行く最短経路の数は、

$10 \times 6 = 60$

したがって、PからQへ×印の箇所を通らずに行く最短経路の数は、

$126 - 60 = 66$

(3) Rを通り、×印の箇所は通らないで行く場合

PからRを通ってQへ行く最短経路の数から、PからRを通って×印の箇所を通ってQへ行く最短経路の数を引きます。

PからRへは、右に2回、下に1回移動する必要があります。したがって、PからRへの最短経路の数は、

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

Rから×印の箇所へは、右に1回、下に1回移動する必要があります。したがって、Rから×印の箇所への最短経路の数は、

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

×印の箇所からQへは、右に2回、下に2回移動する必要があります。したがって、×印の箇所からQへの最短経路の数は、

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

したがって、PからRを通って×印の箇所を通ってQへ行く最短経路の数は、

$3 \times 2 \times 6 = 36$

したがって、PからRを通り、×印の箇所を通らずにQへ行く最短経路の数は、

$60 - 36 = 24$

3. 最終的な答え

(1) 60通り

(2) 66通り

(3) 24通り