容斥原理

命题陈述

对于有限集合 $A_1,\dots,A_n$，$\Big|\bigcup_{i=1}^n A_i\Big| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1}|A_1 \cap \cdots \cap A_n|$。

为什么成立?

简单地把各集合的大小相加，会把同时属于多个集合的元素重复计数。减去两两相交的部分能修正这种重复计数，但这样一来三三相交的部分又被减去太多次，因此必须再加回来，如此交替变号，直到并集中每个元素恰好被计数一次。

用到此定理的主题

相关定理

分步证明

该定理暂无分步证明。