今回は場合の数の頻出問題、「最短経路」の問題です。
道順の問題を、同じものを含む順列の問題に対応させるという、
とても面白い内容なのでぜひ考えてみて下さい。
問題
問 右の図のような道がある。以下の最短経路は何通りか。
（１）AからBまでいく道順
（２）AからCを通ってBまでいく道順
（３）AからDを通らずBまでいく道順
問題の意味
Aから道を通ってBまでたどり着く道順は全部で何通りあるか数え上げる問題です。最短経路ということで、回り道や遠回りはしてはいけないので、←や↓は選択せず、→か↑のみでたどり着きます。
解説
（１）AからBまでいく道順
道順を→（右に１マス）と↑（上に１マス）の並び替えと対応させます。
例えば
→ → → → → ↑ ↑ ↑
→ → → → ↑ → ↑ ↑
↑ → ↑ → → ↑ → →
などのように、「最短経路の総数」と「→（右に１マス）5個と↑（上に１マス）3個の同じものを含む順列の総数」と一致します。
→ → → → → ↑ ↑ ↑の並び替えは
$${}_{8}\mathrm{C}_{3}=\frac{8\times7\times6}{3\times2\times1}=56$$
同じものを含む順列に関しては以下の記事をご覧ください。
（２）AからCを通ってBまでいく道順
必ず通る点は、そこまでの最短経路とそこからの最短経路に分割して考えます。
A〜Cの最短経路は→→→↑の並びかえ
$${}_{4}\mathrm{C}_{1}=4$$
C〜Bの最短経路は→→↑↑の並びかえ
$${}_{4}\mathrm{C}_{2}=6$$
A〜Cのそれぞれの道順に対して、C〜Bの道順が考えられるので、
\(4\times6=24\)通り
（３）AからDを通らずBまでいく道順
余事象を考えます。
AからDを通ってBまでいく道順を求めます。
A〜Cの最短経路は→→→↑の並びかえ
$${}_{6}\mathrm{C}_{2}=15$$
C〜Bの最短経路は→→↑↑の並びかえ
$${}_{2}\mathrm{C}_{1}=2$$
A〜Dのそれぞれの道順に対して、D〜Bの道順が考えられるので、
$$15\times2=30$$
AからBの最短経路の総数から、Dを通る総数を引けばよいので
（１）の結果を利用して
\(56-30=26\)通り
まとめ
最短経路問題は、同じものを含む順列と対応させることができる素晴らしい問題です。
入試や定期テストでも頻出の問題です。解法の仕組みを理解して活用して下さい。
ポイントは以下の点です。
- 最短経路は矢印の並び替えと対応させて考える
- 必ず通る点は、そこまでの最短経路とそこからの最短経路に分割する
- 通らない場合は、余事象を考える
コメント