右の図のような道のある町で、PからQまで遠回りをしないで行く。次のそれぞれの条件における道順の総数を求めよ。 (1) Rを通って行く。 (2) ×印の箇所を通らないで行く。 (3) Rを通り、×印の箇所を通らないで行く。

1. 問題の内容

右の図のような道のある町で、PからQまで遠回りをしないで行く。次のそれぞれの条件における道順の総数を求めよ。

(1) Rを通って行く。

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

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

2. 解き方の手順

(1) PからRまでの最短経路の数と、RからQまでの最短経路の数をそれぞれ求め、それらを掛け合わせる。

PからRまでの最短経路は、右に2回、下に2回進むので、$\frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ 通り。

RからQまでの最短経路は、右に3回、下に5回進むので、$\frac{8!}{3!5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$ 通り。

よって、PからRを通りQまで行く最短経路は、$6 \times 56 = 336$ 通り。

(2) PからQまでの最短経路の総数を求め、そこから×印の箇所を通る経路の数を引く。

PからQまでの最短経路は、右に5回、下に7回進むので、$\frac{12!}{5!7!} = \frac{12 \times 11 \times 10 \times 9 \times 8}{5 \times 4 \times 3 \times 2 \times 1} = 792$ 通り。

×印の箇所をXとおくと、

PからXまでの最短経路は、右に3回、下に4回進むので、$\frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ 通り。

XからQまでの最短経路は、右に2回、下に3回進むので、$\frac{5!}{2!3!} = \frac{5 \times 4}{2 \times 1} = 10$ 通り。

よって、PからXを通りQまで行く最短経路は、$35 \times 10 = 350$ 通り。

したがって、PからQまで行く最短経路のうち、Xを通らないのは、$792 - 350 = 442$ 通り。

(3) Rを通り、かつ×印を通る経路の数を求め、(1)の結果から引く。

Rを通り×印を通る経路を考えると、

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

RからXまでは、右に1回、下に2回進むので、$\frac{3!}{1!2!} = \frac{3}{1} = 3$ 通り。

XからQまでは(2)より10通り。

よって、PからR、Xを通りQまで行く最短経路は、$6 \times 3 \times 10 = 180$ 通り。

したがって、Rを通り、×印を通らないのは、$336 - 180 = 156$ 通り。

3. 最終的な答え

(1) 336通り

(2) 442通り

(3) 156通り