概率论 Cheat Sheet 1：组合分析
本系列整理自《概率论基础教程（原书第 9 版）》，包含关键定义、定理和证明，便于查用。
1. 引言
概率论中的很多问题都可以通过计算某个事件可能发生结果的数目来解决。关于计数的数学理论通常称为组合分析（Combinatorial Analysis）。
2. 计数基本法则
计数基本法则 假设有两个试验，其中试验 1 有 $m$ 种可能的结果，对应于试验 1 的每一个结果，试验 2 有 $n$ 种可能的结果，则这两个试验一共有 $mn$ 种可能的结果。
推广的计数基本法则 如果一共有 $r$ 个试验，试验 1 有 $n_1$ 种可能的结果，对应于试验 1 的每一种可能的结果，试验 2 有 $n_2$ 种可能的结果，对应于前两个试验的每一种可能的结果，试验 3 有 $n_3$ 种可能的而结果······那么这 $r$ 个试验一共有 $n_1 n_2 \cdots n_r$ 种可能的结果。
3. 排列
随意排列字母 a，b，c，一共有 abc，acb，bac，bca，cab，cba 六种不同的排列方式，每一种都称为一个排列（Permutation）。
假设对 $n$ 个元素进行排列，由计数基本法则，第一个位置可供选择的元素有 $n$ 个，第二个位置可供选择的元素有 $n – 1$ 个，以此类推，可知一共有
\begin{equation}
n \times (n – 1) \times (n – 2) \times \cdots \times 3 \times 2 \times 1 = n!
\end{equation}
种不同的排列方式。
假设 $n$ 个元素中有 $n_1$ 个元素是相同的，对于 $n_1$ 个 相同的元素，虽然它们可以有 $n_1!$ 种排列，但这些排列都是相同的，因此这 $n$ 个元素一共有 $n! / n_1!$ 种排列。
对于 $n$ 个元素，如果其中 $n_1$ 个元素彼此相同，另 $n_2$ 个彼此相同，···，$n_r$ 个也彼此相同，那么一共有
\begin{equation}
\frac{n!}{n_1! n_2! \cdots n_r!}
\end{equation}
种不同的排列方式。
4. 组合
如果考虑顺序，从 $n$ 个元素中取 $r$ 个排成一组，一共有 $n(n-1)\cdots(n-r+1)$ 种不同的方式，而每个含 $r$ 个元素的小组都被重复计算了 $r!$ 次。所以，从 $n$ 个元素中取 $r$ 个组成不同组的数目为
\begin{equation}
\frac{n (n – 1) \cdots (n – r + 1)}{r!} = \frac{n!}{(n – r)! r!}
\end{equation}
对于 $n \leq r$，定义 $\binom{n}{r}$ 如下：
\begin{equation}
\binom{n}{r} = \frac{n!}{(n – r)! r!}
\end{equation}
这样 $\binom{n}{r}$ 就表示从 $n$ 个元素中一次取 $r$ 个的可能组合数。定义 $0! = 1$，故 $\binom{n}{0} = \binom{n}{n} = 1$；当 $i < 0$ 或 $i > n$ 时，认为 $\binom{n}{i} = 0$。
因此，如果不考虑抽取顺序，$\binom{n}{r}$ 就表示从 $n$ 个元素中取 $r$ 个元素所组成的不同组的数目。
等价地，$\binom{n}{r}$ 就是从一个大小为 $n$ 的集合中选出大小为 $r$ 的子集的个数。由 $0! = 1$，注意
\begin{equation}
\binom{n}{n} = \binom{n}{0} = \frac{n!}{0!n!}= 1
\end{equation}
在一个大小为 $n$ 的集合里，恰好只有一个大小为 $n$ 的子集（也就是全集），而且也恰好只有一个大小为 $0$ 的子集（也就是空集）。约定当 $r > n$ 或 $r < 0$ 时，定义 $\binom{n}{r} = 0$。
下面的组合恒等式非常有用：
\begin{equation}
\binom{n}{r} = \binom{n – 1}{r – 1} + \binom{n – 1}{r}, \; 1 \leq r \leq n
\end{equation}
实际上，上面的等式描述了从 $n$ 个元素中选取 $r$ 个的选法。对 $n$ 个元素中的一个特定元素 X：若选取了 X，则还需在 $n – 1$ 个元素中选取 $r – 1$ 个元素，有 $\binom{n – 1}{r – 1}$ 种选法；若没有选取 X，则需在 $n – 1$ 个元素中选取 $r$ 个元素，有 $\binom{n – 1}{r}$ 种选法。二者相加，即为从 $n$ 个元素中选取 $r$ 个的选法数量。
值 $\binom{n}{r}$ 也称为二项式系数（Binomial Coefficient），因为它们是下面二项式定理中的系数。
二项式定理
\begin{equation}
(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}
\end{equation}
5. 多项式系数
将 $n$ 个不同的元素分成 $r$ 组，每组分别有 $n_1, n_2, \cdots, n_r$ 个元素，其中 $\sum_{i=1}^r n_i = n$，则第一组有 $\binom{n}{n_1}$ 种选法；选定第一组后，要从 $n – n_1$ 个元素中选出第二组，有 $\binom{n – n_1}{n_2}$ 种选法；第三组有 $\binom{n – n_1 – n_2}{n_3}$ 种选法，以此类推。根据推广的技术基本法则，将 $n$ 个元素分成 $r$ 组的分法数量为：
\begin{align}
&\binom{n}{n_1} \binom{n – n_1}{n_2} \cdots \binom{n – n_1 – n_2 – \cdots – n_{r-1}}{n_r} \\
&= \frac{n!}{(n – n_1)! n_1!} \cdot \frac{(n – n_1)!}{(n – n_1 – n_2)! n_2!} \cdots \frac{(n – n_1 – n_2 – \cdots – n_{r-1})!}{0! n_r!} \\
&= \frac{n!}{n_1! n_2! \cdots n_r!}
\end{align}
记号 如果 $n_1 + n_2 + \cdots + n_r = n$，则定义 $\binom{n}{n_1, n_2, \cdots, n_r}$ 为
\begin{equation}
\binom{n}{n_1, n_2, \cdots, n_r} = \frac{n!}{n_1! n_2! \cdots n_r!}
\end{equation}
因此，$\binom{n}{n_1, n_2, \cdots, n_r}$ 表示把 $n$ 个不用的元素分成大小分别为 $n_1, n_2, \cdots, n_r$ 的 $r$ 个不同组的组合数。
多项式定理
\begin{equation}
(x_1 + x_2 + \cdots + x_r)^n = \sum_{(n_1, \cdots, n_r): \\ n_1 + \cdots + n_r = n} \binom{n}{n_1, n_2, \cdots, n_r} x_1^{n_1} x_2^{n_2} \cdots x_r^{n_r}
\end{equation}
上式的求和符号是对满足 $n_1 + n_2 + \cdots + n_r = n$ 的所有非负整数向量 $(n_1, n_2, \cdots, n_r)$ 求和。
$\binom{n}{n_1, n_2, \cdots, n_r} $ 也称为多项式系数（Multinomial Coefficient）。
6. 方程的整数解个数
考虑满足
\begin{equation}
x_1 + x_2 + \cdots + x_r = n \tag{1}
\end{equation}
的正整数向量 $(x_1, x_2, \cdots, x_r)$，假设有 $n$ 个连续的数值 $0$ 排成一行
\begin{equation}
0 \; 0 \; 0 \; \cdots \; 0 \; 0
\end{equation}
从 $n – 1$ 个相邻的 $0$ 的间隔中选出 $r – 1$ 个间隔的每一种选择，对应 $(1)$ 式的一个正数解，使得 $x_1$ 等于第一个被选择的间隔之前的 $0$ 的个数，$x_2$ 等于第一个和第二个被选择的间隔之间的 $0$ 的个数，···，$x_r$ 等于最后一个被选择的间隔后面的 $0$ 的个数。
命题 1 共有 $\binom{n – 1}{r – 1}$ 个不同的正整数向量 $(x_1, x_2, \cdots, x_r)$ 满足
\begin{equation}
x_1 + x_2 + \cdots + x_r = n, \; x_i > 0, \; i = 1, \cdots, r
\end{equation}
令 $y_i = x_i + 1$，则 $x_1 + x_2 + \cdots + x_r = n$ 的非负整数解与 $x_1 + x_2 + \cdots + x_r = n + r$ 的正整数解的个数是相同的的，故有如下命题。
命题 2 共有 $\binom{n + r – 1}{r – 1}$ 个不同的非负整数向量 $(x_1, x_2, \cdots, x_r)$ 满足
\begin{equation}
x_1 + x_2 + \cdots + x_r = n
\end{equation}