Principle of Inclusion–Exclusion (PIE): Fundamentals and Extensions

Lesson · Intermediate

Combinatorics

Inclusion–Exclusion Principle for two sets

For finite sets A and B:

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

Inclusion–Exclusion Principle for three sets

For finite sets A, B, and C:

|A\cup B\cup C| =|A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C|

General Inclusion–Exclusion Principle for n sets

For sets A₁, A₂, ..., Aₙ:

\left|A_1\cup A_2\cup\cdots\cup A_n\right| = \sum_i |A_i| -\sum_{i<j}|A_i\cap A_j| +\sum_{i<j<k}|A_i\cap A_j\cap A_k| -\cdots

In compact form, the general principle is:

\left|\bigcup_{i=1}^{n}A_i\right| = \sum_{k=1}^{n}(-1)^{k+1} \sum_{1\le i_1<i_2<\cdots<i_k\le n} \left|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}\right|

Counting elements in exactly one set

Let E_j denote the number of elements that are contained in exactly j of the sets A₁, A₂, ..., Aₙ.

For two sets:

E_1=|A_1|+|A_2|-2|A_1\cap A_2|

For three sets:

E_1 = |A_1|+|A_2|+|A_3| -2|A_1\cap A_2| -2|A_1\cap A_3| -2|A_2\cap A_3| +3|A_1\cap A_2\cap A_3|

The coefficients here are different from those in the ordinary Inclusion–Exclusion formula.

This is the natural extension of the exactly one set section.

Define

S_k = \sum_{1\le i_1<\cdots<i_k\le n} \left|A_{i_1}\cap\cdots\cap A_{i_k}\right|

Then the number Eᵣ of elements contained in exactly r sets is

\boxed{ E_r = \sum_{k=r}^{n} (-1)^{k-r} \binom{k}{r} S_k }

For r = 1,

\boxed{ E_1=S_1-2S_2+3S_3-4S_4+\cdots }