今天我们对排列组合的核心原理与公式进行了系统性的复盘，重点不在于死记硬背，而是理解每一个公式的推导逻辑。以下是今日内容的详细总结，涵盖每个重要概念的推导思路与方法：
一、加法原理与乘法原理
-
加法原理：完成一件事有若干类方法，每类方法独立，总方法数为各类方法数之和。
推导逻辑：分类讨论，类与类之间互不影响，直接相加。 -
乘法原理：完成一件事需要若干步骤，每步方法数相乘得总方法数。
推导逻辑：分步进行，步步相关，前一步的每一种选择都会影响后一步的可能性，因此用乘法。
二、容斥原理
- 公式：
[
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|
] - 推导思路：为了避免重复计算交集部分，先加所有单集合，减去两两交集，再加回三重重叠部分。推广到多个集合时，遵循“奇加偶减”的原则。
三、排列与组合
1. 排列数公式
[
A_n^m = \frac{n!}{(n-m)!}
]
推导：从 (n) 个元素中选 (m) 个并按顺序排列，第一个位置有 (n) 种选择，第二个有 (n-1) 种，依此类推，第 (m) 个有 (n-m+1) 种，乘起来就是 (n(n-1)\cdots(n-m+1))，即 (\frac{n!}{(n-m)!})。
2. 组合数公式
[
C_n^m = \frac{n!}{m!(n-m)!}
]
推导：从排列数中去掉顺序的影响。每个组合对应 (m!) 种排列，所以 (C_n^m = \frac{A_n^m}{m!})。
四、特殊排列与组合
1. 圆排列
[
\frac{A_n^r}{r}
]
推导：线性排列有 (A_n^r) 种，但圆排列中旋转相同的视为一种，每个圆排列对应 (r) 种线性排列（以不同元素开头），所以除以 (r)。
2. 有重复元素的全排列
[
\frac{(\sum n_i)!}{\prod n_i!}
]
推导：先视为所有元素不同，得全排列数，再除以每组相同元素内部排列数（因为它们互换不产生新排列）。
3. 不相邻组合
[
C_{n-r+1}^r
]
推导F1（插空法）：
- 先将 (n-r) 个未选元素排成一列，形成 (n-r+1) 个空位。
- 选 (r) 个空位放入选中的元素，每个空位最多放一个，保证不相邻。
推导F2（变量映射法）：
- 设选中的数为 (a_1 < a_2 < \cdots < a_r)，且 (a_{i+1} \geq a_i + 2)。
- 令 (b_i = a_i - (i-1))，则 (b_i) 是严格递增且 (1 \leq b_i \leq n-r+1)。
- 原问题转化为从 (1) 到 (n-r+1) 中选 (r) 个数，即 (C_{n-r+1}^r)。
4. 有重复元素的组合
[
C_{n+r-1}^r
]
推导（插板法）：将 (r) 个相同球放入 (n) 个不同盒子（可空），相当于在 (r) 个球和 (n-1) 个板子中选位置，即 (C_{n+r-1}^{n-1}) 或 (C_{n+r-1}^r)。
五、错位排列（错排）
- 递推公式：
[
D_n = (n-1)(D_{n-1} + D_{n-2})
]
推导：- 第 (n) 个元素不能放在第 (n) 个位置，假设它放在第 (k) 个位置（(k \neq n)）。
- 情况1：第 (k) 个元素放在第 (n) 个位置，则剩下的 (n-2) 个元素错排，有 (D_{n-2}) 种。
- 情况2：第 (k) 个元素不放在第 (n) 个位置，则剩下的 (n-1) 个元素错排，有 (D_{n-1}) 种。
- (k) 有 (n-1) 种选择，所以总数为 ((n-1)(D_{n-1} + D_{n-2}))。
六、球盒问题（8种情况）
| 球 | 盒 | 是否可空 | 公式 | 推导思路 |
|---|---|---|---|---|
| 相同 | 不同 | 否 | (C_{n-1}^{k-1}) | 插板法，(n) 个球之间 (n-1) 个空位插 (k-1) 个板 |
| 相同 | 不同 | 是 | (C_{n+k-1}^{k-1}) | 先每个盒放一个虚拟球，转化为不可空 |
| 相同 | 相同 | 否 | (P(n,k)) | 正整数拆分，递推 (P(n,k)=P(n-1,k-1)+P(n-k,k)) |
| 相同 | 相同 | 是 | (P(n+k,k)) | 先每个盒放一个球，转化为不可空 |
| 不同 | 相同 | 否 | (S(n,k)) | 第二类斯特林数，递推 (S(n,k)=S(n-1,k-1)+kS(n-1,k)) |
| 不同 | 相同 | 是 | (\sum_{i=1}^k S(n,i)) | 所有非空划分之和 |
| 不同 | 不同 | 否 | (k!S(n,k)) | 先分组再分配盒子 |
| 不同 | 不同 | 是 | (k^n) | 每个球有 (k) 种选择 |
七、平面分割类问题
1. 直线分平面
- 递推：(f(n) = f(n-1) + n)
- 推导：第 (n) 条直线与前 (n-1) 条相交，被分成 (n) 段，每段将原区域一分为二，增加 (n) 个区域。
2. 折线分平面
- 递推：(f(n) = f(n-1) + 4(n-1) + 1)
- 推导：每条折线相当于2条直线，但顶点处少分1个区域。
3. 圆分平面
- 递推：(f(n) = f(n-1) + 2(n-1))
- 推导：第 (n) 个圆与前 (n-1) 个圆交于 (2(n-1)) 个点，将圆分成 (2(n-1)) 段弧，每段增加一个区域。
4. 三角形分平面
- 递推：(f(n) = f(n-1) + 6(n-1))
- 推导：每个三角形三边与前 (n-1) 个三角形各交于2点，共 (6(n-1)) 个交点，将三角形分成 (6(n-1)) 段边，每段增加一个区域。
5. 平面分空间
- 递推：(f(n) = f(n-1) + \frac{n(n-1)}{2} + 1)
- 推导：第 (n) 个平面与前 (n-1) 个平面交于 (n-1) 条直线，将平面分成 (\frac{n(n-1)}{2} + 1) 个区域，每个区域将空间一分为二。
八、卡特兰数
-
递推式：
[
C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}, \quad C_0 = 1
] -
推导：
- 选定一条边 (P_1P_n)，再选一个顶点 (P_k)（(1<k<n)）构成三角形。
- 将多边形分为三个部分：一个三角形、一个 (k) 边形、一个 (n-k+1) 边形。
- 方案数为 (C_k \cdot C_{n-k+1})，对 (k) 求和即得。
-
组合数表达：
[
C_n = \frac{1}{n+1} \binom{2n}{n}
]