The 2nd UCup Stage 7: Two Capitals. A.
Aleph1022
2023-11-10 17:19:29
令 $a_0 = a_{n+1} = m$,然后差分再反转,转化为计数长度为 $n+1$ 的整数序列,使得和为 $0$,且正数之和 $\le m$。
进一步转化为把括号对数 $\le m$ 的括号序列划分成 $n+1$ 个可以为空的段。其中同一段里不能同时出现两种括号。
立刻写出生成函数方程
$$
F(x, t) = x(1 + F(x, t))\left(\frac t{(1-t)^2} + \frac1{(1-t)^2} F(x, t)\right)
$$
而最后要求 $[x^m t^{n+1}] \frac{F(x, t)}{(1-x)(1-t)}$。
Lagrange 反演的**前途比较有限**,因此我们直接**大力解出方程**,然后考虑提取系数:
$$
\begin{aligned}
F(x, t)
&= \frac{(1-t)^2-x(1+t^2)-\sqrt{((1-t)^2-x(1+t^2))^2-4x^2t^2}}{2x} \\
&= \frac{(1-t)^2\left(1-\sqrt{\left(1-x\frac{(1+t)^2}{(1-t)^2}\right)(1-x)}\right)-x(1+t^2)}{2x} \\
\frac{1+F(x, t)}{(1-x)(1-t)} &= \frac{(1-t)\left(1-\sqrt{\left(1-x\frac{(1+t)^2}{(1-t)^2}\right)(1-x)}\right)-x\frac{1+t^2}{1-t}}{2x(1-x)} + \frac1{(1-x)(1-t)} \\
[x^m t^{n+1}] \frac{1+F(x, t)}{(1-x)(1-t)} &= -1+1+[x^{m+1} t^{n+1}] \frac{(1-t)\left(1-\sqrt{\left(1-x\frac{(1+t)^2}{(1-t)^2}\right)(1-x)}\right)}{2(1-x)} \\
&= -[x^{m+1} t^{n+1}] \frac{(1-t)\sqrt{\left(1-x\frac{(1+t)^2}{(1-t)^2}\right)(1-x)}}{2(1-x)} \\
\end{aligned}
$$
注意到只有一个根式里同时有 $x, t$,且形式比较简单。
考虑枚举其中 $x$ 的次数。$\sqrt{1-x}, \frac1{\sqrt{1-x}}$ 的系数是熟知的,则我们需要对各 $k$ 求出
$$
[t^{n+1}] \frac{(1+t)^{2k}}{(1-t)^{2k-1}}
$$
Lagrange 反演的**前途依然比较有限**,但幸运的是我们可以用**别的手法**处理。
$$
\begin{aligned}
&\quad\; [t^{n+1}] \frac{(1+t)^{2k}}{(1-t)^{2k-1}} \\
&= [t^{n+1} u^{2k}] \frac{1-t}{1-u\frac{1+t}{1-t}} \\
&= [t^{n+1} u^{2k}] \frac{(1-t)^2}{(1-u)(1-t\frac{1+u}{1-u})} \\
&= [u^{2k}] \left(\frac{(1+u)^{n+1}}{(1-u)^{n+2}} - 2\frac{(1+u)^n}{(1-u)^{n+1}} + \frac{(1+u)^{n-1}}{(1-u)^n}\right)
\end{aligned}
$$
也容易整式递推。
一个疑点是,通过 OEIS 等手段可以发现答案等于
$$
\frac1n \sum_{k=0}^n \binom nk \binom{2n-k}{n+1} \binom{m+1}{n-k}
$$
但不知有什么简洁的推导能够建立其与如上做法的联系,进一步地,在不知道规律的情况下如何从 GF 推出尽可能简洁的式子。