组合意义天地灭，代数推导保平安

· · 算法·理论

\large{\sum_{i\geq 0}{\binom{x+y+i}{i}\binom{x}{b-i}\binom{y}{a-i}}=\binom{x+a}{b}\binom{y+b}{a}}

\leftarrow 左转组合意义

我们希望用生成函数，于是我们用生成函数。

首先有 \displaystyle\binom{y}{a-i}=\binom{y}{y-a+i}=[v^{y-a+i}](1+v)^y。

然后我们希望求的 v 指数上不含 i，于是就可以用到第二个组合数，把它变成 \displaystyle\binom{x}{b-i}=[v^{b-i}](1+v)^x，这样合起来就相当于求 v^{y-a+b} 的系数了。

上面是典型的范德蒙德卷积，然而还有第一个组合数不好处理。考虑在 (1+v)^x 上加一点东西变成 (1+u+v)^x，这样除了有 v^{b-i} 之外还多了 (1+u)^{x-b+i}。

在此基础上乘一个 (1+u)^{y+b} 凑成 (1+u)^{x+y+i}，然后求 u^{x+y}v^{y-a+b} 上的系数就可以得到左式。

于是 LHS=[u^{x+y}v^{y-a+b}](1+u)^{y+b}(1+u+v)^x(1+v)^y。

观察上述过程的实质是枚举 (1+v)^y 对 v 的贡献，于是考虑换成枚举 (1+u)^{y+b} 对 u 的贡献：

\begin{aligned} LHS &= [u^{x+y}v^{y-a+b}](1+u)^{y+b}(1+u+v)^x(1+v)^y\\ &= \sum_{i\geq 0}{\binom{y+b}{i}\binom{x}{x+y-i}\binom{i}{y-a+b}}\\ &= \sum_{i\geq 0}{\binom{y+b}{y-a+b}\binom{a}{i-y+a-b}\binom{x}{x+y-i}}\\ &= \binom{y+b}{a}\binom{x+a}{b}=RHS \end{aligned} Q.E.D.