贡献者： 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 相关页面。