II鳥取大学 2011年 数学 第II問解答・解説

始点から南東へ進む回数を $i$、南西へ進む回数を $j$ とすると、終点では $(i,j)=(5,5)$。従って最短経路の総数は $$\displaystyle \binom{10}{5}=252.$$

(2) 図の $T$ は3段目のAのうち左から2番目にあり、座標は向きの取り方を除けば $(1,2)$（または $(2,1)$）。始点から $T$ までは $\displaystyle \binom31=3$ 通り、そこから終点までは $\displaystyle \binom73=35$ 通りなので、通過経路は $3\cdot35=105$ 通り。

(3) $U$ はDの段の中央で $(3,3)$。始点から $U$ までは $\displaystyle \binom63=20$ 通り、$U$ から終点までは $\displaystyle \binom42=6$ 通り。よって $U$ を通る経路は $120$ 通り。$T$ から $U$ までは3歩のうち一方向へ2歩、他方向へ1歩なので $\displaystyle \binom32=3$ 通り。両方を通る経路は $$3\cdot3\cdot6=54$$ 通り。

(4) 包除原理より、どちらも通らない経路は $$252-105-120+54=81$$ 通り。

南東・南西への10歩は、それぞれ5歩ずつである。格子点間の経路数を二項係数で数える。TとUを通る場合は節点で経路を分けて積を取り、どちらも通らない場合は包除原理を使う。