Inclusion-Exclusion Principle

combinatorics

Definition

Inclusion-Exclusion Principle

The inclusion-exclusion principles that state the number of elements of of $n$ finite sets $A_1,\dots ,A_n$ is given by:

$$|\bigcup _{i=1}^n{A}_i|=\sum _{\varnothing \ne I\subseteq \{1,\dots ,n\}}(-1{)}^{|I|-1}\cdot |\bigcup _{i\in I}{A}_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, their 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|$$