Counting with inclusion–exclusion (applications)

SECTION 1

Historical Context & Motivation

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.

1708

De Moivre's Problem of Rencontres

Abraham de Moivre studied the problème des rencontres (matches problem): what is the probability that no card in a shuffled deck lands in its original position? His solution implicitly used inclusion–exclusion over individual position events.

1761

Euler's Totient Function

Leonhard Euler introduced φ(n), counting the integers from 1 to n that are coprime to n. His product formula is a direct consequence of inclusion–exclusion applied to sets of multiples of each prime factor of n.

1854

Sylvester's Sieve Formula

James Joseph Sylvester formally stated the general inclusion–exclusion formula for n sets, calling it the sieve formula. He connected it to the enumeration of permutations with forbidden patterns.

1919

Brun's Sieve in Number Theory

Viggo Brun adapted inclusion–exclusion into a combinatorial sieve to bound the count of twin primes, proving that the sum of reciprocals of twin primes converges—a landmark in analytic number theory.

1964

Rota's Möbius Inversion

Gian-Carlo Rota generalized inclusion–exclusion to arbitrary partially ordered sets via the Möbius function of a poset, unifying the principle with number-theoretic Möbius inversion and lattice theory.

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.

SECTION 2

Core Principles & Definitions

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.

Alternating Sign Correction

Each successive order of intersection carries an alternating sign: positive for odd-sized index subsets, negative for even-sized. An element in exactly k sets is added C(k,1) − C(k,2) + C(k,3) − ⋯ = 1 time by the alternating sum identity.

Complement Counting

Many applications focus on counting elements in none of the sets: |U| − |A₁ ∪ ⋯ ∪ Aₙ|. Derangements, surjections, and the Euler totient all reduce to this complementary form.

Symmetry in Intersection Sizes

In many classical applications, the intersection of any k chosen sets depends only on k, not on which k sets are chosen. This symmetric structure collapses the exponentially many terms into a single binomial sum.

From Sets to Properties

We model each "bad" property as a set Aᵢ of objects possessing that property. Inclusion–exclusion then counts objects satisfying exactly zero, exactly one, or exactly k of the properties—the foundation of sieve methods.

✦ KEY TAKEAWAY

Think of inclusion–exclusion like reconciling bank statements: if a transaction appears on multiple credit-card bills, you don't want to pay it twice. You add up every bill, subtract every pairwise overlap, add back every triple overlap, and continue until every charge is counted exactly once. The alternating correction is the mathematical analogue of this reconciliation process.

SECTION 3

Visual Explanation — Venn Diagram Accounting

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.

Each region shows its net count after all three stages of the formula. Elements in exactly one set are counted once by the first sum and never subtracted. Elements in two sets are counted twice, then subtracted once. The triple intersection receives +3 − 3 + 1 = 1, confirming the alternating correction.

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.

SECTION 4

Mathematical Framework

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.

GENERAL INCLUSION–EXCLUSION

|A₁ ∪ A₂ ∪ ⋯ ∪ Aₙ| = Σᵢ |Aᵢ| − Σᵢ<ⱼ |Aᵢ ∩ Aⱼ| + Σᵢ<ⱼ<ₖ |Aᵢ ∩ Aⱼ ∩ Aₖ| − ⋯ + (−1)ⁿ⁺¹ |A₁ ∩ ⋯ ∩ Aₙ|

The sum at depth k runs over all C(n, k) subsets of indices of size k. The sign of the k-th layer is (−1)^k+1.

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.

DERANGEMENT COUNT Dₙ

Dₙ = n! Σₖ₌₀ⁿ (−1)ᵏ / k! ≈ n! / e

Dₙ = number of derangements of n elements. The ratio Dₙ/n! → 1/e ≈ 0.3679 as n → ∞, so roughly 36.8% of all permutations are derangements.

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.

EULER'S TOTIENT

φ(n) = n ∏ₚ|ₙ (1 − 1/p)

The product runs over the distinct prime divisors p of n. For example, φ(12) = 12 × (1 − 1/2)(1 − 1/3) = 12 × 1/2 × 2/3 = 4.

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.

SURJECTION COUNT

S(m, n) = Σₖ₌₀ⁿ (−1)ᵏ C(n, k) (n − k)ᵐ

S(m, n) counts functions from an m-set onto an n-set. The Stirling numbers of the second kind are related by S₂(m, n) = S(m, n) / n!.

SECTION 5

Detailed Applications & Classification

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.

The taxonomy shows three major families—permutation problems, function problems, and number-theoretic problems—each branching into specific applications. The probability row at the bottom emphasizes that every counting application has a direct probabilistic analogue.

Comparison of four classic inclusion–exclusion applications

Application	Universe U	Property Aᵢ	\|Aᵢ₁ ∩ ⋯ ∩ Aᵢₖ\|
Derangements	All n! permutations	σ(i) = i (fixed point at i)	(n − k)!
Surjections	All nᵐ functions [m] → [n]	j not in image of f	(n − k)ᵐ
Euler φ(n)	{1, 2, …, n}	pᵢ divides k	n / (pᵢ₁ ⋯ pᵢₖ)
Hatcheck (probability)	All n! permutations (uniform)	Person i gets own hat	(n − k)! / n! = 1/(n(n−1)⋯(n−k+1))

SECTION 6

Worked Example — Counting Surjections

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.

How many surjections f: {1, 2, 3, 4, 5} → {a, b, c} exist?

Step 1 — Define the universe and propertiesLet U be the set of all functions from {1, 2, 3, 4, 5} to {a, b, c}, so |U| = 3⁵ = 243. Define A₁ = {f : a ∉ im(f)}, A₂ = {f : b ∉ im(f)}, A₃ = {f : c ∉ im(f)}. We want |U| − |A₁ ∪ A₂ ∪ A₃|.

Step 2 — Compute single-set sizesEach Aᵢ consists of functions mapping into a 2-element codomain, so |Aᵢ| = 2⁵ = 32. There are C(3,1) = 3 such sets.

Σ|Aᵢ| = 3 × 32 = 96

Step 3 — Compute pairwise intersectionsAᵢ ∩ Aⱼ consists of functions mapping into a single remaining element, so |Aᵢ ∩ Aⱼ| = 1⁵ = 1. There are C(3,2) = 3 such pairs.

Σ|Aᵢ ∩ Aⱼ| = 3 × 1 = 3

Step 4 — Compute the triple intersection|A₁ ∩ A₂ ∩ A₃| counts functions mapping into the empty set, which is impossible.

|A₁ ∩ A₂ ∩ A₃| = 0

Step 5 — Apply inclusion–exclusion|A₁ ∪ A₂ ∪ A₃| = 96 − 3 + 0 = 93. Therefore, the number of surjections is 243 − 93 = 150.

Number of surjections = 150

Step 6 — Verify with the formulaUsing S(5, 3) = Σₖ₌₀³ (−1)ᵏ C(3,k)(3−k)⁵ = C(3,0)·3⁵ − C(3,1)·2⁵ + C(3,2)·1⁵ − C(3,3)·0⁵ = 243 − 96 + 3 − 0 = 150. ✓ The formula confirms our step-by-step calculation.

SECTION 7

Strengths, Limitations & Comparisons

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.

Strengths and limitations of the inclusion–exclusion principle

Aspect	Strength	Limitation
Generality	Works for any finite union of finite sets with no structural assumptions on the sets.	Must evaluate 2ⁿ − 1 intersection terms for n sets, which is exponential.
Exactness	Yields exact counts, unlike probabilistic sieves that only give bounds.	Cancellation among large terms can cause numerical instability in floating-point computation.
Symmetric cases	When intersection sizes depend only on the number of sets, the 2ⁿ terms collapse to n + 1 terms.	Asymmetric cases may require computing each intersection individually.
Extensions	Generalizes to weighted versions, Möbius inversion, and chromatic polynomials.	For problems with special structure (e.g., graph coloring), specialized formulas (e.g., deletion-contraction) may be simpler.

⚡ WHEN TO USE (AND NOT USE) PIE

Reach for inclusion–exclusion when you can cleanly define "bad" properties whose intersections have computable sizes. If the number of properties is small (say ≤ 10) or symmetric, PIE is ideal. For large n with non-symmetric intersections, consider generating functions, transfer matrices, or Burnside's lemma, which may exploit additional structure that PIE ignores.

SECTION 8

Connection to Advanced Theory

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.

Classical PIE as a special case of Möbius inversion

Feature	Classical PIE	Möbius Inversion on Posets
Domain	Boolean lattice 2^[n]	Any locally finite poset (P, ≤)
Inversion weight	(−1)^\|S\| for each subset S	μ(x, y) defined recursively on intervals of the poset
Key identity	g(S) = Σ_{T⊇S} f(T) ⇒ f(S) = Σ_{T⊇S} (−1)^{\|T\|−\|S\|} g(T)	g(x) = Σ_{y≤x} f(y) ⇒ f(x) = Σ_{y≤x} μ(y,x) g(y)
Example application	Derangements, surjections, Euler φ	Number-theoretic Möbius function, chromatic polynomials, Tutte polynomial

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.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain why simply adding |A₁| + |A₂| + ⋯ + |Aₙ| over-counts the union |A₁ ∪ ⋯ ∪ Aₙ|, and describe the precise role of the alternating signs in the inclusion–exclusion formula. Why does the correction terminate after the n-fold intersection?

PROBLEM 2 — BASIC CALCULATION

Compute D₄, the number of derangements of 4 elements, using the formula Dₙ = n! Σₖ₌₀ⁿ (−1)ᵏ / k!.

PROBLEM 3 — INTERMEDIATE

A classroom has 100 students. Among them, 40 study French, 35 study German, 30 study Spanish, 15 study both French and German, 12 study both French and Spanish, 10 study both German and Spanish, and 5 study all three languages. How many students study none of these three languages?

PROBLEM 4 — APPLIED

A software system generates 6-digit numeric PINs (digits 0–9 for each position). How many such PINs use all three digits 0, 1, and 2 at least once? (A PIN is an ordered sequence of 6 digits.)

PROBLEM 5 — CRITICAL THINKING

Derive Euler's product formula φ(n) = n ∏_{p|n} (1 − 1/p) from the inclusion–exclusion principle. Specifically, for n = p₁^{a₁} ⋯ pₘ^{aₘ}, define appropriate sets, verify that their intersection sizes satisfy the conditions for PIE, and show that the alternating sum telescopes into the product form.

SUMMARY

Summary & Review

The inclusion–exclusion principle computes the size of a union of sets by an alternating sum over all possible intersections: add the individual sizes, subtract pairwise intersections, add triple intersections, and continue with alternating signs through the n-fold intersection. The key algebraic identity C(k,1) − C(k,2) + ⋯ + (−1)^k+1C(k,k) = 1 guarantees that every element is counted exactly once.

Major applications include derangements (permutations with no fixed points, yielding Dₙ = n! Σ (−1)ᵏ/k!), surjections (onto functions, yielding S(m,n) = Σ (−1)ᵏ C(n,k)(n−k)ᵐ), and Euler's totient function (φ(n) = n ∏(1 − 1/p)). All share the same engine: define a universe, specify forbidden properties as sets, compute symmetric intersection sizes, and apply the alternating formula. The principle generalizes to Möbius inversion on arbitrary posets, connecting combinatorics to number theory, graph theory, and algebraic structures.