東西に4本、南北に5本の道がある格子状の道において、以下の経路の数を求めよ。 ア: AからBまでの最短経路の数 イ: AからCを経由してBまでの最短経路の数 ウ: AからCを経由せずにBまでの最短経路の数

1. 問題の内容

東西に4本、南北に5本の道がある格子状の道において、以下の経路の数を求めよ。

ア: AからBまでの最短経路の数

イ: AからCを経由してBまでの最短経路の数

ウ: AからCを経由せずにBまでの最短経路の数

2. 解き方の手順

ア: AからBまでの最短経路の数

AからBまでの最短経路は、東に3回、北に4回進む必要がある。したがって、7回の移動のうち、東に3回進む場合の数を数えればよい。これは組み合わせで計算できる。

$$$$

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

$$$$

イ: AからCを経由してBまでの最短経路の数

AからCまでの最短経路は、東に1回、北に2回進む必要がある。

CからBまでの最短経路は、東に2回、北に2回進む必要がある。

AからCまでの経路数は、

$$$$

{}_3 C_1 = \frac{3!}{1!2!} = 3

$$$$

CからBまでの経路数は、

$$$$

{}_4 C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6

$$$$

したがって、AからCを経由してBまでの最短経路数は、

$3 \times 6 = 18$

ウ: AからCを経由せずにBまでの最短経路の数

AからBまでの最短経路の総数から、AからCを経由してBまでの最短経路数を引けばよい。

したがって、$35 - 18 = 17$

3. 最終的な答え

ア: 35

イ: 18

ウ: 17