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

后记

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

分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

4 条评论

B_Z_B_Y · 2018年10月30日 7:23 下午

qwq

B_Z_B_Y · 2018年10月30日 6:29 下午

您性质 2 中的证明是不是有问题啊 qwq C1 m != C0 m

    litble · 2018年10月30日 6:48 下午

    是第一个 $C_{m+1}^1$要改成 $C_{m+1}^0$

    不过反正这是我神志不清的情况下 xjb 乱写的文章,这种笔误都不想改了

    还有最后一个性质缺了个约束条件,所以不是成立的,也懒得删了

      XZYQvQ · 2018年10月30日 6:57 下午

      服务态度恶劣.avi(光速逃

发表评论

电子邮件地址不会被公开。 必填项已用*标注