Toolkit 50

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

For finite sets $A$ and $B$ :

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

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|

For sets $A_1,A_2,\dots,A_n$ :

|A_1\cup A_2\cup\cdots\cup A_n|=\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|

Let $P_{A_1,A_2,\dots,A_n}$ denote the number of elements that are contained in exactly one of the sets $A_1,A_2,\dots,A_n$ .

For two sets:

P_{A_1,A_2}=|A_1|+|A_2|-2|A_1\cap A_2|

For three sets:

P_{A_1,A_2,A_3}=|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 the ordinary Inclusion–Exclusion formula.

Related Problems