最短経路問題の解法
例えば次の図においてAからBまでの最短経路の場合の数は、
最短で進むので、区画分けより右に３回、上に４回進めば最短で目的地まで行けます。よって次の７つの記号を並べ替えたらその分だけ新しい経路ができます。
「 → → → ↑ ↑ ↑ ↑ 」なら
「 → ↑ → → ↑ ↑ ↑ 」なら
したがって→が３つ、↑が４つの合計７つの記号の同じものを含む順列として計算できるので、$$~~~~~\frac{7!}{3!\cdot 4!}$$$$~=\frac{7\times6\times5\times4\times3\times2\times1}{3\times2\times1\times4\times3\times 2\times1}$$$$~=35$$よって、答えは35通りとなります。
このように最短経路問題は２方向の矢印の同じものを含む順列として計算できます。
問題解説：最短経路問題
問題解説(1)
\({\small (1)}~\)AからBまでの最短経路
ＡからＢに行くには、→に４回と↑に５回の合計９回進むことになります。同じものを含む順列で考えると、$$~~~~~~\frac{9!}{4!\times 5!}$$$$~=\frac{9\times8\times7\times6\times5\times4\times3\times2\times1}{4\times3\times2\times1\times5\times4\times3\times2\times1}$$$$~=126$$よって、答えは126通りとなります。
問題解説(2)
\({\small (2)}~\)AからBまでの最短経路でCを必ず通る経路
次の問題では、Ａから一度Ｃに行きＢまで行きます。ですので「ＡからＣまでの経路」と「ＣからＢまでの経路」に分けて考えましょう。
まずはＡからＣまでの経路は、→に２回、↑に３回の合計５回進むので、同じものを含む順列より$$~~~\frac{5!}{2!\times 3!}=\frac{5\times4\times3\times2\times1}{2\times1\times3\times2\times1}=10$$よって、10通りとなります。
次にＣからＢまでの経路は、→に２回、↑に２回の合計４回進むので、同じものを含む順列より$$~~~\frac{4!}{2!\times 2!}=\frac{4\times3\times2\times1}{2\times1\times2\times1}=6$$よって、6通りとなります。
これらはＡからＣ、ＣからＢと「連続して起こる」ので積の法則より$$~~~10 \times 6 =60$$したがって、答えは60通りとなります。
問題解説(3)
\({\small (3)}~\)AからBまでの最短経路でDを通らない経路
この問題ではＤを通らずにＢまで行かないといけませんが、それを考えるのは難しいのでＤを必ず通る場合の数を考えましょう。
「ＡからＢに行くすべての場合の数」から「Ｄを必ず通る場合の数」を引けば「ＡからＤを通らずにＢに行く場合の数」を求めることができます。
Ｄを必ず通る場合の数は、
① ＡからＤの左の十字路まで
② Ｄの道
③ Ｄの右の十字路からＢまで
と進めばよいことになります。
ＡからＤの左の十字路に行くには、→に２回、↑に２回の合計４回進めばよいので、同じものを含む順列より$$~~~\frac{4!}{2!\times 2!}=\frac{4\times3\times2\times1}{2\times1\times2\times1}=6$$よって、6通りとなります。
次にＤの道を進むのは１通りとなります。
次にＤの右の十字路からＢまで行くには、→に１回、↑に３回の合計４回進めばよいので、同じものを含む順列より$$~~~\frac{4!}{3!}=\frac{4\times3\times2\times1}{3\times2\times1}=4$$よって、4通りとなります。
したがって、これらは「連続して起こる」ので積の法則より$$~~~6 \times 1 \times 4 =24$$よって、24通りとなります。
また、ＡからＢに行くすべての場合の数は(1)より126通りとなります。
したがって、$$~~~126 – 24 =102$$答えは102通りとなります。
今回のまとめ
最短経路問題は「→」と「↑」の矢印の同じものを含む順列として計算できます。また条件があるパターンの解法も合わせて覚えておきましょう！
