从 m 个物品里选出 n 个的方案数，记作 $C_m^n$，即为组合数
组合数有很多很多的性质和定理。。。
注意由于本人沉迷玩梗无法自拔，如果看见您看不懂的梗请随意跳过。

组合数通项公式

$$C_m^n=\frac{m!}{n! * (m-n)!}$$
证明：现在我们从 m 个不同的数里选出 n 个数组成一个排列，第一个位子上的数有 m 种取法，第二个位子上的有 m-1 种，第三个位子上有 m-2 种。。。共有 $\frac{m!}{(m-n)!}$种
然而，我们对于顺序没有要求，假设取出了 n 个数，第一个位子上有 n 种放法，第二个位子上有 n-1 种。。。所以我们刚才得到的哪个东西还要除一个 $n!$

组合数递推公式

$$C_m^n=C_{m-1}^n+C_{m-1}^{n-1}$$
证明：从 m 个不同的数中取 n 个，第 m 个数如果取的话有 $C_{m-1}^{n-1}$种取法，如果不取则有 $C_{m-1}^n$种。
如果您是组合数新手，请牢记以上两个公式

性质 1

$$C_m^n=C_m^{m-n}$$
证明：显然从 m 个物品里选 n 个和从 m 个物品里选 m-n 个丢掉的方案数是一样的。

性质 2

$$C_{m+r+1}^r=\sum_{i=0}^n C_{m+i}^i$$
证明：用组合数的递推公式。
首先 $C_m^0=C_{m+1}^0=1$
$C_m^0+C_{m+1}^1+C_{m+2}^2+…+C_{m+r}^r$=
$C_m^1+C_{m+1}^1+C_{m+2}^2+…+C_{m+r}^r$=
$C_{m+2}^1+C_{m+2}^2+…+C_{m+r}^r$=
$C_{m+r+1}^r$

性质 3

$$C_m^n * C_n^r=C_m^r * C_{n-r}^{m-r}$$
证明: 用组合数的通项公式
$C_m^n * C_n^r=$
$\frac{m!}{n!(m-n)!} * \frac{n!}{r!(n-r)!}=$
$\frac{m!}{r!(m-r)!} * \frac{(m-r)!}{(m-n)!(n-r)!}=$
$C_m^r * C_{n-r}^{m-r}$

性质 4（二项式定理）

$$\sum_{i=0}^m C_m^i=2^m$$
证明：显然 $C_m^i$代表一个 m 位二进制数有 i 个 0 的情况下的数量，那么这个和就是 m 位二进制数的数量了。
推广一下这个二项式定理：
$$\sum_{i=0}^m C_m^i * x^i=(x+1)^m$$
这个又怎么证明呢？先把 $(x+1)^m$写成 $(x+1)(x+1)(x+1)…$的格式，然后每一项很精妙啊，比如说 i 次方项，选的 $i$个 $x$是从哪个括号里来呢？有 $C_m^i$种方案吧，所以 $x^i$项的系数是 $C_m^i$。
这就是杨辉三角的应用（可以自行百度）

性质 5

$$C_m^0-C_m^1+C_m^2-…±C_m^m=0$$
证明：假如 m 是奇数的花，由性质 1 可知正确。
假如 m 是偶数的花，这个里面的花，用一下递推公式, 然后显然 $C_{m-1}^0=C_m^0=1$并且 $C_{m-1}^{m-1}=C_m^m=1$，则：
$C_m^0-C_m^1+C_m^2-…+C_m^m=$
$C_{m-1}^0-C_{m-1}^0-C_{m-1}^1+C_{m-1}^1+C_{m-1}^2-…+C_{m-1}^{m-1}=0$

性质 6

$$C_m^0+C_m^2+C_m^4…=C_m^1+C_m^3+C_m^5+…=2^{m-1}$$
证明：这个根据性质 4 和性质 5 可知正确。

性质 7

$$C_{m+n}^r=C_m^0 * C_n^r+C_m^1 * C_n^{r-1}+…+C_m^r * C_n^0$$
证明：很简单，考虑我选出的 r 个物品在前 m 个物品有几个，在后 n 个物品里有几个即可。
特别的：$$C_{m+n}^n=C_m^0 * C_n^0+C_m^1 * C_n^1+…+C_m^m * C_n^m$$
这个是根据性质 1 变形得到的。

性质 8

$$n * C_m^n=m * C_{m-1}^{n-1}$$
证明：运用通项公式
$n * C_m^n=$
$n * \frac{m!}{n!(m-n)!}=$
$\frac{m!}{(n-1)!(m-n)!}=$
$m * \frac{(m-1)!}{(n-1)!(m-n)!}=m * C_{m-1}^{n-1}$

性质 9

$$\sum_{i=1}^n C_n^i * i=n * 2^{n-1}$$
证明：用通项公式
$\sum_{i=1}^n C_n^i * i=n * 2^{n-1}=$
$\sum_{i=1}^n \frac{n!}{(i-1)!(n-i)!}=$
$(\sum_{i=1}^n \frac{(n-1)!}{(i-1)!(n-i)!}) * n=$
$(\sum_{i=0}^{n-1} C_n^i) * n=$
现在看性质 4。
$n * 2^{n-1}$

性质 10

$$\sum_{i=1}^n C_n^i * i^2=n * (n+1) * 2^{n-2}$$
证明：这个里面的花。。。我们还是用 CY 证明法好了。。。
首先你看 n=1 的情况下成立吧？
n=2 的情况下成立吧？
n=3 的情况下成立吧？
n=4 的情况下成立吧？
这不就成了！
。
。
。
。
。
。
。
。
好吧是我太弱不不会证明 QAQ，如果大佬您会证明请评论留言。

性质 11

$$\sum_{i=0}^n (C_n^i)^2=C_{2n}^n$$
证明：boshi 说，他的门前有两棵树，~~一棵是枣树，另一棵也是枣树，~~每棵树上有 n 个枣子，每个枣子都有一个不同的神奇的膜法符号。现在 boshi 从两棵树上一共打下了 n 个枣子，那么一共有多少种方案？是 $C_{2n}^n$, 也是第一棵树上打下 i 个枣子，从第二棵树上打下（n-i）棵枣子的方案，根据乘法原理乘起来，又因为 $C_n^i=C_n^{n-i}$，所以得到上一个式子。

性质 12

$$(1+x)^m \equiv 1+x^m \pmod m$$
证明：这个使人想起性质 4 的扩展（即杨辉三角的应用）
$$\sum_{i=0}^m C_m^i * x^i=(x+1)^m$$
那么我们知道 $x^0*C_m^0=1$然后 $x^m * C_m^m=x^m$对不对啊？
那么中间这一陀呢，我们随便取一个 $\frac{m!}{i!(m-i)!}$出来看一看啊，你说它是不是 m 的倍数？？？你说它是不是 m 的倍数？？？你说它是不是 m 的倍数？？？

卢卡斯定理

简单的说就是求 $C_m^n \% p$的时候可以化作 $C_m^n =C_{m/p}^{n/p} *C_{m \% p}^{n \% p}$，那么只要递归 $C_{m/p}^{n/p}$即可。
证明~~我蠢我不会~~自己想

后记

啊啊啊搞了一下午终于证完了累死了。。。感觉自己和组合数的感情有了明显的提升~~（才怪）~~。。。
在文章的最后% 一发数王。。。
%%%%%%%%% 数王您太强了%%%%%%%%%%%
数王说以上所有定理都可以用那个那个那个证，虽然我不知道那个是哪个，但是反正好强啊%%%%%%%%