図のような道路がある町で、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回進むので、最短経路の数は

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

RからQまでは、右に3回、下に4回進むので、最短経路の数は

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

したがって、Rを通って行く最短経路の数は

$3 \times 35 = 105$

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

まず、PからQまでの最短経路の総数を求めます。

PからQまでは、右に5回、下に5回進むので、最短経路の総数は

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

次に、×印の箇所を通る最短経路の数を求めます。

Pから×印の箇所までは、右に3回、上に2回進むので、最短経路の数は

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

×印の箇所からQまでは、右に2回、下に3回進むので、最短経路の数は

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

したがって、×印の箇所を通る最短経路の数は

$10 \times 10 = 100$

したがって、×印の箇所を通らない最短経路の数は

$252 - 100 = 152$

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

Rを通って行く経路の総数は(1)で求めた105通りです。

次に、Rを通り、かつ×印を通る経路の数を求めます。

PからRまでは(1)より3通り

Rから×印までは、右に1回、下に1回進むので、最短経路の数は

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

×印からQまでは(2)より10通り

したがって、Rを通り、×印を通る経路の数は

$3 \times 2 \times 10 = 60$

したがって、Rを通り、×印を通らない経路の数は

$105 - 60 = 45$

3. 最終的な答え

(1) Rを通って行く場合の数: 105通り

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

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