Inclusion-Exclusion

Two Sets

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

We subtract $|A \cap B|$ because elements in both sets were counted twice.

Three Sets

$|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, \ldots, A_n$:

$\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|$

Or more compactly: $\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset \neq S \subseteq \{1,\ldots,n\}} (-1)^{|S|+1} \left| \bigcap_{i \in S} A_i \right|$

Complement Form

For counting elements NOT in any set: $\left| \overline{A_1 \cup A_2 \cup \cdots \cup A_n} \right| = |U| - \left| \bigcup_{i=1}^{n} A_i \right|$

This is useful for "none of the above" counting.

Examples

Integers Divisible by 2, 3, or 5

How many integers from 1 to 1000 are divisible by 2, 3, or 5?

Let $A_2, A_3, A_5$ be sets of multiples.

$|A_2| = \lfloor 1000/2 \rfloor = 500$ $|A_3| = \lfloor 1000/3 \rfloor = 333$ $|A_5| = \lfloor 1000/5 \rfloor = 200$ $|A_2 \cap A_3| = \lfloor 1000/6 \rfloor = 166$ $|A_2 \cap A_5| = \lfloor 1000/10 \rfloor = 100$ $|A_3 \cap A_5| = \lfloor 1000/15 \rfloor = 66$ $|A_2 \cap A_3 \cap A_5| = \lfloor 1000/30 \rfloor = 33$

$|A_2 \cup A_3 \cup A_5| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$

Euler's Totient Function

$\phi(n)$ = count of integers from 1 to $n$ that are coprime to $n$.

For $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$:

$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$

Example: $\phi(12) = \phi(2^2 \cdot 3) = 12 \cdot (1 - 1/2)(1 - 1/3) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4$

Derangements

A derangement is a permutation where no element is in its original position.

Let $A_i$ = permutations where element $i$ is fixed.

The number of derangements of $n$ elements: $D_n = n! - |A_1 \cup A_2 \cup \cdots \cup A_n|$

Using inclusion-exclusion: $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n! \left(1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$

$n$	$D_n$	Formula
0	1	—
1	0	$1 - 1$
2	1	$2 - 2 + 0$
3	2	$6 - 6 + 3 - 1$
4	9	$24 - 24 + 12 - 4 + 1$
5	44	—

As $n \to \infty$: $D_n / n! \to 1/e \approx 0.368$

Surjective Functions

The number of surjective (onto) functions from an $n$-set to a $k$-set:

$S(n, k) \cdot k! = \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n$

where $S(n, k)$ is the Stirling number of the second kind.

Derivation: Let $A_i$ = functions missing element $i$ in the range. Surjections = Total functions - (functions missing at least one element)

Sieve of Eratosthenes

Primes up to $n$: Start with all numbers, sieve out multiples.

Using inclusion-exclusion with prime divisors gives the count of numbers with no small prime factors.

Hat Check Problem

$n$ people check hats, hats returned randomly. Probability no one gets own hat?

$P = \frac{D_n}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!} \approx \frac{1}{e} \approx 0.368$

Counting with "At Least" Conditions

Example: Distribute 10 identical balls into 4 distinct boxes, each box has at least 1 ball.

First give each box 1 ball (4 balls used). Distribute remaining 6: $\binom{6 + 4 - 1}{4 - 1} = \binom{9}{3} = 84$

Alternatively, using inclusion-exclusion on "box $i$ is empty": $\binom{13}{3} - 4\binom{12}{3} + \binom{4}{2}\binom{11}{3} - \binom{4}{3}\binom{10}{3} + \binom{4}{4}\binom{9}{3}$

Both methods give 84.