最短経路1

PからQまでいく最短経路の総数を求める。
図2に示したのは最短経路の１つである。
横・縦・横・縦・縦・横・縦の順に1区画ずつ進んでいるが、
縦と横の順序を入れ替えても縦に4区画、横に3区画進めば最短の経路になる。
つまり縦・縦・縦・縦・横・横・横の文字の順列 7!4!3!が最短経路の総数である。

PからQまで行く最短経路のうち、次の場合は何通りあるか。
総数
点Aを通る
点AとBを両方通る
×印を通らない

縦4区画、横6区画である。
PからAまでの経路とAからQまでの経路を考える
PからAまで、AからBまで、BからQまでの経路を考える
全体から必ず×印を通るのを引く

縦4, 横6の順列なので、10!4!6!=210通り PからAまでは4!2!2! 、 AからQまでは6!4!2!
よって 4!2!2!×6!4!2!=90通り PからAまで4!2!2!、AからBまで3!2!、 BからQまで3!2!
よって 4!2!2!×3!2!×3!2!=54通り ×印を必ず通るのは5!4!×4!2!2!
全体からこれを引くと 10!4!6!-5!4!×4!2!2!=180通り