研究生课程 · 组合数学
组合数学
组合数学研究"有多少种方式"：排列、分组、配对、着色、走格。它的三大武器——鸽笼（存在性）、容斥（精确计数）、生成函数（把数列变成代数）——支撑着算法设计与复杂度分析。
1 计数的基本原理
概念排列、组合与二项式恒等式
乘法原理（分步相乘）、加法原理（分类相加）。
排列 P(n,r) = n!/(n−r)!（有顺序）；组合 C(n,r) = n!/[r!(n−r)!]（无顺序）。
多重集排列：n 个元素含重复，全排列数 = n!/(n₁!n₂!…)；多重集组合（隔板法）：C(n+k−1, k−1)。
常用恒等式：帕斯卡 C(n,r) = C(n−1,r−1) + C(n−1,r)；ΣᵣC(n,r) = 2ⁿ；范德蒙德 C(m+n,r) = Σ C(m,k)C(n,r−k)； Hockey-stick Σ_{i=r}^{n}C(i,r) = C(n+1,r+1)。
排列 P(n,r) = n!/(n−r)!（有顺序）；组合 C(n,r) = n!/[r!(n−r)!]（无顺序）。
多重集排列：n 个元素含重复，全排列数 = n!/(n₁!n₂!…)；多重集组合（隔板法）：C(n+k−1, k−1)。
常用恒等式：帕斯卡 C(n,r) = C(n−1,r−1) + C(n−1,r)；ΣᵣC(n,r) = 2ⁿ；范德蒙德 C(m+n,r) = Σ C(m,k)C(n,r−k)； Hockey-stick Σ_{i=r}^{n}C(i,r) = C(n+1,r+1)。
2 鸽笼原理
定理抽屉里的必然
简单形式：n+1 个物体放入 n 个抽屉 ⇒ 必有抽屉含 ≥ 2 个物体。
加强形式：n 个物体放入 k 个抽屉 ⇒ 必有抽屉含 ≥ ⌈n/k⌉ 个。
典型应用：任取 13 人必有两人同月生；n+1 个 ≤ 2n 的正整数中必有两个互质（相邻数）；拉姆齐数 R(3,3)=6（任何 6 人中必有 3 人互相认识或互相陌生）。
加强形式：n 个物体放入 k 个抽屉 ⇒ 必有抽屉含 ≥ ⌈n/k⌉ 个。
典型应用：任取 13 人必有两人同月生；n+1 个 ≤ 2n 的正整数中必有两个互质（相邻数）；拉姆齐数 R(3,3)=6（任何 6 人中必有 3 人互相认识或互相陌生）。
随堂检测计数与鸽笼
3 容斥原理
定理多退少补
|A∪B∪C| = |A|+|B|+|C| − |A∩B|−|A∩C|−|B∩C| + |A∩B∩C|
补集形式（数论利器）：≤N 中能被 a₁..aₖ 之一整除的个数 = Σ⌊N/aᵢ⌋ − Σ⌊N/lcm⌋ + …
经典应用：欧拉函数 φ(n) = n·Π(1−1/p)；错排数 Dₙ = n!·Σ(−1)ᵏ/k!。
补集形式（数论利器）：≤N 中能被 a₁..aₖ 之一整除的个数 = Σ⌊N/aᵢ⌋ − Σ⌊N/lcm⌋ + …
经典应用：欧拉函数 φ(n) = n·Π(1−1/p)；错排数 Dₙ = n!·Σ(−1)ᵏ/k!。
4 生成函数
概念把数列编码成多项式
普通生成函数 G(x) = Σaₙxⁿ；
关键对应：组合问题的"独立选择" ↔ 生成函数相乘（系数卷积恰好合并方案数）。
常用：1/(1−x) = Σxⁿ（无限取）；1/(1−x)ᵏ = ΣC(n+k−1,k−1)xⁿ（隔板法）；斐波那契的 G(x) = x/(1−x−x²)。
指数生成函数（排列问题）：Σaₙxⁿ/n!。
关键对应：组合问题的"独立选择" ↔ 生成函数相乘（系数卷积恰好合并方案数）。
常用：1/(1−x) = Σxⁿ（无限取）；1/(1−x)ᵏ = ΣC(n+k−1,k−1)xⁿ（隔板法）；斐波那契的 G(x) = x/(1−x−x²)。
指数生成函数（排列问题）：Σaₙxⁿ/n!。
5 递推关系
方法特征根法解常系数线性递推
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂：特征方程 r² = c₁r + c₂。
① 两异实根 r₁, r₂ ⇒ aₙ = A r₁ⁿ + B r₂ⁿ；② 重根 r ⇒ (A + Bn)rⁿ；③ 共轭复根 ρe^{±iθ} ⇒ ρⁿ(A cos nθ + B sin nθ)。
斐波那契：F₁ = F₂ = 1，特征根 φ = (1+√5)/2 与 ψ = (1−√5)/2，Binet 公式 Fₙ = (φⁿ − ψⁿ)/√5。
① 两异实根 r₁, r₂ ⇒ aₙ = A r₁ⁿ + B r₂ⁿ；② 重根 r ⇒ (A + Bn)rⁿ；③ 共轭复根 ρe^{±iθ} ⇒ ρⁿ(A cos nθ + B sin nθ)。
斐波那契：F₁ = F₂ = 1，特征根 φ = (1+√5)/2 与 ψ = (1−√5)/2，Binet 公式 Fₙ = (φⁿ − ψⁿ)/√5。
6 Catalan 数、Stirling 数与错排
概念三个明星数列
Catalan 数 Cₙ = C(2n,n)/(n+1)：合法括号序、n+1 边形三角剖分、不越过对角线的格路、二叉树计数。1, 1, 2, 5, 14, 42, 132…
递推 Cₙ₊₁ = ΣCᵢCₙ₋ᵢ；反射原理：好路径 C(2n,n) − C(2n,n+1)。
第二类 Stirling 数 S(n,k)：n 元集划分成 k 块的方案数，n 个球放 k 个相同盒子（不空）。
错排 Dₙ：n 个元素全部不在原位的排列；Dₙ = n!Σ(−1)ᵏ/k! → n!/e（信封问题）。
递推 Cₙ₊₁ = ΣCᵢCₙ₋ᵢ；反射原理：好路径 C(2n,n) − C(2n,n+1)。
第二类 Stirling 数 S(n,k)：n 元集划分成 k 块的方案数，n 个球放 k 个相同盒子（不空）。
错排 Dₙ：n 个元素全部不在原位的排列；Dₙ = n!Σ(−1)ᵏ/k! → n!/e（信封问题）。