Inclusion–Exclusion

The sum rule adds set sizes — but only when the sets are disjoint. The moment they overlap, naive addition double-counts: anyone in two sets gets tallied twice. The Venn diagram makes the fix visible, and inclusion–exclusion turns that fix into an exact formula that works for any number of overlapping sets. It is one of the most quietly powerful counting tools there is.

Two sets first. To count A \cup B, add |A| and |B| — now the lens-shaped overlap A \cap B has been counted twice, so subtract it back once:

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

If 18 students take French, 15 take German, and 6 take both, then 18 + 15 - 6 = 27 take at least one language. Add, then correct for the overlap — that is the entire idea, and everything below is just keeping the corrections straight as the sets pile up.

Three sets: over-correct, then correct again

With three sets, adding |A|+|B|+|C| counts each pairwise overlap twice and the central triple overlap three times. Subtract all three pairwise intersections — but that now removes the triple region three times, so it has been counted 3 - 3 = 0 times and must be added back once. Step through the figure: the running total lands exactly on the true union.

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

The signs alternate by the number of sets in the intersection: singles +, pairs -, triples +.

The general principle

The pattern continues forever: add all single sets, subtract all pairwise intersections, add all triples, subtract all quadruples, and so on — the sign of a term with j sets intersected is (-1)^{j+1}.

\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i} |A_i| - \sum_{i

Worked example — count by the complement

How many integers from 1 to 100 are divisible by 2, 3, or 5? Let A, B, C be the multiples of each. Then |A| = \lfloor 100/2 \rfloor = 50, |B| = 33, |C| = 20; the pairwise overlaps count multiples of the products 6, 10, 15: 16, 10, 6; the triple counts multiples of 30: 3. So

50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.

Hence 100 - 74 = 26 integers up to 100 are divisible by none of them (they are coprime to 30). This "count the union, subtract from the whole" move is how inclusion–exclusion powers sieve arguments across number theory.

The showpiece: derangements

n guests leave their hats at a party and grab one at random on the way out. How many ways are there for nobody to get their own hat back? Such a permutation with no fixed point is called a derangement, and its count D_n is the crown jewel of inclusion–exclusion.

Let A_i be the arrangements where guest i does get their own hat. We want the permutations in none of the A_i, i.e. n! - |A_1 \cup \cdots \cup A_n|. Fixing a specific set of j guests leaves (n-j)! arrangements of the rest, and there are \binom{n}{j} such sets, so the j-th inclusion–exclusion sum is \binom{n}{j}(n-j)! = \frac{n!}{j!}. Assembling:

D_n = n! \sum_{j=0}^{n} \frac{(-1)^j}{j!} = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!}\right).

The first few are D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44. The bracketed sum is the truncation of e^{-1}, so D_n \approx n!/e — remarkably, the fraction of hat-arrangements that are derangements tends to 1/e \approx 0.3679 regardless of how many guests there are. Whether it is 5 guests or 5 million, "nobody gets their own hat" happens about 37\% of the time.

Nothing continuous is anywhere in sight — just permutations and counting — yet 1/e falls out. The reason is that the inclusion–exclusion signs (-1)^j against the weights 1/j! are exactly the terms of the Taylor series e^{x} = \sum x^j/j! evaluated at x = -1. The alternating over- and under-corrections of inclusion–exclusion are the alternating series for e^{-1} in disguise. This is a first taste of a theme the generating functions page makes central: analysis and counting are the same subject in two languages.