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

后记

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