Counting with inclusion–exclusion (applications)

Counting the size of a union of overlapping sets is one of the oldest problems in combinatorics, yet its deceptive simplicity has attracted some of the finest minds in mathematics. The core difficulty is clear: if two sets share elements, naïvely adding their sizes double-counts the intersection. The inclusion–exclusion principle (PIE) provides a systematic correction for arbitrary overlaps among any finite number of sets, and its applications reach far beyond simple set unions into number theory, probability, topology, and algorithm design.

The story of inclusion–exclusion is intertwined with the development of combinatorial analysis itself. From Abraham de Moivre's investigations into card-matching problems in the early 18th century, through Euler's work on the totient function, to the modern sieve methods used in analytic number theory, the principle has continually found new domains of applicability. Understanding its historical arc reveals why the formula takes the form it does and how mathematicians recognized its power.

The recurring question across all these developments is deceptively simple: given a universe of objects and several overlapping properties, how many objects possess none of the properties—or exactly k of them? The inclusion–exclusion principle answers this question completely, and its applications illustrate the extraordinary reach of a single combinatorial identity.

Before diving into applications, we establish the conceptual foundations that make inclusion–exclusion work. The principle rests on a careful alternating correction: first we over-count by adding, then we over-correct by subtracting pairwise intersections, then we re-correct by adding triple intersections, and so on. This alternation ensures that every element in the union is counted exactly once, regardless of how many sets it belongs to.

The Venn diagram below illustrates inclusion–exclusion for three sets A, B, and C. Each region is labeled with the net count it receives at each stage of the formula. Observe how the alternating signs systematically correct every region to a final count of exactly 1.

The diagram makes the algebraic identity tangible: the binomial alternating-sum identity C(k,1) − C(k,2) + C(k,3) − ⋯ + (−1)^k+1C(k,k) = 1 is precisely the statement that an element belonging to exactly k of the n sets is counted exactly once by the inclusion–exclusion formula. This fact is the combinatorial engine behind every application we will see.

We now state the principle formally and derive the key formulas used in its most important applications. Let U be a finite universe and A₁, A₂, …, Aₙ be subsets of U.

Application 1: Derangements

A derangement of [n] = {1, 2, …, n} is a permutation σ with no fixed points: σ(i) ≠ i for all i. Let Aᵢ be the set of permutations fixing i. The set of derangements is the complement of A₁ ∪ ⋯ ∪ Aₙ within the universe of all n! permutations. Since any intersection Aᵢ₁ ∩ ⋯ ∩ Aᵢₖ has size (n − k)! (the remaining n − k elements permute freely), inclusion–exclusion yields the classical formula.

Application 2: Euler's Totient Function

For a positive integer n with prime factorization n = p₁^a₁ p₂^a₂ ⋯ pₘ^aₘ, define Aᵢ = {k ∈ {1, …, n} : pᵢ | k}. Then |Aᵢ| = n/pᵢ, and more generally the intersection of sets corresponding to distinct primes pᵢ₁, …, pᵢₖ has size n/(pᵢ₁ ⋯ pᵢₖ). The complement count gives Euler's formula.

Application 3: Surjections

The number of surjections (onto functions) from an m-element set to an n-element set can be computed by letting Aⱼ be the set of functions whose image misses element j. The intersection of any k such sets consists of functions mapping into a codomain of size n − k, giving (n − k)^m functions.

Inclusion–exclusion applications share a common structure: define a universe U, identify n "bad" properties, model each property as a set, compute intersection sizes, and apply the formula. The diagram below organizes the major application families by the nature of the universe and the type of forbidden property.

We compute the number of surjections (onto functions) from a 5-element set onto a 3-element set. The total number of functions is 3⁵ = 243, but most of these miss at least one element of the codomain.

Inclusion–exclusion is a universal tool—it works for any finite collection of sets—but universality comes at a cost. Understanding when the principle shines and when alternative methods are preferable is essential for efficient problem-solving in combinatorics.

The inclusion–exclusion principle is a special case of Möbius inversion on the Boolean lattice of subsets of [n]. Rota's landmark 1964 paper showed that for any locally finite partially ordered set (poset), the Möbius function μ plays the same role that (−1)^|S| plays in PIE. This unification connects inclusion–exclusion to number-theoretic Möbius inversion (where the poset is the divisibility lattice), the chromatic polynomial of a graph (via the lattice of partitions), and even to the theory of species in algebraic combinatorics.

The connection to Möbius inversion also opens the door to efficient computation. For specific poset structures—such as the divisor lattice or the partition lattice—the Möbius function has closed-form expressions, and fast algorithms (like the fast zeta transform on subsets, running in O(n × 2ⁿ) time) can evaluate the full inclusion–exclusion sum efficiently. These techniques form the backbone of modern competitive programming and are active areas of research in algebraic combinatorics.