⚡ 基础概念与核心公式
组合数学（Combinatorics）是研究离散结构的一门学科，它主要关注“有多少种”、“是否存在”以及“如何构造”等问题。对于初学者而言，掌握加法原理与乘法原理是通往高阶理论的基石。这两个看似简单的原理，实际上是解决所有复杂计数问题的逻辑起点。
1. 加法原理与乘法原理
加法原理适用于分类完成一件事的情况。如果完成一件事有 类办法，在第 1 类办法中有 种不同的方法，在第 2 类办法中有 种不同的方法……在第 类办法中有 种不同的方法，那么完成这件事共有 种不同的方法。关键在于“类”之间的互斥性。
乘法原理适用于分步完成一件事的情况。如果完成一件事需要 个步骤，做第 1 步有 种不同的方法，做第 2 步有 种不同的方法……做第 步有 种不同的方法，那么完成这件事共有 种不同的方法。关键在于“步”之间的依赖性与顺序性。
💡 记忆口诀
分类相加，分步相乘。互斥用加法，依赖用乘法。
2. 排列与组合
在确定了基本原理后，我们需要处理具体的元素选取问题。排列（Permutation）是指从 个不同元素中取出 () 个元素，按照一定的顺序排成一列。其公式为：
其中 表示 的阶乘，即 。
组合（Combination）是指从 个不同元素中取出 () 个元素并成一组，不考虑顺序。其公式为：
组合数具有对称性，即 ，这在计算中非常有用，特别是当 时，计算 会更简便。
3. 多重集排列
当元素中存在重复时，我们需要使用多重集排列公式。假设有 个元素，其中第 1 种元素有 个，第 2 种元素有 个……第 种元素有 个，且 。则不同的排列数为：
例如，单词 "BANANA" 有 6 个字母，其中 A 出现 3 次，N 出现 2 次，B 出现 1 次。其不同排列数为 种。
⚙️ 核心计数原理深度解析
随着问题的复杂化，直接枚举变得不可行，我们需要更强大的工具。容斥原理、抽屉原理和递推关系是组合数学中解决存在性问题和复杂计数问题的三大支柱。
1. 容斥原理 (Inclusion-Exclusion Principle)
容斥原理是处理“至少”、“至多”或“都不”这类条件计数问题的利器。对于两个集合 和 ，其并集的大小为：
推广到 个集合 ，并集的大小为：
应用示例：错排问题。 个人各写一张贺卡，混合后每人随机拿一张，求没有人拿到自己贺卡的方案数 。利用容斥原理，总排列数为 ，减去至少一人拿到自己的，加上至少两人拿到自己的……最终得到错排公式：。
2. 抽屉原理 (Pigeonhole Principle)
抽屉原理，又称鸽巢原理，是组合数学中最简单的原理之一，却蕴含着深刻的逻辑。基本形式是：如果有 个物体放入 个抽屉，那么至少有一个抽屉里有两个或更多的物体。
广义形式：如果有 个物体放入 个抽屉，那么至少有一个抽屉里有 个或更多的物体。
应用示例：在任意 13 个人中，至少有 2 个人的生日在同一个月。因为一年只有 12 个月（抽屉），13 个人（物体），由抽屉原理可知必然存在月份包含至少 2 人。
3. 递推关系 (Recurrence Relations)
许多组合问题可以通过将大问题分解为小问题来求解，从而建立递推关系。例如，斐波那契数列 就是典型的递推关系。在组合数学中，楼梯问题、平面分割问题等常通过递推求解。
错排问题 (Derangement)
公式：
解释：第 个人没拿到自己的贺卡，他拿到了第 个人的。若第 个人拿到了第 个人的，则剩 人错排；若没拿到，则剩 人错排。
Catalan 数
公式：
应用：括号匹配、栈操作序列、凸多边形三角剖分、不交叉连线等。
Stirling 数
第一类：排列成 个循环的方案数。
第二类：将 个元素划分到 个非空集合的方案数。
🚀 高级工具：生成函数与伯恩赛德引理
当面对极其复杂的约束条件或对称性问题时，我们需要引入代数工具和群论概念。生成函数将序列转化为多项式或幂级数，通过代数运算解决计数问题；伯恩赛德引理则用于解决在对称性影响下的计数问题。
1. 生成函数 (Generating Functions)
生成函数是将序列 编码为一个形式幂级数 的工具。它将组合问题转化为代数问题。
普通生成函数 (OGF)
用于解决组合问题，如整数分拆、硬币找零等。例如，若每个物品只能选一次，其生成函数因子为 ；若可选无限次，因子为 。
指数生成函数 (EGF)
用于解决排列问题，特别是涉及标签或顺序的问题。EGF 定义为 。乘法原理在 EGF 中对应于卷积，非常适合处理排列组合的混合问题。
2. 伯恩赛德引理 (Burnside's Lemma)
在考虑对称性（如旋转、翻转）时，直接计数会重复计算。伯恩赛德引理提供了计算“本质不同”配置数量的方法。公式为：
其中 是作用在集合 上的对称群， 是群的大小， 是在变换 下保持不变的元素个数。
应用示例：立方体涂色
用 3 种颜色给立方体的 6 个面涂色，求本质不同的涂色方案数。立方体的对称群 有 24 个元素（旋转）。我们需要分别计算每种旋转下保持不变的涂色方案数，然后求平均。例如，恒等变换保持所有 种涂色不变；绕相对面中心旋转 90 度，只有 3 种涂色不变（上下不变，侧面必须同色）。
整数分拆问题
求将整数 5 分拆为若干个正整数之和的方法数（不考虑顺序）。
生成函数为：
我们需要求 的系数。展开前几项：
(1+x+x^2+x^3+x^4+x^5+...)(1+x^2+x^4+...)(1+x^3+...)(1+x^4+...)(1+x^5+...)
通过多项式乘法， 的系数为 7。即 5 有 7 种分拆方式：5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1。
带标签的排列
考虑 3 个不同的球放入 2 个不同的盒子，每个盒子非空。
每个球有 2 种选择，总共有 种。减去全在盒子 1 或全在盒子 2 的 2 种情况，剩 6 种。
使用 EGF：每个盒子的生成函数为 （非空）。两个盒子的 EGF 为 。
我们需要 的系数乘以 。 中 的系数为 。乘以 得 6。结果一致。
项链计数
用 2 种颜色给 4 颗珠子组成的项链涂色，旋转和翻转视为相同。
对称群 有 8 个元素：4 个旋转，4 个翻转。
- 旋转 0°： 种不变。
- 旋转 90°, 270°： 种不变（所有珠子同色）。
- 旋转 180°： 种不变（对角同色）。
- 翻转 2 次（过对角线）： 种不变。
- 翻转 2 次（过边中点）： 种不变。
总数 种本质不同的项链。
💻 组合数学在算法中的应用
组合数学不仅是纯数学的研究对象，更是计算机科学中算法设计与分析的基石。从动态规划到图论算法，组合数学的思想无处不在。
1. 动态规划 (Dynamic Programming)
许多 DP 问题本质上是组合计数问题。例如，背包问题可以看作是多重集组合问题的变种；最长公共子序列 (LCS) 问题涉及子序列的计数与构造。
2. 图论计数
树的计数：Cayley 公式指出， 个标记顶点的完全图有 棵生成树。这一结论在计算机网络拓扑设计中有重要应用。
欧拉回路：判断图中是否存在欧拉回路（经过每条边恰好一次），其条件是图连通且所有顶点度数为偶数。这涉及图的结构分析。
3. 算法复杂度分析
在最坏情况分析中，组合数学帮助我们确定输入规模的增长趋势。例如，排序算法的比较次数下界为 ，这是由排列总数决定的。
| 算法/问题 | 涉及的组合数学概念 | 关键公式/结论 |
|---|---|---|
| 旅行商问题 (TSP) | 哈密顿回路计数 | (对称情况) |
| 哈希冲突 | 生日悖论 | 冲突概率 |
| 数据库索引 | B-树结构 | 节点度与树高关系 |
| 密码学 | 组合设计 | 有限几何与编码理论 |
📅 组合数学发展简史
《易经》与二进制
中国古代《易经》中的八卦与六十四卦，体现了早期的二进制思想和组合排列概念。
帕斯卡与费马
帕斯卡三角形被发现，费马与帕斯卡通信讨论赌博问题，奠定了概率论与组合数学的基础。
欧拉
欧拉解决了柯尼斯堡七桥问题，开创了图论；研究了拉丁方和正多面体计数。
凯莱与伯恩赛德
凯莱提出树的计数公式；伯恩赛德发展了群论在计数中的应用。
计算机时代
组合数学与计算机科学深度融合，NP 完全性理论、随机图论、代数组合学等分支蓬勃发展。
❓ 常见问题解答 (FAQ)
排列（Permutation）关注顺序，即元素的位置不同视为不同的结果；组合（Combination）不关注顺序，只关心选取了哪些元素。例如，从A、B中选两个，排列有AB和BA两种，组合只有{A,B}一种。在实际应用中，如果题目强调“选出来后还要排队”或“分配不同任务”，通常用排列；如果只强调“选出来”或“分组”，通常用组合。
容斥原理是一种计数技巧，用于计算多个集合并集的大小。基本思想是：先加上所有单个集合的大小，减去两两交集的大小，加上三个集合交集的大小，以此类推。常用于解决“至少有一个”、“都不满足”等计数问题。例如，计算 1 到 100 中不能被 2、3、5 整除的数的个数。
非常有用，尤其是当递推关系复杂时。生成函数将序列转化为代数对象，使得复杂的组合问题可以通过多项式运算、泰勒展开等代数方法解决。例如，求解斐波那契数列的通项公式，使用生成函数比特征方程法更直观。
如果 是质数，可以使用 卢卡斯定理 (Lucas' Theorem)：。如果 不是质数，可能需要分解质因数或使用扩展卢卡斯定理。预处理阶乘及其逆元也是常用技巧。