从 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$种。 如果您是组合数新手，请牢记以上两个公式

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

$$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$

$$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}$

$$\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$。 这就是杨辉三角的应用（可以自行百度）

$$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$

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

$$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 变形得到的。

$$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}$

$$\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}$

$$\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，如果大佬您会证明请评论留言。

$$\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}$，所以得到上一个式子。

$$(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}$即可。 证明~~我蠢我不会~~自己想

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