组合数学

1. 基本计数原理

1.1 加法原理

若完成一件事有 $n$ 类方法，第 $i$ 类有 $m_i$ 种方法，各类方法互不相容，则完成该事共有 $m_1 + m_2 + \cdots + m_n$ 种方法。

1.2 乘法原理

若完成一件事需 $n$ 个步骤，第 $i$ 步有 $m_i$ 种方法，则完成该事共有 $m_1 \times m_2 \times \cdots \times m_n$ 种方法。

例：从 A 到 B 有3条路，从 B 到 C 有4条路，从 A 经 B 到 C 有 $3 \times 4 = 12$ 种走法。

2. 排列与组合

2.1 排列

无重复排列：从 $n$ 个不同元素中取 $r$ 个排列：

$P(n, r) = \frac{n!}{(n-r)!}$

全排列：$P(n, n) = n!$

有重复排列：从 $n$ 个不同元素中取 $r$ 个（允许重复）排列：$n^r$

圆排列：$n$ 个不同元素的圆排列数：$(n-1)!$

2.2 组合

无重复组合：从 $n$ 个不同元素中取 $r$ 个：

$\binom{n}{r} = C(n, r) = \frac{n!}{r!(n-r)!}$

多重组合（可重复组合）：从 $n$ 种元素中取 $r$ 个（允许重复）：

$\binom{n+r-1}{r} = \binom{n+r-1}{n-1}$

例：将10个相同的球放入3个不同的盒子，有多少种方法？

可重复组合：$\binom{10+3-1}{10} = \binom{12}{10} = 66$。

2.3 组合恒等式

Pascal 恒等式：$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

二项式定理：$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$

特殊值：

• $\sum_{k=0}^{n} \binom{n}{k} = 2^n$
• $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$
• $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$（Vandermonde 恒等式的特例）

Vandermonde 恒等式：$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$

2.4 多重集的排列

设多重集 $S = \{n_1 \cdot a_1, n_2 \cdot a_2, \ldots, n_k \cdot a_k\}$，$n = n_1 + n_2 + \cdots + n_k$，则全排列数为：

$\frac{n!}{n_1! \cdot n_2! \cdots n_k!}$

例：MISSISSIPPI 的字母排列数。

$M:1$, $I:4$, $S:4$, $P:2$，共11个字母。 $\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = 34650$

3. 容斥原理

3.1 两集合

$|A \cup B| = |A| + |B| - |A \cap B|$

3.2 三集合

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

3.3 一般形式

$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i}|A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap \cdots \cap A_n|$

3.4 错排问题

$n$ 个元素的错排（derangement）数：

$D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + (-1)^n \frac{1}{n!}\right) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$

例：4个人的帽子全戴错的方案数。

$D_4 = 4!(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}) = 24 \cdot \frac{9}{24} = 9$

3.5 Euler 函数

不超过 $n$ 且与 $n$ 互素的正整数个数：

$\varphi(n) = n\prod_{p \mid n}\left(1 - \frac{1}{p}\right)$

其中 $p$ 取遍 $n$ 的所有不同素因子。

例：$\varphi(12) = 12(1 - \frac{1}{2})(1 - \frac{1}{3}) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4$。

4. 鸽巢原理

4.1 基本形式

将 $n+1$ 个物品放入 $n$ 个盒子，至少有一个盒子包含至少2个物品。

4.2 加强形式

将 $n$ 个物品放入 $k$ 个盒子，则至少有一个盒子包含至少 $\lceil n/k \rceil$ 个物品。

4.3 应用

例：在任意 $n+1$ 个正整数中，必有两个数之差是 $n$ 的倍数。

考虑这 $n+1$ 个数除以 $n$ 的余数，余数只有 $0, 1, \ldots, n-1$ 共 $n$ 种，由鸽巢原理，必有两个数余数相同，其差是 $n$ 的倍数。

例：在边长为1的正三角形中任取5个点，必有两点距离不超过 $\frac{1}{2}$。

将正三角形分为4个边长为 $\frac{1}{2}$ 的小正三角形，5个点放入4个区域，必有2个在同一区域，距离不超过 $\frac{1}{2}$。

5. 递推关系

5.1 常系数线性齐次递推

$a_n + c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} = 0$

特征方程：$x^k + c_1 x^{k-1} + \cdots + c_k = 0$

求解：

• 单根 $r$：贡献 $A r^n$
• $m$ 重根 $r$：贡献 $(A_0 + A_1 n + \cdots + A_{m-1} n^{m-1}) r^n$

例：Fibonacci 数列 $F_n = F_{n-1} + F_{n-2}$，$F_0 = 0$，$F_1 = 1$。

特征方程：$x^2 - x - 1 = 0$，$x = \frac{1 \pm \sqrt{5}}{2}$。 $F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$

5.2 常系数线性非齐次递推

$a_n + c_1 a_{n-1} + \cdots + c_k a_{n-k} = f(n)$

通解 = 齐次通解 + 非齐次特解

特解形式取决于 $f(n)$：

6. 生成函数

6.1 定义

序列 $\{a_n\}$ 的普通生成函数：

$G(x) = \sum_{n=0}^{\infty} a_n x^n$

6.2 常用生成函数

6.3 应用

例：用1元、2元、5元硬币凑出 $n$ 元的方案数。

生成函数： $G(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^5}$ $a_n$ 为 $G(x)$ 展开式中 $x^n$ 的系数。

6.4 指数生成函数

$E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$

适用于排列计数问题。

7. Catalan 数

7.1 定义

$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$

前几项：$C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42$

7.2 递推关系

$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}, \quad C_0 = 1$

7.3 组合意义

$C_n$ 计数的问题：

1. $n$ 对括号的合法匹配数
2. $n+1$ 个矩阵连乘的加括号方式数
3. 从 $(0,0)$ 到 $(n,n)$ 不越过对角线的路径数
4. $n$ 个节点的不同二叉搜索树个数
5. 凸 $n+2$ 边形的三角剖分数
6. 栈的合法出栈序列数

例：3对括号的合法匹配：$C_3 = 5$ 种。

((())), (()()), (())(), ()(()), ()()()

7.4 生成函数

$C(x) = \sum_{n=0}^{\infty} C_n x^n = \frac{1 - \sqrt{1-4x}}{2x}$

8. Stirling 数

8.1 第一类 Stirling 数

$s(n, k)$：将 $n$ 个不同元素排成 $k$ 个非空轮换的方案数。

递推：

$s(n, k) = s(n-1, k-1) + (n-1) \cdot s(n-1, k)$

边界：$s(0,0) = 1$，$s(n,0) = 0$（$n > 0$），$s(n,n) = 1$

与阶乘的关系：

$x^{\underline{n}} = x(x-1)(x-2)\cdots(x-n+1) = \sum_{k=0}^{n} s(n,k) x^k$

8.2 第二类 Stirling 数

$S(n, k)$：将 $n$ 个不同元素分成 $k$ 个非空子集的方案数。

递推：

$S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k)$

边界：$S(0,0) = 1$，$S(n,0) = 0$（$n > 0$），$S(n,n) = 1$，$S(n,1) = 1$

与幂的关系：

$x^n = \sum_{k=0}^{n} S(n,k) x^{\underline{k}}$

显式公式：

$S(n, k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$

例：$S(4, 2) = 7$。

4个元素分成2个非空子集：$\{1\}\{2,3,4\}$, $\{2\}\{1,3,4\}$, $\{3\}\{1,2,4\}$, $\{4\}\{1,2,3\}$, $\{1,2\}\{3,4\}$, $\{1,3\}\{2,4\}$, $\{1,4\}\{2,3\}$。

8.3 Bell 数

$B_n = \sum_{k=0}^{n} S(n, k)$

$B_n$ 是 $n$ 个元素的划分总数。

前几项：$B_0 = 1, B_1 = 1, B_2 = 2, B_3 = 5, B_4 = 15, B_5 = 52$

递推：$B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$

指数生成函数：$\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x - 1}$