auto_ai 知识库

Appearance

容斥原理是处理"至少/至多、排除重复计数"的利器。本笔记覆盖容斥原理基本形式与推论、四类典型应用、对称筛公式、错位排列以及棋盘多项式与有限制排列。

容斥原理（核心考点） ​

基本形式 ​

设 S 为有穷集，P₁,…,Pₘ 是 m 种性质，Aᵢ 是具有性质 Pᵢ 的元素集。不具有任何性质的元素数：

|S − A₁ − … − Aₘ| = |S| − Σ|Aᵢ| + Σ|Aᵢ∩Aⱼ| − Σ|Aᵢ∩Aⱼ∩Aₖ| + … + (−1)ᵐ|A₁∩…∩Aₘ|

推论：至少具有一条性质的元素数 = |S| − 上面结果。

记忆口诀："奇加偶减"——单元素交集项为负（被减去），两两交集项为正，三三交集项为负……交替加减。

证明思路（组合分析） ​

每个元素按"具有的性质条数"贡献计数：不具有性质贡献 1；具有 n 条性质的元素贡献 (1−1)ⁿ = 0（n≥1）。

典型应用（考点） ​

1. 计数多重集的 r-组合数 ​

求多重集 {3·a, 4·b, 5·c} 的 10-组合数：设 S 为无限制 10-组合，A₁ = "至少含 4 个 a"，A₂ = "至少含 5 个 b"，A₃ = "至少含 6 个 c"，用容斥排除。

关键：性质的设定与要求条件相反——把"不超过上限"转成"减去超过上限的"。

2. 计数限制条件下的元素数（素数个数） ​

不超过 120 的素数个数：合数必含素因子 2,3,5,7。用容斥排除被 2、3、5、7 整除的数。

3. 计算欧拉函数 φ(n) ​

φ(n) = 小于 n 且与 n 互素的自然数个数。若 n = p₁ʳ¹…pₖʳᵏ，则：

φ(n) = n·(1−1/p₁)(1−1/p₂)…(1−1/pₖ)

（对 n 做素因子分解后，用容斥排除被各素因子整除的数）

4. 证明组合恒等式 ​

把恒等式两边解释为同一集合的两种计数方式。

对称筛公式 ​

当各性质的交集大小只取决于交集元素个数时（对称情形）：

|S 中不具有任何性质的元素数| = Σ (−1)ᵏ·C(m,k)·Nₖ

其中 Nₖ 是任意 k 个性质交集的公共大小。

错位排列（重点） ​

  • 错位排列数 Dₙ：n 个元素的排列中，每个元素都不在原来位置的排列数
  • 公式：Dₙ = n!·[1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!]
  • 递推：Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂)，D₁=0, D₂=1
  • 性质：Dₙ 为偶数当且仅当 n 为奇数；n 充分大时 Dₙ/n! → 1/e

例：4 封信装 4 个信封全装错的方法数 D₄ = 9。

棋盘多项式与有限制排列（难点） ​

基本对应 ​

  • n 个棋子放在 n×n 棋盘，每行每列至多一个 ⇔ n 元排列
  • 有限制排列（某些位置不允许放）⇔ 有禁区的布棋方案
  • rₖ(C)：k 个棋子放入禁区 C 的方案数；棋盘多项式 = Σ rₖ(C)xᵏ

有禁区排列计数定理 ​

有禁区排列数 = n! − r₁·(n−1)! + r₂·(n−2)! − … + (−1)ⁿrₙ·0!

其中 rᵢ 是 i 个棋子布置到禁区的方案数（即棋盘多项式系数）。

应用 ​

  • 错排：禁区为主对角线，rₖ = C(n,k)，代回即得 Dₙ
  • 工作分配：G/L/W/Y 四人不能从事的工作构成禁区，用棋盘多项式计算可行分配数

一句话总结 ​

容斥原理"奇加偶减"，难点在设好性质（反向设）；错排 Dₙ 三个公式（求和/递推/极限）必背；有禁区排列 = n! − r₁(n−1)! + r₂(n−2)! − …

相关概念 ​