Contents / Combinatorics / Counting Principles

Chapter 2

Counting Principles

The rules every count rests on: bijections, the sum and product rules, pigeonhole, inclusion–exclusion and double counting.

Introduction

The rules every count rests on: bijections, the sum and product rules, pigeonhole, inclusion–exclusion and double counting.

2.1Sets, Bijections and the Two Basic Rules

Before anything can be counted, "the number of elements" has to mean something. The definition is the one recorded in Basic Counting, restated here in the vocabulary this chapter uses throughout: a set has $n$ elements when it can be labelled $1$ through $n$ without repetition and without omission, and such a labelling is called a listing.

Definition 2.1 (Cardinality of a finite set). A set $A$ is finite of cardinality $n$ , written $∣ A ∣ = n$ , if there is a bijection $f : [n] \to A$ , where $[n] = {1, 2, \dots, n}$ and $[0] = \emptyset$ . Such an $f$ is a listing of $A$ : it writes $A$ as ${f (1), f (2), \dots, f (n)}$ with all entries distinct.

Note. That the integer $n$ is unique — that no set admits both a listing of length $5$ and a listing of length $6$ — is the pigeonhole principle in disguise, and is proved as a corollary at the end of this section. Until then, read " $∣ A ∣ = n$ " as "some listing of length $n$ exists".

Everything in this chapter is ultimately an argument about listings. The three rules that manipulate them were stated and proved in Basic Counting, the preceding chapter, and are used here without reproof. In the form needed below: the bijection principle says that if there is a bijection $g : A \to B$ then $∣ A ∣ = ∣ B ∣$ , because composing $g$ with a listing of $A$ is a listing of $B$ ; the sum rule says that pairwise disjoint sets satisfy $∣ A_{1} \cup \dots \cup A_{k} ∣ = ∣ A_{1} ∣ + \dots + ∣ A_{k} ∣$ ; and the product rule says that $∣ A_{1} \times \dots \times A_{k} ∣ = ∣ A_{1} ∣ \dots ∣ A_{k} ∣$ . Every argument in this chapter rests on these three and on nothing else.

The bijection principle looks like bookkeeping at this stage. Its power appears later: to prove two complicated families have the same size one need not compute either size. The section Bijections and counting in two ways develops the idea properly.

Pitfall. Disjointness is not decoration — it is the only hypothesis the proof of the sum rule uses, and dropping it makes the conclusion false. With $A = {1, 2}$ and $B = {2, 3}$ the sum rule would claim $∣ A \cup B ∣ = 4$ , while $A \cup B = {1, 2, 3}$ has three elements. Repairing exactly this failure is what inclusion–exclusion is for.

The product rule is usually applied in a slightly stronger form, and it is worth being precise about why the stronger form is legitimate.

Proposition 2.2 (Sequential choice rule). Suppose each object of a set $S$ is built by a sequence of $k$ choices, where the number of options at step $i$ is a constant $n_{i}$ independent of how the earlier choices were made, and distinct choice sequences build distinct objects. Then $∣ S ∣ = n_{1} n_{2} \dots n_{k}$ .

Proof. Induct on $k$ . For $k = 1$ the claim is the definition of $n_{1}$ . For $k > 1$ , group the objects of $S$ by their first choice. Distinct sequences give distinct objects, so no object arises from two different first choices and the groups are pairwise disjoint; their union is $S$ . Each group consists of the objects extending one fixed first choice, built by $k - 1$ further choices with $n_{2}, \dots, n_{k}$ options, so by induction each group has $n_{2} \dots n_{k}$ elements. There are $n_{1}$ groups, so the sum rule gives $∣ S ∣ = n_{1} (n_{2} \dots n_{k})$ .∎

Pitfall. "Independent of how the earlier choices were made" refers to the number of options, not to which options they are. When you seat $5$ people in $5$ chairs, the second person's available chairs depend entirely on where the first sat — but there are always exactly $4$ of them, so the rule applies and gives $5! = 120$ . The rule genuinely fails when the count itself varies with the history, and then the product must be replaced by a sum over cases.

Example 2.3 (Both rules in one problem). How many strings of length $4$ over the alphabet ${a, b, c, d, e}$ either consist entirely of vowels ( $a$ and $e$ ) or have four distinct letters?

Solution. Let $V$ be the set of all-vowel strings and $D$ the set of strings with four distinct letters.

Each of the four positions of a string in $V$ is filled independently from the $2$ vowels, so the product rule gives $∣ V ∣ = 2^{4} = 16$ .

A string in $D$ is built by choosing its first letter ( $5$ ways), then a different second letter ( $4$ ways), then a third ( $3$ ), then a fourth ( $2$ ). The counts do not depend on which letters were used, so the sequential choice rule gives $∣ D ∣ = 5 \cdot 4 \cdot 3 \cdot 2 = 120$ .

Are the two sets disjoint? An element of $V \cap D$ would be a string of four distinct letters all drawn from a two-letter alphabet, which the pigeonhole principle below forbids outright. So $V \cap D = \emptyset$ , the sum rule applies, and the answer is $16 + 120 = 136$ .□

Intuition. The two rules are "or" and "and". If an object is an $A$ -thing or a $B$ -thing, and never both, add. If an object is an $A$ -thing and a $B$ -thing chosen separately, multiply. Nearly every elementary counting error is a misdiagnosis of which of those two words fits — or an "or" whose cases secretly overlap.

With the two rules in place we can state the principle that gives this chapter half its name. It says a set cannot be squeezed into a smaller one without a collision.

Theorem 2.4 (Pigeonhole principle). Let $A$ and $B$ be finite sets with $∣ A ∣ > ∣ B ∣$ . Then no function $f : A \to B$ is injective: there exist distinct $a, a^{'} \in A$ with $f (a) = f (a^{'})$ .

Equivalently: if $n$ objects are placed into $m$ boxes and $n > m$ , some box contains at least two objects.

Proof. Suppose for contradiction that $f : A \to B$ is injective. For $b \in B$ write $A_{b} = f^{- 1} (b) = {a \in A : f (a) = b}$ . The sets $A_{b}$ are pairwise disjoint, since each $a$ has exactly one image, and their union is $A$ ; so the sum rule gives

∣ A ∣ = b \in B \sum ∣ A_{b} ∣.

Injectivity says $∣ A_{b} ∣ \leq 1$ for every $b$ , so the right-hand side is a sum of $∣ B ∣$ terms each at most $1$ , hence at most $∣ B ∣$ . Thus $∣ A ∣ \leq ∣ B ∣$ , contradicting $∣ A ∣ > ∣ B ∣$ .∎

Notice what the proof used: only the sum rule and the bound $∣ A_{b} ∣ \leq 1$ . Everything in the next section comes from replacing that $1$ by a larger number.

Corollary 2.5 (Cardinality is well defined). No finite set admits listings of two different lengths: if $f : [m] \to A$ and $g : [n] \to A$ are both bijections, then $m = n$ .

Proof. The composite $g^{- 1} \circ f : [m] \to [n]$ is a bijection, hence injective, so the pigeonhole principle forbids $m > n$ . Symmetrically $f^{- 1} \circ g : [n] \to [m]$ is injective, so $n > m$ is forbidden too. Hence $m = n$ .∎

Corollary 2.6 (Injections, surjections and equal size). Let $A$ and $B$ be finite sets.

If there is an injection $A \to B$ then $∣ A ∣ \leq ∣ B ∣$ .
If there is a surjection $A \to B$ then $∣ A ∣ \geq ∣ B ∣$ .
If $∣ A ∣ = ∣ B ∣$ , a function $f : A \to B$ is injective if and only if it is surjective.

Proof. Part 1 is the contrapositive of the pigeonhole principle. For part 2, let $f : A \to B$ be surjective and pick for each $b \in B$ some $s (b) \in A$ with $f (s (b)) = b$ . Then $s : B \to A$ is injective, because $s (b) = s (b^{'})$ gives $b = f (s (b)) = f (s (b^{'})) = b^{'}$ ; now apply part 1.

For part 3, decompose $A$ into the fibres $A_{b} = f^{- 1} (b)$ , so $∣ A ∣ = \sum_{b \in B} ∣ A_{b} ∣$ , a sum of $∣ B ∣$ terms whose total is $∣ A ∣ = ∣ B ∣$ . If $f$ is injective every term is at most $1$ ; a sum of $∣ B ∣$ terms each at most $1$ that equals $∣ B ∣$ must have every term equal to $1$ , so every fibre is non-empty and $f$ is surjective. If $f$ is surjective every term is at least $1$ , and the same accounting forces every term to equal $1$ , so no fibre has two elements and $f$ is injective.∎

Remark. Part 3 fails spectacularly for infinite sets: $n \mapsto n + 1$ is an injection $N \to N$ that is not surjective. That failure is not a defect but a definition — Dedekind takes it as the definition of infinite. Every pigeonhole argument in this chapter therefore depends on finiteness, and the hypothesis is never harmless.

Intuition. Thirteen socks, twelve drawers: however carefully you spread them out, some drawer ends up with two. You do not learn which drawer, and no cleverness in the spreading can help. The principle states what arithmetic forbids, not what strategy achieves.

Example 2.7 (The birthday guarantee, and its threshold). Show that among any $367$ people two share a birthday (allowing $29$ February, so $366$ possible dates), and that $367$ is the smallest number for which this is guaranteed.

Solution. Let $A$ be the set of people, $∣ A ∣ = 367$ , let $B$ be the set of $366$ dates, and let $f : A \to B$ send a person to their birthday. Since $∣ A ∣ = 367 > 366 = ∣ B ∣$ , the pigeonhole principle says $f$ is not injective, so two distinct people share a date.

For minimality, exhibit $366$ people with no repeat: give the $i$ -th person the $i$ -th date, which is possible precisely because $366$ dates exist. So $366$ people can avoid a collision and $367$ is exactly the threshold.

This second half is worth naming, because every sharp pigeonhole bound needs it. The principle supplies a sufficient number; showing that number is also necessary requires constructing a collision-free configuration one size smaller.□

Example 2.8 (A counting argument disguised as a pigeonhole argument). Show that in any group of $n \geq 2$ people, two people have the same number of acquaintances within the group. (Acquaintance is mutual, and nobody is their own acquaintance.)

Solution. Each person has an acquaintance count in ${0, 1, \dots, n - 1}$ , which is $n$ possible values for $n$ people — not yet a contradiction, so the naive pigeonhole fails and the boxes must be chosen more carefully.

The point is that the values $0$ and $n - 1$ cannot both occur: if someone knows everyone else, then nobody knows nobody, and conversely. So the actual value set is contained either in ${0, 1, \dots, n - 2}$ or in ${1, \dots, n - 1}$ , and in either case has at most $n - 1$ elements. Now $n$ people map into at most $n - 1$ boxes, and the pigeonhole principle forces two people into the same box.

This is the pattern to internalise: the hard part of a pigeonhole proof is almost never the principle. It is designing the boxes so that the collision means what you want.□

Exercises for §2.1 →

2.2The Generalised Pigeonhole Principle

The basic principle promises only "at least two". Often more is needed: what forces "at least three", or "at least $k$ "? The proof above answers this immediately, because it never used the number $1$ for any reason other than that injectivity supplied it.

Theorem 2.9 (Generalised pigeonhole principle). Let $f : A \to B$ with $A$ , $B$ finite and $∣ B ∣ = m$ . If $∣ A ∣ > (k - 1) m$ for a positive integer $k$ , then some fibre has at least $k$ elements: there is $b \in B$ with $∣ f^{- 1} (b) ∣ \geq k$ .

In box language: $(k - 1) m + 1$ objects in $m$ boxes force some box to contain at least $k$ objects.

Proof. Suppose every fibre had at most $k - 1$ elements. The fibres are disjoint with union $A$ , so by the sum rule

∣ A ∣ = b \in B \sum ∣ f^{- 1} (b) ∣ \leq b \in B \sum (k - 1) = (k - 1) m,

contradicting $∣ A ∣ > (k - 1) m$ .∎

Proposition 2.10 (The bound is sharp). For all positive integers $k$ and $m$ there is a distribution of $(k - 1) m$ objects into $m$ boxes in which no box holds $k$ objects. Hence $(k - 1) m + 1$ is the least number of objects that forces a box of size $k$ .

Proof. Put exactly $k - 1$ objects in each of the $m$ boxes. The total is $(k - 1) m$ and no box reaches $k$ . Together with the theorem, this shows the threshold is exactly $(k - 1) m + 1$ .∎

The same fact is often more convenient in a form that takes the number of objects as given and reports the guaranteed load of the fullest box.

Corollary 2.11 (Ceiling form). If $n$ objects are placed into $m \geq 1$ boxes, some box contains at least $⌈ n / m ⌉$ objects, and some box contains at most $⌊ n / m ⌋$ objects. Here $⌈ x ⌉$ is the least integer $\geq x$ and $⌊ x ⌋$ the greatest integer $\leq x$ .

Proof. For the first claim, suppose every box held at most $⌈ n / m ⌉ - 1$ objects. Since $⌈ n / m ⌉ - 1 < n / m$ , the sum rule would give

n \leq m (⌈ \frac{n}{m} ⌉ - 1) < m \cdot \frac{n}{m} = n,

which is absurd. The second claim is the same argument with the inequalities reversed: if every box held at least $⌊ n / m ⌋ + 1 > n / m$ objects, the total would exceed $m \cdot (n / m) = n$ .∎

Remark. The ceiling form is exactly the statement that the maximum of a list is at least its average, and the minimum at most its average — with the extra information that box loads are integers, which is where the ceiling and floor come from. Stated that way it generalises far beyond boxes: in any finite list of real numbers, some entry is at least the mean. That averaging principle is the form the argument usually takes in analysis and graph theory.

Pitfall. The ceiling form is a statement about the fullest box, not about every box and not about a box you get to name. If $101$ letters are sorted into $10$ sacks, some sack holds at least $11$ letters — but nine sacks may be empty, and the sack you are interested in may be one of them.

Intuition. To force three socks into one of twelve drawers, first imagine an adversary trying to prevent it. The best they can do is two per drawer, which uses $24$ socks. The $25$ th sock has nowhere safe to go. Every generalised-pigeonhole bound is that adversary calculation: fill each box as far as the target allows, count, and add one.

Figure 2.12. One hundred candies among seven children. No distribution can keep every bar below the dashed average

100/7 \approx 14.29

, so the tallest bar is always at least

⌈ 100/7 ⌉ = 15

Example 2.13 (Candies and children). One hundred identical candies are given to $7$ children. What is the largest number $N$ such that, in every possible distribution, some child receives at least $N$ candies?

Solution. By the ceiling form with $n = 100$ and $m = 7$ : since $100 = 14 \cdot 7 + 2$ , we get $⌈ 100/7 ⌉ = 15$ , so in every distribution some child gets at least $15$ .

No larger claim is possible. The distribution $15, 15, 14, 14, 14, 14, 14$ totals $100$ and has no child above $15$ , so "some child gets at least $16$ " is false for that distribution. Hence $N = 15$ exactly.

Both halves matter: the ceiling form gives the guarantee, and an explicit distribution shows the guarantee cannot be improved.□

Example 2.14 (Forcing a large monochromatic set). A bag contains balls in $4$ colours. How many balls must be drawn to guarantee $7$ of the same colour? What if the bag contains only $5$ red balls?

Solution. Colours are the boxes, $m = 4$ , and the target is $k = 7$ . The generalised pigeonhole principle gives the threshold $(k - 1) m + 1 = 6 \cdot 4 + 1 = 25$ , and the sharpness proposition confirms $24$ is not enough: six of each colour is a $24$ -ball draw with no colour reaching seven.

If red is limited to $5$ balls, the adversary's best blocking configuration is no longer uniform: red can contribute at most $5$ , while the other three colours contribute $6$ each. That gives $5 + 18 = 23$ balls with no colour reaching $7$ , so $24$ draws now suffice and $23$ do not. The threshold is $24$ .

The moral is that the clean formula $(k - 1) m + 1$ is the answer to the unconstrained problem. When supplies are bounded, go back to the underlying argument — maximise the blocking configuration, then add one — rather than to the formula.□

Example 2.15 (A pigeonhole bound with a non-obvious box design). Show that any sequence of $n^{2} + 1$ distinct real numbers contains a monotone subsequence of length $n + 1$ — increasing or decreasing.

Solution. This is the Erdős–Szekeres theorem, and it is proved in full in the next section. The point to see here is the shape of the argument: to each term $a_{i}$ attach the pair $(u_{i}, d_{i})$ , where $u_{i}$ is the length of the longest increasing subsequence ending at $a_{i}$ and $d_{i}$ the length of the longest decreasing one ending at $a_{i}$ . If no monotone subsequence of length $n + 1$ exists, each coordinate lies in $[n]$ , so the pairs live in a set of $n^{2}$ boxes while there are $n^{2} + 1$ terms.

The generalised principle is not even needed — the basic one suffices once the boxes are right. Designing $(u_{i}, d_{i})$ is the entire content of the proof; see the next section for why two terms in the same box are impossible.□

Exercises for §2.2 →

2.3Existence Proofs: Ramsey, Erdős–Szekeres and Dirichlet

The pigeonhole principle is a non-constructive tool: it certifies that a collision exists without saying where. Three classical theorems show how much can be extracted from that, and all three are proved here in full.

Theorem 2.16 (Divisibility by design of boxes). Let $n \geq 1$ .

Among any $n + 1$ integers, two have a difference divisible by $n$ .
Among any $n + 1$ integers chosen from $[2 n]$ , one divides another.

Proof. For part 1, map each integer to its residue class modulo $n$ . There are $n$ residues and $n + 1$ integers, so by the pigeonhole principle two integers $a \neq = b$ share a residue, and then $n ∣ (a - b)$ .

For part 2, write each chosen integer uniquely as $x = 2^{e} q$ with $q$ odd — this is possible and unique because factoring out the largest power of $2$ leaves an odd number. Each odd part $q$ lies in ${1, 3, 5, \dots, 2 n - 1}$ , a set of exactly $n$ values, while we have $n + 1$ integers. The pigeonhole principle gives two chosen integers $x = 2^{e} q$ and $y = 2^{f} q$ with the same odd part; since $x \neq = y$ we have $e \neq = f$ , and whichever exponent is smaller yields a divisor of the other.∎

Remark. Part 2 is sharp: the $n$ integers $n + 1, n + 2, \dots, 2 n$ lie in $[2 n]$ and none divides another, because the ratio of any two of them is strictly between $1$ and $2$ . So $n + 1$ is genuinely needed.

Example 2.17 (Consecutive terms summing to a multiple). Let $a_{1}, \dots, a_{n}$ be any integers. Show that some block of consecutive terms $a_{i + 1} + a_{i + 2} + \dots + a_{j}$ is divisible by $n$ .

Solution. Form the partial sums $s_{0} = 0$ and $s_{j} = a_{1} + \dots + a_{j}$ for $j = 1, \dots, n$ . That is $n + 1$ integers, so by part 1 of the theorem above two of them, say $s_{i}$ and $s_{j}$ with $i < j$ , are congruent modulo $n$ . Then

a_{i + 1} + \dots + a_{j} = s_{j} - s_{i} \equiv 0 (mod n) .

The block is non-empty because $i < j$ . Note how the boxes were designed: the sums, not the terms. Applying the principle directly to $a_{1}, \dots, a_{n}$ would have given nothing, since $n$ objects in $n$ boxes force no collision.□

Theorem 2.18 (Ramsey's theorem for triangles). Colour each of the $15$ edges of the complete graph $K_{6}$ red or blue, arbitrarily. Then there is a monochromatic triangle: three vertices whose three connecting edges all have the same colour.

Proof. Fix a vertex $v$ . It meets $5$ edges, each coloured red or blue, so by the generalised pigeonhole principle with $m = 2$ boxes and $k = 3$ — note $5 > (3 - 1) \cdot 2 = 4$ — at least three of them share a colour. Say $v$ is joined to $x$ , $y$ , $z$ all in red (the blue case is identical with the colours exchanged).

Now consider the three edges $x y$ , $yz$ , $x z$ . If any one of them is red, say $x y$ , then $v$ , $x$ , $y$ form a red triangle. If none is red, then all three are blue and $x$ , $y$ , $z$ form a blue triangle. Either way a monochromatic triangle exists.∎

Proposition 2.19 (Six is optimal). There is a red/blue colouring of the edges of $K_{5}$ with no monochromatic triangle. Hence the Ramsey number $R (3, 3)$ equals $6$ .

Proof. Place the five vertices on a circle. Colour the five edges of the outer pentagon red and the five diagonals blue. The red edges form a $5$ -cycle, and a cycle of length $5$ contains no triangle, since a triangle would require three mutually adjacent vertices and in a $5$ -cycle no two edges sharing no vertex can be completed. Concretely, with vertices $0, 1, 2, 3, 4$ and red edges joining $i$ to $i \pm 1 mod 5$ , a red triangle would need three vertices pairwise at circular distance $1$ , which is impossible. The blue edges join $i$ to $i \pm 2 mod 5$ , and these also form a $5$ -cycle (in the order $0, 2, 4, 1, 3$ ), so the same argument applies. No monochromatic triangle exists.∎

Intuition. In any party of six people, there are three who all know each other or three who are all mutual strangers. The proof is nothing but "look at one person: among their five relationships, three are of the same kind" — and then a single case check. The result is genuinely surprising, and the proof is four lines; that gap is what makes pigeonhole arguments memorable.

Theorem 2.20 (Erdős–Szekeres). Let $m, n \geq 1$ . Every sequence of $mn + 1$ distinct real numbers contains an increasing subsequence of length $m + 1$ or a decreasing subsequence of length $n + 1$ .

Proof. Let the sequence be $a_{1}, \dots, a_{mn + 1}$ . For each index $i$ let $u_{i}$ be the length of the longest increasing subsequence ending at $a_{i}$ , and $d_{i}$ the length of the longest decreasing subsequence ending at $a_{i}$ . Both are at least $1$ , since the single term $a_{i}$ qualifies.

Suppose, for contradiction, that there is no increasing subsequence of length $m + 1$ and no decreasing one of length $n + 1$ . Then $u_{i} \in [m]$ and $d_{i} \in [n]$ for every $i$ , so the map $i \mapsto (u_{i}, d_{i})$ sends $mn + 1$ indices into the set $[m] \times [n]$ , which has $mn$ elements by the product rule. By the pigeonhole principle there are indices $i < j$ with $(u_{i}, d_{i}) = (u_{j}, d_{j})$ .

Now compare $a_{i}$ and $a_{j}$ ; they are distinct. If $a_{i} < a_{j}$ , append $a_{j}$ to a longest increasing subsequence ending at $a_{i}$ to get an increasing subsequence of length $u_{i} + 1$ ending at $a_{j}$ , so $u_{j} \geq u_{i} + 1 > u_{i}$ , contradicting $u_{i} = u_{j}$ . If $a_{i} > a_{j}$ , the same move with decreasing subsequences gives $d_{j} \geq d_{i} + 1$ , again a contradiction.∎

Proposition 2.21 (Erdős–Szekeres is sharp). There is a sequence of $mn$ distinct reals with no increasing subsequence of length $m + 1$ and no decreasing subsequence of length $n + 1$ .

Proof. Take $n$ blocks, each an increasing run of $m$ numbers, with every number in a block larger than every number in the following block. For $m = 3$ , $n = 2$ this is $4, 5, 6, 1, 2, 3$ . An increasing subsequence must stay inside a single block, because moving to a later block strictly decreases the value, so it has length at most $m$ . A decreasing subsequence uses at most one term from each block, since within a block the values increase, so it has length at most $n$ .∎

Figure 2.22. The sharpness construction for

m = 3

n = 2

: two descending blocks of three increasing terms. Any increasing run is trapped inside one block (length at most

3

), any decreasing run takes at most one term per block (length at most

2

), and the sequence has

mn = 6

terms — one short of the guarantee.

Remark. Erdős–Szekeres has a well-known geometric consequence, which is how the two authors came to it: among any $mn + 1$ points in the plane with distinct $x$ -coordinates, some $m + 1$ or $n + 1$ of them form a "staircase" — a set of points whose $y$ -coordinates rise or fall consistently as the $x$ -coordinates increase. Order the points by $x$ -coordinate and apply the theorem to the sequence of $y$ -coordinates.

The last classical application moves from finite boxes to intervals, and is the reason the principle is called the Schubfachprinzip or Dirichlet box principle in much of the literature.

Theorem 2.23 (Dirichlet's approximation theorem). Let $α$ be a real number and $N$ a positive integer. Then there are integers $p$ and $q$ with $1 \leq q \leq N$ and

α - \frac{p}{q} < \frac{1}{qN} \leq \frac{1}{q ^{2}} .

Proof. Write ${x} = x - ⌊ x ⌋ \in [0, 1)$ for the fractional part. Consider the $N + 1$ numbers ${0 \cdot α}, {1 \cdot α}, \dots, {N α}$ , all lying in $[0, 1)$ . Partition $[0, 1)$ into the $N$ half-open boxes

[0, \frac{1}{N}), [\frac{1}{N}, \frac{2}{N}), \dots, [\frac{N - 1}{N}, 1),

which are disjoint and cover $[0, 1)$ . With $N + 1$ numbers and $N$ boxes, the pigeonhole principle gives indices $0 \leq i < j \leq N$ with ${i α}$ and ${j α}$ in the same box, hence

{j α} - {i α} < \frac{1}{N} .

Set $q = j - i$ , so $1 \leq q \leq N$ , and $p = ⌊ j α ⌋ - ⌊ i α ⌋$ . Then ${j α} - {i α} = q α - p$ , so $∣ q α - p ∣ < 1/ N$ , and dividing by $q$ gives $∣ α - p / q ∣ < 1/ (qN)$ . Finally $q \leq N$ gives $1/ (qN) \leq 1/ q^{2}$ .∎

Remark. The theorem is the gateway to continued fractions and to the theory of irrationality measures: it says every real number has infinitely many rational approximations of quality $1/ q^{2}$ when $α$ is irrational — take $N \to \infty$ and note that the resulting $p / q$ cannot stabilise, since $∣ α - p / q ∣ > 0$ for each fixed fraction while the bound tends to $0$ . Hurwitz later sharpened $1/ q^{2}$ to $1/ (5 q^{2})$ , and that constant cannot be improved, as the golden ratio shows. Those refinements are beyond this chapter; we state them to mark where the elementary argument stops.

Pitfall. A pigeonhole proof tells you a collision exists and nothing else. It does not locate the collision, does not tell you how many there are, and gives no algorithm better than search. When a problem asks which pair collides, the principle is the wrong tool — or at best the first step.

The pigeonhole principle in all its forms rests on one inequality: a sum of $m$ fibre sizes equals $∣ A ∣$ , so they cannot all be small. The work in any application is choosing the map $f$ — residues, odd parts, partial sums, colour of an edge, the pair $(u_{i}, d_{i})$ , an interval of $[0, 1)$ . Choose the boxes well and the theorem does the rest.

Exercises for §2.3 →

2.4Inclusion–Exclusion: Two Sets

The sum rule requires disjointness. When the pieces overlap, adding their sizes counts the shared elements more than once, and the correction is the subject of the rest of this chapter's middle. We begin with two sets, where everything can be seen at once.

Theorem 2.24 (Inclusion–exclusion for two sets). For any finite sets $A$ and $B$ ,

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.

Proof. Write $A ∖ B = {a \in A : a \in / B}$ . The three sets $A ∖ B$ , $B ∖ A$ and $A \cap B$ are pairwise disjoint and their union is $A \cup B$ : every element of the union lies in $A$ only, in $B$ only, or in both, and these cases exclude one another. So the sum rule gives

∣ A \cup B ∣ = ∣ A ∖ B ∣ + ∣ B ∖ A ∣ + ∣ A \cap B ∣. (*)

Also $A$ is the disjoint union of $A ∖ B$ and $A \cap B$ , so $∣ A ∖ B ∣ = ∣ A ∣ - ∣ A \cap B ∣$ , and likewise $∣ B ∖ A ∣ = ∣ B ∣ - ∣ A \cap B ∣$ . Substituting into $(*)$ ,

∣ A \cup B ∣ = (∣ A ∣ - ∣ A \cap B ∣) + (∣ B ∣ - ∣ A \cap B ∣) + ∣ A \cap B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.

∎

Two corollaries are used constantly and deserve names of their own.

Corollary 2.25 (Subtraction rule). If $B \subseteq A$ are finite sets, then $∣ A ∖ B ∣ = ∣ A ∣ - ∣ B ∣$ . In particular, for a universe $U$ and $S \subseteq U$ , the complement satisfies $∣ U ∖ S ∣ = ∣ U ∣ - ∣ S ∣$ .

Proof. $A$ is the disjoint union of $B$ and $A ∖ B$ , so the sum rule gives $∣ A ∣ = ∣ B ∣ + ∣ A ∖ B ∣$ ; rearrange.∎

Corollary 2.26 (Union bound). For any finite sets, $∣ A \cup B ∣ \leq ∣ A ∣ + ∣ B ∣$ , with equality if and only if $A$ and $B$ are disjoint.

Proof. Subtract: $∣ A ∣ + ∣ B ∣ - ∣ A \cup B ∣ = ∣ A \cap B ∣ \geq 0$ , and this is zero exactly when $A \cap B = \emptyset$ .∎

Figure 2.27. The three disjoint regions the proof uses. Adding

∣ A ∣

and

∣ B ∣

counts the darker overlap twice, so subtracting

∣ A \cap B ∣

once leaves every element counted exactly once.

Intuition. Count the cat lovers, count the dog lovers, and the people who love both have been counted twice — once in each list. Subtract them once and everybody is counted exactly once. The formula is nothing more than that sentence, and the proof above is that sentence made checkable by splitting the crowd into three groups that cannot overlap.

Example 2.28 (Sports in a class). In a class of $30$ students, $18$ play soccer, $12$ play basketball and $5$ play both. How many play at least one sport? How many play neither?

Solution. Let $S$ and $B$ be the two sets, so $∣ S ∣ = 18$ , $∣ B ∣ = 12$ , $∣ S \cap B ∣ = 5$ . By the two-set formula,

∣ S \cup B ∣ = 18 + 12 - 5 = 25.

The students playing neither sport form the complement of $S \cup B$ in the class, so by the subtraction rule there are $30 - 25 = 5$ of them.

Check against the disjoint decomposition of the proof: soccer only $18 - 5 = 13$ , basketball only $12 - 5 = 7$ , both $5$ , neither $5$ ; and $13 + 7 + 5 + 5 = 30$ .□

Example 2.29 (Recovering an intersection). Of $200$ surveyed households, $150$ subscribe to streaming service $X$ , $90$ to service $Y$ , and every household subscribes to at least one. How many subscribe to both?

Solution. "Every household subscribes to at least one" says $∣ X \cup Y ∣ = 200$ . The two-set formula rearranges to

∣ X \cap Y ∣ = ∣ X ∣ + ∣ Y ∣ - ∣ X \cup Y ∣ = 150 + 90 - 200 = 40.

The formula is an equation in four quantities; any three determine the fourth. That is how inclusion–exclusion is used at least as often as in the "find the union" direction.□

Example 2.30 (Counting the complement instead). How many integers in $[100]$ are divisible by neither $4$ nor $6$ ?

Solution. Let $A$ be the multiples of $4$ in $[100]$ and $B$ the multiples of $6$ . The number of multiples of $d$ in $[n]$ is $⌊ n / d ⌋$ , because the multiples are $d, 2 d, \dots, ⌊ n / d ⌋ d$ . So $∣ A ∣ = ⌊ 100/4 ⌋ = 25$ and $∣ B ∣ = ⌊ 100/6 ⌋ = 16$ .

An integer divisible by both $4$ and $6$ is exactly one divisible by $lcm (4, 6) = 12$ — not by $24$ , which is the trap here — so $∣ A \cap B ∣ = ⌊ 100/12 ⌋ = 8$ . Hence $∣ A \cup B ∣ = 25 + 16 - 8 = 33$ , and the count of integers divisible by neither is $100 - 33 = 67$ .□

Pitfall. The intersection of "multiples of $a$ " and "multiples of $b$ " is the multiples of $lcm (a, b)$ , which equals $ab$ only when $a$ and $b$ are coprime. Using $ab$ for $4$ and $6$ would give $⌊ 100/24 ⌋ = 4$ and a final answer of $63$ , which is wrong.

Exercises for §2.4 →

2.5Inclusion–Exclusion in General

The two-set formula extends to any number of sets, with signs that alternate. We state the three-set case first because it is the one worth memorising, then prove the general theorem twice — once by induction, once by an argument that explains why the binomial coefficients cancel.

Proposition 2.31 (Three sets). For finite sets $A$ , $B$ , $C$ ,

∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣.

Proof. Apply the two-set formula to $(A \cup B) \cup C$ :

∣ A \cup B \cup C ∣ = ∣ A \cup B ∣ + ∣ C ∣ - ∣ (A \cup B) \cap C ∣.

Expand $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ . For the last term, distributivity gives $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ , and the two-set formula applies again:

∣ (A \cap C) \cup (B \cap C) ∣ = ∣ A \cap C ∣ + ∣ B \cap C ∣ - ∣ A \cap B \cap C ∣,

using $(A \cap C) \cap (B \cap C) = A \cap B \cap C$ . Substituting and collecting terms gives the stated identity.∎

Theorem 2.32 (Inclusion–exclusion principle). Let $A_{1}, \dots, A_{n}$ be finite sets. For a non-empty index set $I \subseteq [n]$ write $A_{I} = ⋂_{i \in I} A_{i}$ . Then

i = 1 ⋃ n A_{i} = \emptyset \neq = I \subseteq [n] \sum (- 1)^{∣ I ∣ + 1} ∣ A_{I} ∣ = k = 1 \sum n (- 1)^{k + 1} ∣ I ∣ = k \sum ∣ A_{I} ∣.

That is: add the sizes of the sets, subtract the sizes of all pairwise intersections, add back all triple intersections, and so on, with the $k$ -fold intersections carrying sign $(- 1)^{k + 1}$ .

Proof. We count each element's contribution to both sides. Fix $x \in A_{1} \cup \dots \cup A_{n}$ and let $r \geq 1$ be the number of indices $i$ with $x \in A_{i}$ ; say $x$ lies in exactly the sets indexed by $R$ , $∣ R ∣ = r$ .

On the left, $x$ contributes $1$ . On the right, $x$ is counted by the term for $I$ precisely when $x \in A_{I}$ , that is when $I \subseteq R$ . The number of $k$ -element subsets $I \subseteq R$ is $(k r)$ , so the total contribution of $x$ to the right-hand side is

k = 1 \sum r (- 1)^{k + 1} (k r) = - k = 1 \sum r (- 1)^{k} (k r) = - [k = 0 \sum r (- 1)^{k} (k r) - 1] = 1 - (1 - 1)^{r} = 1,

where the binomial theorem was applied to $(1 + (- 1))^{r} = 0$ , valid because $r \geq 1$ .

An element $x$ in none of the sets contributes $0$ to both sides, since it lies in no $A_{I}$ . So every element contributes equally to the two sides, and the sums over all elements agree.∎

Remark. The computation $\sum_{k} (- 1)^{k} (k r) = 0$ is the whole mechanism, and it has a purely combinatorial reading: a non-empty set has as many even-sized subsets as odd-sized ones. We prove that by an explicit bijection in the section Classic bijections and double counting, which makes the proof above bijective rather than algebraic.

An alternative proof by induction is also worth seeing, because it is the version that generalises to measures and probabilities, where "count each element" is unavailable.

Proposition 2.33 (Inclusion–exclusion by induction). The inclusion–exclusion principle follows from the two-set case by induction on $n$ .

Proof. The case $n = 1$ is trivial and $n = 2$ is the two-set theorem. Assume the formula for $n - 1$ sets and write $U = A_{1} \cup \dots \cup A_{n - 1}$ . The two-set formula gives

i = 1 ⋃ n A_{i} = ∣ U ∣ + ∣ A_{n} ∣ - ∣ U \cap A_{n} ∣.

Expand $∣ U ∣$ by the inductive hypothesis: it contributes $\sum (- 1)^{∣ I ∣ + 1} ∣ A_{I} ∣$ over non-empty $I \subseteq [n - 1]$ . For the last term, $U \cap A_{n} = ⋃_{i = 1}^{n - 1} (A_{i} \cap A_{n})$ , so the inductive hypothesis applied to the sets $A_{i} \cap A_{n}$ gives

∣ U \cap A_{n} ∣ = \emptyset \neq = I \subseteq [n - 1] \sum (- 1)^{∣ I ∣ + 1} ∣ A_{I} \cap A_{n} ∣ = \emptyset \neq = I \subseteq [n - 1] \sum (- 1)^{∣ I ∣ + 1} ∣ A_{I \cup {n}} ∣.

Subtracting this term flips each sign, turning $(- 1)^{∣ I ∣ + 1}$ into $(- 1)^{∣ I ∣ + 2} = (- 1)^{∣ I \cup {n} ∣ + 1}$ , which is exactly the sign the general formula assigns to the index set $I \cup {n}$ . Together with the isolated term $∣ A_{n} ∣ = ∣ A_{{n}} ∣$ , every non-empty subset of $[n]$ appears exactly once with the correct sign.∎

The complementary form is often more useful than the union form, because in applications one usually wants the objects avoiding all of a list of bad properties.

Corollary 2.34 (Complementary form). Let $U$ be a finite universe and $A_{1}, \dots, A_{n} \subseteq U$ . Then the number of elements of $U$ lying in none of the $A_{i}$ is

U ∖ i = 1 ⋃ n A_{i} = I \subseteq [n] \sum (- 1)^{∣ I ∣} ∣ A_{I} ∣,

with the convention $A_{\emptyset} = U$ , so the $I = \emptyset$ term is $∣ U ∣$ .

Proof. By the subtraction rule the left side is $∣ U ∣ - ∣ ⋃_{i} A_{i} ∣$ . Substituting the inclusion–exclusion principle and noting $- (- 1)^{∣ I ∣ + 1} = (- 1)^{∣ I ∣}$ gives the sum over non-empty $I$ ; the term $I = \emptyset$ supplies $∣ U ∣$ .∎

Truncating the alternating sum does not merely approximate — it brackets the answer, which is frequently all one needs.

Theorem 2.35 (Bonferroni inequalities). With the notation above, let $S_{k} = \sum_{∣ I ∣ = k} ∣ A_{I} ∣$ for $1 \leq k \leq n$ . Then for every odd $t$ ,

i = 1 ⋃ n A_{i} \leq k = 1 \sum t (- 1)^{k + 1} S_{k},

and for every even $t$ the inequality is reversed. In particular $∣ ⋃ A_{i} ∣ \leq S_{1}$ and $∣ ⋃ A_{i} ∣ \geq S_{1} - S_{2}$ .

Proof. Repeat the element-counting proof, but stop the inner sum at $t$ . An element in exactly $r \geq 1$ of the sets contributes $c_{t} (r) = \sum_{k = 1}^{m i n (t, r)} (- 1)^{k + 1} (k r)$ to the truncated sum, and $1$ to the union. If $t \geq r$ the contribution is exactly $1$ , as computed before. If $t < r$ , use the identity $\sum_{k = 0}^{t} (- 1)^{k} (k r) = (- 1)^{t} (t r - 1)$ , proved by induction on $t$ from Pascal's rule $(k r - 1) + (k - 1 r - 1) = (k r)$ . It gives

c_{t} (r) = 1 - k = 0 \sum t (- 1)^{k} (k r) = 1 - (- 1)^{t} (t r - 1),

so $c_{t} (r) \geq 1$ when $t$ is odd and $c_{t} (r) \leq 1$ when $t$ is even. Summing over all elements of the union gives the stated inequalities.∎

Intuition. The alternating sum overshoots and undershoots by turns, like the partial sums of an alternating series: after adding the singles you have overcounted, after subtracting the pairs you have undercounted, and each further term brings you closer. Bonferroni's inequalities say that this is not a heuristic but a theorem, which is why $S_{1}$ (the union bound) and $S_{1} - S_{2}$ are legitimate bounds even when the later terms are hopeless to compute.

Example 2.36 (Three sets, from the formula and from the pieces). Suppose $∣ A ∣ = 20$ , $∣ B ∣ = 15$ , $∣ C ∣ = 10$ , $∣ A \cap B ∣ = 5$ , $∣ A \cap C ∣ = 4$ , $∣ B \cap C ∣ = 3$ and $∣ A \cap B \cap C ∣ = 2$ . Find $∣ A \cup B \cup C ∣$ , and verify by decomposing into disjoint regions.

Solution. By the three-set formula,

∣ A \cup B \cup C ∣ = (20 + 15 + 10) - (5 + 4 + 3) + 2 = 45 - 12 + 2 = 35.

To verify, compute the seven disjoint regions. The triple region has $2$ elements. The " $A$ and $B$ but not $C$ " region has $∣ A \cap B ∣ - ∣ A \cap B \cap C ∣ = 3$ ; similarly $A \cap C$ only has $2$ and $B \cap C$ only has $1$ . Then $A$ only is $20 - 3 - 2 - 2 = 13$ , $B$ only is $15 - 3 - 1 - 2 = 9$ , and $C$ only is $10 - 2 - 1 - 2 = 5$ . Total: $13 + 9 + 5 + 3 + 2 + 1 + 2 = 35$ , as claimed.□

Pitfall. The data in such a problem must be consistent: the seven region counts computed above must all be non-negative. If a problem states $∣ A \cap B ∣ = 5$ and $∣ A \cap B \cap C ∣ = 7$ , no such sets exist, and the formula will happily return a meaningless number. Always sanity-check by reconstructing the disjoint regions.

Example 2.37 (Four sets). At a conference, $60$ delegates attended at least one of four workshops $W_{1}, \dots, W_{4}$ . Each workshop had $20$ attendees, each of the six pairs shared $6$ attendees, each of the four triples shared $2$ , and $1$ delegate attended all four. Are these numbers consistent?

Solution. By the inclusion–exclusion principle with $n = 4$ ,

⋃ W_{i} = 4 \cdot 20 - 6 \cdot 6 + 4 \cdot 2 - 1 = 80 - 36 + 8 - 1 = 51.

This contradicts the stated $60$ , so the data are inconsistent: no such configuration exists. Note that the union bound $S_{1} = 80 \geq 60$ and the Bonferroni bound $S_{1} - S_{2} = 44 \leq 60$ were both satisfied, so neither inequality alone would have caught the error; only the full alternating sum does.□

Exercises for §2.5 →

2.6Applications of Inclusion–Exclusion

Three applications show the principle doing real work: sieving the integers, counting derangements, and counting surjections. Each follows the same template — choose a universe, choose the "bad" properties, and apply the complementary form.

Theorem 2.38 (Sieve for multiples). Let $p_{1}, \dots, p_{n}$ be pairwise coprime positive integers. The number of integers in $[N]$ divisible by none of them is

I \subseteq [n] \sum (- 1)^{∣ I ∣} ⌊ \frac{N}{\prod _{i \in I} p _{i}} ⌋,

with the empty product equal to $1$ .

Proof. Take $U = [N]$ and let $A_{i}$ be the multiples of $p_{i}$ in $[N]$ . An integer is divisible by every $p_{i}$ with $i \in I$ if and only if it is divisible by $lcm_{i \in I} p_{i}$ , which equals $\prod_{i \in I} p_{i}$ because the $p_{i}$ are pairwise coprime. The multiples of $d$ in $[N]$ are $d, 2 d, \dots, ⌊ N / d ⌋ d$ , so $∣ A_{I} ∣ = ⌊ N / \prod_{i \in I} p_{i} ⌋$ . Now apply the complementary form of inclusion–exclusion.∎

Corollary 2.39 (Euler's totient formula). If $n$ has distinct prime factors $p_{1}, \dots, p_{r}$ , then the number of integers in $[n]$ coprime to $n$ is

φ (n) = n i = 1 \prod r (1 - \frac{1}{p _{i}}) .

Proof. Apply the sieve with $N = n$ and the primes $p_{1}, \dots, p_{r}$ , which are pairwise coprime. An integer in $[n]$ is coprime to $n$ exactly when it is divisible by none of the $p_{i}$ . Since each $\prod_{i \in I} p_{i}$ divides $n$ , the floors are exact: $⌊ n / \prod_{i \in I} p_{i} ⌋ = n / \prod_{i \in I} p_{i}$ . Hence

φ (n) = I \subseteq [r] \sum (- 1)^{∣ I ∣} \frac{n}{\prod _{i \in I} p _{i}} = n I \subseteq [r] \sum i \in I \prod (\frac{- 1}{p _{i}}) = n i = 1 \prod r (1 - \frac{1}{p _{i}}),

the last step being the expansion of the product: multiplying out $\prod_{i} (1 + x_{i})$ produces exactly one term $\prod_{i \in I} x_{i}$ for each subset $I$ , and here $x_{i} = - 1/ p_{i}$ .∎

Example 2.40 (Sieving to one hundred). How many integers in $[100]$ are divisible by $2$ , $3$ or $5$ ?

Solution. With $A$ , $B$ , $C$ the multiples of $2$ , $3$ , $5$ : $∣ A ∣ = 50$ , $∣ B ∣ = 33$ , $∣ C ∣ = 20$ ; $∣ A \cap B ∣ = ⌊ 100/6 ⌋ = 16$ , $∣ A \cap C ∣ = ⌊ 100/10 ⌋ = 10$ , $∣ B \cap C ∣ = ⌊ 100/15 ⌋ = 6$ ; and $∣ A \cap B \cap C ∣ = ⌊ 100/30 ⌋ = 3$ . So

∣ A \cup B \cup C ∣ = 103 - 32 + 3 = 74.

Check by complement. The integers divisible by none of $2, 3, 5$ number $100 - 74 = 26$ . Within each block of $30$ consecutive integers there are $30 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 8$ such integers, by the totient formula applied to $30$ . Three blocks cover $[90]$ and give $24$ ; the tail $91, \dots, 100$ contributes $91$ and $97$ , for $26$ in total.□

Definition 2.41 (Derangement). A derangement of $[n]$ is a permutation $σ$ of $[n]$ with no fixed point: $σ (i) \neq = i$ for every $i$ . The number of derangements of $[n]$ is written $D_{n}$ .

Theorem 2.42 (Derangement formula). For $n \geq 0$ ,

D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !},

and consequently $D_{n}$ is the nearest integer to $n! / e$ for $n \geq 1$ .

Proof. Let $U$ be the set of all $n!$ permutations of $[n]$ , and for $i \in [n]$ let $A_{i}$ be the set of permutations fixing $i$ . A derangement is a permutation in none of the $A_{i}$ , so the complementary form applies.

For $I \subseteq [n]$ with $∣ I ∣ = k$ , the set $A_{I}$ consists of the permutations fixing every element of $I$ ; such a permutation is an arbitrary permutation of the remaining $n - k$ points, so $∣ A_{I} ∣ = (n - k)!$ . There are $(k n)$ index sets of size $k$ , hence

D_{n} = k = 0 \sum n (- 1)^{k} (k n) (n - k)! = k = 0 \sum n (- 1)^{k} \frac{n !}{k ! ( n - k )!} (n - k)! = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !} .

For the final claim, $\sum_{k = 0}^{n} (- 1)^{k} / k!$ is the $n$ -th partial sum of the alternating series for $e^{- 1}$ , whose terms decrease in absolute value, so the error is at most the first omitted term $1/ (n + 1)!$ . Thus $∣ D_{n} - n! / e ∣ \leq n! / (n + 1)! = 1/ (n + 1) < 1/2$ for $n \geq 2$ , and the case $n = 1$ ( $D_{1} = 0$ , $1/ e \approx 0.368$ ) is checked directly.∎

Example 2.43 (The hat-check problem). Five guests leave their hats at a party and each collects a hat at random on leaving. In how many of the $120$ possible assignments does nobody get their own hat?

Solution. This asks for $D_{5}$ . By the formula,

D_{5} = 120 (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}) = 120 - 120 + 60 - 20 + 5 - 1 = 44.

So $44$ of the $120$ assignments are derangements, a proportion of $44/120 \approx 0.367$ , strikingly close to $1/ e \approx 0.3679$ . The convergence is fast: already at $n = 5$ the proportion is right to three decimal places, which is the analytic content of the error bound in the proof.□

Theorem 2.44 (Counting surjections). The number of surjective functions from an $n$ -set onto a $k$ -set is

Sur (n, k) = j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n} .

Proof. Let $U$ be the set of all functions $[n] \to [k]$ , so $∣ U ∣ = k^{n}$ by the product rule ( $n$ independent choices from $k$ values). For $i \in [k]$ let $A_{i}$ be the set of functions that miss $i$ , that is, whose image avoids $i$ . A function is surjective exactly when it lies in no $A_{i}$ .

For $I \subseteq [k]$ with $∣ I ∣ = j$ , the functions in $A_{I}$ are exactly the functions $[n] \to [k] ∖ I$ , and there are $(k - j)^{n}$ of them. Since there are $(j k)$ such $I$ , the complementary form gives the stated sum.∎

Remark. Dividing by $k!$ — which is legitimate because relabelling the $k$ target values permutes the surjections freely — gives the Stirling number of the second kind $S (n, k) = Sur (n, k) / k!$ , the number of ways to partition an $n$ -set into $k$ non-empty unlabelled blocks. Set partitions are the subject of their own chapter; here we note only that inclusion–exclusion is where their formula comes from.

Example 2.45 (Every prize awarded). In how many ways can $6$ distinct prizes be distributed to $3$ people so that nobody goes empty-handed?

Solution. This is $Sur (6, 3)$ :

Sur (6, 3) = (0 3) 3^{6} - (1 3) 2^{6} + (2 3) 1^{6} - (3 3) 0^{6} = 729 - 192 + 3 - 0 = 540.

Check the magnitude: $3^{6} = 729$ distributions in total, and $540/729 \approx 0.74$ , so about three quarters of distributions use all three people — plausible, since only distributions concentrated on one or two people are excluded.□

Pitfall. In the surjection count, the term $j = k$ contributes $0^{n}$ , which is $0$ for $n \geq 1$ but $1$ for $n = 0$ . The convention $0^{0} = 1$ is the right one here, and it makes the formula give the correct value $Sur (0, 0) = 1$ (the empty function is onto the empty set) and $Sur (0, k) = 0$ for $k \geq 1$ .

Exercises for §2.6 →

2.7Bijections and Counting in Two Ways

We now return to the bijection principle and develop the two techniques it powers. The first is the bijective proof: to show $∣ A ∣ = ∣ B ∣$ , exhibit a bijection. The second is double counting: to prove an identity, count one set in two ways.

Definition 2.46 (Bijection). A map $f : A \to B$ is injective if $f (a) = f (a^{'})$ implies $a = a^{'}$ , surjective if every $b \in B$ equals $f (a)$ for some $a$ , and bijective if both. Equivalently, $f$ is bijective if and only if it has a two-sided inverse $g : B \to A$ with $g (f (a)) = a$ and $f (g (b)) = b$ for all $a, b$ .

Proposition 2.47 (Inverses certify bijectivity). If $f : A \to B$ and $g : B \to A$ satisfy $g \circ f = id_{A}$ and $f \circ g = id_{B}$ , then $f$ is a bijection.

Proof. If $f (a) = f (a^{'})$ then applying $g$ gives $a = g (f (a)) = g (f (a^{'})) = a^{'}$ , so $f$ is injective. Given $b \in B$ , the element $a = g (b)$ satisfies $f (a) = f (g (b)) = b$ , so $f$ is surjective.∎

Method 2.48 (How to write a bijective proof). To prove $∣ A ∣ = ∣ B ∣$ :

Describe the map. Give an explicit rule taking each $a \in A$ to an object $f (a)$ .
Check the target. Verify $f (a) \in B$ — that the output really has the defining property of $B$ . This step is skipped more often than any other, and it is where most flawed bijections fail.
Produce the inverse. Describe $g : B \to A$ and check $g (f (a)) = a$ and $f (g (b)) = b$ . By the proposition above this settles injectivity and surjectivity at once.
Conclude by the bijection principle.

An involution — a map $f : A \to A$ with $f (f (a)) = a$ — is its own inverse, so step 3 is free whenever the map can be arranged to be one.

Intuition. An algebraic proof of $∣ A ∣ = ∣ B ∣$ computes two numbers and observes they agree. A bijective proof never computes anything: it pairs each object of $A$ with an object of $B$ so that nothing is left over on either side. That is why bijective proofs feel explanatory — they answer "why are these equal?" with "because they are the same objects, differently described".

The archetype of the recipe is the indicator-string bijection: a subset $S \subseteq [n]$ is matched with the string $(b_{1}, \dots, b_{n})$ that has $b_{i} = 1$ exactly when $i \in S$ , its inverse reads the set of positions carrying a $1$ , and the bijection principle then gives $2^{n}$ subsets from the $2^{n}$ strings. That argument is carried out in full in Basic Counting; it is worth rereading there as an instance of the four steps above rather than as a fact about subsets.

We now formalise the second technique. It is the sum rule applied twice to the same set, and although it is almost trivial to state, naming it changes how one reads identities.

Theorem 2.49 (Double counting). Let $S$ be a finite set and let $S = ⨆_{i \in I} P_{i}$ and $S = ⨆_{j \in J} Q_{j}$ be two decompositions of $S$ into pairwise disjoint parts. Then

i \in I \sum ∣ P_{i} ∣ = ∣ S ∣ = j \in J \sum ∣ Q_{j} ∣.

Proof. Both equalities are the sum rule applied to the respective decomposition; the middle quantity is the same number in each case, since it is the size of the same set.∎

Corollary 2.50 (Counting a table in two directions). Let $R \subseteq X \times Y$ be any relation between finite sets, and for $x \in X$ , $y \in Y$ write $r (x) = ∣ {y : (x, y) \in R} ∣$ and $c (y) = ∣ {x : (x, y) \in R} ∣$ . Then

x \in X \sum r (x) = ∣ R ∣ = y \in Y \sum c (y) .

Proof. The sets $R_{x} = {(x, y) \in R}$ , one for each $x \in X$ , are pairwise disjoint with union $R$ , and $∣ R_{x} ∣ = r (x)$ via the bijection $(x, y) \mapsto y$ . The sets $R^{y} = {(x, y) \in R}$ for $y \in Y$ give a second such decomposition with $∣ R^{y} ∣ = c (y)$ . Apply the double counting theorem.∎

Intuition. Write the relation as a grid of ticks: rows indexed by $X$ , columns by $Y$ , a tick in cell $(x, y)$ when $(x, y) \in R$ . Count the ticks row by row and you get $\sum r (x)$ ; count them column by column and you get $\sum c (y)$ . The ticks did not move, so the totals agree. Every double-counting proof is that picture with a well-chosen grid.

Theorem 2.51 (Handshake lemma). In any finite graph $G = (V, E)$ , the degrees sum to twice the number of edges:

v \in V \sum de g (v) = 2∣ E ∣.

Consequently the number of vertices of odd degree is even.

Proof. Apply the table corollary to the incidence relation $R = {(v, e) \in V \times E : v is an endpoint of e}$ . Row sums: for fixed $v$ , the number of incident edges is $de g (v)$ , so $\sum_{v} de g (v) = ∣ R ∣$ . Column sums: each edge has exactly two endpoints, so $c (e) = 2$ for every $e$ and $∣ R ∣ = 2∣ E ∣$ .

For the consequence, split the sum by parity: $\sum_{v} de g (v) = \sum_{d e g v even} de g (v) + \sum_{d e g v odd} de g (v)$ . The total is even and the first part is even, so the second is even; being a sum of odd numbers, it can be even only if it has an even number of terms.∎

Example 2.52 (There is always a repeat handshake). At a party some pairs shake hands. Show that the number of people who shook hands an odd number of times is even.

Solution. Model the party as a graph: people are vertices, handshakes are edges, and the number of handshakes a person made is their degree. The handshake lemma says the number of odd-degree vertices is even, which is exactly the claim.

Note what was gained: the statement concerns the parity of a count over a structure that may be arbitrarily complicated, and the proof never examines the structure at all. It only counts incidences twice.□

Theorem 2.53 (Binomial identities by double counting). For integers $0 \leq k \leq n$ :

$k = 0 \sum n (k n) = 2^{n}$ .
$k (k n) = n (k - 1 n - 1)$ for $k \geq 1$ , and hence $k = 0 \sum n k (k n) = n 2^{n - 1}$ .
(Vandermonde) $(r m + n) = k = 0 \sum r (k m) (r - k n)$ .

Proof.

Count the subsets of $[n]$ in two ways. All at once, there are $2^{n}$ of them. Alternatively, partition them by size: the subsets of size $k$ number $(k n)$ , and every subset has exactly one size, so the parts are disjoint and cover. Double counting gives the identity.
Count pairs $(S, x)$ with $S \subseteq [n]$ , $∣ S ∣ = k$ , and $x \in S$ — "a committee of $k$ with a designated chair". Choosing the committee first gives $(k n)$ committees and then $k$ choices of chair, so the count is $k (k n)$ . Choosing the chair first gives $n$ choices, and then the other $k - 1$ members are any $(k - 1)$ -subset of the remaining $n - 1$ people, so the count is $n (k - 1 n - 1)$ . For the consequence, sum $k (k n) = n (k - 1 n - 1)$ over $k$ and use part 1 applied to $n - 1$ : $\sum_{k \geq 1} n (k - 1 n - 1) = n \cdot 2^{n - 1}$ .
Count the $r$ -element subsets of a set of $m + n$ elements that has been split into a block $M$ of size $m$ and a block $N$ of size $n$ . Directly there are $(r m + n)$ . Alternatively classify by $k = ∣ S \cap M ∣$ , which takes one value per subset, so the classes are disjoint and cover; a subset with $∣ S \cap M ∣ = k$ is determined by choosing $k$ elements of $M$ and $r - k$ of $N$ , which by the product rule can be done in $(k m) (r - k n)$ ways. Summing over $k$ gives the identity.

∎

Remark. Identity 2 is worth rereading as a slogan: choose the special element first. Whenever a formula has a stray factor of $k$ or $n$ in front of a binomial coefficient, there is usually a distinguished element being chosen, and pinning down what it is converts the algebra into a sentence.

Example 2.54 (The hockey-stick identity). Prove that $i = k \sum n (k i) = (k + 1 n + 1)$ for $0 \leq k \leq n$ .

Solution. Count the $(k + 1)$ -element subsets of $[n + 1]$ in two ways.

Directly there are $(k + 1 n + 1)$ of them.

Alternatively, classify each subset $S$ by its largest element $m$ . Since $∣ S ∣ = k + 1 \geq 1$ , every subset has a well-defined largest element, and the classes are disjoint and cover. If the largest element is $m$ , the remaining $k$ elements form an arbitrary $k$ -subset of $[m - 1]$ , which can be chosen in $(k m - 1)$ ways. As $m$ ranges over $k + 1, \dots, n + 1$ , writing $i = m - 1$ gives

(k + 1 n + 1) = m = k + 1 \sum n + 1 (k m - 1) = i = k \sum n (k i) .

The "classify by the largest (or smallest) element" move is the workhorse of such proofs; once you have it, hockey-stick is not a formula to memorise but a sentence to recall.□

Exercises for §2.7 →

2.8Classic Bijections and Double Counting

This section collects the bijections every combinatorialist knows, each stated as a theorem and proved by an explicit map with an explicit inverse.

The pattern is already familiar from one case: $(k n) = (n - k n)$ , proved in Basic Counting by complementation $S \mapsto [n] ∖ S$ , a map from the $k$ -subsets of $[n]$ to the $(n - k)$ -subsets that is its own inverse and hence a bijection. Every proof below has that shape, applied to a less obvious pair of families.

Theorem 2.55 (Even and odd subsets). For $n \geq 1$ , the set $[n]$ has exactly as many even-sized subsets as odd-sized ones, namely $2^{n - 1}$ of each. Equivalently, $\sum_{k = 0}^{n} (- 1)^{k} (k n) = 0$ .

Proof. Let $E$ and $O$ be the families of even- and odd-sized subsets. Define $g : E \to O$ by toggling the element $1$ :

g (S) = {S \cup {1} S ∖ {1} 1 \in / S, 1 \in S .

Toggling changes the size by exactly $\pm 1$ , so it reverses parity and $g$ does map $E$ into $O$ . The same formula defines a map $O \to E$ , and toggling twice restores $S$ , so $g$ is an involution and hence a bijection. Therefore $∣ E ∣ = ∣ O ∣$ , and since $∣ E ∣ + ∣ O ∣ = 2^{n}$ by the sum rule and the subset count, each is $2^{n - 1}$ .

The alternating-sum form follows by grouping subsets by size: $\sum_{k} (- 1)^{k} (k n) = ∣ E ∣ - ∣ O ∣ = 0$ .∎

Remark. This is the combinatorial content of the cancellation used in the proof of the inclusion–exclusion principle, where $\sum_{k} (- 1)^{k} (k r) = 0$ for $r \geq 1$ was obtained from the binomial theorem. The toggle involution replaces that algebra with a pairing, which is exactly the trade a bijective proof offers.

Pitfall. The hypothesis $n \geq 1$ is essential and is exactly what makes a toggling element available. For $n = 0$ there is one even-sized subset — the empty set — and no odd-sized one, so the conclusion is false. A bijective proof always breaks at the point where the map cannot be defined; finding that point is a good way to discover the hypothesis you forgot.

Stars and bars is the next: the number of solutions of $x_{1} + x_{2} + \dots + x_{k} = n$ in non-negative integers is $(k - 1 n + k - 1)$ . It is proved in Basic Counting, and proved there by precisely the bijection this section is about — write $x_{1}$ stars, a bar, $x_{2}$ stars, a bar, and so on, so that a solution becomes an arrangement of $n$ stars and $k - 1$ bars, an arrangement being determined by which $k - 1$ of the $n + k - 1$ positions hold the bars. The formula is used in the example below without further comment.

Example 2.56 (Distributing identical objects). In how many ways can $10$ identical chocolates be divided among $4$ children, if a child may get none? And if every child must get at least one?

Solution. The first question is stars and bars with $n = 10$ , $k = 4$ : $(4 - 1 10 + 4 - 1) = (3 13) = 286$ .

For the second, substitute $x_{i} = y_{i} + 1$ with $y_{i} \geq 0$ . The equation becomes $y_{1} + \dots + y_{4} = 6$ , and the substitution is a bijection between the positive solutions of the first equation and the non-negative solutions of the second (its inverse subtracts one from each coordinate). So the count is $(3 6 + 4 - 1) = (3 9) = 84$ .□

Theorem 2.57 (Conjugation of partitions). For all $n, r \geq 1$ , the number of partitions of $n$ into at most $r$ parts equals the number of partitions of $n$ into parts each of size at most $r$ .

Proof. Represent a partition $λ_{1} \geq λ_{2} \geq \dots \geq λ_{ℓ} \geq 1$ with $\sum λ_{i} = n$ by its Young diagram: left-justified rows of boxes, the $i$ -th row having $λ_{i}$ boxes. Define the conjugate $λ^{'}$ by reflecting the diagram in its main diagonal, so that $λ_{j}^{'}$ is the number of rows with at least $j$ boxes — that is, the length of the $j$ -th column.

The reflected diagram is again a valid Young diagram: column lengths are weakly decreasing because the rows are weakly decreasing and left-justified. Reflection preserves the number of boxes, so $λ^{'}$ is again a partition of $n$ . Reflecting twice returns the original diagram, so conjugation is an involution, hence a bijection on the partitions of $n$ .

Finally, conjugation exchanges the two conditions: $λ$ has at most $r$ rows if and only if every column of $λ$ has length at most $r$ , which is precisely the statement that every part of $λ^{'}$ is at most $r$ . So conjugation restricts to a bijection between the two families in the statement.∎

Example 2.58 (Checking conjugation by hand). Verify the theorem for $n = 6$ , $r = 2$ .

Solution. Partitions of $6$ with at most $2$ parts: $6$ , $5 + 1$ , $4 + 2$ , $3 + 3$ — four of them.

Partitions of $6$ with every part at most $2$ : $2 + 2 + 2$ , $2 + 2 + 1 + 1$ , $2 + 1 + 1 + 1 + 1$ , $1 + 1 + 1 + 1 + 1 + 1$ — also four.

Conjugation matches them: $6 \leftrightarrow 1 + 1 + 1 + 1 + 1 + 1$ , $5 + 1 \leftrightarrow 2 + 1 + 1 + 1 + 1$ , $4 + 2 \leftrightarrow 2 + 2 + 1 + 1$ , $3 + 3 \leftrightarrow 2 + 2 + 2$ . Note that the bijection is between the two families, not a symmetry within one: only self-conjugate partitions are fixed.□

Theorem 2.59 (Ballot problem and Catalan numbers). The number of lattice paths from $(0, 0)$ to $(n, n)$ using unit steps right and up that never rise above the diagonal $y = x$ is the Catalan number

C_{n} = \frac{1}{n + 1} (n 2 n) = (n 2 n) - (n - 1 2 n) .

Proof. A path from $(0, 0)$ to $(n, n)$ consists of $2 n$ steps, $n$ of them right, and is determined by which steps are right; so there are $(n 2 n)$ paths in all.

Call a path bad if it touches the line $y = x + 1$ at some point; the good paths are exactly the ones we want to count. We biject the bad paths with the paths from $(- 1, 1)$ to $(n, n)$ .

Given a bad path, let $P$ be its first contact with the line $y = x + 1$ and reflect the portion of the path before $P$ in that line. Reflection in $y = x + 1$ sends $(a, b)$ to $(b - 1, a + 1)$ and exchanges right steps with up steps, so the reflected segment is again a lattice path; it now starts at the image of $(0, 0)$ , namely $(- 1, 1)$ , and still ends at $P$ . Leaving the rest of the path untouched gives a path from $(- 1, 1)$ to $(n, n)$ .

The map is invertible. A path from $(- 1, 1)$ to $(n, n)$ starts strictly above the line $y = x + 1$ , since at $x = - 1$ the line has height $0 < 1$ , and ends strictly below it, since at $x = n$ the line has height $n + 1 > n$ ; a lattice path changing one coordinate by one at a time cannot get from one side to the other without landing on the line, so it meets the line. Reflecting its initial segment at the first contact returns a path from $(0, 0)$ to $(n, n)$ that touches the line, hence a bad path, and the two reflections undo one another.

A path from $(- 1, 1)$ to $(n, n)$ takes $n + 1$ right steps and $n - 1$ up steps, so there are $(n - 1 2 n)$ of them. Hence the good paths number

(n 2 n) - (n - 1 2 n) = (n 2 n) (1 - \frac{n}{n + 1}) = \frac{1}{n + 1} (n 2 n),

using $(n - 1 2 n) = (n 2 n) \cdot \frac{n}{n + 1}$ , which follows from the factorial expressions.∎

Figure 2.60. The reflection, drawn for

n = 3

. The bad path (solid) touches

y = x + 1

first at

P = (0, 1)

; reflecting only the portion before

P

moves its start from

(0, 0)

(- 1, 1)

and leaves the rest alone, producing a path from

(- 1, 1)

(3, 3)

Intuition. The reflection principle is a sign-cancelling device in disguise. Bad paths are objects we want to discard; instead of discarding them one at a time, we match each with a path to a different endpoint, whose count we already know. Subtracting a known count is the same as cancelling, and the bijection is what licences it.

Example 2.61 (Balanced bracket sequences). Show that the number of sequences of $n$ opening and $n$ closing brackets in which every prefix has at least as many openings as closings is $C_{n}$ .

Solution. Map a bracket sequence to a lattice path by reading left to right: an opening bracket is a right step, a closing bracket an up step. A sequence with $n$ of each becomes a path from $(0, 0)$ to $(n, n)$ , and the reverse reading recovers the sequence, so this is a bijection between bracket sequences and paths.

The prefix condition says that after any number of symbols, the closings so far do not exceed the openings — that is, the path's height never exceeds its horizontal position, so the path stays weakly below $y = x$ . By the previous theorem the count is $C_{n}$ .

This is the pattern for every Catalan bijection: find the map that turns a structural constraint into a geometric one, then count the geometry.□

Theorem 2.62 (Counting edges in two ways: Mantel's theorem). A graph on $n$ vertices with no triangle has at most $n^{2} /4$ edges.

Proof. Let $G$ be triangle-free with vertex set $V$ , $∣ V ∣ = n$ , and edge set $E$ . For an edge $uv \in E$ , the neighbourhoods of $u$ and $v$ are disjoint: a common neighbour $w$ would make $uv w$ a triangle. Hence $de g (u) + de g (v) \leq n$ for every edge $uv$ .

Sum this over all edges and count the left side in the other direction. Each vertex $u$ appears in the sum once for each incident edge, that is $de g (u)$ times, so

uv \in E \sum (de g (u) + de g (v)) = u \in V \sum de g (u)^{2} \leq n ∣ E ∣.

By the Cauchy–Schwarz inequality, or equivalently because the mean of squares is at least the square of the mean,

u \in V \sum de g (u)^{2} \geq \frac{( \sum _{u} de g ( u ) ) ^{2}}{n} = \frac{( 2∣ E ∣ ) ^{2}}{n},

using the handshake lemma. Combining, $4∣ E ∣^{2} / n \leq n ∣ E ∣$ , so $∣ E ∣ \leq n^{2} /4$ .∎

Remark. The bound is attained by the complete bipartite graph with parts of sizes $⌈ n /2 ⌉$ and $⌊ n /2 ⌋$ , which has $⌊ n^{2} /4 ⌋$ edges and no triangle, since any triangle would need two vertices in the same part and those are never adjacent. Mantel's theorem is the first case of Turán's theorem, and the proof above — count a quantity over edges, then over vertices — is the standard entry point into extremal graph theory.

Exercises for §2.8 →

2.9The Reach and the Limits of These Principles

Having seen the principles work, it is worth asking honestly what they do and do not deliver.

Bijections generalise for free. A bijection between two families usually respects more structure than the statement mentions, and each extra invariant it preserves upgrades the theorem. Conjugation of partitions was stated as an equality of two counts, but the map itself preserves the number of boxes, sends the largest part to the number of parts, and fixes exactly the self-conjugate partitions — three further theorems from one map.

Proof. Conjugation is a bijection on partitions of $n$ which exchanges "largest part" with "number of parts": the largest part of $λ$ is the length of the first row, which becomes the length of the first column of $λ^{'}$ , that is the number of parts of $λ^{'}$ . Applying this to both statistics in the statement gives the claim, since a bijection restricts to a bijection between subfamilies defined by corresponding conditions.∎

Sign-reversing involutions extend the method to identities with minus signs. A bijective proof of $∣ A ∣ = ∣ B ∣$ needs both sides to be counts of things. An identity such as $\sum_{k} (- 1)^{k} a_{k} = c$ has no such reading — until one builds a single set of signed objects and pairs off objects of opposite sign.

Method 2.64 (Proving an identity by a sign-reversing involution). To prove $\sum_{x \in S} sign (x) = c$ :

Realise the alternating sum as a signed set $S$ , each object carrying a sign $\pm 1$ .
Construct an involution $ι$ on $S$ that reverses sign, defined on all of $S$ except a set $F$ of fixed points.
Objects paired by $ι$ cancel, so the sum reduces to the signed count of $F$ .
Show $sign$ -summing over $F$ gives $c$ — ideally $F$ is small and all of one sign.

Example 2.65 (An alternating identity by cancellation). Prove that for $n \geq 1$ , $k = 0 \sum n (- 1)^{k} (k n) = 0$ , by exhibiting a sign-reversing involution.

Solution. Let $S$ be the set of all subsets of $[n]$ , with $sign (T) = (- 1)^{∣ T ∣}$ . Grouping by size shows $\sum_{T \in S} sign (T) = \sum_{k} (- 1)^{k} (k n)$ , which is the sum in question.

Let $ι$ toggle the element $1$ , as in the even/odd theorem. It is an involution on $S$ , it changes $∣ T ∣$ by $\pm 1$ and therefore reverses sign, and it has no fixed points, since $T$ and $T △ {1}$ always differ. So $S$ is partitioned into pairs of opposite sign, every pair contributes $0$ , and the total is $0$ .

The hypothesis $n \geq 1$ is what guarantees the element $1$ exists — the same place the argument must break, since for $n = 0$ the sum is $1$ .□

Not everything has a nice bijection, and some equalities resist one for decades. The Rogers–Ramanujan identities — that the partitions of $n$ into parts differing by at least $2$ are equinumerous with those into parts congruent to $1$ or $4$ modulo $5$ — were proved analytically by Rogers in 1894, but a genuinely bijective proof (Garsia–Milne, 1981) took almost ninety years and is famously intricate. We state the identity without proof: its proof is far beyond this chapter, and rests on $q$ -series machinery rather than on anything developed here.

Remark. A word on honesty about scope. Three results in this chapter are quoted rather than proved from scratch: the binomial theorem (used once, to evaluate $(1 - 1)^{r}$ ), the Cauchy–Schwarz inequality (used once, in Mantel's theorem), and the alternating-series error bound (used to place $D_{n}$ near $n! / e$ ). Each is standard and each is proved elsewhere in this corpus. Everything else above is proved where it is stated.

Pigeonhole proves existence and nothing more. This is a genuine limitation, not a stylistic one. The pigeonhole argument for Dirichlet's theorem shows a good rational approximation exists but offers no way to find it; continued fractions, a different technique entirely, produce it. Ramsey's theorem for $K_{6}$ guarantees a monochromatic triangle in a $15$ -edge colouring, and the proof even suggests where to look, but the corresponding guarantee for larger Ramsey numbers is spectacularly ineffective: $R (5, 5)$ is known only to lie between $43$ and $46$ , and Erdős's remark that humanity would do better to fight an alien demanding $R (6, 6)$ than to compute it remains apt.

Inclusion–exclusion is exact but can be computationally hopeless. The formula for $n$ sets has $2^{n} - 1$ terms, so it is a practical tool only when the intersections have a closed form (as in the sieve, the derangement count and the surjection count) or when a truncation suffices. That truncation is exactly what the Bonferroni inequalities licence, and it is why the union bound $∣ ⋃ A_{i} ∣ \leq \sum ∣ A_{i} ∣$ — the crudest possible instance — is nevertheless one of the most used inequalities in probability and in the probabilistic method.

Pitfall. Inclusion–exclusion is a statement about finite cardinalities. For infinite sets it has no meaning as stated, since the terms are not numbers; the correct generalisation is to finite measures, where $μ (A \cup B) = μ (A) + μ (B) - μ (A \cap B)$ holds, and the proof is the same disjoint decomposition with $μ$ in place of $∣ \cdot ∣$ . Probability, where $μ$ is a probability measure, is the most common such setting.

Summary. The chapter in one paragraph. The sum rule counts disjoint pieces; the product rule counts independent choices; both follow from the definition of cardinality as a listing. The bijection principle transports a count across a matching, and is the engine behind both rules. Pigeonhole is the sum rule read as an inequality: fibres cannot all be small, which yields existence theorems — Ramsey, Erdős–Szekeres, Dirichlet — whose conclusions are far stronger than their proofs are long. Inclusion–exclusion repairs the sum rule when the pieces overlap, and its complementary form counts objects avoiding a list of properties: the sieve, derangements, surjections. Double counting equates two decompositions of one set and yields identities — handshake, Vandermonde, hockey-stick, Mantel — with no algebra at all.

Exercises for §2.9 →

Common Mistakes

Adding without checking disjointness. The sum rule requires $A_{i} \cap A_{j} = \emptyset$ . If the cases overlap, the answer is too big, and the fix is inclusion–exclusion, not a smaller estimate.
Multiplying when the number of options depends on history. The sequential choice rule needs the count at each step to be constant. When it varies, split into cases and add.
Forgetting the "+1". $m$ objects in $m$ boxes force no collision; $m + 1$ do. Likewise the generalised threshold is $(k - 1) m + 1$ , not $(k - 1) m$ .
Quoting the generalised bound when supplies are limited. $(k - 1) m + 1$ answers the unconstrained problem. If some box cannot hold $k - 1$ objects, recompute the maximal blocking configuration and add one.
Treating the ceiling form as a claim about every box. It bounds the fullest box only; other boxes may be empty, and you do not get to choose which box is full.
Claiming a pigeonhole argument locates the collision. It proves existence. Which pair collides, and how to find it, are different questions needing different tools.
Using $ab$ where $lcm (a, b)$ is needed. The multiples of $a$ and of $b$ intersect in the multiples of $lcm (a, b)$ ; that is $ab$ only when $a$ and $b$ are coprime.
Getting the inclusion–exclusion signs wrong. The $k$ -fold intersections carry $(- 1)^{k + 1}$ in the union form and $(- 1)^{k}$ in the complementary form. Confusing the two flips the whole answer.
Stopping after the pairwise terms. Triples have been added three times and subtracted three times and would otherwise vanish; they must be added back.
Accepting inconsistent intersection data. If the seven (or $2^{n} - 1$ ) disjoint regions come out negative, no such sets exist and the formula's output is meaningless.
Asserting a bijection without exhibiting it. "There is an obvious correspondence" is not a proof. Give the map, check that its output has the required property, and give the inverse.
Forgetting to check the target. Half of all faulty bijective proofs define a perfectly good map whose outputs do not actually lie in the intended set.
Confusing a bijection with an injection. An injection proves $∣ A ∣ \leq ∣ B ∣$ only. Both directions, or an explicit inverse, are needed for equality.
Missing the degenerate case. Toggling arguments need an element to toggle, so they fail at $n = 0$ ; largest-element arguments need the set to be non-empty. Check the smallest case.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter