# principle of inclusion-exclusion

The principle of inclusion-exclusion provides a way of methodically counting the union of possibly non-disjoint sets.

Let $C=\{A_{1},A_{2},\dots A_{N}\}$ be a finite collection of finite sets. Let $I_{k}$ represent the set of $k$-fold intersections of members of $C$ (e.g., $I_{2}$ contains all possible intersections of two sets chosen from $C$).

Then

 $\left|\bigcup_{i=1}^{N}A_{i}\right|=\sum_{j=1}^{N}\left((-1)^{(j+1)}\sum_{S\in I% _{j}}|S|\right)$

For example:

 $|A\cup B|=|A|+|B|-|A\cap B|$
 $|A\cup B\cup C|=|A|+|B|+|C|-(|A\cap B|+|A\cap C|+|B\cap C|)+|A\cap B\cap C|$

The principle of inclusion-exclusion, combined with de Morgan’s laws, can be used to count the intersection of sets as well. Let $A$ be some universal set such that $A_{k}\subseteq A$ for each $k$, and let $\overline{A_{k}}$ represent the complement of $A_{k}$ with respect to $A$. Then we have

 $\left|\bigcap_{i=1}^{N}A_{i}\right|=\left|\overline{\bigcup_{i=1}^{N}\overline% {A_{i}}}\right|$

thereby turning the problem of finding an intersection into the problem of finding a union.

Title principle of inclusion-exclusion PrincipleOfInclusionexclusion 2013-03-22 12:33:25 2013-03-22 12:33:25 Mathprof (13753) Mathprof (13753) 9 Mathprof (13753) Theorem msc 05A99 inclusion-exclusion principle SieveOfEratosthenes2 BrunsPureSieve