碁盤の目状の道路がある街において、地点Aから地点Bまで最短経路で移動する場合の道順の数を、以下の条件でそれぞれ求める。 (1) 全ての道順 (2) 地点Cを通る道順 (3) 地点Pを通らない道順 (4) 地点Pも地点Qも通らない道順

1. 問題の内容

碁盤の目状の道路がある街において、地点Aから地点Bまで最短経路で移動する場合の道順の数を、以下の条件でそれぞれ求める。

(1) 全ての道順

(2) 地点Cを通る道順

(3) 地点Pを通らない道順

(4) 地点Pも地点Qも通らない道順

2. 解き方の手順

地点Aから地点Bまで、右に $m$ 回、上に $n$ 回移動する必要がある場合、最短経路の総数は二項係数 ${}_{m+n}C_{m}$（または ${}_{m+n}C_{n}$）で表される。これは、全部で $m+n$ 回の移動のうち、右への移動を $m$ 回選択する組み合わせの数である。${}_{m+n}C_m = \frac{(m+n)!}{m!n!}$で計算できる。

(1) 全ての道順

地点Aから地点Bまでは、右に5回、上に4回移動する必要がある。したがって、全ての道順の数は

${}_{5+4}C_{5} = {}_{9}C_{5} = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$通り。

(2) 地点Cを通る道順

地点Aから地点Cまでは、右に1回、上に2回移動する必要がある。したがって、地点Aから地点Cまでの道順の数は

${}_{1+2}C_{1} = {}_{3}C_{1} = \frac{3!}{1!2!} = 3$通り。

地点Cから地点Bまでは、右に4回、上に2回移動する必要がある。したがって、地点Cから地点Bまでの道順の数は

${}_{4+2}C_{4} = {}_{6}C_{4} = {}_{6}C_{2} = \frac{6!}{4!2!} = \frac{6 \times 5}{2 \times 1} = 15$通り。

地点Cを通る道順の数は、地点Aから地点Cまでの道順の数と地点Cから地点Bまでの道順の数の積である。

$3 \times 15 = 45$通り。

(3) 地点Pを通らない道順

地点Aから地点Pまでは、右に2回、上に3回移動する必要がある。したがって、地点Aから地点Pまでの道順の数は

${}_{2+3}C_{2} = {}_{5}C_{2} = \frac{5!}{2!3!} = \frac{5 \times 4}{2 \times 1} = 10$通り。

地点Pから地点Bまでは、右に3回、上に1回移動する必要がある。したがって、地点Pから地点Bまでの道順の数は

${}_{3+1}C_{3} = {}_{4}C_{3} = {}_{4}C_{1} = \frac{4!}{3!1!} = 4$通り。

地点Pを通る道順の数は、地点Aから地点Pまでの道順の数と地点Pから地点Bまでの道順の数の積である。

$10 \times 4 = 40$通り。

地点Pを通らない道順の数は、全ての道順の数から地点Pを通る道順の数を引いたものである。

$126 - 40 = 86$通り。

(4) 地点Pも地点Qも通らない道順

地点Aから地点Qまでは、右に3回、上に3回移動する必要がある。したがって、地点Aから地点Qまでの道順の数は

${}_{3+3}C_{3} = {}_{6}C_{3} = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$通り。

地点Qから地点Bまでは、右に2回、上に1回移動する必要がある。したがって、地点Qから地点Bまでの道順の数は

${}_{2+1}C_{2} = {}_{3}C_{2} = {}_{3}C_{1} = \frac{3!}{2!1!} = 3$通り。

地点Qを通る道順の数は、地点Aから地点Qまでの道順の数と地点Qから地点Bまでの道順の数の積である。

$20 \times 3 = 60$通り。

地点Pと地点Qの両方を通る道順の数を求める。

地点Aから地点Pまでの道順の数は${}_5C_2 = 10$通り。

地点Pから地点Qまでは、右に1回、上に0回移動する必要がある。したがって、地点Pから地点Qまでの道順の数は

${}_{1+0}C_{1} = 1$通り。

地点Qから地点Bまでは、右に2回、上に1回移動する必要がある。したがって、地点Qから地点Bまでの道順の数は

${}_{2+1}C_{2} = 3$通り。

地点PとQの両方を通る道順の数は、$10 \times 1 \times 3 = 30$通り。

地点PまたはQを通る道順の数は、地点Pを通る道順の数と地点Qを通る道順の数を足し、PとQの両方を通る道順の数を引いたものである。

$40 + 60 - 30 = 70$通り。

地点Pも地点Qも通らない道順の数は、全ての道順の数から地点PまたはQを通る道順の数を引いたものである。

$126 - 70 = 56$通り。

3. 最終的な答え

(1) 全ての道順：126通り

(2) 地点Cを通る道順：45通り

(3) 地点Pを通らない道順：86通り

(4) 地点Pも地点Qも通らない道順：56通り