组合数学笔记
计数原理
一、加法原理
无相关性的两件任务，完成第一件有 \(n_1\) 种方式，第二件有 \(n_2\) 种方式，则总方式为 \(n_1 + n_2\) 种。
二、乘法原理
在第一件事基础上完成第二件事，总方式有：\(n_1 \cdot n_2\) 种。
三、减法原理（即容斥原理）
记 \(n(A)\) 表示事件 \(A\) 发生的方式数：
\(n(A \cup B) = n(A) + n(B) - n(A \cap B)\)
概率形式：
\(P(A \cup B) = P(A) + P(B) - P(A \cap B)\)
四、除法法则
若任务 \(A\) 可由 \(n\) 种方式完成，且每种方式重复 \(d\) 次，在 \(n\) 种方式中恰有 \(d\) 种与之对应，则完成 \(A\) 的方法数为 \(\frac{n}{d}\)。
集合语言理解：若有限集 \(A\) 是 \(n\) 个有 \(d\) 个元素的互斥集合的并集，则 \(n = \frac{|A|}{d}\)，\(|A|\) 表示 \(A\) 的势（元素个数）。
例1：证明烷烃中H的个数一定是偶数
设化学式为 \(\ce{C_{x}H_{y}}\)，C连四根键，H连一根键。
C-C键的总数为 \(\frac{4x - y}{2}\)（每根C-C键含2个C），因此 \(2 \mid y\)，即H的个数必为偶数。
排列与组合
排列数
\(n\) 个元素集合的排列数（取 \(r\) 个）：
\(A_n^r = n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)}\)
\(A_n^r\) 也记作 \(P_n^r\)。
组合数
\(C_n^r = \frac{n!}{r!(n-r)!} = \frac{A_n^r}{A_r^r}\)
\(C_n^r\) 也记作 \(\binom{n}{r}\)。
组合数的一些结论
- 对称性：\(\binom{m}{n} = \binom{m}{m-n}\)
- 帕斯卡恒等式：\(\binom{m}{n} = \binom{m-1}{n-1} + \binom{m-1}{n}\)
- 二项式定理：\((1+x)^n = \sum_{i=0}^{n} \binom{n}{i} x^i\)
- 范德蒙德恒等式：\(\sum_{i=0}^{k} \binom{n}{i} \binom{m}{k-i} = \binom{n+m}{k}\)
- 朱世杰恒等式：\(\sum_{i=n}^{m} \binom{i}{n} = \binom{m+1}{n+1}\)
组合的一些模型
1. \(n\) 个不同的球放入 \(m\) 个不同的桶
方案数：\(m^n\)
每个球有 \(m\) 种放法，由乘法原理可得。
2. 从 \(m\) 个桶中选出 \(n\) 个（桶有顺序）
方案数：\(A_m^n\)（直接排列）
3. 从 \(m\) 个桶中无序选 \(n\) 个
方案数：\(\binom{m}{n}\)
4. \(n\) 个相同的球放入 \(m\) 个不同的桶（桶非空）
等价于插板法：在 \(n-1\) 个空隙中插入 \(m-1\) 个板子，方案数为：
\(\binom{n-1}{m-1}\)
等价问题：方程 \(\sum_{i=1}^{m} x_i = n\)（\(x_i > 0\)）的正整数解的个数。
5. \(n\) 个相同的球放入 \(m\) 个不同的桶（桶可空）
先在每个桶中预先放1个球，转化为非空问题，方案数为：
\(\binom{n+m-1}{m-1}\)
等价问题：方程 \(\sum_{i=1}^{m} x_i = n\)（\(x_i \ge 0\)）的非负整数解的个数（令 \(x_i' = x_i + 1\)，则 \(\sum_{i=1}^{m} x_i' = n + m\)，转化为正整数解问题）。
6. \(n\) 个相同的球放入 \(m\) 个相同的桶（桶非空）
等价于将 \(n\) 划分为 \(m\) 个无序正整数的方案数（整数分拆）。
设 \(f_{n,m}\) 表示方案数，递推关系：
\(
\begin{cases}
f_{0,0} = 1 \\
f_{n,m} = f_{n-1,m-1} + f_{n-m,m}
\end{cases}
\)
解释：
- \(f_{n-1,m-1}\)：其中一个桶只放1个球，剩下 \(n-1\) 个球放入 \(m-1\) 个桶。
- \(f_{n-m,m}\)：每个桶先放1个球，再将剩下的 \(n-m\) 个球放入 \(m\) 个桶。
7. \(n\) 个相同的球放入 \(m\) 个相同的桶（桶可空）
等价于将 \(n+m\) 划分为 \(m\) 个无序正整数的方案数，答案为 \(f_{n+m,m}\)。
8. \(n\) 个不同的球放入 \(m\) 个相同的桶（桶非空）
方案数为第二类斯特林数，记作 \(\begin{Bmatrix} n \\ m \end{Bmatrix}\)，递推关系：
\(\begin{Bmatrix} n \\ m \end{Bmatrix} = m\begin{Bmatrix} n-1 \\ m \end{Bmatrix} + \begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix}\)
解释：
- \(m\begin{Bmatrix} n-1 \\ m \end{Bmatrix}\)：第 \(n\) 个球加入前 \(m\) 个等价类中。
- \(\begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix}\)：第 \(n\) 个球单独为一类。
9. \(n\) 个不同的球放入 \(m\) 个不同的桶（桶非空）
先将桶视为相同，再排列桶的顺序，方案数为：
\(m! \cdot \begin{Bmatrix} n \\ m \end{Bmatrix}\)
10. \(n\) 个不同的球放入 \(m\) 个相同的桶（桶可空）
枚举有 \(k\) 个桶装了球，方案数为：
\(\sum_{k=1}^{m} \begin{Bmatrix} n \\ k \end{Bmatrix}\)
错位排序问题
定义：对于 \(1 \sim n\) 的排列 \(a_1,a_2,\dots,a_n\)，满足 \(a_i \neq i\) 的排列个数，记为 \(f_n\)。
递推关系：
\(f_n = (n-1)f_{n-1} + (n-1)f_{n-2}\)
解释：
- \((n-1)f_{n-1}\)：已错位排列的数中选一个与 \(n\) 交换，剩下 \(n-1\) 个数仍错位。
- \((n-1)f_{n-2}\)：先交换一个数与 \(n\)，剩下 \(n-2\) 个数错位排列。
鸽巢原理
基础形式
若 \(k+1\) 个或更多物体放入 \(k\) 个盒子，则至少有一个盒子含2个或更多物体。
广义形式
\(N\) 个物体放入 \(k\) 个盒子，则至少有一个盒子含至少 \(\left\lceil \frac{N}{k} \right\rceil\) 个物体。
例2：证明 \(\forall |S|=10, S \subseteq \{1,\dots,100\}, \exists A,B \neq \varnothing, A \cap B = \varnothing, A,B \subseteq S\)，使得 \(\sum A = \sum B\)
证明：
- \(S\) 共有 \(2^{10}-1=1023\) 个非空子集。
- \(S\) 非空子集的元素和范围为 \([1, 10+99+\dots+91=495]\)，共495种可能。
- 由鸽巢原理，必存在两个不同的非空子集 \(A', B'\)，使得 \(\sum A' = \sum B'\)。
- 令 \(A = A' \setminus B'\)，\(B = B' \setminus A'\)，则 \(A,B\) 非空、不交且和相等。
例3：Erdős–Szekeres定理
每个由 \(n^2+1\) 个不同实数构成的序列，都包含一个长度为 \(n+1\) 的严格递增或递减子序列。
证明：
设序列为 \(a_1,a_2,\dots,a_{n^2+1}\)，记 \(u_k\) 为从 \(a_k\) 开始的最长递增子序列长度，\(d_k\) 为从 \(a_k\) 开始的最长递减子序列长度。
若结论不成立，则 \(u_k, d_k \le n\)，因此 \((u_k, d_k)\) 共有 \(n \times n = n^2\) 种可能。但序列有 \(n^2+1\) 项，故存在 \(k>j\)，使得 \(u_k=u_j\) 且 \(d_k=d_j\)。
分两种情况：
- 若 \(a_k > a_j\)：则从 \(a_k\) 开始的最长递增子序列长度 \(u_k \ge u_j + 1\)，矛盾。
- 若 \(a_k < a_j\)：则从 \(a_k\) 开始的最长递减子序列长度 \(d_k \ge d_j + 1\)，矛盾。
因此结论成立。
Catalan数
Dyck路径问题
定义：从 \((0,0)\) 出发至 \((n,n)\)，每步仅能向右或向上走1个单位，且路径不能超过 \(y=x\) 线（可重合），合法路径数即第 \(n\) 个Catalan数 \(C_n\)。
解法1：反射原理
- 从 \((0,0) \to (n,n)\)，共需 \(2n\) 步，其中 \(n\) 步向右、\(n\) 步向上，总路径数为 \(\binom{2n}{n}\)。
- 不合法路径（碰到 \(y=x+1\)）可通过关于 \(y=x+1\) 反射，对应从 \((0,0) \to (n-1,n+1)\) 的路径，共需 \(n-1\) 步向右、\(n+1\) 步向上，路径数为 \(\binom{2n}{n+1}\)。
因此：
\(C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}\)
解法2：递推角度
设经过点 \((i,i)\)，则：
- 从 \((0,0) \to (i,i)\)，方案数为 \(C_i\)。
- 从 \((i,i) \to (n-1,n-1)\)，方案数为 \(C_{n-i-1}\)。
- 从 \((n-1,n-1) \to (n,n)\)，仅1种走法（先右后上）。
因此递推关系：
\(C_n = \sum_{i=0}^{n-1} C_i C_{n-i-1}\)