右の街路図において、AからBまで行く最短経路の総数を求め、そのうちCとDの両方を通る最短経路の総数を求め、CとDのどちらも通らない最短経路の総数を求める。

1. 問題の内容

右の街路図において、AからBまで行く最短経路の総数を求め、そのうちCとDの両方を通る最短経路の総数を求め、CとDのどちらも通らない最短経路の総数を求める。

2. 解き方の手順

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

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

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

(2) CとDの両方を通る最短経路の総数

AからCまでの最短経路は、右に1回、上に1回移動するので、$\binom{2}{1}=2$通りある。

CからDまでの最短経路は、右に2回移動するので、1通り。

DからBまでの最短経路は、上に2回移動するので、1通り。

したがって、A→C→D→Bの最短経路の総数は、$2 \times 1 \times 1 = 2$通りである。

(3) CもDも通らない最短経路の総数

AからBまでの最短経路の総数から、Cを通る最短経路の総数とDを通る最短経路の総数を引き、CとDの両方を通る最短経路の総数を足す（包除原理）。

AからCを通る最短経路の総数：A→Cは2通り、C→Bは右に3回、上に2回なので$\binom{5}{3}=10$通り。したがって$2 \times 10 = 20$通り。

AからDを通る最短経路の総数：A→Dは右に3回、上に1回なので$\binom{4}{3}=4$通り、D→Bは上に2回なので1通り。したがって$4 \times 1 = 4$通り。

Cを通るまたはDを通る最短経路の総数 = Cを通る + Dを通る - CとDを通る = $20 + 4 - 2 = 22$通り。

したがって、CもDも通らない最短経路の総数 = 全体の最短経路 - Cを通るまたはDを通る最短経路 = $35 - 22 = 13$通り。

3. 最終的な答え

ア：35

イ：2

ウ：13