组合

贡献者： jingyuan; addis

本文处于草稿阶段。

预备知识　排列

　　¹数学上，组合（combination）用于计算从 $n$ （ $n = 0, 1, 2, \dots$ ）个不同的物体中选取 $0 ⩽ r ⩽ n$ 个，有几种方法。国内高中课本常用 $C_{n}^{r}$ 来表示，欧美教材常记为 $(\begin{matrix} n \\ r \end{matrix})$ 。组合可以用阶乘表示（推导见下文）。

\begin{matrix} (1) & C_{n}^{r} = \frac{n!}{(n - r)! r!} (n, r \in N, r ⩽ n), \end{matrix}

注意

0! = 1

。

　　我们可以从排列来推导组合，在组合中认为 $a, b$ ， $b, a$ 是等效的，在排列中认为两者是不等的，现在我们有 $n$ 个元素，我们要从中选取 $m$ 个元素，即 $C_{n}^{m}$ 。我们先根据组合的知识可以知道 $A_{n}^{m}$ 表示 $n$ 个元素，从中选取 $m$ 个再对选中的 $m$ 个元素进行全排，我们就可以得到如下公式

\begin{matrix} (2) & A_{n}^{m} = C_{n}^{m} A_{m}^{m} . \end{matrix}

对等式进行变换，可得

\begin{matrix} (3) & C_{n}^{m} = \frac{A_{n}^{m}}{A_{m}^{m}} . \end{matrix}

对于这个公式，我们可以理解为，从排列中排除组合中认为等效的组合。我们将式 3 展开，可得

\begin{matrix} (4) & C_{n}^{m} = \frac{n (n - 1) \dots (n - m + 1)}{m (m - 1) \dots 1} . \end{matrix}

进一步变换，可得

\begin{matrix} (5) & C_{n}^{m} = \frac{n!}{m! (n - m)!}, \end{matrix}

　　我们将式 5 中的 $m$ 用 $n - (n - m)$ 代换，可得组合的性质 1

\begin{matrix} (6) & C_{n}^{m} = \frac{n!}{(n - m)! [n - (n - m)]!} = C_{n}^{n - m} . \end{matrix}

对于性质 1 我们可以用一种直观的方式理解，到我们取 m 个元素时，剩余的元素本身就是取

n - m

个元素时的组合

　　当我们的总元素个数从 $n$ 变为 $n + 1$ 时，我们可以分为两类，一类为不包含新元素的组合，一类为包含新元素的组合，由分类加法计数原理，可得组合的性质 2

\begin{matrix} (7) & C_{n + 1}^{m} = C_{n}^{m} + C_{n}^{m - 1} . \end{matrix}

当然我们也可以对性质 2 进行数学证明，

\begin{matrix} (8) & \begin{aligned} C_{n}^{m} + C_{n}^{m - 1} & = \frac{n!}{m! (n - m)!} + \frac{n!}{(m - 1)! (n - m + 1)!} \\ = \frac{n! (n - m + 1)! + n! \cdot m}{m! (n - m + 1)!} \\ = \frac{n! [(n - m + 1) + m]}{m! (n - m + 1)!} \\ = \frac{(n + 1)!}{m! (n - m + 1)!} \\ = C_{n + 1}^{m} . \end{aligned} \end{matrix}

1. ^ 参考 Wikipedia 相关页面。

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。