【場合の数】最短経路問題【同じものを含む順列】

問題

問題の意味

Aから道を通ってBまでたどり着く道順は全部で何通りあるか数え上げる問題です。最短経路ということで、回り道や遠回りはしてはいけないので、←や↓は選択せず、→か↑のみでたどり着きます。

解説

（１）AからBまでいく道順

道順を→（右に１マス）と↑（上に１マス）の並び替えと対応させます。

例えば

などのように、「最短経路の総数」と「→（右に１マス）5個と↑（上に１マス）3個の同じものを含む順列の総数」と一致します。

→ → → → → ↑ ↑ ↑の並び替えは

$${}_{8}\mathrm{C}_{3}=\frac{8\times7\times6}{3\times2\times1}=56$$

（２）AからCを通ってBまでいく道順

必ず通る点は、そこまでの最短経路とそこからの最短経路に分割して考えます。

A〜Cのそれぞれの道順に対して、C〜Bの道順が考えられるので、

$4\times6=24$通り

（３）AからDを通らずBまでいく道順

余事象を考えます。

AからDを通ってBまでいく道順を求めます。

A〜Dのそれぞれの道順に対して、D〜Bの道順が考えられるので、

$$15\times2=30$$

AからBの最短経路の総数から、Dを通る総数を引けばよいので

まとめ