组合数学期末

🏆 《组合数学》期末终极通关秘籍

📦 第一部分：排列组合与基本模型 (第1章)

📌 核心公式速记

1. 全排列：$P(n,n) = n!$
2. 普通排列：$P(n,r) = \frac{n!}{(n-r)!}$
3. 普通组合：$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$
4. 圆周排列：$n$个全排为 $(n-1)!$；$n$中取$r$个排一圈为 $Q(n,r) = \frac{P(n,r)}{r}$
5. 允许重复的组合：$\bar{C}(n,r) = C(n+r-1, r)$
6. 不相邻的组合：$C(n-r+1, r)$

🎯 题型 1：组合意义解释大题（必考，5-10分）

• 解题步骤：
  1. 指出左式的现实模型：如“从 $m+n$ 个人中选出 $r$ 个人”，或“从 $(0,0)$ 走到 $(m,n)$”。
  2. 给出分类/分步依据：如“按是否包含某元素分类”、“按队伍中男女人数分类”、“按最后一步经过哪条线分类”。
  3. 解释右式的每一项：对应分类中的每一种情况。
  4. 总结：由于两边计算的是同一物理过程，由加法/乘法原则，等式成立。
• 必背等式：
  • $\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$ （选人：含不含某人）
  • $\binom{n}{l}\binom{l}{r} = \binom{n}{r}\binom{n-r}{l-r}$ （选拔：先大名单再首发 $\iff$ 先首发再替补）

🎯 题型 2：多重集/方程非负整数解问题

• 题型：求 $x_1 + x_2 + … + x_n = r$ 的解的个数。
• 解题步骤：
  1. 处理下限：若 $x_i \ge k$，令 $y_i = x_i - k \ge 0$，更新右端项 $r’ = r - k$。
  2. 套用隔板法公式：直接写出答案 $C(n+r’-1, n-1)$ 或 $C(n+r’-1, r’)$。
• 变种：排队买票找零（Catalan模型）：
  • $m$人拿100元（向右），$n$人拿50元（向上），$n \ge m$，无零钱。
  • 合法公式：$C(m+n, m) - C(m+n, m-1)$。

---

⚙️ 第二部分：递推关系与母函数 (第2章，计算重灾区)

📌 核心公式速记（母函数弹药库）

1. 普通型母函数 (OGF) 展开：
   • $\frac{1}{1-x} = 1 + x + x^2 + \dots$
   • 广义二项式定理（极重要）：$\frac{1}{(1-x)^n} = \sum_{k=0}^{\infty} C(n+k-1, k)x^k$
2. 指数型母函数 (EGF) 展开：
   • 无限制：$e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots$
   • 偶数次：$\frac{e^x + e^{-x}}{2} = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \dots$
   • 奇数次：$\frac{e^x - e^{-x}}{2} = \frac{x}{1!} + \frac{x^3}{3!} + \dots$

🎯 题型 3：母函数解限制排列/组合问题

• 解题步骤：
  1. 区分组合与排列：组合用 OGF（不除阶乘），排列用 EGF（除以阶乘）。
  2. 写出每一项的因子：例如“物品出现偶数次”，OGF写 $(1+x^2+x^4…)$，EGF写 $\frac{e^x+e^{-x}}{2}$。
  3. 全部相乘并化简：OGF利用等比数列和广义二项式定理化简；EGF利用 $e^{kx}$ 展开。
  4. 提取系数：OGF找 $x^r$ 的系数；EGF找 $\frac{x^r}{r!}$ 的系数（记得最后乘个 $r!$）。

🎯 题型 4：线性常系数递推关系的求解（全卷最大计算题，20分）

• 解题步骤（八股文，必须按步写）：
  1. 化标准式：把 $a_n$ 全部移到左边：$a_n + c_1 a_{n-1} + \dots = b(n)q^n$。
  2. 写齐次特征方程：令右边为 0，写出 $x^k + c_1 x^{k-1} + \dots = 0$。
  3. 解特征根，写齐次通解：
     • 单根 $r_1, r_2$：$a_n^* = A_1 r_1^n + A_2 r_2^n$。
     • $m$ 重根 $r$：$a_n^* = (A_0 + A_1 n + \dots + A_{m-1} n^{m-1}) r^n$。
  4. 寻找非齐次特解 $\bar{a}_n$（⚠️ 死亡深渊）： 观察右边 $b(n) \cdot q^n$：
     • 若 $q$ 不是特征根：设 $\bar{a}_n = P(n) q^n$ （$P(n)$与$b(n)$同次）。
     • 若 $q$ 是特征根（重数为 $m$）：设 $\bar{a}_n = \mathbf{n^m} \cdot P(n) q^n$。
  5. 代入求特解系数：把 $\bar{a}_n$ 代回原递推式，比较系数，解出 $P(n)$ 里的常数。
  6. 合并通解并代初值：$a_n = a_n^* + \bar{a}_n$。最后代入 $a_0, a_1$ 解出 $A_1, A_2$。

🎯 题型 5：整数拆分与特殊数列（填空/证明必考）

• Ferrers 图像两大定理：
  1. 最大数为 $k$ 的拆分数 == 分成 $k$ 个数的拆分数（共轭变换）。
  2. 互不相同的奇数拆分 == 自共轭图形拆分。
• 特殊数列必背：
  1. 错排 $D_n$：$D_n = n!(1 - \frac{1}{1!} + \frac{1}{2!} - \dots + (-1)^n \frac{1}{n!})$
  2. 第二类斯特林数 $S(n,k)$（$n$不同球放$k$相同盒无空）：$S(n,k) = S(n-1, k-1) + kS(n-1, k)$
  3. 卡特兰数 $C_n$：$C_n = \frac{1}{n+1}\binom{2n}{n}$ （进出栈、不越界格路、括号匹配、二叉树）。

---

🛡️ 第三部分：容斥原理与鸽巢原理 (第3章)

📌 核心公式速记

1. 标准容斥（求补集交）： $|\overline{A_1} \cap \overline{A_2} \dots| = N - \sum|A_i| + \sum|A_i \cap A_j| - \dots + (-1)^n|A_1 \dots A_n|$
2. 广义容斥（求恰好满足 $m$ 个）： $\beta(m) = \alpha(m) - \binom{m+1}{m}\alpha(m+1) + \binom{m+2}{m}\alpha(m+2) - \dots$ (注意：$\alpha(k)$ 代表所有 $k$ 个集合的交集大小之和)。
3. 棋盘多项式降阶：$R(C) = x \cdot R(C_{(I)}) + R(C_{(e)})$
4. 有禁区排列公式：$Ans = n! - r_1(n-1)! + r_2(n-2)! - \dots$

🎯 题型 6：带上限约束的方程解（容斥解法）

• 题型：$x_1 + x_2 + x_3 = r$，且 $x_1 \le m_1, x_2 \le m_2$。
• 解题步骤：
  1. 算全集 $N$：无视上限，只算 $\ge 0$ 的解 $\Rightarrow C(n+r-1, n-1)$。
  2. 设违规集合：设 $A_i$ 为 $x_i \ge m_i + 1$ 的集合。

  3. 算交集：对于 $

     A_i

     $，令 $y_i = x_i - (m_i+1) \ge 0$，代入方程使等号右边减少 $m_i+1$，求新方程非负整数解。

  4. 套容斥公式：$N - \sum|A_i| + \sum|A_i \cap A_j| - \dots$ （🔥 奇招：如果变量上限之和跟目标值 $r$ 极度接近，立刻使用变量代换 $y_i = \text{max}_i - x_i$，瞬间转化为纯隔板法！）

🎯 题型 7：有禁区的排列/员工分配问题

• 解题步骤：
  1. 画禁区棋盘：画 $n \times n$ 网格，把不能去的地方涂黑（提取阴影 $C$）。
  2. 求棋盘多项式 $R(C)$：找十字交叉点（度数最高的格子）用 $x R(C_{(I)}) + R(C_{(e)})$ 不断降阶，直到棋盘分裂，利用乘法公式得出 $1 + r_1x + r_2x^2 + \dots$。
  3. 代入禁区公式：将 $r_1, r_2, \dots$ 提取出来，代入 $n! - r_1(n-1)! + r_2(n-2)! \dots$ 求出最终答案。

🎯 题型 8：鸽巢原理与 Ramsey 证明大题 (压轴 10分)

• 解题步骤（八股文默写）：
  1. 指定鸽子：“设…为鸽子，共 $N$ 只。”（如：构造前缀和序列 $s_1 \dots s_n$ 与 $s_1+k \dots s_n+k$ 组合成鸽子群）。
  2. 指定鸽巢：“设…为鸽巢，共 $M$ 个。”（如：余数的取值范围、数值的最大边界）。
  3. 比大小：“因为鸽子数 $N >$ 鸽巢数 $M$ …”
  4. 下结论：“根据鸽巢原理，必有至少两只鸽子同巢，即…相等，相减得证/产生冲突得证。”
• 必背证明树：$R(3,3)=6$： 六个顶点，任取一点 $V_1$，连出 5 条边。分红蓝两色，由广义鸽巢 $\lceil 5/2 \rceil = 3$，必有 3 条同色边（假定红色连 $V_2, V_3, V_4$）。观察 $\triangle V_2V_3V_4$，若有一条红边，则组成红三角；若无红边（全蓝），则自身构成蓝三角。得证。

---

🚫 考场生存“三大纪律”

1. 遇到大数绝不硬算：老师说了不带计算器，写出 $C(18, 5) \times 6!$ 或者 $2^n$ 就是最终答案，硬算算错反而扣分！
2. 不要在特解上翻车：第二章非齐次递推，看到右边有 $q^n$，一定要回去看一眼第一步的特征根有没有 $q$！有的话必须乘 $n$！
3. 组合意义解释全靠写字：写“左式代表…”和“右式代表…”，把现实生活中的“选人、走迷宫、涂颜色”编个故事套进去，文字写得越清晰，给分越高。