Inclusion-Exclusion Principle

combinatorics

Definition

Inclusion-Exclusion Principle

Let $A_1,\dots ,A_n$ be finite sets indexed by the index set $I=\{1,\dots ,n\}$. The inclusion–exclusion principle computes the number of elements in their union by alternately adding and subtracting the sizes of their intersections:

$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{\varnothing \ne J\subseteq I}(-1{)}^{|J|+1}\left|\bigcap _{j\in J}{A}_j\right|.$$

Terms involving one set are added, intersections of two sets are subtracted, intersections of three sets are added, and so on.

Two finite sets $n=2$ gives

Setting

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

Adding $|A|$ and $|B|$ counts each element of the intersection twice. Subtracting $|A\cap B|$ removes one copy, leaving every element of the union counted once.

Three finite sets $n=3$ gives

Setting

$$\begin{array}{rl}|A\cup B\cup C|=& |A|+|B|+|C|\\ & -|A\cap B|-|A\cap C|-|B\cap C|\\ & +|A\cap B\cap C|.\end{array}$$

The pairwise intersections remove the double counts. Their common intersection is then added back because it was subtracted once for each of the three pairs.

Why the Signs Alternate

Fix an element $x$ that belongs to exactly $k$ of the sets. It appears in $\left(\genfrac{}{}{0ex}{}{k}{r}\right)$ intersections of $r$ sets, so its total contribution to the right-hand side is

$$\sum _{r=1}^k(-1{)}^{r+1}(\genfrac{}{}{0ex}{}{k}{r})=1,$$

because ${\sum }_{r=0}^k(-1{)}^r(\genfrac{}{}{0ex}{}{k}{r})=(1-1{)}^k=0$. Thus every element of the union is counted exactly once.

Examples

3 Intersecting Sets

Include the individual sets

Begin with

$$S_1=|D|+|E|+|F|.$$

This counts an element once for every set containing it. An element in exactly two sets is therefore counted twice, while an element in all three sets is counted three times.

Exclude the pairwise intersections

Subtract each pairwise overlap:

$$S_2=S_1-|D\cap E|-|D\cap F|-|E\cap F|.$$

An element in exactly two sets belongs to one pairwise intersection, so its count becomes $2-1=1$. An element in all three sets belongs to all three pairwise intersections, so its count becomes $3-3=0$.

Include the triple intersection again

The central region must be restored once. Hence

$$\begin{array}{rl}|D\cup E\cup F|=& |D|+|E|+|F|\\ & -|D\cap E|-|D\cap F|-|E\cap F|\\ & +|D\cap E\cap F|.\end{array}$$

The correction leaves every element counted exactly once.