Inclusion-Exclusion Principle

The inclusion-exclusion principle is a fundamental counting technique that allows us to calculate the cardinality of the union of sets by systematically adding and subtracting intersections. This principle corrects for overcounting when elements belong to multiple sets.

DefinitionInclusion-Exclusion Principle

Let $A_1, A_2, \ldots, A_n$ be finite sets. The cardinality of their union is: $\left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap A_2 \cap \cdots \cap A_n|$

More compactly, this can be written as: $\left|\bigcup_{i=1}^n A_i\right| = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right|$ where $[n] = \{1, 2, \ldots, n\}$ .

The principle works by first counting all elements (possibly multiple times), then removing those counted twice, adding back those removed too many times, and so forth. The alternating signs ensure that each element is counted exactly once in the final sum.

ExampleDerangements

A derangement is a permutation where no element appears in its original position. The number of derangements $D_n$ of $n$ elements can be computed using inclusion-exclusion.

Let $A_i$ be the set of permutations where element $i$ is in position $i$ . Then: $D_n = n! - \left|\bigcup_{i=1}^n A_i\right|$

We have $|A_i| = (n-1)!$ , $|A_i \cap A_j| = (n-2)!$ , and generally $\left|\bigcap_{i \in S} A_i\right| = (n-|S|)!$ .

Therefore: $D_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n\binom{n}{n}0!$ $= n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$

This approaches $n!/e$ for large $n$ , meaning approximately $1/e \approx 36.8\%$ of all permutations are derangements.

DefinitionSurjective Function Counting

The number of surjective functions from an $n$ -element set to a $k$ -element set can be computed using inclusion-exclusion. Let $f: [n] \to [k]$ be a function. We want to count surjections (onto functions).

Let $A_i$ be the set of functions that do not have $i$ in their range. Then: $\text{# surjections} = k^n - \left|\bigcup_{i=1}^k A_i\right|$

By inclusion-exclusion: $= k^n - \binom{k}{1}(k-1)^n + \binom{k}{2}(k-2)^n - \cdots + (-1)^{k-1}\binom{k}{k-1}1^n$ $= \sum_{j=0}^k (-1)^{k-j}\binom{k}{j}j^n$

Remark

The inclusion-exclusion principle has a natural generalization to probability theory. For events $E_1, \ldots, E_n$ in a probability space: $P\left(\bigcup_{i=1}^n E_i\right) = \sum_{i=1}^n P(E_i) - \sum_{i<j} P(E_i \cap E_j) + \cdots + (-1)^{n+1}P(E_1 \cap \cdots \cap E_n)$

This probabilistic version is known as the Bonferroni inequalities when truncated at various stages.

ExampleEuler's Totient Function

The Euler totient function $\phi(n)$ counts integers in $[1,n]$ that are coprime to $n$ . If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ , let $A_i$ be the set of integers in $[1,n]$ divisible by $p_i$ .

By inclusion-exclusion: $\phi(n) = n - \left|\bigcup_{i=1}^k A_i\right| = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$

For example, $\phi(12) = 12(1 - 1/2)(1 - 1/3) = 12 \cdot 1/2 \cdot 2/3 = 4$ , corresponding to $\{1, 5, 7, 11\}$ .

The principle extends to more abstract settings through Möbius inversion on posets, providing a systematic framework for "inverting" summation formulas in combinatorics and number theory.