Combinatorics and discrete mathematics

Inclusion–exclusion principle

A formula for the size of a union of sets that corrects for overlaps counted multiple times.

IntuitionIdea: how big is the union when the pieces overlap?

If a class has students who like math and students who like art, simply adding "like math" plus "like art" double-counts every student who likes both. To get the true number who like at least one subject, you must subtract the overlap once: this is the whole idea behind inclusion–exclusion, and it generalizes cleanly from two sets to any number of sets.

Three overlapping sets

A, B, C

: to count

|A\cup B\cup C|

, add the three circles, subtract the three pairwise lenses, and add back the central triple intersection.

SchoolTwo and three sets

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

Here $|A|$ denotes the number of elements of a finite set $A$ ; $A\cup B$ is the set of elements in $A$ or $B$ (or both), and $A\cap B$ is the set of elements in both. Subtracting $|A\cap B|$ removes the double count of elements that belong to both sets.

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

From two sets to n sets
Number of sets	Formula	Terms in the sum
$2$	$\|A\cup B\|=\|A\|+\|B\|-\|A\cap B\|$	$3$
$3$	$\|A\cup B\cup C\|=\|A\|+\|B\|+\|C\|-\|A\cap B\|-\|A\cap C\|-\|B\cap C\|+\|A\cap B\cap C\|$	$7$
$n$	$\left\|\bigcup_{i=1}^n A_i\right\|=\sum_{k=1}^n(-1)^{k+1}\sum_{1\le i_1<\cdots<i_k\le n}\left\|A_{i_1}\cap\cdots\cap A_{i_k}\right\|$	$2^n-1$

UndergraduateProof for two sets and the general n-set formula

Theorem: Inclusion–exclusion for two sets

For finite sets $A$ , $B$ : $|A\cup B|=|A|+|B|-|A\cap B|$

Why is it true?

Every element of $A\cup B$ falls into exactly one of three disjoint groups: only in $A$ , only in $B$ , or in both; adding $|A|+|B|$ counts the "both" group twice, so one copy must be removed.

Proof

Partition $A\cup B$ into three pairwise disjoint pieces: $A\setminus B$ (in $A$ only), $B\setminus A$ (in $B$ only), and $A\cap B$ (in both). Since these pieces are disjoint and cover $A\cup B$ , $|A\cup B|=|A\setminus B|+|B\setminus A|+|A\cap B|$ .

Now observe that $A$ itself splits into the disjoint pieces $A\setminus B$ and $A\cap B$ , so $|A|=|A\setminus B|+|A\cap B|$ , which means $|A\setminus B|=|A|-|A\cap B|$ . Symmetrically, $|B\setminus A|=|B|-|A\cap B|$ .

Substituting these two expressions back into the first equation gives $|A\cup B|=(|A|-|A\cap B|)+(|B|-|A\cap B|)+|A\cap B|=|A|+|B|-|A\cap B|$ , which is exactly $|A\cup B|=|A|+|B|-|A\cap B|$ .

Theorem: General inclusion–exclusion

For finite sets $A_1,\ldots,A_n$ : $\left|\bigcup_{i=1}^n A_i\right|=\sum_{k=1}^n(-1)^{k+1}\sum_{1\le i_1<\cdots<i_k\le n}\left|A_{i_1}\cap\cdots\cap A_{i_k}\right|$

Why is it true?

Each element that lies in several of the sets gets added once for every single set, subtracted once for every pair, added back for every triple, and so on; the alternating pattern is exactly what is needed to bring its total count back down to exactly $1$ .

Proof

Fix any element $x$ . If $x$ belongs to none of $A_1,\ldots,A_n$ , it contributes $0$ to both sides of the formula, so assume $x$ belongs to exactly $m\ge 1$ of the sets.

For each $k$ , the number of $k$ -fold intersections $A_{i_1}\cap\cdots\cap A_{i_k}$ that contain $x$ equals the number of ways to choose $k$ of the $m$ sets containing $x$ , namely $\binom{m}{k}$ . So $x$ 's total contribution to the right-hand side is $\sum_{k=1}^n(-1)^{k+1}\binom{m}{k}=\sum_{k=1}^m(-1)^{k+1}\binom{m}{k}$ (terms with $k>m$ vanish since $\binom{m}{k}=0$ ).

By the binomial theorem, $\sum_{k=0}^m(-1)^k\binom{m}{k}=(1-1)^m=0$ , so $\sum_{k=1}^m(-1)^k\binom{m}{k}=-1$ , and multiplying by $-1$ gives exactly $\sum_{k=1}^m(-1)^{k+1}\binom{m}{k}=1$ .

So every element in at least one set contributes exactly $1$ to the right-hand side, matching its contribution of $1$ to $\left|\bigcup_{i=1}^n A_i\right|$ ; elements in no set contribute $0$ to both sides. Since every element contributes equally to both sides, the two sides are equal.

Definition: Derangement

A derangement of $n$ objects is a permutation in which no object stays in its original position. Let $A_i$ be the set of permutations of $n$ objects that fix position $i$ (object $i$ stays put); then the number of derangements is $D_n=n!-\left|\bigcup_{i=1}^n A_i\right|$ , the permutations left over after removing every one that fixes at least one position.

D_n=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!}

Applying the general formula to these sets, $\left|A_{i_1}\cap\cdots\cap A_{i_k}\right|=(n-k)!$ (the other $n-k$ objects can be arranged freely), so the inclusion–exclusion sum has $\binom{n}{k}$ identical terms of size $(n-k)!$ at each level $k$ , which simplifies to $D_n=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!}$ after dividing by $n!$ and factoring — the second theorem block on this page derives the general case in full.

UndergraduateReal-World Applications and Worked Examples

Inclusion–exclusion is a everyday tool in computer science (sieving out unwanted cases when counting), number theory (counting multiples), and reliability engineering (combining overlapping failure events), wherever "at least one of several conditions holds" needs to be counted exactly.

Example: Counting multiples with a sieve

A programmer needs to count how many integers from $1$ to $100$ are divisible by $2$ , $3$ , or $5$ — the same sieving idea used to precompute primes or filter valid keys in cryptographic code.

Solution

Let $A$ be multiples of $2$ , $B$ multiples of $3$ , $C$ multiples of $5$ in $\{1,\ldots,100\}$ . Counting multiples up to $100$ by division: $|A|=50$ , $|B|=33$ , $|C|=20$ .

The triple overlap is multiples of $30$ : $|A\cap B\cap C|=\lfloor 100/30\rfloor=3$ .

By the three-set formula, $|A\cup B\cup C|=50+33+20-16-10-6+3=74$ , so $74$ of the first $100$ integers are divisible by $2$ , $3$ or $5$ , and the sieve avoids ever listing them one by one.

Example: Redundant satellite subsystems

A satellite has three subsystems $A$ , $B$ , $C$ with independent one-year failure probabilities $P(A)=0.02$ , $P(B)=0.03$ , $P(C)=0.01$ , but shared components make some pairs of failures correlated: $P(A\cap B)=0.004$ , $P(A\cap C)=0.001$ , $P(B\cap C)=0.0006$ , and $P(A\cap B\cap C)=0.0002$ . A reliability engineer needs the probability that at least one subsystem fails, to decide whether more redundancy is needed.

Solution

Probabilities behave like proportions of a population, so the same three-set formula applies: $P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C)$ .

Substitute the given values: $P(A\cup B\cup C)=0.02+0.03+0.01-0.004-0.001-0.0006+0.0002$ .

Adding the single-subsystem terms gives $0.06$ , subtracting the pairwise terms gives $0.06-0.0056=0.0544$ , and adding back the triple overlap gives $0.0544+0.0002=0.0546$ .

So there is about a $5.46\%$ chance that at least one subsystem fails in a year; without correcting for the correlated failures (i.e. just adding $0.02+0.03+0.01=0.06$ ), the engineer would have overestimated the risk and possibly over-engineered the redundancy.

If $|A|=10$ , $|B|=7$ , and $|A\cap B|=3$ , what is $|A\cup B|$ ?

Given $|A|=30$ , $|B|=20$ , $|C|=15$ , $|A\cap B|=10$ , $|A\cap C|=8$ , $|B\cap C|=5$ , $|A\cap B\cap C|=3$ , what is $|A\cup B\cup C|$ ?

In how many ways can 4 letters be placed into 4 addressed envelopes so that no letter goes into its correct envelope?

How many integers from 1 to 30 are divisible by neither 2 nor 3?

References

Wikipedia contributors (2024). Inclusion–exclusion principle
James Maynard (2015). Small gaps between primes · arXiv:1311.4600
Richard A. Brualdi (2017). Introductory Combinatorics (Classic Version), 5th edition