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