与えられた格子状の道において、点Aから点Bへ行く最短経路の総数、点Cを通る最短経路の数、そして点Cを通りかつ点Dを通らない最短経路の数をそれぞれ求める問題です。

1. 問題の内容

与えられた格子状の道において、点Aから点Bへ行く最短経路の総数、点Cを通る最短経路の数、そして点Cを通りかつ点Dを通らない最短経路の数をそれぞれ求める問題です。

2. 解き方の手順

(1) AからBへの最短経路の総数

AからBへ行くには、右に5回、上に4回移動する必要があります。これは、9回の移動のうち右への移動を5回選ぶ組み合わせの数に等しくなります。したがって、最短経路の総数は $\binom{9}{5}$ で計算できます。

(2) AからCを通ってBへの最短経路の数

AからCへ行くには、右に2回、上に1回移動する必要があります。これは、3回の移動のうち右への移動を2回選ぶ組み合わせの数に等しくなります。つまり、$\binom{3}{2}$通りです。

次に、CからBへ行くには、右に3回、上に3回移動する必要があります。これは、6回の移動のうち右への移動を3回選ぶ組み合わせの数に等しくなります。つまり、$\binom{6}{3}$通りです。

したがって、AからCを通ってBへ行く最短経路の総数は、$\binom{3}{2} \times \binom{6}{3}$ で計算できます。

(3) AからCを通ってBへ行く最短経路のうち、Dを通るものの数

AからCへ行く経路は $\binom{3}{2}$ 通りです。CからDへ行くには、右に1回、上に2回移動する必要があります。これは、3回の移動のうち右への移動を1回選ぶ組み合わせの数に等しくなります。つまり、$\binom{3}{1}$通りです。DからBへ行くには、右に2回、上に1回移動する必要があります。これは、3回の移動のうち右への移動を2回選ぶ組み合わせの数に等しくなります。つまり、$\binom{3}{2}$通りです。

したがって、AからCを通ってDを通ってBへ行く最短経路の総数は、$\binom{3}{2} \times \binom{3}{1} \times \binom{3}{2}$ で計算できます。

(4) AからCを通ってBへ行く最短経路のうち、Dを通らないものの数

これは、AからCを通ってBへ行く最短経路の総数から、AからCを通ってDを通ってBへ行く最短経路の総数を引くことで得られます。

したがって、その数は $\binom{3}{2} \times \binom{6}{3} - \binom{3}{2} \times \binom{3}{1} \times \binom{3}{2}$ で計算できます。

計算:

(1) $\binom{9}{5} = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$

(2) $\binom{3}{2} \times \binom{6}{3} = 3 \times \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 3 \times 20 = 60$

(3) $\binom{3}{2} \times \binom{3}{1} \times \binom{3}{2} = 3 \times 3 \times 3 = 27$

(4) $60 - 27 = 33$

3. 最終的な答え

AからBへ行く最短経路は 126 通り。

そのうち、Cを通るものは 60 通り。

また、AからBへ行く最短経路のうち、Cを通りDを通らないものは 33 通り。