右の図のような道がある町で、A地点からB地点まで最短距離で行く経路について、以下の3つの条件を満たす場合の数を求める問題です。 (1) P地点を通る場合 (2) P地点を通るが、Q地点を通らない場合 (3) R地点を通らない場合

1. 問題の内容

右の図のような道がある町で、A地点からB地点まで最短距離で行く経路について、以下の3つの条件を満たす場合の数を求める問題です。

(1) P地点を通る場合

(2) P地点を通るが、Q地点を通らない場合

(3) R地点を通らない場合

2. 解き方の手順

(1) P地点を通る場合

AからPまでの最短経路の数と、PからBまでの最短経路の数をそれぞれ計算し、掛け合わせます。

AからPまでの経路は、右に1回、上に2回進むので、${(1+2)!} / {1!2!} = 3! / (1! * 2!) = 3$通り。

PからBまでの経路は、右に3回、上に1回進むので、${(3+1)!} / {3!1!} = 4! / (3! * 1!) = 4$通り。

よって、P地点を通る経路は、$3 * 4 = 12$通り。

(2) P地点を通るが、Q地点を通らない場合

P地点を通る経路の総数から、P地点とQ地点の両方を通る経路の数を引きます。

P地点を通る経路は12通り（(1)より）。

PからQを通る経路は、右に2回、上に1回なので、${(2+1)!} / {2!1!} = 3! / (2! * 1!) = 3$通り。

QからBまでの経路は、右に1回、上に0回なので、${(1+0)!} / {1!0!} = 1! / (1! * 0!) = 1$通り。

したがって、PとQの両方を通る経路は、$3 * 3 * 1 = 9$通り

P地点を通るがQ地点を通らない経路は、$12 - 3 = 9$通りとなります。

(3) R地点を通らない場合

AからBまでのすべての経路の数から、R地点を通る経路の数を引きます。

AからBまでのすべての経路は、右に4回、上に3回進むので、${(4+3)!} / {4!3!} = 7! / (4! * 3!) = (7*6*5) / (3*2*1) = 35$通り。

AからRまでの経路は、右に1回、上に3回進むので、${(1+3)!} / {1!3!} = 4! / (1! * 3!) = 4$通り。

RからBまでの経路は、右に3回、上に0回進むので、${(3+0)!} / {3!0!} = 3! / (3! * 0!) = 1$通り。

したがって、R地点を通る経路は、$4 * 1 = 4$通り。

R地点を通らない経路は、$35 - 4 = 31$通り。

3. 最終的な答え

(1) 12

(2) 9

(3) 31