右図において、点Aから点Bまでの最短経路の数を考える。 (1) 全ての最短経路の数を求める。 (2) 点Pを通る最短経路の数を求める。 (3) 点Pを通らない最短経路の数を求める。

1. 問題の内容

右図において、点Aから点Bまでの最短経路の数を考える。

(1) 全ての最短経路の数を求める。

(2) 点Pを通る最短経路の数を求める。

(3) 点Pを通らない最短経路の数を求める。

2. 解き方の手順

(1) 全ての最短経路の数

AからBへの最短経路は、右に2回、上に2回移動する必要がある。

したがって、4回の移動のうち、右への移動を2回選ぶ組み合わせを考えればよい。

これは、4つの場所から2つを選ぶ組み合わせ$_4C_2$で計算できる。

$_4C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$

(2) 点Pを通る最短経路の数

AからPへの最短経路は、右に1回、上に1回移動する必要がある。

したがって、2回の移動のうち、右への移動を1回選ぶ組み合わせを考えればよい。

これは、2つの場所から1つを選ぶ組み合わせ$_2C_1$で計算できる。

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

PからBへの最短経路も、右に1回、上に1回移動する必要がある。

したがって、2回の移動のうち、右への移動を1回選ぶ組み合わせを考えればよい。

これは、2つの場所から1つを選ぶ組み合わせ$_2C_1$で計算できる。

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

AからPを通りBへ行く経路数は、AからPへの経路数とPからBへの経路数の積となる。

$2 \times 2 = 4$

(3) 点Pを通らない最短経路の数

点Pを通らない最短経路の数は、全ての最短経路の数から点Pを通る最短経路の数を引けばよい。

$6 - 4 = 2$

3. 最終的な答え

(1) 全ての最短経路の数は6通り。

(2) 点Pを通る最短経路の数は4通り。

(3) 点Pを通らない最短経路の数は2通り。