Inclusion–exclusion principle

Builds on Cardinality of a finite set Inclusion–exclusion for two sets

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.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Cardinality of a finite set definition
Rule of sum statement
Inclusion–exclusion for two sets statement
Inclusion–exclusion principle statement

Tag	`0FF7726C7P`
URI	`m2://0FF7726C7P`
Kind	statement, theorem
Writing	W1 stated
MSC	05A05
Status	This copy of the site has no build data. Run `m2 status 0FF7726C7P`.
Uses	Cardinality of a finite set, Inclusion–exclusion for two sets
Same as	Wikidata Q849335 Wikipedia Inclusion–exclusion principle

Inclusion–exclusion principle

Statement

Remarks

Reading path

Further reading

What this page needs for W2

What links here