容斥原理

容斥原理是组合学中的一个基本结论, 用于计算一些有限集的并集的元素个数. 例如, 对有限集 $A,B$ 而言, 容斥原理说明$$|A\cup B|=|A|+|B|-|A\cap B|.$$也就是说, 为计算 $A\cup B$ 的元素个数, 只需先把 $A,B$ 各自的元素个数加起来, 再减去重复的部分, 即 $A\cap B$ 的元素个数. 又例如, 当我们有三个集合 $A,B,C$ 时, 容斥原理说明$$\begin{array}{rl}|A\cup B\cup C|=& |A|+|B|+|C|\\ & -|A\cap B|-|B\cap C|-|C\cap A|\\ & +|A\cap B\cap C|.\end{array}$$也就是说, 为计算 $A\cup B\cup C$ 的元素个数, 我们首先把 $A,B,C$ 各自的元素个数加起来, 再减去重复的部分, 两两交集的元素个数. 但这样就多减去了 $A\cap B\cap C$ 中的元素, 因此还需再把这部分加回来.

一般地, 我们可以考虑 $n$ 个集合的并, 则为了计算其元素个数, 只需先将每个集合各自的元素个数加起来, 再减去它们两两相交的元素个数, 再加上它们任意三个相交的元素个数, 再减去它们任意四个相交的元素个数, 如此等等.

1陈述

在计数中

定理 1.1 (容斥原理). 设 $n\ge 0$ 为自然数, $X$ 为有限集, 并且 $X=X_1\cup \cdots \cup X_n$, 其中每个 $X_i$ 为 $X$ 的子集. 则$$|X|=\sum _{k=1}^n(-1{)}^{k-1}\cdot (\sum _{1\le i_1<\cdots <i_k\le n}|X_{i_1}\cap \cdots \cap X_{i_k}|).$$

在测度论中

容斥原理也可以推广到一般的测度空间上.

定理 1.2 (容斥原理). 设 $(X,\mathcal{A},\mu )$ 为测度空间. 设 $n\ge 0$ 为自然数, $E\subset X$ 为可测集, 并且 $E=E_1\cup \cdots \cup E_n$, 其中每个 $E_i$ 为 $E$ 的可测子集. 则$$\mu (E)=\sum _{k=1}^n(-1{)}^{k-1}\cdot (\sum _{1\le i_1<\cdots <i_k\le n}\mu (X_{i_1}\cap \cdots \cap X_{i_k})).$$

特别地, 在概率空间中, 可将上述 $E$ 与 $E_i$ 视为事件, 而将 $\mu$ 视为概率, 从而得到关于这些事件的概率的等式.

2例子

3相关概念

术语翻译

容斥原理 • 英文 inclusion–exclusion principle • 德文 Prinzip von Inklusion und Exklusion (n) • 法文 principe d’inclusion–exclusion (m) • 日文 包除原理 (ほうじょげんり)