范德蒙德卷积
2026-04-24
范德蒙德卷积公式
i=0∑n(in)×(k−im)=(kn+m)
证明
二项式定理证明:
k=0∑n+m(kn+m)×xk=(x+1)n+m=(x+1)n+(x+1)m=(r=0∑n(rn)×xr)×(s=0∑m(sm)×xs)=k=0∑n+mr=0∑k(rn)×(k−rm)×xk
其中最后一步可以理解为:xk 的系数只能由 xr×xs 而来(这里 r+s=k),所以 xk 的系数即为 (rn)×(k−rm)。
最后两边同时脱去一层求和及 xk 即可。
组合意义证明:
考虑从 n+m 个物品中取 k 个,即为 (kn+m)。
同时,考虑将这些物品分为两组,前 n 个一组,后 m 个一组,从第一组中取 i 个,第二组中取 k−i 个,然后对 i 求和,即为 k=0∑n+m(kn+m)×xk。
