组合

                     

贡献者: jingyuan; addis

  • 本文处于草稿阶段。
预备知识 排列

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

\begin{equation} C_n^r = \frac{n!}{(n-r)!r!} \qquad (n, r \in \mathbb N,\, r \leqslant n)~, \end{equation}
注意 $0! = 1$。

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

\begin{equation} A_n^m = C_n^m A_m^m~. \end{equation}
对等式进行变换,可得
\begin{equation} C_n^m = \frac{A_n^m}{A_m^m}~. \end{equation}
对于这个公式,我们可以理解为,从排列中排除组合中认为等效的组合。 我们将式 3 展开,可得
\begin{equation} C_n^m = \frac{n(n - 1) \cdots (n - m + 1)}{m(m-1)\cdots 1}~. \end{equation}
进一步变换,可得
\begin{equation} C_n^m = \frac{n!}{m!(n-m)!}~, \end{equation}

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

\begin{equation} C_n^m = \frac{n!}{(n-m)![n-(n-m)]!} = C_n^{n-m}~. \end{equation}
对于性质 1 我们可以用一种直观的方式理解,到我们取 m 个元素时,剩余的元素本身就是取 $n-m$ 个元素时的组合

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

\begin{equation} C_{n + 1}^m = C_n^m + C_n^{m - 1}~. \end{equation}
当然我们也可以对性质 2 进行数学证明,
\begin{equation} \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{equation}


1. ^ 参考 Wikipedia 相关页面

                     

© 小时科技 保留一切权利