一类恒等式的应用（退役选手的杂谈）

退役后的诈尸。对，诈尸了。 ~~推销博客~~（既然退役了就不推销了，虽然可能$github$博客有更好的观赏体验） ~~听说没有灵魂那就没有灵魂了。~~ 故事的开头： 退役弱鸡选手在家里听网课，下课的时候发现一位神仙学弟吐槽了$CF1097G$的一部分题解。本着无所事事的原则，随手点开看了下，发现这道题好像有点眼熟。冷静思考下发现之前$noip$模拟赛做过一个类似的，于是给神仙学弟讲解了下我的思路，发现我的思路的确比网上大部分题解清晰一点（雾）。然后神仙学弟又说这个技术好像能解决他之前不会的$CF1264D2$，于是我又推了下那道题，发现的确可以做，而且和网上的大部分做法也有点区别。最终我就因无所事事来开了篇博客。 其实就是一条恒等式。 $$\sum_{i=0}^t \binom{n}{i}\binom{m}{t-i}=\binom{n+m}{t}$$ $(1)$ 证明倒也不算复杂，构造生成函数当然是最简单的做法，从组合意义考虑隔板法也是可以的。 这条形式上来看倒也有点东西，比如说，如果$n+m$是个定值，$t$是个定值，很多式子倒是可以利用这条式子直接化简。同时这条式子可以解释类似$CF1097G$的树形背包的正确性问题（可能是我太菜，我只会这样解释）。 就先拿$CF1097G$来说。 把$k$次幂用第二类斯特林数化简后，我们就是要求出 $$\sum_{i=0}^k i!S_k^i\sum_{s\subseteq U} \binom{f(s)}{i}$$ 至于这个式子怎么划出来，意义是什么跟这篇博客无关，所以就不详讲了。接下来我们就是要对每一个$i=1,...,k$求出后面那个东西。好像大部分题解就是简单的带过一句背包合并吧，着重放在了说明复杂度。不过在我看来这种树上背包复杂度恐怕是路人皆知的吧，反而这样合并的正确性是重中之重。 我们直接考虑$dp[x][i]$表示$x$这个节点求$i$时的贡献。转移的确就是正常的树上背包合并，但为什么是对的呢？ 考虑背包合并的本质，发现就是把一堆组合数乘起来再相加。冷静整理下，发现对于每一个下标$i$，我们做的是把$j$和$i-j$合并起来，即$f[x][i]=\sum g[j]*f[tox][i-j]$，这时再考虑$(1)$，惊讶地发现的确会是$f[x][i]$（严谨证明可以归纳），于是就证明了这种背包合并的正确性。 这一类组合数的背包合并大概都可以用$(1)$理解，其实还是挺有用的。 当然，组合数嘛，对于$OI$而言最大的意义还是在于化简式子吧，于是引入下$CF1264D2$这道题，看看化简式子有什么帮助。 这道题考虑下组合意义啥的，大概可以把答案写成这么一条式子 $$\sum_{i=1}^n \sum_{j=1}^n j\binom{s0[n-i]}{j-s1[n-i]}\binom{s0[n]-s0[n-i]}{i-j-(s1[n]-s1[n-i])}$$ 其中$s0[i]$表示前缀$?$的个数，$s1[i]$表示前缀$($的个数，具体这条式子怎么出来的不是这篇博客的重点，这里就不讲了。 为了接下来方便书写，我们先写成这样子 $$\sum_{i=1}^n \sum_{j=1}^n j\binom{A[n-i]}{j-p[n-i]}\binom{B[n-i]}{i-j-q[n-i]}$$ 其中$A[i]+B[i]=S,p[i]+q[i]=T$，$S,T$为定值。 然后开始化简 $$=\sum_{i=1}^n \sum_{j=0}^n (j+p[n-i])\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}$$ $$=\sum_{i=1}^n \sum_{j=0}^n (j\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}+p[n-i]\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T})$$ $$=\sum_{i=1}^n \sum_{j=0}^n j\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}+\sum_{i=1}^n \sum_{j=0}^{i-T} p[n-i]\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}$$ 接下来用一次$(1)$ $$=\sum_{i=1}^n \sum_{j=0}^n j\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}+\sum_{i=1}^n p[n-i]\binom{S}{i-T}$$ $$=\sum_{i=1}^n \sum_{j=0}^n A[n-i]\binom{A[n-i]-1}{j-1}\binom{B[n-i]}{i-j-T}+\sum_{i=1}^n p[n-i]\binom{S}{i-T}$$ $$=\sum_{i=1}^n \sum_{j=0}^{i-T-1} A[n-i]\binom{A[n-i]-1}{j}\binom{B[n-i]}{i-j-T-1}+\sum_{i=1}^n p[n-i]\binom{S}{i-T}$$ 再用一次$(1)$ $$=\sum_{i=1}^n (p[n-i]\binom{S}{i-T}+A[n-i]\binom{S-1}{i-T-1})$$ （写得有点复杂，我背锅） 于是就得到一条$O(n)$的式子了，成功地解决了此题。 同时这条式子可以对一类数进行变形，称之为$Delannoy$数，写成$D(n,m)$，组合意义表示的是网格图中从$(0,0)$走到$(n,m)$的方案数（只走上、右、右上）。 我们直接考虑组合意义的话，可以得出$D(n,m)=\sum_{i=0}^n \frac{(n+m-i)!}{(n-i)!(m-i)!i!}$（即枚举走$i$步右上来算，这时右走了$n-i$步，上走了$m-i$步）。 我们写成组合数的形式，那么 $$D(n,m)=\sum_{i=0}^n \binom{n+m-i}{n}\binom{n}{i}$$ 我们尝试用$(1)$ $$D(n,m)=\sum_{i=0}^n \binom{n+m-i}{n}\binom{n}{i}$$ $$=\sum_{i=0}^n \binom{n}{i}\sum_{j=0}^n \binom{n-i}{n-j}\binom{m}{j}$$ $$=\sum_{i=0}^n \sum_{j=0}^n \binom{n}{i}\binom{n-i}{n-j}\binom{m}{j}$$ $$=\sum_{i=0}^n \sum_{j=0}^n \binom{n}{j}\binom{j}{i}\binom{m}{j}$$ $$=\sum_{j=0}^n \binom{n}{j}\binom{m}{j}\sum_{i=0}^n \binom{j}{i}$$ $$=\sum_{j=0}^n \binom{n}{j}\binom{m}{j}2^j$$ $$=\sum_{i=0}^n \binom{n}{i}\binom{m}{i}2^i$$ （中间用到二项式定理） 我们发现，似乎成功将$D(n,m)$换到一个不太一样的形式，但我们也不知道这样的转换有什么用。或许这对出题而言，既没有降低复杂度，也没有特殊形式，显得多余。 但这份多余，可能恰恰才是数学的魅力所在吧。 笔者水平低，随便写点东西，有错误也欢迎大家指出。