Inclusion-Exclusion: Counting Overlaps Without Double-Counting

The problem with just adding set sizes

Suppose you want to count how many people in a room speak French or German. Adding the number of French speakers to the number of German speakers overcounts anyone who speaks both — they get counted twice. The fix is obvious once you see it: subtract the overlap back out. |A ∪ B| = |A| + |B| − |A ∩ B|. That single correction is the seed of the inclusion-exclusion principle, and the interesting part is what happens when you scale it up from two sets to three, ten, or a hundred.

Three sets: add, subtract, add back

With three overlapping sets, a Venn diagram has seven distinct regions, and simply adding |A| + |B| + |C| overcounts every pairwise overlap and then undercounts the triple overlap after you subtract those pairs back out — the region where all three sets overlap gets added three times, subtracted three times, and needs to be added back once more to land on the correct count:

|A ∪ B ∪ C| = |A| + |B| + |C|
              − |A∩B| − |A∩C| − |B∩C|
              + |A∩B∩C|

pattern: alternate + and −, one term per possible intersection size

The general rule for n sets keeps alternating signs by the number of sets in each intersection: add all single-set sizes, subtract all pairwise intersections, add all triple intersections, subtract all quadruple intersections, and so on, ending with a single term for the intersection of all n sets, signed (−1)^(n+1).

Why the alternating sum works: counting each element exactly once

The clean way to see why this always lands on the right answer is to check how many times a single element gets counted. Take an element that belongs to exactly k of the n sets. It contributes to C(k,1) single-set terms, C(k,2) pairwise terms, and so on up to C(k,k). The alternating sum of those binomial coefficients, C(k,1) − C(k,2) + C(k,3) − ..., always equals exactly 1 for any k ≥ 1 (a direct consequence of the binomial theorem applied to (1−1)^k = 0). So every element that belongs to at least one set gets counted exactly once in the final total, regardless of how many of the sets it happens to sit in — that's the whole proof, and it's why the formula generalises cleanly to any number of sets.

Derangements: the classic counting application

A textbook use of inclusion-exclusion is counting derangements — permutations of n items where no item lands in its own original position (the 'hat-check problem': n people check n hats, in how many ways can every single person get back a hat that isn't theirs?). Let A_i be the set of permutations where item i does land in its own spot; you want everything outside the union of all the A_i. Inclusion-exclusion on those n sets gives:

D(n) = n! · Σ_{k=0}^{n} (−1)^k / k!

D(1) = 0
D(2) = 1
D(3) = 2
D(4) = 9
D(5) = 44

as n grows, D(n)/n! → 1/e ≈ 0.3679

That last line is a small piece of mathematical magic: the fraction of all permutations that are complete derangements converges to 1/e, meaning roughly 37% of random shufflings leave nobody in their original spot, almost regardless of how large n gets once n is more than a handful.

The same trick counts surjections and the sieve of Eratosthenes

Inclusion-exclusion is one of the most reused tools in combinatorics because so many counting problems reduce to 'count things that avoid all of a list of bad properties.' Counting surjections (functions from an n-element set onto an m-element set, hitting every target) is inclusion-exclusion over 'target j is missed'. The number-theoretic sieve of Eratosthenes for counting integers up to N free of any prime factor from a chosen list is inclusion-exclusion over 'divisible by prime p_i'. Anywhere a direct count would overcount overlapping bad cases, the alternating add-subtract-add pattern is usually the cleanest way to fix it exactly.

Frequently asked questions

Try it live

Everything above runs in your browser — open Inclusion-Exclusion and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.