组合数

定义

考虑一个 $n$ 元素集合 $T$ 的子集 $S\subseteq T$，$S$ 的元素个数为 $m$。满足条件的 $S$ 的个数即为组合数 $C_n^m$。有时也记为 $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$。

此即组合数的定义，形式上，可以写为：

$$C_n^m=\left\{S\subseteq T:|T|=n,|S|=m\le n\right\}$$

其计算公式为：

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

计算公式推导

首先考虑从 $n$ 个元素中依次选出 $m$ 个元素。由步骤法计数原理，选法有：

$$n\times (n-1)\times \cdots \times (n-m+1)=\frac{n!}{(n-m)!}$$

种。此选法考虑了选择的顺序，得到的结果又称为“排列数”，记为 $A_n^m$ 或 $n^m$：

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

然后，由于选出的 $m$ 个元素顺序当不计顺序，故需排除上述选法中的重复。从这 $m$ 个元素中考虑顺序地依次全部选出（又称“全排列”），即得到所有可能的重复有共 $A_m^m=m!$ 种。

在排列数的基础上除以 $m$ 个元素的全排列数，得到：

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

性质

设正整数 $n\ge 1$ 且 $0\le m\le n$，通过上述定义，易得：

1. $C_n^0=C_n^n=1C_n^1=C_n^{n-1}=n$

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

3. 组合数的递推式：$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$