ACM-ICPC 组合数学：排列组合详解
ACM-ICPC 组合数学：排列组合详解
排列组合是组合数学中的基础内容，在解决实际问题和竞赛编程中扮演着重要角色。本文系统地介绍了排列组合的基础知识和高级应用，从加法原理和乘法原理开始，逐步深入到排列数、组合数、插板法、多重集排列组合、圆排列等概念，并详细介绍了组合数的性质和二项式反演等高级应用。
引言
排列组合是组合数学中的基础内容。在解决实际问题和竞赛编程中，它们都扮演着重要角色。排列是指从给定的元素中按一定顺序取出若干元素进行排序；组合则是从给定的元素中取出若干元素，不考虑顺序。排列组合的核心问题是研究满足特定条件的排列和组合的数量。它与古典概率论有着密切的联系。
加法与乘法原理
加法原理
完成一个工程可以有 $n$ 种方法，记第 $i$ 种方法的数量为 $a_i (1 \le i \le n)$。那么完成这件事情共有 $S = a_1 + a_2 + \cdots + a_n$ 种不同的方法。
乘法原理
完成一个工程需要分 $n$ 个步骤，记第 $i$ 个步骤的不同方法数为 $a_i (1 \le i \le n)$。那么完成这件事情共有 $S = a_1 \times a_2 \times \cdots \times a_n$ 种不同的方法。
排列与组合基础
排列数
从 $n$ 个不同元素中，任取 $m(m \le n)$ 个元素按照一定的顺序排成一列，称为从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；所有这些排列的个数称为排列数，用符号 $A_n^m$ 或 $P_n^m$ 表示。
排列的计算公式为：
$$
A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}
$$
这里，$n!$ 代表 $n$ 的阶乘，即 $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$。
公式可以这样理解：从 $n$ 个人中选 $m$ 个人排队，第一个位置可以选 $n$ 个人，第二个位置可以选 $n-1$ 个人，以此类推，第 $m$ 个位置可以选 $n-m+1$ 个人。
全排列
全排列是排列数的一个特殊情况，当 $m=n$ 时，即从 $n$ 个人中选 $n$ 个人排队：
$$
A_n^n = n(n-1)(n-2) \cdots 1 = n!
$$
组合数
从 $n$ 个不同元素中，任取 $m(m \le n)$ 个元素组成一个集合，称为从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；所有这些组合的个数称为组合数，用符号 $\binom{n}{m}$ 表示，读作「$n$ 选 $m$」。
组合数的计算公式为：
$$
\binom{n}{m} = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}
$$
如何理解上述公式？我们考虑从 $n$ 个人中选 $m$ 个人，不排队，不在乎顺序。如果在乎顺序，那么就是排列数 $A_n^m$，如果不在乎顺序，那么就要除去重复排列的数量，这些重复排列数量为 $m!$。因此有：
$$
\binom{n}{m} = \frac{A_n^m}{m!}
$$
所以得：
$$
\binom{n}{m} = \frac{n!}{m!(n-m)!}
$$
插板法
插板法（Stars and Bars）是一种求解分配问题和不定方程整数解的技巧。
正整数和的数目
问题：将 $n$ 个完全相同的元素分成 $k$ 组，每组至少有一个元素，有多少种分法？
解法：可以在 $n$ 个元素之间插入 $k-1$ 个板子，将元素分成 $k$ 组。因此，答案是 $\binom{n-1}{k-1}$。
非负整数和的数目
问题：将 $n$ 个完全相同的元素分成 $k$ 组，每组可以为空，有多少种分法？
解法：可以先借 $k$ 个元素，再在 $n+k$ 个元素之间插入 $k-1$ 个板子，然后减去借来的 $k$ 个元素。因此，答案是 $\binom{n+k-1}{k-1}$。
不同下界整数和的数目
问题：如果对每组的元素数量设定下限，即每组至少分到 $a_i$ 个元素，总和不超过 $n$，有多少种分法？
解法：可以借 $\sum a_i$ 个元素，保证第 $i$ 组至少有 $a_i$ 个元素，将问题转化为非负整数和的问题：
$$
\binom{n - \sum a_i + k - 1}{k - 1}
$$
排列组合进阶
多重集的排列数与组合数
多重集是指包含重复元素的集合。设 $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$ 等组成的多重集。多重集的排列数为：
$$
\frac{(n_1 + n_2 + \cdots + n_k)!}{n_1!n_2! \cdots n_k!}
$$
圆排列
将 $n$ 个人排成一圈，所有的排列数记为 $Q_n^n$。考虑从不同位置断开后又形成不同的队列，因此有：
$$
Q_n^n = \frac{A_n^n}{n} = \frac{n!}{n} = (n-1)!
$$
部分圆排列的公式为：
$$
Q_n^m = \frac{A_n^m}{m} = \frac{n!}{m(n-m)!}
$$
组合数性质
组合数在竞赛编程中非常重要，因此介绍一些常见性质：
对称性：
$$
\binom{n}{m} = \binom{n}{n-m}
$$递推公式：
$$
\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}
$$杨辉三角公式：
$$
\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}
$$二项式定理：
$$
(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k
$$二项式定理的特殊情况：
$$
2^n = \sum_{k=0}^{n} \binom{n}{k}
$$
这些性质可以用于优化算法，快速计算组合数，提高编程竞赛中的解题效率。
二项式反演
二项式反演是一种重要的数学工具，用于在组合数学中转换不同的计数问题。记 $f_n$ 表示恰好使用 $n$ 个不同元素形成特定结构的方案数，$g_n$ 表示从 $n$ 个不同元素中选出 $i \geq 0$ 个元素形成特定结构的总方案数。
若已知 $f_n$ 求 $g_n$
$$
g_n = \sum_{k=0}^{n} \binom{n}{k} f_k
$$
若已知 $g_n$ 求 $f_n$
$$
f_n = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} g_k
$$
上述已知 $g_n$ 求 $f_n$ 的过程，就称为二项式反演。
证明过程
将反演公式的 $g_i$ 展开得到：
$$
f_n = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} \sum_{i=0}^{k} \binom{k}{i} f_i
$$
先枚举 $j$，再枚举 $i$，得到：
$$
f_n = \sum_{i=0}^{n} f_i \sum_{k=i}^{n} (-1)^{n-k} \binom{n}{k} \binom{k}{i}
$$
使用「组合数性质」中的公式 (11) 得到：
$$
f_n = \sum_{i=0}^{n} f_i \sum_{k=i}^{n} (-1)^{n-k} \binom{n}{i} \binom{n-i}{k-i}
$$
令 $k=i-j$，则 $i=k+j$，上式转换为：
$$
f_n = \sum_{i=0}^{n} f_i \binom{n}{i} \sum_{j=0}^{n-i} (-1)^{n-i-j} \binom{n-i}{j}
$$
使用「组合数性质」中的公式 (5) 得到：
$$
f_n = \sum_{i=0}^{n} f_i \binom{n}{i} [n-i=0]
$$
即：
$$
f_n = f_n
$$
证毕。
结论
通过对排列组合的基础知识和高级应用的学习，能够更好地理解和解决组合数学中的各种问题。这些知识不仅在数学研究中具有重要意义，在竞赛编程中也是不可或缺的工具。希望本文能帮助读者更好地掌握排列组合的相关内容，为实际应用和竞赛解题提供有力支持。