京都大学 2005年度 後期日程 第2次学力試験文系（後期）数学 第5問

各格子点 $(x,y)$ までの最短経路数を $N(x,y)$ とする。障害点では $N(x,y)=0$、それ以外では$$N(x,y)=N(x-1,y)+N(x,y-1)$$である。ただし座標軸上では、障害物に達する前の値を1とする。この規則で順に計算すると次の表を得る。$\times$ は障害点を表す。$$\begin{array}{crrrrrr}y\mathrm{\backslash }x& 0& 1& 2& 3& 4& 5\\ 5& 1& 6& 6& 14& 14& 28\\ 4& 1& 5& \times & 8& \times & 14\\ 3& 1& 4& 4& 8& 8& 14\\ 2& 1& 3& \times & 4& \times & 6\\ 1& 1& 2& 3& 4& 5& 6\\ 0& 1& 1& 1& 1& 1& 1\end{array}$$したがって $(5,5)$ までの最短経路は$$28\text{ 通り}$$である。

全経路から，4つの障害点の少なくとも1つを通る経路を包含排除で除く。2点以上を通るには座標が右上方向に並ぶ必要があることに注意する。

障害物を無視した最短経路は，右へ5回，上へ5回進む順序の選び方だから$${\displaystyle \frac{10!}{5!5!}}=252$$通りである。

障害点を$$A=(2,2),B=(2,4),C=(4,2),D=(4,4)$$とする。各点を通る経路数は順に$$\begin{array}{rl}{\displaystyle N(A)}& {\displaystyle ={\displaystyle \frac{4!}{2!2!}}{\displaystyle \frac{6!}{3!3!}}=120,}\\ {\displaystyle N(B)}& {\displaystyle ={\displaystyle \frac{6!}{2!4!}}{\displaystyle \frac{4!}{3!1!}}=60,}\\ {\displaystyle N(C)}& {\displaystyle =60,}\\ {\displaystyle N(D)}& {\displaystyle ={\displaystyle \frac{8!}{4!4!}}{\displaystyle \frac{2!}{1!1!}}=140.}\end{array}$$よって1点を指定して通る経路数の和は $380$ である。

右上方向に両立する2点の組だけを数えると，$$N(A,B)+N(A,C)+N(A,D)+N(B,D)+N(C,D)=24+24+72+30+30=180$$である。$B$ と $C$ は一方から他方へ右・上だけでは移れないので両立しない。

両立する3点の組は $A,B,D$ と $A,C,D$ だけで，それぞれ12通り，合計24通りである。4点すべてを通る経路はない。

包含排除の原理により，障害点を1つも通らない経路数は$$252-380+180-24=28$$通りである。