ある町に東西に7本、南北に8本の道がある。以下の3つの場合について、最短距離で行く方法が何通りあるかを求める。 (i) A地点からC地点へ行く場合 (ii) P地点からB, Cの両地点を通ってQ地点へ行く場合 (iii) P地点からQ地点へ行く場合

1. 問題の内容

ある町に東西に7本、南北に8本の道がある。以下の3つの場合について、最短距離で行く方法が何通りあるかを求める。

(i) A地点からC地点へ行く場合

(ii) P地点からB, Cの両地点を通ってQ地点へ行く場合

(iii) P地点からQ地点へ行く場合

2. 解き方の手順

(i) A地点からC地点へ行く場合

AからCへの最短経路は、右に4回、上に5回進むことで到達できる。したがって、合計9回の移動のうち、どちらの方向に何回進むか考えればよい。

これは、9回の移動のうち、上に5回（または右に4回）を選ぶ組み合わせの数と同じである。

組み合わせの公式を用いると、

$_{9}C_{5} = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$

したがって、A地点からC地点へ行く方法は126通りである。

(ii) P地点からB、Cの両地点を通ってQ地点へ行く場合

まず、PからBへ行く。PからBへは、右に1回、上に2回進む。合計3回の移動のうち上に2回選ぶので、$_{3}C_{2} = \frac{3!}{2!1!} = 3$通り。

次に、BからCへ行く。BからCへは、上に1回進むので1通り。

最後に、CからQへ行く。CからQへは、右に1回進むので1通り。

したがって、P地点からB、Cの両地点を通ってQ地点へ行く方法は、

$3 \times 1 \times 1 = 3$通りである。

(iii) P地点からQ地点へ行く場合

PからQへの最短経路は、右に2回、上に3回進むことで到達できる。したがって、合計5回の移動のうち、どちらの方向に何回進むか考えればよい。

これは、5回の移動のうち、上に3回（または右に2回）を選ぶ組み合わせの数と同じである。

組み合わせの公式を用いると、

$_{5}C_{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$

したがって、P地点からQ地点へ行く方法は10通りである。

3. 最終的な答え

(i) A地点からC地点へ行く方法：126通り

(ii) P地点からB、Cの両地点を通ってQ地点へ行く方法：3通り

(iii) P地点からQ地点へ行く方法：10通り