范德蒙德卷积

引入

范德蒙德卷积是一种合并组合数的式子，主要应用于组合数学的公式推导。

范德蒙德卷积公式

\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}

证明

考虑用二项式定理证明：

\begin{aligned} \sum_{k=0}^{n+m}\binom{n+m}{k}x^k&=(x+1)^{n+m}\\ &=(x+1)^n(x+1)^m\\ &=\sum_{r=0}^n\binom{n}{r}x^r\sum_{s=0}^m\binom{m}{s}x^s\\ &=\sum_{k=0}^{n+m}\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}x^k\\ \end{aligned}

即有：

\binom{n+m}{k}=\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}

若考虑其组合意义证明：

在一个大小为的集合中取出个数，可以等于把大小为的集合拆成两个集合，大小分别为与，然后从中取出个数，从中取出个数的方案数。由于我们有了对于的枚举，于是只需要考虑一种拆法，因为不同的拆法之间是等价的。

推论

推论 1 及证明

\sum_{i=-r}^{s}\binom{n}{r+i}\binom{m}{s-i}=\binom{n+m}{r+s}

证明与原公式证明相似。

推论 2 及证明

\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}

根据基础的组合数学知识推导，有：

\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\sum_{i=0}^{n-1}\binom{n}{i+1}\binom{n}{i}=\sum_{i=0}^{n-1}\binom{n}{n-1-i}\binom{n}{i}=\binom{2n}{n-1}

推论 3 及证明

\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}

根据基础的组合数学知识推导，有：

\sum_{i=0}^n\binom{n}{i}^2=\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}=\binom{2n}{n}

推论 4 及证明

\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m}

根据基础的组合数学知识推导，有：

\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\sum_{i=0}^m\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}

其中 $\binom{n+m}{m}$ 是我们较为熟悉的网格图路径计数的方案数。所以我们可以考虑其组合意义的证明。

在一张网格图中，从走到共走步。规定位于网格图左上角，其中向下走了步，向右走了步，方案数为 $\binom{n+m}{m}$ 。

换个视角，我们将步拆成两部分走，先走步，再走步，那么步中若有步向右，则步中就有步向右，故得证。

习题

参考资料与注释

Vandermonde's Convolution Formula

本页面最近更新：2023/2/18 07:57:07，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：ChungZH, tidongCrazy, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用