容斥原理证明
假设有 \(n\) 个基础集合 \(E_1\sim E_n\)，那么有
\[\left|\bigcup_{i=1}^n E_i\right|=\sum_{k=1}^n (-1)^{k+1}\sum_{1\le i_1证明：
设有 \(c\) 个基础集合包含元素 \(x\)，在左式中 \(x\) 出现 \(1\) 次。右式中，\(x\) 出现次数为
由二项式定理
\[(a+b)^n = \sum_{k=0}^n \binom n k a^kb^{n-k} \]令 \(a=1,b=-1\)，有
\[0=\sum_{k=0}^n (-1)^k \binom n k,\binom n 0-\binom n 1+\binom n 2-\cdots=0 \]\[\therefore \binom c 1-\binom c 2+\cdots=\binom c 0=1 \]因此，\(x\) 在右式中出现次数也为 \(1\)，得证。