格子状の道において、点Pから点Qへの最短経路の総数、点Rを通る経路数、点Rを通って点Sを通らない経路数、点Rと点Sの両方を通らない経路数をそれぞれ求める問題です。

1. 問題の内容

格子状の道において、点Pから点Qへの最短経路の総数、点Rを通る経路数、点Rを通って点Sを通らない経路数、点Rと点Sの両方を通らない経路数をそれぞれ求める問題です。

2. 解き方の手順

まず、各点間の最短経路数を計算します。

ある点Aから点Bへの最短経路数は、AからBへ右に$x$回、上に$y$回移動する場合の数であるため、$_{x+y}C_{x}$または$_{x+y}C_{y}$で計算できます。

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

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

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

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

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

$\binom{1+2}{1} = \binom{3}{1} = \frac{3!}{1!2!} = 3$通りです。

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

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

$\binom{3+3}{3} = \binom{6}{3} = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$通りです。

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

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

$\binom{3+2}{3} = \binom{5}{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$通りです。

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

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

$\binom{1+3}{1} = \binom{4}{1} = 4$通りです。

(1) **点Rを通る経路数:**

PからRを通ってQへ行く経路数は、PからRへの経路数とRからQへの経路数の積で計算できます。

$3 \times 20 = 60$通りです。

**点Rを通り、点Sを通らない経路数:**

点Rを通り、点Sも通る経路数は、PからRへ行き、RからSへ行き、SからQへ行く経路数です。

RからSへの経路数は、右に2回、上に0回なので、$\binom{2}{2} = 1$通りです。

PからRを通ってSを通ってQへ行く経路数は、$3 \times 1 \times 4 = 12$通りです。

したがって、Rを通ってSを通らない経路数は、$60 - 12 = 48$通りです。

(2) **点Rと点Sの両方を通らない経路数:**

全体からRを通る経路とSを通る経路を引けば良さそうですが、RとSの両方を通る経路を二重に引いてしまうので、足し戻す必要があります。

* PからSを通ってQへ行く経路数は、$10 \times 4 = 40$通りです。

RもSも通らない経路数 = 全体の経路数 - Rを通る経路数 - Sを通る経路数 + RもSも通る経路数

= $126 - 60 - 40 + 12 = 38$通りです。

3. 最終的な答え

* アイウ: 126

* エオカ: 60

* キク: 48

* ケコ: 38