JMO2010予選第9問の形式的冪級数を用いた解法

以下，白石を$W$，黒石を$B$で表します．

$$ S\equiv 列中のW\ 1個とB\ 1個の組であって，WがBよりも右にあるようなものの個数\pmod 2$$
とすると，条件は$S\equiv 1\pmod 2$です．

$W$2010個を先に並べて，端または$W$と$W$の間に$B$を次のように入れ，各$(BB\cdots B)$の$S$へ寄与を考えます．
$$ (BB\cdots B)W(BB\cdots B)W\cdots W(BB\cdots B)W(BB\cdots B)$$

左から奇数番目の$(BB\cdots B)$は右側に$W$が偶数個あるので$S$への寄与は$0$です．偶数番目の$(BB\cdots B)$は，右側に$W$が奇数個あるので$S$への寄与は$(BB\cdots B)$の中の$B$の個数です．

まとめると，

• 奇数番目：0
• 偶数番目：$(BB\cdots B)$の中の$B$の個数

となります．

したがって，$B$の個数を$x$，$S$を$y$で記録しようと考えて，
\begin{align*} f(x,y) &= (1+x+x^2+\cdots)(1+xy+x^2+x^3y+\cdots) \\ &\quad (1+x+x^2+\cdots)(1+xy+x^2+x^3y+\cdots) \\ &\quad \cdots \\ &\quad (1+x+x^2+\cdots)(1+xy+x^2+x^3y+\cdots)\\ &\quad (1+x+x^2+\cdots) \end{align*}

とすれば，求めるべきものは$f(x,y)$における$x^{2010}y^{奇数}$の係数の総和だと分かります．

$y^{奇数}$の係数の総和($g(x)$とおく)を求めると，

\begin{align*} g(x) &= \frac{1}{2} \left( f(x,1) - f(x,-1) \right) \\ &= \frac{1}{2} \left( (1+x+x^2+\cdots)^{2011} - (1+x+x^2+\cdots)^{1006}(1-x+x^2+\cdots)^{1005} \right) \\ &= \frac{1}{2} \left( (1-x)^{-2011} - (1-x^2)^{-1006}(1-x) \right) \end{align*}
となります．
括弧内について，$x^{2010}$の係数は，負の二項定理から

• 第一項：$_{4020}C_{2010}$
• 第二項：$_{2010}C_{1005}$

と分かるので，求めるべきものは$\dfrac{1}{2}(_{4020}C_{2010}-_{2010}C_{1005})$となります．