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

1. 問題の内容

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

2. 解き方の手順

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

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

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

(2) AからCを通る最短経路の数：

AからCへは、右に1回、下に2回移動する必要があります。その経路数は、$\binom{3}{1}$です。

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

CからBへは、右に3回、下に1回移動する必要があります。その経路数は、$\binom{4}{3}$です。

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

したがって、AからCを通りBへ行く経路の数は、$3 \times 4 = 12$です。

(3) Cを通りDを通らない経路の数：

まず、AからCを通る経路は12通りであることは先ほど計算しました。

次に、AからCを通りDを通る経路数を計算します。

AからCへの経路は3通りです。

CからDへは、右に2回移動する必要があります。1通りです。

DからBへは、下に1回移動する必要があります。1通りです。

したがって、AからCを通りDを通る経路の数は、$3 \times 1 \times 1 = 3$です。

Cを通りDを通らない経路数は、AからCを通る経路数からAからCを通りDを通る経路数を引けば良いので、$12 - 3 = 9$です。

3. 最終的な答え

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

Cを通るものは12通り。

Cを通りDを通らないものは9通り。