図のような道がある街で、AからBへ行く最短経路の数、そのうちCを通るものの数、そしてCを通りDを通らないものの数をそれぞれ求める問題です。

1. 問題の内容

図のような道がある街で、AからBへ行く最短経路の数、そのうちCを通るものの数、そしてCを通りDを通らないものの数をそれぞれ求める問題です。

2. 解き方の手順

まず、AからBへ行く最短経路の数を求めます。これは右に4回、下に3回移動するので、全部で7回の移動のうち、右への移動を4回選ぶ組み合わせの数になります。

次に、AからBへ行く最短経路のうち、Cを通るものの数を求めます。これはAからCへ行く最短経路の数と、CからBへ行く最短経路の数を掛け合わせることで求められます。AからCへは右に1回、下に1回移動するので、2回の移動のうち右への移動を1回選ぶ組み合わせの数です。CからBへは右に3回、下に2回移動するので、5回の移動のうち右への移動を3回選ぶ組み合わせの数になります。

最後に、AからBへ行く最短経路のうち、Cを通りDを通らないものの数を求めます。これは、Cを通りBへ行く経路から、CとDを両方通る経路の数を引くことで求められます。AからCへの経路数はすでに計算済みです。CからDへは右に1回、下に1回移動します。DからBへは右に2回、下に1回移動します。

計算：

* AからBへの最短経路数：

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

* AからCへの最短経路数：

$\binom{2}{1} = \frac{2!}{1!1!} = 2$

* CからBへの最短経路数：

$\binom{5}{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$

* AからBへの最短経路でCを通るものの数：

$2 \times 10 = 20$

* CからDへの最短経路数：

$\binom{2}{1} = \frac{2!}{1!1!} = 2$

* DからBへの最短経路数：

$\binom{3}{2} = \frac{3!}{2!1!} = 3$

* AからBへの最短経路でCとDを両方通るものの数：

$2 \times 2 \times 3 = 12$

* AからBへの最短経路でCを通りDを通らないものの数：

$20 - 12 = 8$

3. 最終的な答え

* AからBへ行く最短経路は35通り

* そのうち、Cを通るものは20通り

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