---
tag: 0FF7726C7P
kind: statement
role: theorem
name: Inclusion–exclusion principle
msc: [05A05]
uses: [05099E1NMJ, 0C4YEQ9H5E]
sources:
  - url: https://en.wikipedia.org/wiki/Inclusion–exclusion_principle
    locator: Formula
same_as:
  wikidata: Q849335
  wikipedia: 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|0C4YEQ9H5E]].
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|03RSJXF728]] 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.