A地点からB地点まで最短経路で行く場合の数を、以下の4つの条件下でそれぞれ求めます。 (1) Dを通る場合 (2) Cを通らずDを通る場合 (3) CまたはDを通る場合 (4) C, Dともに通らない場合

1. 問題の内容

A地点からB地点まで最短経路で行く場合の数を、以下の4つの条件下でそれぞれ求めます。

(1) Dを通る場合

(2) Cを通らずDを通る場合

(3) CまたはDを通る場合

(4) C, Dともに通らない場合

2. 解き方の手順

まず、AからBへの最短経路の総数を求めます。これは、右に5回、下に3回進む順列の数に等しいので、

$\frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$通りです。

(1) Dを通る場合

AからDへの経路数は$\frac{4!}{3!1!} = 4$通り。

DからBへの経路数は$\frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$通り。

したがって、Dを通る経路数は $4 \times 6 = 24$通り。

(2) Cを通らずDを通る場合

Dを通る経路数から、CとDの両方を通る経路数を引きます。

AからCへの経路数は$\frac{3!}{2!1!} = 3$通り。

CからDへの経路数は$\frac{2!}{1!1!} = 2$通り。

DからBへの経路数は6通り（上記参照）。

CとDの両方を通る経路数は $3 \times 2 \times 6 = 36$通り。

ただし、これは誤りです。CとDの両方を通るということは、A→C→D→Bという経路を通るということですから、このような経路数は $3 \times 2 \times 6 = 36$ となります。しかし、Dを通る経路数24通りより大きいため矛盾しています。

正しい考え方は以下の通りです。

Dを通る経路数は24通り（上記参照）。

Cを通る経路数は $\frac{3!}{2!1!} \times \frac{5!}{3!2!} = 3 \times 10 = 30$通り

CとDの両方を通る経路数は $3 \times 2 \times 6 = 36$通り

Cを通らずDを通る経路数 = Dを通る経路数 - CとDの両方を通る経路数 = 24 - 3 * 2 * 6 = 24 - 36 = -12

これはありえないため、別の方法で計算します。

Cを通らずDを通る場合、以下の考え方で計算します。

AからDまでの経路数は4通り。

DからBまでの経路数は6通り。

AからCまでの経路数は3通り。

CからBまでの経路数は10通り。

AからDを通る経路の中でCを通るものを除きます。

AからCを通る経路は3通り。

CからDを通らないでBに行く経路数はAからBまでのすべての経路数からAからDを通る経路数を引いた数。

AからDを通る経路の中でCを通るものは、A→C→D→Bと通る経路のみなので、3*2*6 = 36通り。しかし、これはAからDを通る経路の総数24を超えるので、計算が間違っている。

（１）より、Dを通る経路数は24通り。

このうち、Cを通る経路は、AからCへ行き、CからDへ行き、DからBへ行く経路です。

AからCへは3通り、CからDへは2通り、DからBへは6通りなので、3*2*6=36通り。

Dを通りかつCも通る経路は存在しません。したがって、Cを通らずにDを通る経路は、Dを通るすべての経路、すなわち24通りです。

(3) CまたはDを通る場合

Cを通る経路数 + Dを通る経路数 - CとDの両方を通る経路数

= 30 + 24 - 36 = 18通り

(4) C, Dともに通らない場合

全体の経路数 - (CまたはDを通る経路数) = 56 - 18 = 38通り

3. 最終的な答え

(1) Dを通る場合：24通り

(2) Cを通らずDを通る場合：Dを通る経路数 - CとDの両方を通る経路数 = 24 - 6 = 18通り (AからCまでの経路数は3通り。CからDへは2通り。DからBへは6通り。よって、CとDを通る経路は3*2*6=36通りではない。CからBへ行く際に、Dを通らない経路を計算しなければならない)

(3) CまたはDを通る場合：30 + 24 - 36 = 18通り

(4) C, Dともに通らない場合：56 - 18 = 38通り