OMCE002-Fを形式的冪級数で解く

OMCE002-F が形式的冪級数で解けそうだと思ったので自分の考察を書いてみます.
わるえふ さんに校閲や図の作成など協力していただきました！ありがとうございます！！

解説

　まず約束事として,$N=9000,M=8998$ とします.$x,y$ の $2$ 変数冪級数を用いて考えます.$x$ の冪級数 $g$ を以下のように定義します.
$$g=\sum _{i=0}^{\mathrm{\infty }}{C}_i{x}^i(C_iはi番目のカタラン数)$$
このとき,
$$f=\sum _{i=0}^{\mathrm{\infty }}\sum _{j=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{2i+4j}{i})x^i{y}^j=\frac{1}{\sqrt{1-4x}}\frac{1}{1-g^{4}y}$$
となります.

証明
$(0,0)$ から出発し, $y=x+k$ 上のある点 $P(s,s+k)$ へと$x,y$ いずれかの正方向に $1$ 進むことを繰り返して得られる経路について考える.
s=7,k=3の場合の例
上の図のように経路を(一意に)分割すると,経路数 $(\genfrac{}{}{0ex}{}{2s+k}{s})$は以下と等しくなる.

$$\sum _{n_1+n_2+\cdots +n_{k+1}=s}{C}_{n_1}{C}_{n_2}\cdots C_{n_k}(\genfrac{}{}{0ex}{}{2n_{k+1}}{n_{k+1}})$$

したがって,
$$\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{2i+k}{i})x^i=(\sum _{i=0}^{\mathrm{\infty }}{C}_i{x}^i{)}^k(\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{2i}{i})x^i)$$
また,
$\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{2i}{i})x^i=\frac{1}{\sqrt{1-4x}}$ であるから,
$$\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{2i+k}{i})x^i=g^k\frac{1}{\sqrt{1-4x}}$$
となる. したがって,
$$\begin{array}{rl}f& =\sum _{i=0}^{\mathrm{\infty }}\sum _{j=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{2i+4j}{i})x^i{y}^j\\ \\ & =\sum _{j=0}^{\mathrm{\infty }}{g}^{4j}{y}^j\frac{1}{\sqrt{1-4x}}\\ \\ & =\frac{1}{\sqrt{1-4x}}\frac{1}{1-g^{4}y}\\ \end{array}$$

　$S_n$は $f$の積の係数となります.しかし制約がいくつかあるので気をつけます.
制約 $a_k\ne 0(k=1,n)$ については, $f-\frac{1}{1-y}$ で, 制約 $(a_k,b_k)\ne (0,0)(k\ne 1,n)$ については $f-1$ で対応します.
よって, $S_n$ は,
$$(f-\frac{1}{1-y})(f-1{)}^{n-2}(f-\frac{1}{1-y})$$
の $x^N{y}^M$ の係数となります. したがって, $\sum _{n=2}^{\mathrm{\infty }}(-1{)}^n{S}_n$ は
$$\begin{array}{rl}& (f-\frac{1}{1-y}{)}^2(1-(f-1)+(f-1{)}^2-(f-1{)}^3+\dots )\\ \\ & =(f-\frac{1}{1-y}{)}^2\frac{1}{1+(f-1)}\\ \\ & =\frac{1}{f}(f-\frac{1}{1-y}{)}^2\\ \\ & =f+\frac{1}{f}\frac{1}{(1-y{)}^2}-\frac{2}{1-y}\end{array}$$
の $x^N{y}^M$ の係数となる.
よって, $$g^k\frac{1}{\sqrt{1-4x}}=\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{2i+k}{i})x^i$$ に気を付ければ以下のように計算できる.
$$\begin{array}{rl}& [x^N{y}^M](f+\frac{1}{f}\frac{1}{(1-y{)}^2}-\frac{2}{1-y})\\ \\ & =[x^N{y}^M]f+[x^N{y}^M]\frac{1}{f}\frac{1}{(1-y{)}^2}\\ \\ & =[x^N{y}^M]\frac{1}{\sqrt{1-4x}}\frac{1}{1-g^{4}y}+[x^N{y}^M]\frac{1-4x}{\sqrt{1-4x}}(1-g^{4}y)\frac{1}{(1-y{)}^2}\\ \\ & =[x^N]g^{4M}\frac{1}{\sqrt{1-4x}}+[x^N]\frac{1-4x}{\sqrt{1-4x}}(M+1-g^{4}M)\\ \\ & =[x^N]g^{4M}\frac{1}{\sqrt{1-4x}}+(M+1)[x^N]\frac{1}{\sqrt{1-4x}}-4(M+1)[x^{N-1}]\frac{1}{\sqrt{1-4x}}\\ \\ & -M[x^N]g^4\frac{1}{\sqrt{1-4x}}+4M[x^{N-1}]g^4\frac{1}{\sqrt{1-4x}}\\ \\ & =(\genfrac{}{}{0ex}{}{2N+4M}{N})+(M+1)(\genfrac{}{}{0ex}{}{2N}{N})-4(M+1)(\genfrac{}{}{0ex}{}{2(N-1)}{N-1})-M(\genfrac{}{}{0ex}{}{2N+4}{N})+4M(\genfrac{}{}{0ex}{}{2(N-1)+4}{N-1})\\ \end{array}$$