(3) 下の図において、PからQへ行く最短経路は何通りあるか。 (4) (3)の最短経路のうち、RS間を通るものは何通りあるか。

1. 問題の内容

(3) 下の図において、PからQへ行く最短経路は何通りあるか。

(4) (3)の最短経路のうち、RS間を通るものは何通りあるか。

2. 解き方の手順

(3) PからQへ行く最短経路の総数を求める。

PからQへは、右に4回、下に3回移動する必要がある。

したがって、最短経路は合計7回の移動で構成され、そのうち4回が右方向への移動、3回が下方向への移動である。

これは、7回の移動のうち、どの4回を右方向への移動にするかを選ぶ組み合わせの数に等しい。

したがって、最短経路の総数は ${7 \choose 4}$ で計算できる。

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

(4) RS間を通る最短経路の数を求める。

PからRへ行く最短経路の数を求める。

PからRへは、右に1回、下に1回移動する必要がある。

したがって、最短経路は合計2回の移動で構成され、そのうち1回が右方向への移動、1回が下方向への移動である。

これは、2回の移動のうち、どの1回を右方向への移動にするかを選ぶ組み合わせの数に等しい。

したがって、PからRへの最短経路の総数は ${2 \choose 1}$ で計算できる。

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

RからSへ行く経路は1通り。

SからQへ行く最短経路の数を求める。

SからQへは、右に2回、下に2回移動する必要がある。

したがって、最短経路は合計4回の移動で構成され、そのうち2回が右方向への移動、2回が下方向への移動である。

これは、4回の移動のうち、どの2回を右方向への移動にするかを選ぶ組み合わせの数に等しい。

したがって、SからQへの最短経路の総数は ${4 \choose 2}$ で計算できる。

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

PからRを通りSを通りQへ行く経路は、PからRへの経路数 $\times$ RからSへの経路数 $\times$ SからQへの経路数で計算できる。

これは、 $2 \times 1 \times 6 = 12$ 通りとなる。

3. 最終的な答え

(3) 35通り

(4) 12通り