容斥原理是一种组合数学方法，可以求集合并的大小，计算复合事件的概率。
容斥原理
对 n 个集合求并集中的元素，可以先加起来，再逐项减去交集中的元素。
$\left|\bigcup{i=1}^n A_i\right|=\sum{i=1}^n\left|Ai\right|-\sum{i, j: 1 \leq i<j \leq n}\left|Ai \cap A_j\right|+\sum{i, j, k:} \sum_{1 \leq i<j<k \leq n}\left|A_i \cap A_j \cap A_k\right|-\ldots+(-1)^{n-1}\left|A_1 \cap \ldots \cap A_n\right|$
写成求和的形式：
$\left|\bigcup{i=1}^n A_i\right|=\sum{C \subseteq B}(-1)^{\operatorname{size}(C)-1}\left|\bigcap_{e \in C} e\right|$
证明
n 较小时，可以通过韦恩图来理解。
一般地，我们可以证明对于任意一个元素，只在等式右边加了1次：
假设这一元素在 k 个集合中出现，则
C = 1 项：加了 k 次。
C = 2 项：$- C_k^2$.
……
C = k: $(-1)^{k-1}C_k^k$.
对这些项求和，得到一个多项式：
$T=C_k^1-C_k^2+C_k^3-\ldots+(-1)^{i-1} \cdot C_k^i+\ldots+(-1)^{k-1} \cdot C_k^k$
注意到：
$(1-x)^k = C_k^0 -C_k^1\cdot x + C_k^2 \cdot x^2 +\dots + (-1)^k\cdot C_k^k \cdot x^k.$
$T= -(1-1)^k + 1 = 0, T = 1.$
例子1: 方程整数解问题。
已知 $0 \leq x_i \leq 8$, 方程 $x_1 + x_2 + \dots + x_6 = 20$ 的整数解有多少？
解：
假设 x 均为自然数，则一共有 $C_{25}^5$ 种解。（20个1和5个分隔板共25个位置，取5个为分隔板。）
考虑某一个 $xk \geq 9$ 的情况。25个位置中，固定了9个位置，再安排5个分隔板，所以解的数目 $|A_k| = C{16}^5$.
计算 $x_k \geq 9$ 和 $x_p \geq 9$ 的交集：
因为不可能有3个及以上的x超过8，所以我们最多只需要考虑两两相交的情况。利用容斥原理：