| For All Solvers
OMC229

OMC229(E) - 体育

ユーザー解説 by UNOwen

　題意を満たす経路は次のように言い換えられる．
・0≤a,b≤7,4≤a+b≤110\leq a,b\leq 7,4\leq a+b\leq 11 なる整数 a,ba,b について，(2a+b,b)(2a+b,b) まで共通部分をもたずに (2a+b,b)(2a+b,b) から (2(a+1)+b,b)(2(a+1)+b,b) に移動してから，それ以降も共通部分をもたないような経路
　このような経路の数を P(a,b)P(a,b) とすると，(2a+b,b)(2a+b,b) までの経路の数から (2(a−1)+b,b)(2(a-1)+b,b) までの経路の数を引くことにより P(a,b)=(a+bCb⋅a+4C8−b−a+b−1Cb⋅a+3C8−b)(15−a−bC8−b⋅11−aCb−14−a−bC8−b⋅10−aCb)P(a,b)=({}_{a+b}\mathrm C_{b}\cdot {}_{a+4}\mathrm C_{8-b}-{}_{a+b-1}\mathrm C_{b}\cdot {}_{a+3}\mathrm C_{8-b})({}_{15-a-b}\mathrm C_{8-b}\cdot {}_{11-a}\mathrm C_{b}-{}_{14-a-b}\mathrm C_{8-b}\cdot {}_{10-a}\mathrm C_{b}) がわかる．ただし，r<0r\lt 0 または n<rn\lt r のとき nCr=0{}_{n}\mathrm C_{r}=0 とする．
　よって，題意を満たす経路の数は ∑0≤a,b≤7,4≤a+b≤11P(a,b)=32391216\sum_{0\leq a,b\leq 7,4\leq a+b\leq 11}P(a,b)=32391216 と求まる．