组合数性质
期末复习开了个坑，不过这一篇应该和课程没太大的关系。
性质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}$$证明基本参考百科。