Inclusion–Exclusion

Inclusion–exclusion is simply how you count groups that overlap: count each group, then take out the people you counted twice. The name describes the moves, including the groups and excluding the overlaps, back and forth. It's good whenever the sum rule fails because the cases overlap. The three-set formula is long, but it's only three moves: $|A| + |B| + |C|$ (count each group), minus the $|A \cap B|$-type terms (the people in two groups, who got double-counted), plus $|A \cap B \cap C|$ (the people in all three, who got subtracted away too many times). The $\cap$ just means "in both." It looks like a mess of symbols, but it's add, fix, fix again.

Two sets. Say 18 students take French, 15 take Spanish and 6 take both. If you add $18 + 15$, the 6 students in both classes got counted once in the French list and again in the Spanish list. Subtract them once and each student is counted exactly once: $18 + 15 - 6 = 27$ take at least one. In symbols, $|A \cup B| = |A| + |B| - |A \cap B|$.

Three sets. The same idea, but now you have to keep track of how many times each element has been counted. Take an element in exactly two of the sets. Adding $|A| + |B| + |C|$ counts it twice, and it sits in one pairwise intersection, so subtracting the pairs takes it back down to once. Now take an element in all three. The singles count it three times, and it's in all three pairwise intersections, so subtracting the pairs takes it to zero. That's why the triple intersection gets added back. Either way, every element ends up counted exactly once. The picture below walks through those three steps region by region.

In general, add the sizes of the single sets, subtract all pairwise intersections, add all triple intersections, and keep alternating.

Derangements. How many arrangements of $n$ letters leave no letter in its own place? Counting the good arrangements directly is hard, but the bad ones are easy with inclusion–exclusion. Let $A_i$ be the arrangements where letter $i$ stays put. Fixing $j$ particular letters leaves $(n - j)!$ arrangements of the rest, and running the alternating sum over all of those gives

The bracket is the start of the series for $e^{-1}$, so about 37% of all arrangements are derangements, whatever $n$ is.

A common mistake. With three sets, it's tempting to stop after subtracting the pairwise overlaps. That undercounts: anything in all three sets has been added three times and subtracted three times, so it isn't counted at all until you add the triple intersection back.

Database engines estimate the size of combined queries with inclusion–exclusion, and the derangement count answers the Secret Santa problem.