别再提取对角线了

· · 算法·理论

考虑证明这样一个式子：

\sum_{i=0}^n \sum_{j=0}^{n-i}\binom{i+j}{i}\binom{n-i}{j}\binom{n-j}{i}=\sum_{r=0}^n \binom{2r}{r}

题目来源是 双射证明题 中的 16 题，不过我们这里不用构造双射的证明，而是用代数推导方法，顺带说明「提取对角线法」容易遇到的一些问题。

简单推一下

起手自然是尝试计算左式关于 n 的生成函数，其为：

\begin{aligned}F(z)&=\sum_{i,j \geq 0}\binom{i+j}{i} \sum_{n =0}^\infty \binom{n-i}{j}\binom{n-j}{i} z^n \\ &=\sum_{i,j \geq 0}\binom{i+j}{i} z^{i+j}\sum_{n=0}^\infty \binom{n+j}{j}\binom{n+i}{i}z^n\end{aligned}

虽然我们知道内层和式必然是分母为 (1-z)^{i+j+1} 的有理分式，但对于计算帮助不大。不妨考虑

\binom{n+i}{i} = [t^i] \frac{1}{(1-t)^{n+1}}

暂时添加一维 t，先让形式上化简一点，就可以直接用广义二项式求和了：

F(z) = \sum_{i,j \geq 0} \binom{i+j}{i} z^{i+j} [t^i] \frac{1}{1-t-z} \frac{1}{\left(1- \frac{z}{1-t}\right)^j}

然后对 j 这层求和再用广义二项式就得到

F(z) = \sum_{i=0}^\infty [t^i] \frac{z^i}{1-t(1-z)-2z} \left(1- \frac{z(1-t)}{1-z-t}\right)^{-i}

提取对角线翻车

比较喜欢提取对角线的同学，做到这里可能就会直接把 [t^i] 变成 [t^0] t^{-i}，然后把提取系数的 [t^0] 丢到求和外面去，然后一个等比数列求和：

F(z)\stackrel{?}{=} [t^0] \frac{1}{1-t(1-z)-2z} \sum_{i=0}^\infty\left( \frac{t}{z}-\frac{t(1-t)}{1-z-t} \right)^{-i}

将等比数列求和化简之后，上式的右侧就变成了这么一坨东西：

[t^0] \frac{t}{(1-z)((1-t)t-z)} \neq F(z)

显然问题出在了最后对等比求和的化简上。我们之前也遇到过这样的例子。由于和式中关于 t 不是形式 Laurent 级数，即它有无限多的负次项。这个东西的性质太差，处理起来稍不注意就挂了。

既然提取对角线容易出错，还是考虑使用经典的 Lagrange 反演来解。

还得是拉反

返回前两节最后的式子，经典方法（链接中的 case 4）就是设（取 H(0)=0 的解，容易验证其展开不含 z 或 t 的负次项） ：

H(t)\left(\frac{1}{z}-\frac{1-H(t)}{1-z-H(t)}\right)=t

那么

F(z) = \sum_{i=0}^\infty [t^i] \frac{H'(t)}{1-H(t)(1-z)-2z} \frac{t}{H(t)}

注意，对于每个自然数 i 都能这样操作，因为这里的负次项数都有限，对其计算也不会有任何问题。
换句话说，因为形式 Laurent 级数的收敛只考虑逐项收敛，对每一项单独提取 [t^i] 得到的是一个关于 z 的有限项的多项式；而像上一节那种做法则不然。

好了，现在整个和式在做的就是把所有 t 的系数加到一起，所以有

F(z) = \frac{H'(1)}{H(1)} \frac{1}{1-H(1)(1-z)(1-2z)}

接下来的计算就很简单了。只不过要注意 H'(1) 是 H(t) 先对 t 求导后代入 t=1。简单计算后可以解出

F(z) = \frac{1}{(1-z) \sqrt{1-4z}}

提取其 [z^n] 系数便直接得证。