Inclusion-Exclusion Principle

Core Idea

|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| − ... The principle counts elements in unions by adding individual sets, subtracting pairwise overlaps, adding triple overlaps, etc., correcting for over-counting.

How It's Best Learned

Visualize with Venn diagrams for 2 or 3 sets first. Apply to derangements (permutations with no fixed points) and other classic problems. Recognize the alternating sum pattern.

Common Misconceptions

Terms alternate in sign strictly—positive for odd-cardinality intersections, negative for even. Applying this correctly requires careful bookkeeping.

Explainer

You already know inclusion-exclusion for two or three sets: |A ∪ B| = |A| + |B| − |A ∩ B|, with the three-set version adding back the triple intersection after subtracting the three pairwise ones. The general principle extends this to any number of sets using an alternating sum that corrects for over- and under-counting in a systematic way. The formula is: add all individual set sizes, subtract all pairwise intersections, add all triple intersections, subtract all quadruple intersections, and continue alternating signs through all k-fold intersections.

The reason the alternating sum works is that every element in the union gets counted exactly once. An element appearing in exactly k of the sets is counted in C(k,1) single-set terms, subtracted in C(k,2) pairwise terms, added back in C(k,3) triple terms, and so on. The total contribution is C(k,1) − C(k,2) + C(k,3) − ... which equals 1 for every k ≥ 1, by a direct application of the binomial theorem to (1−1)^k. The alternating-sign structure is not arbitrary — it is precisely what keeps every element counted once regardless of how many sets it belongs to.

The most elegant application is derangements — permutations of n elements where no element lands in its original position. Let Aᵢ be the set of permutations that fix element i. Derangements are the permutations outside every Aᵢ. Inclusion-exclusion on A₁ ∪ ... ∪ Aₙ counts permutations where "at least one element is fixed"; subtracting from n! gives the derangement count D(n) = n!(1 − 1/1! + 1/2! − 1/3! + ... ± 1/n!). This formula has a remarkable consequence: as n grows, D(n)/n! approaches e⁻¹ ≈ 0.368, so roughly 37% of all permutations are derangements regardless of how large n is.

The key skill is bookkeeping, especially when the sets are not symmetric. For n arbitrary sets there are 2ⁿ − 1 intersection terms to consider. When the problem has symmetry — meaning every k-fold intersection has the same size regardless of which k sets you pick — the formula collapses to a much simpler sum weighted by C(n,k). This symmetric structure appears in derangements, counting integers in [1,n] not divisible by any prime from a given list, and many other problems. Recognizing this symmetry and exploiting it is the difference between a tractable calculation and an enormous bookkeeping nightmare.