容斥原理

容斥原理通过交替加减集合交集的大小来计算集合并集的大小。

Definition

一个计数恒等式，指出有限集合并集的基数等于所有非空子集合的交集基数的交替和。

Scope

本主题介绍了容斥公式及其在计算避免一系列禁止属性的对象（如错排、满射、欧拉函数以及与给定数互质的整数数量）方面的应用。它引入了筛法观点和偏序集上的莫比乌斯函数推广，将该原理置于更广泛的代数背景中。

Core questions

• 有多少元素满足多个重叠条件中的至少一个？
• 如何计算避免所有禁止属性的对象？
• 错排和满射计数如何从该原理推导出来？
• 偏序集上的莫比乌斯函数如何推广容斥原理？

Key concepts

• 重叠集合的并集
• 筛法
• 通过容斥原理计算错排
• 满射计数
• 欧拉函数
• 偏序集上的莫比乌斯函数

Key theories

容斥公式

集合A_1到A_n的并集的基数等于单个集合大小之和减去两两交集之和，再加上三重交集之和，依此类推，系统地纠正了共享元素的重复计数。

偏序集上的莫比乌斯反演

斯坦利基于偏序集的推广用偏序集的莫比乌斯函数取代了容斥原理中的交替符号，将该原理与数论和格论中的反演公式统一起来。

Clinical relevance

筛法思想推广到数论（埃拉托斯特尼筛法和解析筛法）、概率论（邦费罗尼不等式限制并集概率）以及具有重叠故障模式的系统可靠性分析。

History

该原理由棣莫弗和西尔维斯特实质性提出，罗塔于1964年将其置于偏序集上莫比乌斯函数的一般理论中，成为现代组合学的一个里程碑。

Key figures

• Abraham de Moivre
• Gian-Carlo Rota

Seminal works

• stanley2011

Frequently asked questions

为什么符号是交替的？

位于多个集合中的元素被添加了太多次；减去两两交集会过度纠正，因此需要加回三重交集，从而产生交替模式，使每个元素恰好被计数一次。

与莫比乌斯函数有什么联系？

容斥原理是子集布尔格上莫比乌斯反演的特例，其中莫比乌斯函数取值为正一或负一。