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

955

JMO/2010/予選9

白石2010個と黒石2010個を横一列に並べるとき，以下の条件をみたす並べ方は何通りあるか．
条件：列中の白石1個と黒石1個の組であって，白石が黒石よりも右にあるようなものが奇数組ある．

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

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

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

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

まとめると，

奇数番目：0
偶数番目： $(B B \dots B)$ の中の $B$ の個数

となります．

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

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

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

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