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
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