右の図のような道のある町で、AからBまでの最短経路の総数、Qを通る最短経路の総数、そしてPまたはQを通る最短経路の総数をそれぞれ求める問題です。

1. 問題の内容

右の図のような道のある町で、AからBまでの最短経路の総数、Qを通る最短経路の総数、そしてPまたはQを通る最短経路の総数をそれぞれ求める問題です。

2. 解き方の手順

まず、AからBまでの最短経路の総数を求めます。AからBへ行くには、右に4回、上に3回移動する必要があります。したがって、最短経路の総数は、7回の移動のうち右への移動を4回選ぶ組み合わせの数に等しくなります。これは組み合わせの記号を用いて ${}_7 C_4$ と表されます。

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

次に、AからQを通ってBまで行く最短経路の総数を求めます。AからQまでは、右に3回、上に1回移動する必要があります。その最短経路の総数は ${}_4 C_3 = \frac{4!}{3!1!} = 4$です。QからBまでは、右に1回、上に2回移動する必要があります。その最短経路の総数は ${}_3 C_1 = \frac{3!}{1!2!} = 3$です。したがって、AからQを通ってBまで行く最短経路の総数は、$4 \times 3 = 12$です。

次に、AからPを通ってBまで行く最短経路の総数を求めます。AからPまでは、右に2回、上に2回移動する必要があります。その最短経路の総数は ${}_4 C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$です。PからBまでは、右に2回、上に1回移動する必要があります。その最短経路の総数は ${}_3 C_2 = \frac{3!}{2!1!} = 3$です。したがって、AからPを通ってBまで行く最短経路の総数は、$6 \times 3 = 18$です。

最後に、PまたはQを通る最短経路の総数を求めます。これは、Pを通る経路の総数とQを通る経路の総数を足し、PとQの両方を通る経路の総数を引くことで計算できます。PとQの両方を通る最短経路の総数を求めます。AからPまでは${}_4 C_2 = 6$通り、PからQまでは、右に1回、上に-1回なので、Qへは上に移動することはできないので、PからQへは右へ２回移動してQに行くしかなく、${}_2 C_2 = 1$通りです。QからBへは${}_3 C_1 = 3$通りでした。したがって、AからPを通ってQを通り、Bまで行く最短経路の総数は、$6 \times 1 \times 3 = 18$です。

したがって、PまたはQを通る経路の総数は、$18 + 12 - 18 = 12$ です。

したがって、PまたはQを通る経路の総数は、$18 + 12 - (AからPに行ってからQに行くことはできない) = 18 + 12 - 0 = 30$です。

Pを通る経路数：18通り

Qを通る経路数：12通り

PかつQを通る経路数：A→P→Q→Bを通る経路を考える。AからPは6通り。PからQは、右に1、上に-1となるため、一度PからQへ移動することはできない。P→Qに移動するには、右に２移動するしか無い。

この経路数は6通りx1通りx3通り=18通り。

PまたはQを通る経路数は、Pを通る+Qを通る-PかつQを通る。

=18+12-0=30通り。

3. 最終的な答え

最短経路の総数: 35

Qを通る最短経路の総数: 12

PまたはQを通る最短経路の総数: 30

セ: 3

ソ: 5

タ: 1

チ: 2

ツ: 3

テ: 5

ト: 0