[答1274] 最短経路

[答1274] 最短経路


　図のように、東西の道と南北の道が交わっていて、ＡからＢへ最短経路で行き、

　同じ交差点を使わないように、ＢからＡへ最短経路で帰ります。

　東西の道が５本で南北の道が14本のとき、その経路は何通り？

　また、東西の道が５本で南北の道がｎ本のとき、その経路は何通り？


[参考]

　この道順に囲まれる□の位置が、問題の例では、

　上から １段目が 1～4 ，２段目が 3～6 ，３段目が 3～10 ，４段目が 9～13 です。

　この囲まれた部分が決まるとその周りを 右回りと左回りの２種類の道順があります。

　上から １段目が 1～a ，２段目が b～c ，３段目が d～e ，４段目が f～n－1 とすれば、

　1≦a≦n－1 ，1≦b≦a ，a≦c≦n－1 ，b≦d≦c ，c≦e≦n－1 ，d≦f≦e です。

　ｅが決まれば ｆは e＋1－d 通りですので、

　　_{n-1　　a　　n-1　　c　　n-1}
　　Σ　Σ　Σ　Σ　Σ (e＋1－d) ＝ (n＋2)(n＋1)n(n－1)/144 、
　　^{a=1　 b=1　 c=a　 d=b　 e=c}

　右回りと左回りで、(n＋2)(n＋1)n(n－1)/72 としても求められますが、

　途中、省略しているΣの計算が大変です。


[解答]

　東西の道がｍ本で南北の道がｎ本のとき、(図は東西の道が５本，南北の道が14本のときです)

　右上図のように、Ａのすぐ右に┳，Ａのすぐ下に┣，Ｂのすぐ上に┫，Ｂのすぐ左に┻ の印を付ければ、

　右回りの道順は Ａ,┳,………,┫,Ｂ,┻,………,┣,Ａ で表されます。

　行きの「………」の部分は 下へ(m－2)回，右へ(n－2)回の移動で、

　帰りの「………」の部分は 上へ(m－2)回，左へ(n－2)回の移動だから、

　いずれも (m＋n－4)!/｛(m－2)!･(n－2)!｝ 通りで、K＝(m＋n－4)!/｛(m－2)!･(n－2)!｝ とすれば、

　この道順は、K² 通りですが、左下図のような、途中で同じ交差点を通る道順も含まれます。

　途中で同じ交差点を通る場合は帰りに初めて同じ交差点にきたとき、Ｂを含むループができます。

　この交差点からＢを回るルートだけを逆順にする道順は、右下図になり、

　右下図の Ａ,┳,………,┻,Ｂ,┫,………,┣,Ａ の道順は行きと帰りで、必ず同じ交差点を通ります。

　従って、左下図の途中で同じ交差点を通る道順と 1対1に対応し、同数です。

　行きの「………」の部分は 下へ(m－1)回，右へ(n－3)回の移動だから、

　 (m＋n－4)!/｛(m－1)!･(n－3)!｝＝(n－2)K/(m－1) 通り、

　帰りの「………」の部分は 上へ(m－3)回，左へ(n－1)回の移動だから、

　 (m＋n－4)!/｛(m－3)!･(n－1)!｝＝(m－2)K/(n－1) 通り、

　途中で同じ交差点を通る道順は、(m－2)(n－2)K²/｛(m－1)(n－1)｝ 通りです。

　よって、右回りの道順で同じ交差点を通らないものは、

　K²－(m－2)(n－2)K²/｛(m－1)(n－1)｝

　 ＝｛(m－1)(n－1)－(m－2)(n－2)｝K²/｛(m－1)(n－1)｝＝(m＋n－3)K²/｛(m－1)(n－1)｝

　 ＝K･(m＋n－3)(m＋n－4)!/｛(m－2)!･(n－2)!｝/｛(m－1)(n－1)｝＝K･(m＋n－3)!/｛(m－1)!･(n－1)!｝

　 ＝(m＋n－3)!(m＋n－4)!/｛(m－1)!･(m－2)!･(n－1)!･(n－2)!｝ 通りあります。

　左回りのコースも同数あり、

　全部で 2･(m＋n－3)!(m＋n－4)!/｛(m－1)!･(m－2)!･(n－1)!･(n－2)!｝ 通りです。

　m＝5，n＝14 のとき、

　2･16!･15!/(4!･3!･13!･12!)＝2･16･15･14･15･14･13/(4!･3!)＝127400 通りです。

　m＝5 のとき、

　2･(n＋2)!(n＋1)!/｛4!･3!･(n－1)!･(n－2)!｝＝2(n＋2)(n＋1)n(n＋1)n(n－1)/(4!･3!)

　＝(n＋2)(n＋1)²n²(n－1)/72 通りです。

.