Inclusion-Exclusion: Advanced Applications

Core Idea

Beyond basic set counting, inclusion-exclusion applies to derangements, surjections, graph colorings, and permanents. Möbius inversion on the poset of subsets formalizes the principle. Advanced applications include computing chromatic polynomials and counting restricted permutations.

Explainer

You know inclusion-exclusion as a formula for counting elements in unions of sets: add the singletons, subtract the pairs, add the triples, and so on. Advanced applications reveal that the same alternating-sign structure appears across many seemingly unrelated problems. The key insight is that inclusion-exclusion is not just a union formula — it is a general technique for counting objects that avoid a collection of "bad" properties, by complementing through alternating sums over subsets of those properties.

The most celebrated application is derangements: permutations of n elements where no element stays in its original position. Let Aᵢ be the set of all permutations that fix element i. A derangement belongs to none of these sets. The complement formula gives D(n) = n! − C(n,1)(n−1)! + C(n,2)(n−2)! − ⋯ + (−1)ⁿ(0!), which simplifies to n!(1 − 1/1! + 1/2! − 1/3! + ⋯ + (−1)ⁿ/n!). As n grows, this converges to n!/e. The probability that a random permutation is a derangement approaches exactly 1/e — a striking connection between combinatorics and analysis emerging purely from the alternating sum.

Surjections (onto functions from an n-element set to a k-element set, hitting every output at least once) are counted by the same framework: let Aᵢ be the functions that miss output element i, then apply inclusion-exclusion to the complement. The result is Σⱼ (−1)ʲ C(k,j)(k−j)ⁿ. These counts are related to Stirling numbers of the second kind, which count partitions of an n-element set into k non-empty blocks. Chromatic polynomials of graphs — counting proper colorings with exactly k colors — are computed by a similar alternating sum that removes colorings violating each edge's monochromatic constraint.

The abstract structure underlying all of these is Möbius inversion on a partially ordered set. For the Boolean lattice of all subsets of {1, ..., n} ordered by inclusion, the Möbius function is μ(S, T) = (−1)^|T\S|, which is exactly the alternating sign appearing in inclusion-exclusion. This means the principle is a special case of a universal algebraic inversion theorem that works on any poset. Whenever you need to count objects satisfying "none of these bad conditions," the strategy is to define sets Aᵢ for each bad condition, compute their intersection sizes (often via the product rule), and assemble the alternating sum over all subsets. Recognizing this structure is what transforms inclusion-exclusion from a formula into a problem-solving mindset.