范德蒙德卷积公式 (Vandermonde’s Identity)
美观起见,证明在 Part 2 。
Part 1
范德蒙德卷积公式:
k∑i=0(ni)(mk−i)=(n+mk)推论1:
s∑i=−r(nr+i)(ms−i)=(n+mr+s)推论2:
n∑i=1(ni)(ni−1)=(2nn−1)推论3:
n∑i=0(ni)2=(2nn)推论4:
m∑i=0(ni)(mi)=(n+mm)Part 2
范德蒙德卷积公式 证明:
n+m∑k=0(n+mk)xk=(x+1)n+m=(x+1)n(x+1)m=n∑r=0(nr)xrm∑s=0(ms)xs=n+m∑k=0k∑r=0(nr)(mk−r)xk即
(n+mk)=k∑r=0(nr)(mk−r)推论1 证明类似与原公式,这里不再说明。
推论2 证明:
n∑i=1(ni)(ni−1)=n−1∑i=0(ni+1)(ni)=n−1∑i=0(nn−1−i)(ni)=(2nn−1)推论3 证明:
n∑i=0(ni)2=n∑i=0(ni)(nn−i)=(2nn)推论4 证明:
m∑i=0(ni)(mi)=m∑i=0(ni)(mm−i)=(n+mm)推论4中的 (n+mm) 是我们较为熟悉的网格图路径计数的方案数。所以我们可以考虑其组合意义的证明。
在一张网格图中,从 (0,0) 走到 (n,m) 共走 n+m 步。规定 (0,0) 位于网格图左上角,其中向下走了 n 步,向右走了 m 步,方案数为 (n+mm)。
换个视角,我们将 n+m 步拆成两部分走,先走 n 步,再走 m 步,那么 n 步中若有 i 步向右,则 m 步中就有 m−i 步向右,故得证。
参考文献:
[1] https://oi-wiki.org/math/combinatorics/vandermonde-convolution/