碁盤の目状の道路において、点Aから点Bへ行く最短経路の総数を求め、さらに以下の条件を満たす経路の数を求める問題です。 (ア) 点Cを通る (イ) 点Cと点Dの両方を通る (ウ) 点Cまたは点Dを通る (エ) 点Cと点Dのどちらも通らない

1. 問題の内容

碁盤の目状の道路において、点Aから点Bへ行く最短経路の総数を求め、さらに以下の条件を満たす経路の数を求める問題です。

(ア) 点Cを通る

(イ) 点Cと点Dの両方を通る

(ウ) 点Cまたは点Dを通る

(エ) 点Cと点Dのどちらも通らない

2. 解き方の手順

まず、点Aから点Bまでの最短経路の総数を求めます。これは、右に6回、上に4回移動する順列の数と同じです。つまり、10回の移動のうち、右方向への移動を6回選ぶ組み合わせの数なので、$_{10}C_6$ で計算できます。

次に、各条件を満たす経路の数を求めます。

(ア) 点Cを通る経路

点Aから点Cまでの最短経路の数は、右に2回、上に2回移動するので、$_{4}C_2$です。

点Cから点Bまでの最短経路の数は、右に4回、上に2回移動するので、$_{6}C_4$です。

したがって、点Cを通る経路の数は、$_{4}C_2 \times _{6}C_4$です。

(イ) 点Cと点Dの両方を通る経路

点Aから点Cまでの最短経路の数は、$_{4}C_2$です。

点Cから点Dまでの最短経路の数は、右に2回、上に1回移動するので、$_{3}C_2$です。

点Dから点Bまでの最短経路の数は、右に2回、上に1回移動するので、$_{3}C_2$です。

したがって、点Cと点Dの両方を通る経路の数は、$_{4}C_2 \times _{3}C_2 \times _{3}C_2$です。

(ウ) 点Cまたは点Dを通る経路

これは、点Cを通る経路の数 + 点Dを通る経路の数 - 点Cと点Dの両方を通る経路の数で計算できます。

点Dを通る経路の数は、点Aから点Dまでの最短経路の数 $\times$ 点Dから点Bまでの最短経路の数で計算できます。

点Aから点Dまでの最短経路の数は、右に4回、上に3回移動するので、$_{7}C_4$です。

点Dから点Bまでの最短経路の数は、右に2回、上に1回移動するので、$_{3}C_2$です。

したがって、点Dを通る経路の数は、$_{7}C_4 \times _{3}C_2$です。

点Cまたは点Dを通る経路の数は、$_{4}C_2 \times _{6}C_4 + _{7}C_4 \times _{3}C_2 - _{4}C_2 \times _{3}C_2 \times _{3}C_2$となります。

(エ) 点Cと点Dのどちらも通らない経路

これは、点Aから点Bまでの最短経路の総数 - 点Cまたは点Dを通る経路の数で計算できます。

計算を実行します。

$_{10}C_6 = \frac{10!}{6!4!} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 210$

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

$_{6}C_4 = \frac{6!}{4!2!} = \frac{6 \times 5}{2 \times 1} = 15$

$_{3}C_2 = \frac{3!}{2!1!} = 3$

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

(ア) 点Cを通る経路: $6 \times 15 = 90$

(イ) 点Cと点Dの両方を通る経路: $6 \times 3 \times 3 = 54$

(ウ) 点Cまたは点Dを通る経路: $6 \times 15 + 35 \times 3 - 6 \times 3 \times 3 = 90 + 105 - 54 = 141$

(エ) 点Cと点Dのどちらも通らない経路: $210 - 141 = 69$

3. 最終的な答え

* 点Aから点Bまでの最短経路の総数: 210通り

* (ア) 点Cを通る経路: 90通り

* (イ) 点Cと点Dの両方を通る経路: 54通り

* (ウ) 点Cまたは点Dを通る経路: 141通り

* (エ) 点Cと点Dのどちらも通らない経路: 69通り