[答1274] 最短経路
[答1274] 最短経路
図のように、東西の道と南北の道が交わっていて、AからBへ最短経路で行き、
同じ交差点を使わないように、BからAへ最短経路で帰ります。
東西の道が5本で南北の道が14本のとき、その経路は何通り?
また、東西の道が5本で南北の道がn本のとき、その経路は何通り?
[参考]
この道順に囲まれる□の位置が、問題の例では、
上から 1段目が 1~4 ,2段目が 3~6 ,3段目が 3~10 ,4段目が 9~13 です。
この囲まれた部分が決まるとその周りを 右回りと左回りの2種類の道順があります。
上から 1段目が 1~a ,2段目が b~c ,3段目が d~e ,4段目が 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が決まれば fは e+1-d 通りですので、
n-1 a n-1 c n-1
Σ Σ Σ Σ Σ (e+1-d) =(n+2)(n+1)2n2(n-1)/144 、
a=1 b=1 c=a d=b e=c
右回りと左回りで、(n+2)(n+1)2n2(n-1)/72 としても求められますが、
途中、省略しているΣの計算が大変です。
[解答]
東西の道がm本で南北の道がn本のとき、(図は東西の道が5本,南北の道が14本のときです)
右上図のように、Aのすぐ右に┳,Aのすぐ下に┣,Bのすぐ上に┫,Bのすぐ左に┻ の印を付ければ、
右回りの道順は A,┳,………,┫,B,┻,………,┣,A で表されます。
行きの「………」の部分は 下へ(m-2)回,右へ(n-2)回の移動で、
帰りの「………」の部分は 上へ(m-2)回,左へ(n-2)回の移動だから、
いずれも (m+n-4)!/{(m-2)!・(n-2)!} 通りで、K=(m+n-4)!/{(m-2)!・(n-2)!} とすれば、
この道順は、K2 通りですが、左下図のような、途中で同じ交差点を通る道順も含まれます。
途中で同じ交差点を通る場合は帰りに初めて同じ交差点にきたとき、Bを含むループができます。
この交差点からBを回るルートだけを逆順にする道順は、右下図になり、
右下図の A,┳,………,┻,B,┫,………,┣,A の道順は行きと帰りで、必ず同じ交差点を通ります。
従って、左下図の途中で同じ交差点を通る道順と 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)K2/{(m-1)(n-1)} 通りです。
よって、右回りの道順で同じ交差点を通らないものは、
K2-(m-2)(n-2)K2/{(m-1)(n-1)}
={(m-1)(n-1)-(m-2)(n-2)}K2/{(m-1)(n-1)}=(m+n-3)K2/{(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)2n2(n-1)/72 通りです。
.