Inclusion-Exclusion

Definition

Basic Formula

For two sets $A$ and $B$:

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

For three 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 Formula

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

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

Application

The Number of Onto Functions

Let $m$ and $n$ be positive integers with $m\ge n$. Then, there are

$$n^m-\left(\genfrac{}{}{0ex}{}{n}{1}\right)(n-1{)}^m+(\genfrac{}{}{0ex}{}{n}{2})(n-2{)}^m-\cdots +(-1{)}^{n-1}(\genfrac{}{}{0ex}{}{n}{n-1})1^m$$

onto (surjective) functions from set $A$ with $m$ elements to a set $B$ with $n$ elements.

Solution: There are $n^m$ functions of all kind from $A$ to $B$. If $b\in B$, there are $(n-1{)}^m$ functions of all kinds from $A$ to $B\backslash \left\{b\right\}$. We need to subtract these from the original $n^m$, and we need to do it for each of the $n$ members of $B$, so this concludes $n^m-n(n-1{)}^m$

Unfortunately, a function whose range misses two members of $B$ gets subtracted twice in that computation. So we have to add is back

$$n^m-n(n-1{)}^m+(\genfrac{}{}{0ex}{}{n}{2})(n-2{)}^m$$

By this way we can get the formula at first.

Additionally, an onto function from a set with $m$ elements to a set with $n$ elements corresponds to a way to distribute the $m$ elements in the domain to $n$ indistinguishable boxed so that no box is empty, and then apply a permutation of these $n$ elements. Consequently, the number of onto functions from a set with $m$ elements to a set with $n$ elements equals to $n!S(m,n)$, where $S(m,n)$ is the Stirling number of the second kind.

Derangement

A derangement is a permutation of objects that leaves no object in its original position. Te number of derangements of a set with $n$ elements is

$$D_n=n!\left[1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +(-1{)}^n\frac{1}{n!}\right]$$

or in recursive form

$$D_n=(n-1)\left[D_{n-1}+D_{n-2}\right]$$