Inclusion–exclusion principle

Statement

Let $A_1, \dots, A_n$ be finite sets. For a nonempty set $I \subseteq \{1, \dots, n\}$, let $A_I = \bigcap_{i \in I} A_i$. Then $$\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\varnothing \neq I \subseteq \{1, \dots, n\}} (-1)^{|I| + 1} |A_I|.$$

Remarks

For $n = 2$ this is inclusion–exclusion for two sets. A common use counts the elements of a finite set $U$ that are in none of the sets $A_i \subseteq U$. This number is $\sum_{I} (-1)^{|I|} |A_I|$, over all $I$, with $A_\varnothing = U$. The formula for the number of derangements follows in this way.

Explanations

L1 human

Add the sizes of the single sets, subtract the sizes of the pairwise intersections, add the sizes of the triple intersections, and so on. Each element of the union is then counted exactly once in total.