包除原理

二集合の場合

$|A \cup B| = |A| + |B| - |A \cap B|$

両方に属する要素を二度数えているため、共通部分を一度引く。

一般形

$n$ 個の集合では、空でない添字集合 $S$ ごとに共通部分を取り、$|S|$ が奇数なら加え、偶数なら引く。

$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \ne S \subseteq \{1,\dots,n\}} (-1)^{|S|+1}\left|\bigcap_{i\in S} A_i\right|$

部分集合を全探索する実装は $O(2^n)$ なので、$n$ が小さく共通部分を高速に評価できる場合に有効である。