范德蒙德卷积 学习笔记

直接放结论，反正我也不会证。

k∑i=0(ni)(mk−i)=(n+mk)

∑i=0k(ni)(mk−i)=(n+mk)

下面有几个推论，可以稍微不那么严谨的证明一下。

首先你要知道的是这个东西：

(mi)=(mm−i)

(mi)=(mm−i)

感性理解一下就是杨辉三角的对称性，其实直接拆式子也不是什么难事。
下面来看几个推论：

推论一

n∑i=1(ni)(ni−1)=(2nn+1)

∑i=1n(ni)(ni−1)=(2nn+1)

关于证明，我们可以把 (ni−1)(ni−1) 转化成为 (nn−i+1)(nn−i+1) 。
然后原式变成

n∑i=1(ni)(nn−i+1)

∑i=1n(ni)(nn−i+1)

直接套用公式就可以了。

推论二

n∑i=0(ni)2=(2nn)

∑i=0n(ni)2=(2nn)

证明的话先把式子的平方拆开，变成这样

n∑i=0(ni)×(ni)

∑i=0n(ni)×(ni)

然后考虑这样的一个转换：

(ni)=(nn−i)

(ni)=(nn−i)

带入原式可以发现，又变成了范德蒙德卷积的形式

n∑i=0(ni)(nn−i)

∑i=0n(ni)(nn−i)

推论三

m∑i=0(ni)(mi)=(n+mm)

∑i=0m(ni)(mi)=(n+mm)

证明也很简单，考虑这样的一个转换

(mi)=(mm−i)

(mi)=(mm−i)

带入以后成为范德蒙德卷积的形式：

m∑i=0(ni)(mm−i)

∑i=0m(ni)(mm−i)