Inclusion–Exclusion Principle¶
For finite sets \(A_1,\ldots,A_n\):
\[
\left|\bigcup_{i=1}^n A_i\right| = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right|
\]
Two sets: \(|A \cup B| = |A| + |B| - |A \cap B|\).
Three sets: \(|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|\).
Use in counting¶
Count objects that satisfy at least one of several properties by: total minus none, or sum over intersections with alternating signs.
Derangements: permutations with no fixed point—classic inclusion–exclusion.
Complexity¶
Often \(O(2^n)\) over subsets of properties when \(n\) is small.