组合数性质

· · 个人记录

忽然发现组合数有一堆小性质。

定义：C_n^m 表示从 n 个一样的东西中选 m 个的方案数，显然相当于从 A_n^m 去掉重复的方案，发现一种方案被统计了 m!，所以得 C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}

性质：

  1. C_n^m=C_{n-1}^m+C_{n-1}^{m-1}

证明一：由定义得

\begin{aligned} C_{n-1}^m+C_{n-1}^{m-1}&=\frac{(n-1)!}{(m-1)!(n-m)!}+\frac{(n-1)!}{m!(n-m-1)!}\\ &=\frac{(n-1)!m+(n-1)!(n-m)}{m!(n-m)!}\\ &=\frac{n!}{m!(n-m)!}\\ &=C_n^m \end{aligned}

证明2：从组合意义考虑，现在从 n 个人中选 m 个人，显然有 C_n^m。

考虑钦定选第一个人，那么有 C_{n-1}^{m-1} 种选法。

钦定不选第一个人，那么有 C_{n-1}^m 种选法。

根据加法原理，两者相加等于总方案，所以 C_{n-1}^m+C_{n-1}^{m-1}=C_n^m

2.C_n^m=C_n^{n-m}

证明：

由定义得

C_n^m=\frac{n!}{m!(n-m)!}=\frac{n!}{(n-m)!(n-(n-m))!}=C_n^{n-m}

3.C_n^m=\frac{n}{m}C_{n-1}^{m-1}

证明：

由定义得

C_n^m=\frac{n!}{m!(n-m)!}=\frac{n}{m}\frac{(n-1)!}{(m-1)!(n-m)!}=\frac{n}{m}C_{n-1}^{m-1}

4.\sum_{i=0}^n C_n^i = 2^n

证明：

由二项式定理得

2^n=(1+1)^n=\sum_{i=0}^n C_n^i\times 1^i\times 1^{n-i}=\sum_{i=0}^n C_n^i

5.\sum_{i=x}^nC_i^x=C_{n+1}^{x+1}

证明：

可以考虑用归纳法。

首先对于所以 n=x 的情况，显然成立。

所以我们考虑当 n-1 已经成立时，怎么证明 n 也成立。

由性质 1 得

\begin{aligned} C_{n+1}^{x+1}&=C_n^x+C_n^{x+1}\\ &=C_n^x+\sum_{i=x}^{n-1}C_i^x\\ &=\sum_{i=x}^n C_i^x \end{aligned}

6.\sum_{i=0}^n C_{p+i}^{i}=C_{n+p+1}^{n}

证明：

同样考虑归纳法。

当 n=0 时，显然成立。

考虑当 n-1 成立时，n 是否成立。

由性质 1 得

\begin{aligned} C_{n+p+1}^n&=C_{n+p}^n+C_{n+p}^{n-1}\\ &=C_{n+p}^n+\sum_{i=0}^{n-1} C_{p+i}^{i}\\ &=\sum_{i=0}^n C_{p+i}^i \end{aligned}

7.\sum_{i=1}^{n}iC_n^i=n2^{n-1}

证明：

由性质 3 得