组合数学

容斥原理

原理

设 $U$ 中的集合有 $n$ 种不同的属性，而第 $i$ 种属性称为 $P_i$ ,拥有属性 $P_i$ 的元素构成集合 $S_i$，那么
$|\bigcup_{i = 1}^{n}S_i| = \sum_{m=1}^{n} (-1)^{m-1} \sum_{a_i < a_{i + 1}} |\bigcap_{i = 1}^{m}S_{a_i}|$

$|\bigcap_{i = 1}^{n}S_i| = \sum_{m=1}^{n} (-1)^{m-1} \sum_{a_i < a_{i + 1}} |\bigcup_{i = 1}^{m}S_{a_i}|$

咕咕咕