组合数学基础

#计数原理

#加法原理

完成某件事有 $n$ 种途径，每种途径有 $p_i$ 个不同的方案，则完成这件事的方案总数为

$$\sum_{i = 1}^{n} p_i$$

#乘法原理

完成某件事需要进行 $n$ 个步骤，每个步骤有 $p_i$ 个不同的方案，则完成这件事的方案总数为

$$\prod_{i = 1}^{n} p_i$$

#排列组合

#排列数

#定义

从 $n$ 个不同的元素中取出 $m$ 个不同的元素作为一个排列，产生的不同排列数量记为 $\mathrm A_{n}^{m}$。排列数的计算公式为：

$$\mathrm A_{n}^{m} = n(n - 1)(n - 2) \cdots (n - m + 1) = \frac{n!}{(n - m)!}$$

#特化

1. 当 $m = 0$ 时，只有一种方案即什么都不选；
2. 当 $m = n$ 时，排列为全排列 $\mathrm A_{n}^{m} = \mathrm A_{n}^{n} = n!$；
3. 当 $m > n$ 时，排列数为 $0$。

#组合数

#定义

从 $n$ 个不同元素种取出 $m$ 个元素作为一个集合，产生的不同集合数量记为 $\mathrm C_{n}^{m}$，也常用 $\displaystyle \binom{n}{m}$ 表示。组合数的计算公式为：

$$\mathrm C_{n}^{m} = \frac{\mathrm A_{n}^{m}}{\mathrm A_{m}^{m}} = \frac{n!}{m!(n - m)!}$$

#特化

1. 当 $m = 0$ 时，只有一种方案即什么都不选；
2. 当 $m = n$ 时，只有一种方案即全选；
3. 当 $m > n$ 时，组合数为 $0$。

#性质

1. $\displaystyle \binom{n}{m} = \binom{n}{n - m}$，选择 $m$ 个相当于选择 $n - m$ 个留下来；
2. Pascal 公式：$\displaystyle \binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}$，常用于递推求组合数；
3. $\displaystyle \sum_{m = 0}^{n} \binom{n}{m} = 2^n$；
4. $\displaystyle \sum_{k = 0}^{n} (-1)^k \binom{n}{i} = [n = 0]$；
5. $\displaystyle \sum_{k = 0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$；
6. 斐波那契数列：$\displaystyle F_{n + 1} = \sum_{k = 0}^{n} \binom{n - k}{k}$。

#多重集的排列数

多重集是指包含重复元素的广义集合。设 $S = \{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\}$ 表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集，$S$ 的全排列个数为：

$$\frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}$$

#多重集的组合数

设 $S = \{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\}$ 表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集。那么对于整数 $r$（$r < n_i, \forall i \in [1, k]$），从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数就是 多重集的组合数。这个问题等价于 $x_1 + x_2 + \cdots + x_k = r$ 的非负整数解的数目，可以用插板法解决，答案为：

$$\binom{r + k - 1}{k - 1}$$

#二项式定理

$$(a + b) ^ n = \sum_{k = 0}^{n} \binom{n}{k} a^{k} b^{n - k}$$

#证明

可以应用数学归纳法来证明二项式定理。

当 $n = 1$ 时，有：

$$\begin{aligned} & (a + b)^1 \\ =& \binom{n}{0} a^0 b^1 + \binom{n}{1} a^1 b^0 \\ =& a + b \end{aligned}$$

此情况下命题成立。

假设 $n = m$ 时命题成立，令 $n = m + 1$，有：

$$\begin{aligned} (a + b)^{n} &= (a + b) (a + b)^m \\ &= (a + b) \sum_{k = 0}^{m} \binom{m}{k} a^{k} b^{m - k} \\ &= a \sum_{k = 0}^{m} \binom{m}{k} a^{k} b^{m - k} + b \sum_{k = 0}^{m} \binom{m}{k} a^{k} b^{m - k} \\ &= \sum_{k = 0}^{m} \binom{m}{k} a^{k + 1} b^{m - k} + b \sum_{k = 0}^{m} \binom{m}{k} a^{k} b^{m - k + 1} \\ &= \sum_{k = 1}^{m + 1} \binom{m}{k - 1} a^k b^{m - k + 1} + b \sum_{k = 0}^{m} \binom{m}{k} a^k b^{m - k + 1} \\ &= \sum_{k = 0}^{m + 1} (\binom{m}{k - 1} + \binom{m}{k}) a^k + b^{m - k + 1} \\ &= \sum_{k = 0}^{m + 1} \binom{m + 1}{k} a^k + b^{m - k + 1} \\ &= \sum_{k = 0}^{n} \binom{n}{k} a^k + b^{n - k} \\ \end{aligned}$$

故命题成立。证毕。

#自然数平方和公式

$$\sum_{i = 1}^{n} i^2 = \frac{n(n + 1)(2n + 1)}{6}$$

OEIS：A000330。

#证明

可以应用数学归纳法来证明自然数平方和公式。

当 $n = 1$ 时，有：

$$\begin{aligned} 1^2 &= 1 \\ &= \frac{1 \times 2 \times 3}{6} \\ &= 1 \\ \end{aligned}$$

此情况下公式成立。

假设 $n = k$ 时公式成立，令 $n = k + 1$，有：

$$\begin{aligned} & 1^2 + 2^2 + 3^2 + \cdots + (n - 1)^2 + n^2 \\ =& 1^2 + 2^2 + 3^2 + \cdots + k^2 + (k + 1)^2 \\ =& \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 \\ =& \frac{k(k + 1)(2k + 1) + 6(k + 1)^2}{6} \\ =& \frac{(k + 1)[k(2k + 1) + 6(k + 1)]}{6} \\ =& \frac{(k + 1)(2k^2 + 7k + 6)}{6} \\ =& \frac{(k + 1)(2k + 3)(k + 2)}{6} \\ =& \frac{n(n + 1)(2n + 1)}{6} \\ \end{aligned}$$

故公式成立。证毕。

#Lucas 定理

对于质数 $p$，有：

$$\binom{n}{m} \bmod p = \binom{\lfloor n / p \rfloor}{\lfloor m / p \rfloor} \cdot \binom{n \bmod p}{m \bmod p} \bmod p$$

#代码

完整代码请在 GitSB 上查看。

1
2
3
4

int lucas(int n, int m, int p) {
    if (!m) return 1;
    return static_cast<long long>(C(n % p, m % p, p)) * lucas(n / p, m / p, p) % p;
}

#Catalan 数（卡特兰数）

#定义

$$\mathit{Cat}_n = \begin{cases} 1 & (n \in \{1, 2\}) \\ \sum_{i = 1}^{n} \mathit{Cat}_{i - 1} \cdot \mathit{Cat}_{n - i} & (n \geq 2, n \in \N^*) \\ \end{cases}$$

递推定义：

$$\mathit{Cat}_n = \frac{4n - 2}{n + 1} \mathit{Cat}_{n - 1}$$

通项公式：

$$\mathit{Cat}_n = \frac{\binom{2n}{n}}{n + 1} ~~~ (n \geq 2, n \in \N^*)$$

#组合意义

1. 给定 $n$ 个 $0$ 和 $n$ 个 $1$，他们按照某种顺序排成一个长度为 $2n$ 的序列，满足任意前缀中 $0$ 的个数都不少于 $1$ 的个数的序列的数量可以记作 $\mathit{Cat}_n$；
2. 一个栈的进栈序列为 $1, 2, 3, \dots, n$，不同的出栈序列的方案数；
3. $n$ 个节点可以构造的二叉树数目；
4. 在圆上选择 $2n$ 个点，将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数；
5. 等等。

#二项式反演

记 $f_n$ 表示恰好使用 $n$ 个不同元素形成特定结构的方案数，$g_n$ 表示从 $n$ 个不同元素中选出 $i \geq 0$ 个元素形成特定结构的总方案数。

若已知 $f_n$ 求 $g_n$，那么显然有：

$$g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i$$

若已知 $g_n$ 求 $f_n$，那么：

$$f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i$$

上述已知 $g_n$ 求 $f_n$ 的过程，就称为 二项式反演。

#参考资料

1. 0x36 组合计数，《算法竞赛进阶指南》（ISBN 978-7-83009-313-6，河南电子音像出版社），李煜东，2019 年 5 月第 5 次修订版。
2. 排列组合，OI Wiki，2022 年 7 月 17 日。
3. 卡特兰数，OI Wiki，2022 年 2 月 25 日。
4. 组合数学，石家庄市第二中学信息学竞赛集训，张闰清，2022 年 1 月 19 日。