8

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

807
0
$$$$
JMO/2010/予選9

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

以下,白石を$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})$となります.

投稿日:2023825
更新日:115
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

c_2
c_2
40
4233
OMC水色.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中