1. 問題の内容
右図のA地点からB地点へ行く。
(1) 最短経路は何通りあるか。
(2) P地点を通っていく最短経路は何通りあるか。
2. 解き方の手順
(1) AからBへの最短経路は、右に4回、上に3回移動することで構成される。したがって、7回の移動のうち右への移動を4回選ぶ組み合わせの数で求められる。これは、組み合わせの公式で計算できる。
{}_7 C_4 = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35
(2) AからPへの最短経路は、右に2回、上に1回移動することで構成される。
{}_3 C_2 = \frac{3!}{2!1!} = \frac{3 \times 2}{2} = 3
PからBへの最短経路は、右に2回、上に2回移動することで構成される。
{}_4 C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6
したがって、AからPを経由してBへ行く最短経路は、AからPへの経路数とPからBへの経路数を掛け合わせたものになる。
3 \times 6 = 18
3. 最終的な答え
(1) 最短経路は35通りある。
(2) P地点を通っていく最短経路は18通りある。