组合证明的思想，范德蒙德等式

摘要: 组合证明初探，以概率论中经常用到的范德蒙德等式为例子

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

当我们要证明一些等式的时候，我们一般可以通过分析、代数的方法进行推导。当问题复杂的时候，会面临计算过程冗长，或者分析、代数的工具比较抽象，很难想的问题。

有时组合证明就会成为神来之笔。组合证明的思路是将等式的项归结到计数问题，对同一个计数问题以两种不同的方式枚举，分别得到等式的两边，等式自然就成立的。思路还是非常直接的，相比于分析、代数的抽象，组合证明是一种具体的方法，需要我们对常见的组合结构及其对应的计数问题有一些了解，便于将等式中的项转化为计数问题。

如果组合证明能够走通，最直接的好处就是避免了复杂的计算，并且还能提供一些解释，使得等式更好理解。另一方面，很多等式当它给出来了，需要我们去证明的时候非常简单，但是在不知道的时候想把等式猜出来就不简单了，需要一些灵感，而计数问题可以提供很多灵感。这方面有很多精彩的例子，以后会跟大家慢慢分享。

关于组合证明，这里推荐 Benjamin 的这本《Proofs that Really Count : The Art of Combinatorial Proof》，其中涉及到了斐波那契数、卢卡斯数、线性递推、连分式、二项式、调和数、斯特林数、以及数论相关的众多等式，其中很多复杂难懂的等式通过计数的方式可以变得非常简明易懂。就像书名说的，是一种艺术。

范德蒙德等式

下面我们看一个在离散概率中需要反复用到的等式，我们知道算法分析的对象通常是离散的，因此也是一个算法分析中常用的等式，即范德蒙德等式。

对于二项式系数，以下等式称为范德蒙德等式。

$$\binom{m+n}{k} = \sum\limits_{j=0}\limits^{k}\binom{m}{j}\binom{n}{k-j}$$

这个等式并不显然，如果尝试通过暴力的方式去证明，会陷入复杂计算。但是通过将等式的项解释为计数问题，可以轻易给出组合证明。

证明（组合证明）

考虑一个团队中有 $m$ 个男人和 $n$ 个女人，从中选出 $k$ 个人组成一个委员会。总共的选法自然有 $\binom{m+n}{k}$。

另一方面，如果要求委员会中有 $j$ 名男性，$k-j$ 名女性，那么根据乘法原理，选法就是 $\binom{m}{j}\binom{n}{k-j}$。枚举所有可能的 $j=0,1,\cdots,k$，将对应的选法数相加，即得等式右边。

$\Box$

总结

组合证明的思想是对同一个计数问题通过两种不同的枚举方式，得到的计数结果对应到等式的两边，进而证明等式成立。如果能够成功，则可以避免冗长计算，并且有助于理解。计数问题带来的灵感还能帮你猜出一些等式。

---