Inclusion–exclusion principle (intro and applications) - Discrete Math

SECTION 1

Historical Context & Motivation

Counting the elements in a union of overlapping sets is deceptively difficult: a naïve sum of individual cardinalities double-counts every element that belongs to more than one set. The inclusion–exclusion principle (often abbreviated PIE) resolves this overcount through a systematic alternation of additions and subtractions. Its origins trace back to classical problems in number theory and probability, where mathematicians sought exact formulas for quantities such as the count of integers coprime to a given modulus or the probability of no coincidences in a random permutation. What began as ad-hoc corrections eventually crystallized into one of the most general and elegant counting tools in combinatorics.

1713 • Bernoulli's Ars Conjectandi

Abraham de Moivre and Jacob Bernoulli formulate early instances of additive corrections when computing probabilities of compound events, laying conceptual groundwork for inclusion–exclusion.

1854 • Da Silva's Generalization

Daniel da Silva publishes a systematic treatment of alternating sums for counting elements in unions, offering one of the first explicit statements of the general principle.

1867 • Sylvester's Sieve Formula

James Joseph Sylvester frames the principle as a sieve and uses it to derive combinatorial identities, connecting it to the broader theory of sieve methods.

20th c. • Modern Combinatorics & Möbius Inversion

Gian-Carlo Rota generalizes inclusion–exclusion through Möbius inversion on partially ordered sets, embedding the classical formula into abstract algebraic combinatorics.

The central question that inclusion–exclusion answers is both simple to state and surprisingly deep: Given finite sets A₁, A₂, …, Aₙ drawn from a common universe, how do we compute |A₁ ∪ A₂ ∪ … ∪ Aₙ| in terms of the cardinalities of all possible intersections? The answer has far-reaching consequences—from deriving Euler's totient function to computing derangement counts to solving surjection problems—making it indispensable across number theory, probability, and algorithm design.

SECTION 2

Core Principles & Definitions

Before stating the general formula, it is essential to internalize the intuition behind the alternating-sum structure. The principle rests on a self-correcting mechanism: each successive term in the sum repairs the error introduced by the previous round of corrections. Understanding the following foundational ideas provides the conceptual scaffolding for the formal statement.

Overcount by Naïve Summation

Summing |A₁| + |A₂| + … + |Aₙ| counts every element once for each set it belongs to. An element in k sets is counted k times instead of once.

Pairwise Correction

Subtracting all pairwise intersections |Aᵢ ∩ Aⱼ| corrects the double-count but now under-counts elements in three or more sets, since those elements had too much subtracted.

Alternating Sign Pattern

Adding triple intersections, subtracting quadruple intersections, and so on produces a telescoping correction. The sign of the k-fold intersection term is

(−1)^{k+1}

Exact Cancellation Guarantee

A combinatorial identity ensures that the alternating sum of binomial coefficients C(k,1) − C(k,2) + … ± C(k,k) equals exactly 1 for every k ≥ 1, guaranteeing each element is counted precisely once.

Complementary Counting Dual

An equivalent formulation counts elements in the complement: |U| − |A₁ ∪ … ∪ Aₙ| gives the number of elements satisfying none of the properties defined by A₁, …, Aₙ.

✦

KEY TAKEAWAY

Think of inclusion–exclusion as balancing a checkbook with multiple shared expenses. If you and two roommates split overlapping bills, you first total everyone's payments (overcount), then subtract what was double-paid between every pair (undershoot), then add back what all three overpaid together (exact). Each correction layer fixes the error of the previous one, and the process always terminates with the correct balance.

SECTION 3

Visual Explanation — Venn Diagram Perspective

A Venn diagram of three sets provides the canonical visualization for inclusion–exclusion with n = 3. Each region of the diagram corresponds to a distinct intersection pattern, and the principle's alternating sum can be read directly from the diagram. The following SVG illustrates three overlapping sets A, B, and C, labeling each of the seven non-empty regions and showing how the formula accounts for every region exactly once.

The seven regions of a three-set Venn diagram. Summing |A| + |B| + |C| counts the pairwise-intersection regions (A∩B only, A∩C only, B∩C only) twice each and the triple intersection A∩B∩C three times. Subtracting pairwise intersections corrects the pairs but removes A∩B∩C entirely, which must then be added back.

Observe that the diagram partitions the union A ∪ B ∪ C into seven disjoint regions. The inclusion–exclusion formula ensures that each region's contribution to the final count is exactly 1, regardless of how many sets it lies in. An element in exactly k of the three sets initially receives a count of k from the sum of individual cardinalities. After subtracting C(k, 2) pairwise intersections and adding back C(k, 3) triple intersections, the net count is C(k, 1) − C(k, 2) + C(k, 3) = 1 for k = 1, 2, and 3—a fact that generalizes to any number of sets.

SECTION 4

Mathematical Framework

We now present the formal statement of the inclusion–exclusion principle for n finite sets, followed by its proof sketch and complementary counting form. The general formula involves a sum over all 2ⁿ − 1 non-empty subsets of the index set {1, 2, …, n}, grouped by the size of each subset.

GENERAL INCLUSION–EXCLUSION

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

The k-th summation runs over all C(n, k) subsets of size k from {1, …, n}. The sign of the k-th term is (−1)^k+1. For n = 2: |A ∪ B| = |A| + |B| − |A ∩ B|.

COMPACT SIGMA NOTATION

|⋃ᵢ₌₁ⁿ Aᵢ| = Σₖ₌₁ⁿ (−1)ᵏ⁺¹ Σ_{|S|=k, S⊆[n]} |⋂ᵢ∈S Aᵢ|

Here [n] = {1, 2, …, n}. The inner sum ranges over all subsets S of [n] with exactly k elements.

COMPLEMENTARY COUNTING FORM

|Ā₁ ∩ Ā₂ ∩ … ∩ Āₙ| = |U| − Σ|Aᵢ| + Σ|Aᵢ ∩ Aⱼ| − … + (−1)ⁿ|A₁ ∩ … ∩ Aₙ|

Counts elements in the universe U that belong to none of A₁, …, Aₙ. Used extensively in derangement and surjection problems.

Proof Sketch (Double-Counting Argument)

Fix an arbitrary element x ∈ A₁ ∪ A₂ ∪ … ∪ Aₙ and suppose x lies in exactly m of the n sets (where 1 ≤ m ≤ n). The right-hand side counts x a net total of C(m, 1) − C(m, 2) + C(m, 3) − … + (−1)^m+1C(m, m). By the binomial theorem applied to (1 − 1)^m = 0, we know that Σₖ₌₀ᵐ (−1)ᵏ C(m, k) = 0, which implies Σₖ₌₁ᵐ (−1)ᵏ⁺¹ C(m, k) = 1. Hence x contributes exactly 1 to the right-hand side. Since x was arbitrary, the formula correctly counts every element of the union precisely once, completing the proof.

SECTION 5

Detailed Applications & Classification

The inclusion–exclusion principle appears across a remarkable range of discrete mathematics problems. While the formula itself is a single identity, its power lies in the freedom to define the sets A₁, …, Aₙ to encode whichever properties are convenient. This section classifies the major application families and provides a visual decision flow for recognizing when PIE is the right tool.

Application map showing the four major families of inclusion–exclusion problems: derangements, Euler's totient, surjections, and forbidden-pattern counting. The decision checklist at the bottom summarizes when PIE is the appropriate strategy.

Application	Universe U	Property Aᵢ	Goal
Derangements	All n! permutations of [n]	Aᵢ = permutations fixing i	\|Ā₁ ∩ … ∩ Āₙ\| (no fixed points)
Euler's Totient	{1, 2, …, n}	Aᵢ = multiples of pᵢ in U	\|Ā₁ ∩ … ∩ Āᵣ\| = φ(n)
Surjections	All nᵐ functions [m] → [n]	Aᵢ = functions missing i in range	\|Ā₁ ∩ … ∩ Āₙ\| (onto functions)
Hatcheck (classic)	All n! permutations	Aᵢ = person i gets own hat	No one gets their hat → Dₙ

How to set up common PIE problems by choosing the universe and property sets.

SECTION 6

Worked Example — Derangements of 5 Elements

Five students submit homework and a careless TA returns the papers at random. How many ways can the papers be returned so that no student receives their own work? This is the classical derangement problem for n = 5, and it provides an ideal setting to see inclusion–exclusion in action.

Computing D₅ via Inclusion–Exclusion

1
Step 1 — Define the Universe and Properties

Let U be the set of all 5! = 120 permutations of {1, 2, 3, 4, 5}. For each i ∈ {1, …, 5}, define Aᵢ as the set of permutations that fix element i (i.e., σ(i) = i). We seek |Ā₁ ∩ Ā₂ ∩ Ā₃ ∩ Ā₄ ∩ Ā₅|, the number of permutations with no fixed point.

D₅ = |U| − |A₁ ∪ A₂ ∪ A₃ ∪ A₄ ∪ A₅|
2
Step 2 — Compute Individual and Intersection Sizes

If a permutation fixes a particular set S of k elements, the remaining 5 − k elements can be arranged in (5 − k)! ways. Hence |⋂ᵢ∈S Aᵢ| = (5 − k)! for every S with |S| = k. There are C(5, k) such subsets.

Σ over |S|=k: C(5,k) × (5−k)!
3
Step 3 — Apply the Alternating Sum

By the complementary form of PIE: D₅ = Σₖ₌₀⁵ (−1)ᵏ C(5,k)(5−k)!. Expanding: D₅ = 5! − C(5,1)×4! + C(5,2)×3! − C(5,3)×2! + C(5,4)×1! − C(5,5)×0! = 120 − 5×24 + 10×6 − 10×2 + 5×1 − 1×1.

120 − 120 + 60 − 20 + 5 − 1
4
Step 4 — Evaluate

Summing the alternating terms: 120 − 120 = 0; 0 + 60 = 60; 60 − 20 = 40; 40 + 5 = 45; 45 − 1 = 44.

D₅ = 44
5
Step 5 — Verify with the Approximation

The derangement formula gives Dₙ ≈ n!/e. Here 120/e ≈ 120/2.71828 ≈ 44.146, which rounds to 44, confirming our answer. The probability that no student gets their own paper is 44/120 ≈ 0.3667, consistent with the well-known limiting probability of 1/e ≈ 0.3679.

D₅ = 44 ✓ (≈ 5!/e)

SECTION 7

Strengths, Limitations, and Alternatives

Inclusion–exclusion is powerful but not universally efficient. Its computational cost and the availability of alternatives depend heavily on the problem structure. The following comparison highlights when PIE excels and when other techniques may be preferable.

Aspect	Strengths	Limitations
Generality	Works for any finite collection of sets with no structural assumptions on how they overlap.	Requires computing all 2ⁿ − 1 intersection sizes in the worst case—exponential in the number of sets.
Exactness	Yields exact counts (or probabilities), unlike sieve bounds which give only upper or lower estimates.	For approximate answers, Bonferroni inequalities or probabilistic sieves may suffice with far fewer terms.
Symmetry Exploitation	When all k-fold intersections have equal size, the sum reduces to n terms instead of 2ⁿ − 1.	Highly asymmetric problems (e.g., varying set sizes) do not simplify, and the formula can be unwieldy.
Closed-Form Potential	Often produces elegant closed forms (derangements, Euler's totient) after simplification.	Algebraic simplification is not always possible; results may remain as alternating sums.
Alternatives	Serves as the foundation for more advanced methods (Möbius inversion, permanent computation).	Generating functions, transfer matrices, or Burnside's lemma may be more efficient for specific problem classes.

Strengths and limitations of the inclusion–exclusion principle.

✦

KEY TAKEAWAY

Inclusion–exclusion is the Swiss Army knife of combinatorial counting: universally applicable but not always the most efficient tool. In practice, look for symmetry (all k-fold intersections equal) to collapse the exponential sum into a polynomial one. When symmetry is absent and n is large, consider whether Bonferroni bounds, generating functions, or Möbius inversion offer a more tractable path to the answer.

SECTION 8

Connections to Advanced Theory

The inclusion–exclusion principle is not an isolated formula; it is the simplest instance of a far-reaching inversion technique on partially ordered sets (posets). Recognizing this connection enriches one's understanding of why the alternating-sign pattern arises and opens the door to more powerful counting tools.

Feature	Classical PIE	Möbius Inversion on Posets
Domain	Boolean lattice of subsets of [n] (2ⁿ elements)	Any locally finite poset P
Inversion Kernel	(−1)^\|S\| for subsets S	Möbius function μ(x, y) of the poset
Key Identity	g(S) = Σ_{T⊆S} f(T) ⟹ f(S) = Σ_{T⊆S} $(−1)^{\|S\|−\|T\|}$ g(T)	g(x) = Σ_{y≤x} f(y) ⟹ f(x) = Σ_{y≤x} μ(y,x) g(y)
Classical Analogue	Additive number theory: sieve of Eratosthenes	Multiplicative number theory: Möbius function μ(n) and Σ_{d\|n} μ(d)
Computational Cost	O(2ⁿ) subsets in the worst case	Depends on the poset structure; can be polynomial for lattices like the divisor lattice

Classical inclusion–exclusion as a special case of Möbius inversion.

Beyond Möbius inversion, inclusion–exclusion connects directly to the theory of Stirling numbers of the second kind (via surjection counting), the permanent of a 0-1 matrix (via the formula for the number of systems of distinct representatives), and the chromatic polynomial of a graph (via proper colorings as functions avoiding monochromatic edges). These advanced applications exploit the same alternating-sign machinery but interpret the sets Aᵢ in richer combinatorial or algebraic contexts. Students continuing in enumerative combinatorics will encounter PIE as a recurring motif underlying many seemingly disparate identities.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why simply adding |A| + |B| + |C| overcounts the cardinality of A ∪ B ∪ C. In your explanation, describe precisely how many times an element belonging to exactly two of the three sets is counted, and how many times an element in all three sets is counted.

Show answer

An element x in exactly two of the three sets—say A and B but not C—is counted once by |A| and once by |B|, so it contributes 2 to the sum instead of 1. An element y in all three sets is counted once by |A|, once by |B|, and once by |C|, contributing 3 instead of 1. To correct, we subtract pairwise intersections: x then contributes 2 − 1 = 1, which is correct. However, y now contributes 3 − 3 = 0, which is one too few, so we must add back |A ∩ B ∩ C|. This motivates the full formula |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Question 2: BASIC CALCULATION

In a class of 100 students, 40 study French, 35 study Spanish, and 20 study German. Furthermore, 12 study both French and Spanish, 8 study both French and German, 5 study both Spanish and German, and 2 study all three languages. How many students study at least one of the three languages?

Show answer

Let F, S, G denote the sets of students studying French, Spanish, and German respectively. By inclusion–exclusion: |F ∪ S ∪ G| = |F| + |S| + |G| − |F ∩ S| − |F ∩ G| − |S ∩ G| + |F ∩ S ∩ G| = 40 + 35 + 20 − 12 − 8 − 5 + 2 = 72. Thus 72 students study at least one language. The remaining 100 − 72 = 28 students study none of the three.

Question 3: INTERMEDIATE

How many integers from 1 to 1000 are divisible by 2, 3, or 5? Use inclusion–exclusion to find the count and then determine how many integers in this range are coprime to 30.

Show answer

Let A₂, A₃, A₅ be the sets of multiples of 2, 3, and 5 in {1, …, 1000}. We have |A₂| = ⌊1000/2⌋ = 500, |A₃| = ⌊1000/3⌋ = 333, |A₅| = ⌊1000/5⌋ = 200. For intersections: |A₂ ∩ A₃| = ⌊1000/6⌋ = 166, |A₂ ∩ A₅| = ⌊1000/10⌋ = 100, |A₃ ∩ A₅| = ⌊1000/15⌋ = 66, and |A₂ ∩ A₃ ∩ A₅| = ⌊1000/30⌋ = 33. By PIE: |A₂ ∪ A₃ ∪ A₅| = 500 + 333 + 200 − 166 − 100 − 66 + 33 = 734. The number of integers coprime to 30 (i.e., not divisible by 2, 3, or 5) is 1000 − 734 = 266. This agrees with 1000 × φ(30)/30 = 1000 × 8/30 ≈ 266.67, rounded by the floor effects.

Question 4: APPLIED

A company assigns 4 distinct tasks to 4 employees by random permutation. Using inclusion–exclusion, compute the probability that no employee is assigned the task they were assigned last month (i.e., the probability of a derangement). Express your answer as a fraction.

Show answer

We need D₄/4!, the number of derangements of 4 elements divided by the total number of permutations. By inclusion–exclusion: D₄ = 4! − C(4,1)×3! + C(4,2)×2! − C(4,3)×1! + C(4,4)×0! = 24 − 4×6 + 6×2 − 4×1 + 1×1 = 24 − 24 + 12 − 4 + 1 = 9. The probability is D₄/4! = 9/24 = 3/8 = 0.375. This is already close to the limiting value 1/e ≈ 0.3679; the convergence to 1/e is remarkably fast, with the error being only about 0.007 for n = 4.

Question 5: CRITICAL THINKING

Derive, using the complementary form of inclusion–exclusion, the number of surjections (onto functions) from a set of 5 elements to a set of 3 elements. Then explain why this count equals 3! × S(5, 3), where S(5, 3) is the Stirling number of the second kind.

Show answer

Let U be the set of all 3⁵ = 243 functions from [5] to [3]. Define Aᵢ as the set of functions whose range does not contain i. We want |Ā₁ ∩ Ā₂ ∩ Ā₃|, functions that miss no element—i.e., surjections. The number of functions missing a specific set S ⊆ [3] of k codomain elements is (3 − k)⁵. By complementary PIE: surjections = Σₖ₌₀³ (−1)ᵏ C(3,k)(3−k)⁵ = C(3,0)×3⁵ − C(3,1)×2⁵ + C(3,2)×1⁵ − C(3,3)×0⁵ = 243 − 3×32 + 3×1 − 0 = 243 − 96 + 3 = 150. Now, a surjection from [5] to [3] partitions [5] into 3 non-empty blocks (the preimages) and then assigns a distinct element of [3] to each block. The number of partitions of [5] into 3 non-empty blocks is exactly S(5,3) = 25. Since there are 3! = 6 bijections between the blocks and [3], the surjection count is 3! × S(5,3) = 6 × 25 = 150, confirming the PIE result. This identity generalizes: the number of surjections from [m] to [n] is always n! × S(m, n).

SUMMARY

Lesson Summary

Summary

The inclusion–exclusion principle computes the cardinality of a union of finite sets by forming an alternating sum over all possible intersections: add individual sizes, subtract pairwise intersections, add triple intersections, and continue with sign (−1)^k+1 for k-fold intersections. The complementary counting form counts elements satisfying none of a list of properties and underpins applications to derangements, Euler's totient function, and surjection counting.

The principle's correctness rests on the binomial identity C(k,1) − C(k,2) + … ± C(k,k) = 1, which guarantees that every element in the union is counted exactly once. While the general formula involves 2ⁿ − 1 intersection terms, symmetric problems—where all k-fold intersections have equal size—collapse this to a manageable sum. In the broader landscape of combinatorics, inclusion–exclusion is the Boolean-lattice special case of Möbius inversion, connecting it to deep algebraic structures in enumerative combinatorics.