格子状の道において、点Pから点Qへ行く最短経路の総数、点Rを通る最短経路の数、点Rを通り点Sを通らない最短経路の数、そして点Rと点Sのどちらも通らない最短経路の数を求める問題です。

1. 問題の内容

格子状の道において、点Pから点Qへ行く最短経路の総数、点Rを通る最短経路の数、点Rを通り点Sを通らない最短経路の数、そして点Rと点Sのどちらも通らない最短経路の数を求める問題です。

2. 解き方の手順

まず、PからQへの最短経路の総数を計算します。次に、Rを通る最短経路の数を計算します。さらに、Rを通りSを通る経路の数を計算し、Rを通る経路の数から引くことで、Rを通りSを通らない経路の数を求めます。最後に、PからQへのすべての経路から、Rを通る経路、Sを通る経路を引きます。ただし、RとSの両方を通る経路は二重に引かれているので、最後にそれを足し戻します。

* PからQへの最短経路の総数:

右に5回、上に5回移動するので、合計10回の移動が必要です。したがって、最短経路の数は ${}_{10}C_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からRへの最短経路の数:

右に2回、上に1回移動するので、${}_3C_2 = \frac{3!}{2!1!} = 3$通りです。

* RからQへの最短経路の数:

右に3回、上に4回移動するので、${}_7C_3 = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$通りです。

* PからRを経由してQへの最短経路の数:

$3 \times 35 = 105$通りです。

* PからSへの最短経路の数:

右に3回、上に3回移動するので、${}_6C_3 = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$通りです。

* SからQへの最短経路の数:

右に2回、上に2回移動するので、${}_4C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通りです。

* PからSを経由してQへの最短経路の数:

$20 \times 6 = 120$通りです。

* PからRを経由してSへの最短経路の数：

PからRは3通り。RからSは右に1回、上に2回なので${}_3C_1 = 3$通り。よって、$3 \times 3 = 9$通り

* SからQは6通りなので、PからR,Sを経由してQへの最短経路の数：

$9 \times 6 = 54$通り

* Rを通りSを通らない経路の数：Rを通る経路数からR,Sを通る経路数を引く

$105 - 54 = 51$通り

* RもSも通らない経路の数：全体からRを通る経路とSを通る経路を引いて、R,S両方を通る経路を足す

$252 - 105 - 120 + 54 = 81$通り

3. 最終的な答え

* PからQへの最短経路は全部で 252 通り

* Rを通るものは 105 通り

* Rを通り、Sを通らないものは 51 通り

* R, Sをともに通らないものは 81 通り