Inclusion-Exclusion Principle

combinatorics

Definition

Inclusion-Exclusion Principle

The Inclusion-Exclusion Principle states that the number of elements in the union of $n$ finite sets $A_1,\dots ,A_n$ is given by:

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

using an index set $I=\{1,2,\dots ,n\}$ and sum over all non-empty index subsets $J\subseteq I$.

Example

3 Intersecting Sets

When creating the union over all sets $D,E,F$, the number of unique elements in that set can be computed by:

$$|D\cup E\cup F|=|D|+|E|+|F|$$

However, there might be intersections between two of those sets, meaning that some elements are counted multiple times. Therefore, the intersections need to be subtracted:

$$|D\cup E\cup F|=|D|+|E|+|F|-|D\cap F|-|D\cap E|-|E\cap F|$$

Another problem arises: The intersection $D\cap E\cap F$ is subtracted more than once. Therefore, we need to add it back to the equation:

$$|D\cup E\cup F|=|D|+|E|+|F|-|D\cap F|-|D\cap E|-|E\cap F|+|D\cap E\cap F|$$