OMC卬高杯2(E)

　$M$ を求めるお話です．FPS (形式的冪級数) が使えそうだったので使いました．

　まず，$M$ は以下で表される式を展開したときの $x^{2^{2021}}y^{奇数}$ の係数の総和に等しい（※）． $$f(x,y)=(1+x+x^2+\cdots)(1+xy + x^2y^2+\cdots)(1+xy^2 + x^2y^4 + \cdots)\cdots(1+xy^{2^{2021}}+x^2y^{2\times 2^{2021}}+\cdots)$$ さらに，実際に展開した後の様子を考えれば，これは $(f(x,1)-f(x,-1))/2$ の $x^{2^{2021}}$ の係数に等しい．以下これを求める．

• $f(x,1)$ について． $$f(x,1)=(1+x+x^2+\cdots)^{2^{2021}+1}$$ の $x^{2^{2021}}$ の係数を考えればよく，これは「 $2^{2021}+1$ 個の順序付いた非負整数の組であって，その総和が $2^{2021}$ であるものの総数」と等しいことから ${}_{2^{2022}} \mathrm{C}_{2^{2021}}$ と求められる．

• $f(x,-1)$ について． $$f(x,y)=\frac{1}{1-x}\times \frac{1}{1-xy} \times \cdots \frac{1}{1-xy^{2^{2021}}}$$ より，特に $$f(x,-1)=\left(\frac{1}{1-x}\times \frac{1}{1+x}\right)^{2^{2020}+1}(1+x) = (1+x^2+x^4+\cdots)^{2^{2020}+1}(1+x)$$ つまり $(1+x^2+x^4+\cdots)^{2^{2020}+1}$ の $x^{2^{2021}}$ の係数を考えればよいから，これは先ほどと同様に ${}_{2^{2021}} \mathrm{C}_{2^{2020}}$ と求められる．

以上より， $$M=\frac{f(x,1)-f(x,-1)}{2} = \frac{{}_{2^{2022}} \mathrm{C}_{2^{2021}} - {}_{2^{2021}} \mathrm{C}_{2^{2020}}}{2}$$ と求められた．

（※）
　各因子は左から順番に $0$ の個数とその総和への寄与， $1$ の個数とその総和への寄与，... を意味しています．ここで，$y$ は $a_1+a_2+\cdots$ に対応します．本問では「$2^{2021}$ 個の非負整数」の和が奇数となる場合の数を求めるので，文字 $x$ を導入し，$\underline{{x^{2^{2021}}}} y^{奇数}$ の係数，という縛りを設けて対応しています．
　また，実際にはある数が $a_1, a_2, \cdots, a_{2^{2021}}$の中に $2^{2021}$ 個以上含まれることはないため，各因子は無限次にならないのでは？という疑問があるかもしれませんが，最終的に見るのは $x^{2^{2021}}y^{奇数}$ の係数のみなので無限次にしたところで答えには影響しません．
　この式の立て方は PCT 氏の Mathlog の記事を参考にしました．