右のような格子状の道において、点Aから点Bへ最短距離で移動する方法について、以下の2つの場合について経路数を求める。 (1) 点Aから点Bまでの全ての経路数 (2) 点Cを通らずに点Aから点Bまでの経路数

## 問題7

1. 問題の内容

右のような格子状の道において、点Aから点Bへ最短距離で移動する方法について、以下の2つの場合について経路数を求める。

(1) 点Aから点Bまでの全ての経路数

(2) 点Cを通らずに点Aから点Bまでの経路数

2. 解き方の手順

(1) AからBまでの最短経路は、右に4回、上に3回移動することで到達できます。したがって、これは7回の移動の中で右に移動する4回を選ぶ組み合わせの数と考えることができます。これは組み合わせの公式で計算できます。

経路数は $_7C_4 = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ 通りです。

(2) AからBまでの経路のうち、Cを通る経路数を求め、(1)の経路数から引けば、Cを通らない経路数が求められます。

AからCまでの最短経路は、右に2回、上に1回移動します。その経路数は、$_3C_2 = \frac{3!}{2!1!} = 3$ 通りです。

CからBまでの最短経路は、右に2回、上に2回移動します。その経路数は、$_4C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ 通りです。

したがって、AからCを経由してBまで行く経路数は、$3 \times 6 = 18$ 通りです。

Cを通らずにAからBまで行く経路数は、$35 - 18 = 17$ 通りです。

3. 最終的な答え

(1) AからBまでのすべての経路: 35通り

(2) Cを通らずにAからBまで行く経路: 17通り