右のような格子状の街路において、点Pから点Qまで最短経路で移動する方法について、以下の3つの場合についてそれぞれの場合の数を求める問題です。 (1) PからQまでのすべての最短経路の総数 (2) PからQまでの最短経路のうち、点Rを通る経路の数 (3) PからQまでの最短経路のうち、×印の箇所を通らない経路の数

1. 問題の内容

右のような格子状の街路において、点Pから点Qまで最短経路で移動する方法について、以下の3つの場合についてそれぞれの場合の数を求める問題です。

(1) PからQまでのすべての最短経路の総数

(2) PからQまでの最短経路のうち、点Rを通る経路の数

(3) PからQまでの最短経路のうち、×印の箇所を通らない経路の数

2. 解き方の手順

(1) 総数：

PからQまでの最短経路は、右に5回、上に5回移動することで到達できます。したがって、全移動回数は10回であり、そのうち右への移動5回の順番を選べば経路が一意に定まります。これは組み合わせの問題として考えられ、 $_{10}C_5$ で計算できます。

$_{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$

(2) Rを通る経路：

PからRまでの最短経路数は、右に2回、上に2回移動するので、$_{4}C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通りです。

RからQまでの最短経路数は、右に3回、上に3回移動するので、$_{6}C_3 = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$通りです。

したがって、PからRを経由してQまで行く経路数は、PからRまでの経路数とRからQまでの経路数の積で求まります。

$6 \times 20 = 120$

(3) ×印の箇所を通らない経路：

PからQへの総経路数は252通りです。

Pから×印の地点までの経路数は、右に3回、上に2回移動するので、$_{5}C_2 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$通りです。

×印の地点からQまでの経路数は、右に2回、上に3回移動するので、$_{5}C_2 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$通りです。

したがって、Pから×印を経由してQまで行く経路数は、$10 \times 10 = 100$通りです。

×印の箇所を通らない経路の数は、総経路数から×印を通る経路数を引けばよいので、$252 - 100 = 152$通りです。

3. 最終的な答え

(1) 252通り

(2) 120通り

(3) 152通り