概率论之组合数性质

组合数性质

期末复习开了个坑，不过这一篇应该和课程没太大的关系。

• 性质1：$\binom{n}{m}=\binom{n}{n-m}$，易得。

• 性质2：$\binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1}$，也是很容易证明的。

• 性质3：$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$，可以理解为从$n$个球里面选$m$个球，可以分为两种情况，一种是选了第$n$个球，另一种是没有选第$n$个球。

• 性质4：$\sum\limits_{i=0}^{n}\binom{n}{m}=2^n$，二项式定理。

• 性质5：$\sum\limits_{i=0}^{n}(-1)^{i}\binom{n}{m}=0$，也是二项式定理。

• 性质6：$\sum\limits_{i=0}^{m}\binom{n}{i}\binom{m}{k-i}=\binom{m+n}{k}$，范德蒙恒等式，可以理解为从$m+n$个球里面选$k$个的方案为从$n$个球里选$i$个，$m$个球里选$k-i$个的方案数的卷积。

• 性质7：$\sum\limits_{i=0}^{n}\binom{n}{i}^2=\binom{2n}{n}$，$n=m=k$的特殊情况。

• 性质8：$\sum\limits_{l=0}^{n}\binom{l}{k}=\binom{n+1}{k+1}$，朱世杰恒等式
  证明如下：

  法一：直接递推

  $$\binom{k+1}{k+1} + \binom{k+2}{k} + \dots + \binom{n}{k} = \binom{k+2}{k+1} + \binom{k+3}{k} + \dots + \binom{n}{k} = \dots = \binom{n+1}{k+1}.$$

  法二：组合意义

  从$n+1$元集合$S = \{a_0, a_1, a_2, \dots, a_n\}$中选择$k+1$个元素，共有$\binom{n+1}{k+1}$ 种方案。
  现在考虑必选$a_0$的情况，从剩下的$n$个元素中选$k$个，共有$\binom{n}{k}$种方案。
  接着考虑必选$a_1$的情况，由于选$a_0$的情况已经枚举过了，从剩下的$n-1$个元素中选$k$个，共有$\binom{n-1}{k}$种方案。
  依次类推，最后对所有方案求和即可得证

• 性质10：$\binom{n+m}{m}^2 = \sum_{i=0}^m \binom{m}{i}^2 \binom{n+2m-i}{2m}$，李善兰恒等式。
  证明:

  $$\binom{n}{k}=\sum_{i=0}^k\binom{n-l}{i}\binom{l}{k-i}$$

  $$\binom{n}{k}\binom{n}{l}=\sum_{i=0}^k\binom{n}{l}\binom{n-l}{i}\binom{l}{k-i}=\sum_{i=0}^k\binom{n}{i}\binom{n-i}{l}\binom{l}{k-i}$$

$$=\sum_{i=0}^k\binom{n}{i}\binom{n-i}{l+i-i}\binom{l}{k-i}=\sum\limits_{i=0}^{k}\binom{n}{l+i}\binom{l+i}{i}\binom{l}{k-i}$$

$$=\sum\limits_{i=0}^{k}\binom{n}{l+i}\binom{l+i}{k}\binom{k}{i}=\sum\limits_{i=0}^{k}\binom{n}{l+i}\binom{k}{i}\sum\limits_{j=0}^{k}\binom{l}{j}\binom{i}{k-j}$$

$$=\sum\limits_{j=0}^{k}\binom{l}{j}\sum\limits_{i=0}^{k}\binom{k}{i}\binom{n}{l+i}\binom{i}{k-j}$$

$$=\sum\limits_{j=0}^{k}\binom{l}{j}\sum\limits_{i=0}^{k}\binom{k}{j}\binom{j}{k-i}\binom{n}{l+i}$$

$$=\sum\limits_{j=0}^{k}\binom{l}{j}\binom{k}{j}\sum\limits_{i=0}^{k}\binom{j}{k-i}\binom{n}{l+i}$$

$$=\sum\limits_{j=0}^{k}\binom{l}{j}\binom{k}{j}\binom{n+j}{k+l}$$

令$k=l=m$，得

$$\binom{n}{m}=\sum\limits_{i=0}^{m}\binom{m}{i}^2\binom{n+i}{2m}$$

$$\binom{n+m}{m}=\sum\limits_{i=0}^{m}\binom{m}{i}^2\binom{n+m+i}{2m}$$

$$\binom{n+m}{m}=\sum\limits_{i=0}^{m}\binom{m}{m-i}^2\binom{n+m+m-i}{2m}=\sum\limits_{i=0}^{k}\binom{m}{i}^2\binom{n+2m-i}{2m}$$

证明基本参考百科。