组合（高中）

贡献者： jingyuan; addis

预备知识　排列

1. 定义

　　一般地，从 $n$ 个不同元素中，任取出 $m (m \leq n)$ 个元素并成一组，叫做从 $n$ 个元素中任取 $m$ 个元素的一个组合（combination）。

　　从 $n$ 个不同元素中，任取 $m (m \leq n)$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中，任意取出 $m$ 个元素的组合数（number of combination），用符号 $C_{n}^{m}$ 表示。

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

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

对等式进行变换，可得

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

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

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

进一步变换，可得

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

2. 性质

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

\begin{matrix} (5) & 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} (6) & C_{n + 1}^{m} = C_{n}^{m} + C_{n}^{m - 1} . \end{matrix}

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

\begin{matrix} (7) & \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}

　　下面这个公式出现在课本（人教 B 版）的《离散型随机变量的数字特征》这一章节，不要求掌握但这里还是作为拓展给出，

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

下面给出证明，

\begin{matrix} (9) & \begin{aligned} 左边 = & m \cdot \frac{n!}{m! (n - m)!} = \frac{n!}{(m - 1)! (n - m)!}, \\ 右边 = & n \cdot \frac{(n - 1)!}{(m - 1)! (n - m)!} = \frac{n!}{(m - 1)! (n - m)!}, \end{aligned}} ⟹ 左边 = 右边 . \end{matrix}

　　我们对式 8 进行变形可得

\begin{matrix} (10) & C_{n}^{m} = \frac{n}{m} \cdot C_{n - 1}^{m - 1} . \end{matrix}

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