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,\mathrm{\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
Canonical name	PrincipleOfInclusionexclusion
Date of creation	2013-03-22 12:33:25
Last modified on	2013-03-22 12:33:25
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	9
Author	Mathprof (13753)
Entry type	Theorem
Classification	msc 05A99
Synonym	inclusion-exclusion principle
Related topic	SieveOfEratosthenes2
Related topic	BrunsPureSieve