同じものを含む順列

ある町には、東西に6本の道と南北に7本の道がある。
最南西にはP地点が、最北東にはＱ地点があります。

【問】ＰからＱまで良く最短経路のうち、右折左折の回数の合計がちょうど8になるのは何通りあるか？

ちなみに、最短経路は11!÷6!5!で４６２通りだと思います。

No.2 ベストアンサー 回答者： tknakamuri 回答日時： 2011/08/01 12:40

えーと

右折回数+左折回数が偶数⇒
(A) Pを東へ出発して、Qに西から到着
(B) Pを北へ出発してQへ南から到着

の2パターンになる。この2パターンで分けて考えればよさそう。

(A)では最西、最東の南北方向も道は使えず、最南、最北の東西方向の道は必ず使うが、
右折回数+左折回数=8ならば、南北方向の道は4本、東西方向の道は最南、最北を除くと
3本使うので、全ての組み合わせは

5C4 X 4C3= 5 X 4 = 20


(B)では最南、最北の東西方向も道は使えず、最西、最東の南北方向の道は必ず使うが、
右折回数+左折回数=8ならば、東西方向の道は4本、南北方向の道は最南、最北を除くと
3本使うので、全ての組み合わせは

5C3 X 4C4= 10 X 1 = 10

計 30通り

No.1 回答者： hrsmmhr 回答日時： 2011/08/01 12:11

すみません。

東西と南北が逆かもしれません

曲がる場合を１直進を０として８個の１と２個の０の並べ方を考えますが
東に２回、北に３回（最初の進行方向を直進とみなしてカウントして）進むと、残りで８回曲がれません
東から始めると最初は必ず１で
残り９個は、残りの偶数回目で０が来て０と０の間が偶数個の１が来る場合となり
０と０の間の１が０のとき残り７個の２分割＝４通り（残りの偶数回目で最初の０がくることにより）
０と０の間の１が２のとき残り５個の２分割＝３通り
０と０の間の１が４のとき残り３個の２分割＝２通り
０と０の間の１が６のとき残り１個の２分割＝１通り
で１０通り
北から始めると二つの０の間が奇数個の１が来る場合となり、
０と０の間の１が１のとき残り７個の２分割＝８通り
０と０の間の１が３のとき残り５個の２分割＝６通り
０と０の間の１が５のとき残り３個の２分割＝４通り
０と０の間の１が７のとき残り１個の２分割＝２通り
で２０通り
合計３０通りと思います