Contents / Discrete Mathematics / Combinatorics

Chapter 4

Combinatorics

The sum and product rules with counterexamples when their hypotheses fail; permutations and combinations derived by uniform overcounting; Pascal's identity proved combinatorially; the binomial theorem with Vandermonde and the hockey-stick identity; stars and bars as a bijection; the pigeonhole principle with its generalised form and classic applications; and inclusion-exclusion with derangements as a corollary.

Introduction

Counting sounds like the first thing a person learns and the last thing worth a chapter. But the sets a computer scientist wants to count are never small enough to count one at a time. How many passwords of length eight are there over a $94$ -character keyboard? How many distinct ways can a hash function scatter $23$ keys into $365$ buckets without a collision? How many subsets of a $40$ -flag configuration space must a test suite cover? Each of these is a number no one will ever enumerate, and each is computed in one line by the rules of this chapter.

The subject has a characteristic style of argument. To count a set $S$ , you do not inspect $S$ ; you build a bijection between $S$ and a set whose size you already know, or you decompose $S$ into pieces you can count separately, or you count something larger and divide by the exact factor by which you overcounted. Almost every result below is one of those three moves, and the value of learning them is that they compose: the count of poker hands, of binary strings with a fixed number of ones, and of the ways to distribute identical tasks over distinct servers are all the same calculation wearing different clothes.

We begin with the two rules everything rests on — the sum rule and the product rule — stated carefully enough that their hypotheses are visible, since almost every wrong count in practice is one of those two rules applied where its hypothesis fails. From there we get functions, injections and permutations, then combinations and the binomial coefficients, whose identities are proved twice over: once by algebra and once by counting a set in two ways, which is the more instructive proof and often the shorter one. The pigeonhole principle then shows that counting proves existence, not just size. We finish with inclusion–exclusion, the systematic way to count a union whose pieces overlap.

Throughout, all sets are finite, $∣ S ∣$ denotes the number of elements of $S$ , and $[n] = {1, 2, \dots, n}$ . The deeper theory — generating functions, the transfer-matrix method, enumerative and extremal combinatorics — belongs to the separate subject Combinatorics; here we build the vocabulary it presumes.

4.1Basic Counting Principles

Two rules generate the entire chapter. They correspond to the two ways a decision can be structured: a choice between alternatives, and a sequence of choices made one after another. Getting a count wrong almost always means one of these was applied when its hypothesis did not hold, so we state the hypotheses explicitly and then break each rule on purpose to see what the hypothesis was doing.

Definition 4.1 (Disjoint sets and a partition). Two sets $A$ and $B$ are disjoint if $A \cap B = \emptyset$ . A family $A_{1}, \dots, A_{k}$ is pairwise disjoint if $A_{i} \cap A_{j} = \emptyset$ whenever $i \neq = j$ , and it is a partition of $S$ if in addition $A_{1} \cup \dots \cup A_{k} = S$ .

Theorem 4.2 (Sum rule). Let $A_{1}, A_{2}, \dots, A_{k}$ be pairwise disjoint finite sets. Then

∣ A_{1} \cup A_{2} \cup \dots \cup A_{k} ∣ = ∣ A_{1} ∣ + ∣ A_{2} ∣ + \dots + ∣ A_{k} ∣.

Proof. Induct on $k$ . For $k = 1$ there is nothing to prove.

For $k = 2$ , suppose $∣ A_{1} ∣ = m$ and $∣ A_{2} ∣ = n$ , witnessed by bijections $f : A_{1} \to [m]$ and $g : A_{2} \to [n]$ . Define $h : A_{1} \cup A_{2} \to [m + n]$ by $h (x) = f (x)$ for $x \in A_{1}$ and $h (x) = m + g (x)$ for $x \in A_{2}$ . This is well defined precisely because $A_{1} \cap A_{2} = \emptyset$ : no $x$ receives two values. It is injective, since $f$ and $g$ are injective and their images $[m]$ and ${m + 1, \dots, m + n}$ are disjoint, and it is surjective because every element of $[m + n]$ lies in one of those two images. So $∣ A_{1} \cup A_{2} ∣ = m + n$ .

For the induction step, write $A_{1} \cup \dots \cup A_{k + 1} = (A_{1} \cup \dots \cup A_{k}) \cup A_{k + 1}$ . The set $A_{k + 1}$ is disjoint from each $A_{i}$ with $i \leq k$ , hence from their union, so the case $k = 2$ applies and the inductive hypothesis finishes the sum.∎

Pitfall. Drop disjointness and the rule fails immediately. Among the integers in $[10]$ , let $A$ be the even ones and $B$ the multiples of $3$ . Then $∣ A ∣ = 5$ and $∣ B ∣ = 3$ , but $∣ A \cup B ∣ = ∣ {2, 3, 4, 6, 8, 9, 10} ∣ = 7$ , not $8$ — the element $6$ was counted twice. Repairing that double count in general is exactly what the section Inclusion-Exclusion is for.

Theorem 4.3 (Product rule). Suppose an object is built by a sequence of $k$ choices, where the first choice has $n_{1}$ options and, for each $i \geq 2$ , the number of options at step $i$ is $n_{i}$ no matter how steps $1$ through $i - 1$ turned out. Suppose also that distinct sequences of choices produce distinct objects. Then the number of objects built is

n_{1} n_{2} \dots n_{k} .

In particular, for finite sets $S_{1}, \dots, S_{k}$ , $∣ S_{1} \times \dots \times S_{k} ∣ = ∣ S_{1} ∣ \dots ∣ S_{k} ∣$ .

Proof. Induct on $k$ . For $k = 1$ the claim is the definition of $n_{1}$ .

Suppose it holds for $k$ and consider a process of $k + 1$ steps. Partition the objects by the outcome of the first step: for each of the $n_{1}$ options $c$ , let $A_{c}$ be the set of objects whose first choice was $c$ . These sets are pairwise disjoint, since distinct choice sequences give distinct objects and an object records its first choice. Within $A_{c}$ the remaining $k$ steps have $n_{2}, \dots, n_{k + 1}$ options, independent of prior outcomes, so the inductive hypothesis gives $∣ A_{c} ∣ = n_{2} \dots n_{k + 1}$ . The theorem Sum rule now gives

c \sum ∣ A_{c} ∣ = n_{1} \cdot (n_{2} \dots n_{k + 1}),

as claimed. The product form for Cartesian products is the special case where step $i$ chooses a coordinate from $S_{i}$ .∎

The hypothesis that the number of options at step $i$ is constant is weaker than it first looks, and weaker than it needs to be in practice. The options themselves may change wildly; only the count must not. Choosing an ordered pair of distinct letters from ${a, b, c, d}$ has $4$ options at step one and $3$ at step two — a different three letters each time, but always three — so the product rule applies and gives $12$ .

Pitfall. When the count at step two genuinely depends on step one, the product rule is simply false. Count the strings of length two over ${a, b, c}$ in which the second character differs from the first and, if the first character is $a$ , the second must also avoid $b$ . Step one has $3$ options; step two has $2$ options after $b$ or after $c$ , but only $1$ after $a$ (namely $c$ ). The true count is $1 + 2 + 2 = 5$ , whereas $3 \times 2 = 6$ . The repair is always the same: split into cases with the theorem Sum rule first, then apply the product rule inside each case, where the counts are constant.

Theorem 4.4 (Counting functions). Let $∣ A ∣ = k$ and $∣ B ∣ = n$ . The number of functions $f : A \to B$ is $n^{k}$ .

Proof. List the elements of $A$ as $a_{1}, \dots, a_{k}$ . A function $f$ is determined by, and determines, the sequence of values $(f (a_{1}), \dots, f (a_{k}))$ , so the set of functions is in bijection with $B^{k}$ . Each coordinate is chosen from $B$ freely and independently of the others, so the theorem Product rule applies with $n_{1} = \dots = n_{k} = n$ , giving $n^{k}$ .∎

Corollary 4.5 (Strings and subsets). Over an alphabet of $n$ symbols there are $n^{k}$ strings of length $k$ . A set with $n$ elements has exactly $2^{n}$ subsets.

Proof. A string of length $k$ is a function from the positions $[k]$ to the alphabet, so the theorem Counting functions gives $n^{k}$ .

For subsets, fix $S = {s_{1}, \dots, s_{n}}$ and map each subset $T \subseteq S$ to its indicator string $χ (T) \in {0, 1}^{n}$ , whose $i$ -th bit is $1$ exactly when $s_{i} \in T$ . Distinct subsets differ at some $s_{i}$ and so have different strings, making $χ$ injective; and any bit string $b$ is the image of $T = {s_{i} : b_{i} = 1}$ , making $χ$ surjective. So subsets are in bijection with binary strings of length $n$ , of which there are $2^{n}$ .∎

Intuition. The indicator string is the reason a set of $n$ feature flags has $2^{n}$ configurations, and the reason a subset is stored as a bitmask. "Choose a subset" and "answer $n$ independent yes/no questions" are the same act.

Example 4.6 (Counting passwords). A system requires passwords of length exactly $8$ over the $62$ alphanumeric characters. How many are there, and how many contain at least one digit?

Solution.

Each of the $8$ positions is filled independently from $62$ symbols, so by the corollary Strings and subsets there are $6 2^{8} = 218, 340, 105, 584, 896$ passwords.
Counting those with at least one digit directly would require splitting on how many digits appear. Count the complement instead: a password with no digit uses only the $52$ letters, and there are $5 2^{8} = 53, 459, 728, 531, 456$ of those.
The digit-free passwords and the rest partition the whole set, so by the theorem Sum rule the answer is $6 2^{8} - 5 2^{8} = 164, 880, 377, 053, 440$ .

□

Remark. Step 2 is the complement trick, and it is worth naming because it recurs: "at least one" is almost always easier to count as "total minus none". The alternative — summing over exactly one digit, exactly two, and so on — is the same number obtained with seven times the work.

Theorem 4.7 (Counting injections). Let $∣ A ∣ = k$ and $∣ B ∣ = n$ . The number of injective functions $f : A \to B$ is

n (n - 1) (n - 2) \dots (n - k + 1),

which is $0$ when $k > n$ .

Proof. Order $A$ as $a_{1}, \dots, a_{k}$ and build $f$ by choosing $f (a_{1}), f (a_{2}), \dots$ in turn. Injectivity says exactly that each value must avoid the values already used. When $f (a_{i})$ is chosen, $i - 1$ values have been used and they are distinct, so exactly $n - (i - 1)$ elements of $B$ remain available — a count that does not depend on which values were used, only how many. The theorem Product rule therefore applies and yields $\prod_{i = 1}^{k} (n - i + 1)$ . Distinct choice sequences give distinct functions, since the sequence is the list of values. If $k > n$ the factor with $i = n + 1$ is zero, matching the fact that no injection exists.∎

Example 4.8 (Hash collisions). A hash function maps $12$ distinct keys into a table of $365$ slots, each key landing in a slot independently and uniformly. How many of the possible outcomes place every key in a different slot, and what fraction of all outcomes is that?

Solution.

An outcome is a function from the $12$ keys to the $365$ slots, so by the theorem Counting functions there are $36 5^{12}$ outcomes.
A collision-free outcome is an injection, so by the theorem Counting injections there are $365 \cdot 364 \dots 354$ of them.
The fraction is $\frac{365 \cdot 364 \dots 354}{36 5 ^{12}} \approx 0.833$ . So even with only $12$ keys and $365$ slots, a collision occurs about $17%$ of the time — this is the birthday problem, and it is why hash tables are designed to handle collisions rather than to avoid them.

□

Example 4.9 (Splitting before multiplying). How many strings of length $4$ over ${a, b, c, d, e}$ begin with a vowel or end with the letter $e$ ?

Solution.

Let $V$ be the set of such strings beginning with $a$ or $e$ , and $E$ those ending with $e$ . The two sets are not disjoint, so the theorem Sum rule does not apply directly to $V \cup E$ .
Partition instead by the first letter. If the first letter is $a$ or $e$ ( $2$ ways), the remaining three positions are free: $2 \cdot 5^{3} = 250$ strings.
If the first letter is one of the three consonants, the string must end in $e$ : $3 \cdot 5 \cdot 5 \cdot 1 = 75$ strings.
These two cases are disjoint and exhaust $V \cup E$ , so the count is $250 + 75 = 325$ .

□

Exercises for §4.1 →

4.2Permutations

An arrangement is an injection whose target is the same set as its source, or a list of distinct items drawn from a pool. The counting was already done in the theorem Counting injections; this section names the result, packages it in factorials, and then handles the case that the items are not all distinguishable.

Definition 4.10 (Factorial). For an integer $n \geq 0$ define

n! = n \cdot (n - 1) \dots 2 \cdot 1, 0! = 1.

The convention $0! = 1$ is forced, not arbitrary: there is exactly one way to arrange nothing, namely the empty arrangement, and every formula below would need a special case without it.

Definition 4.11 (Permutation and $k$ -permutation). A permutation of a finite set $S$ is a linear arrangement of all its elements, equivalently a bijection $S \to S$ . A $k$ -permutation of $S$ is an ordered list of $k$ distinct elements of $S$ . The number of $k$ -permutations of an $n$ -set is written $P (n, k)$ .

Theorem 4.12 (The $k$ -permutation count). For $0 \leq k \leq n$ ,

P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n !}{( n - k )!} .

Proof. A $k$ -permutation of $S$ is exactly an injection $[k] \to S$ , read as the list $(f (1), \dots, f (k))$ , so the theorem Counting injections gives $P (n, k) = n (n - 1) \dots (n - k + 1)$ .

For the factorial form, multiply and divide by the missing tail:

n (n - 1) \dots (n - k + 1) = \frac{n ( n - 1 ) \dots ( n - k + 1 ) \cdot ( n - k ) ( n - k - 1 ) \dots 1}{( n - k ) ( n - k - 1 ) \dots 1} = \frac{n !}{( n - k )!} .

∎

Corollary 4.13 (Permutations of an $n$ -set). A set with $n$ elements has exactly $n!$ permutations.

Proof. A permutation uses all $n$ elements, so it is a $k$ -permutation with $k = n$ . The theorem The $k$ -permutation count gives $n! /0! = n!$ .∎

Intuition. The factorial grows faster than any exponential you are likely to meet: $10! \approx 3.6 \times 1 0^{6}$ , but $20! \approx 2.4 \times 1 0^{18}$ and $70!$ exceeds the number of atoms in the observable universe. This is precisely why brute-force search over all orderings — the naive travelling-salesman algorithm — is hopeless past about twelve cities, and why Combinatorics devotes a whole subject to smarter enumeration.

Example 4.14 (Ordered and unordered officers). A club of $12$ members elects a president, a secretary and a treasurer, no member holding two posts. In how many ways? And how many ways to choose three members to form an unranked steering group?

Solution.

The three posts are distinguishable, so an outcome is an ordered list of three distinct members: $P (12, 3) = 12 \cdot 11 \cdot 10 = 1320$ .
For the unranked group, each set of three members was counted once for each of its $3! = 6$ orderings in step 1, so the count is $1320/6 = 220$ . That division is the argument formalised in the theorem The combination formula.

□

Theorem 4.15 (Permutations with repeated objects). Suppose a multiset consists of $n$ objects of $r$ types, with $n_{1}$ copies of type $1$ , …, $n_{r}$ copies of type $r$ , where $n_{1} + \dots + n_{r} = n$ and copies of the same type are indistinguishable. The number of distinguishable arrangements in a row is

\frac{n !}{n _{1} ! n _{2} ! \dots n _{r} !} .

Proof. Temporarily label the copies of each type to make all $n$ objects distinct — write the three copies of a type as $x^{(1)}, x^{(2)}, x^{(3)}$ . The corollary Permutations of an $n$ -set says the labelled objects have $n!$ arrangements.

Now group the labelled arrangements by the unlabelled arrangement they produce when the superscripts are erased. Fix one unlabelled arrangement $w$ . Which labelled arrangements erase to $w$ ? Precisely those obtained from one of them by permuting the superscripts within each type independently, and by the theorem Product rule there are $n_{1}! n_{2}! \dots n_{r}!$ of these, a count that does not depend on $w$ .

So the $n!$ labelled arrangements fall into groups of equal size $n_{1}! \dots n_{r}!$ , one group per unlabelled arrangement, and the theorem Sum rule gives $n! = (number of unlabelled arrangements) \cdot n_{1}! \dots n_{r}!$ . Divide.∎

Example 4.16 (Arrangements of a word). How many distinguishable strings can be made from all the letters of $MISSISSIPPI$ ? How many of those begin with $M$ ?

Solution.

The word has $11$ letters: one $M$ , four $I$ , four $S$ , two $P$ . By the theorem Permutations with repeated objects the count is

\frac{11 !}{1 ! 4 ! 4 ! 2 !} = \frac{39916800}{1152} = 34650.

Fixing $M$ in position one leaves the multiset ${I^{4}, S^{4}, P^{2}}$ of $10$ letters to arrange, giving $10! / (4! 4! 2!) = 3150$ .
As a check, $M$ is equally likely to occupy any of the $11$ positions by symmetry, and indeed $34650/11 = 3150$ .

□

Example 4.17 (Lattice paths). A robot on a grid moves only right or up, from $(0, 0)$ to $(7, 4)$ , one unit per step. How many routes are there?

Solution.

Every route consists of exactly $7$ right-steps and $4$ up-steps in some order, and the route is determined by that order — so routes correspond bijectively to strings of seven $R$ s and four $U$ s.
By the theorem Permutations with repeated objects, the number of such strings is $\frac{11 !}{7 ! 4 !} = 330$ .

□

Remark. Circular arrangements need one adjustment: seating $n$ people around a round table, where only the cyclic order matters, gives $n! / n = (n - 1)!$ arrangements, because each cyclic arrangement corresponds to $n$ linear ones — one per choice of who is listed first. The same divide-by-the-overcount reasoning as in the theorem Permutations with repeated objects.

Exercises for §4.2 →

4.3Combinations

A permutation records which items were taken and in what order. Discard the order and you have a combination — a subset. Because the discarded information is the same amount for every selection, the count follows by dividing, and that single division is the most used formula in the subject.

Definition 4.18 (Binomial coefficient). For integers $0 \leq k \leq n$ , the binomial coefficient $(k n)$ , read " $n$ choose $k$ ", is the number of $k$ -element subsets of an $n$ -element set. For $k > n$ or $k < 0$ we set $(k n) = 0$ , since no such subset exists.

Theorem 4.19 (The combination formula). For $0 \leq k \leq n$ ,

(k n) = \frac{P ( n , k )}{k !} = \frac{n !}{k ! ( n - k )!} .

Proof. Count the $k$ -permutations of an $n$ -set $S$ in two ways.

Directly, the theorem The $k$ -permutation count gives $P (n, k)$ .

Alternatively, build a $k$ -permutation in two steps: first choose the set of $k$ elements that will appear, then choose the order in which to list them. There are $(k n)$ ways to do the first step by definition, and whichever set is chosen, the corollary Permutations of an $n$ -set gives exactly $k!$ orders — a number independent of the set chosen, which is what the theorem Product rule requires. Distinct pairs (set, order) give distinct lists, and every list arises this way, so the count is $(k n) \cdot k!$ .

Equating the two counts, $(k n) k! = P (n, k)$ , and dividing by $k! \neq = 0$ gives $(k n) = P (n, k) / k! = n! / (k! (n - k)!)$ .∎

Pitfall. The formula divides by $k!$ because every $k$ -subset is overcounted by exactly the same factor $k!$ . Division is legitimate only when the overcounting is uniform. If you try the same move on arrangements of $AAB$ by writing $3! /2$ , you are lucky; on a problem where different objects are overcounted different numbers of times, dividing gives a non-integer and a wrong answer. When in doubt, partition into classes of equal size and divide inside each class, as the theorem Permutations with repeated objects does.

Proposition 4.20 (Symmetry). For $0 \leq k \leq n$ , $(k n) = (n - k n)$ .

Proof. Let $S$ be an $n$ -set and let $A$ be its family of $k$ -subsets, $B$ its family of $(n - k)$ -subsets. Define $c : A \to B$ by complementation, $c (T) = S ∖ T$ . This lands in $B$ because $∣ S ∖ T ∣ = n - k$ .

It is a bijection because it is its own inverse: $c (c (T)) = S ∖ (S ∖ T) = T$ for every $T \subseteq S$ . A map with a two-sided inverse is a bijection, so $∣ A ∣ = ∣ B ∣$ .∎

Intuition. Choosing which $k$ of $n$ features to enable is the same act as choosing which $n - k$ to disable. Symmetry also says where the work is: to compute $(97 100)$ , compute $(3 100) = 161700$ instead — three multiplications rather than ninety-seven.

Example 4.21 (Committees with constraints). From $7$ developers and $5$ designers, how many teams of $4$ contain at least one designer?

Solution.

All teams of $4$ from the $12$ people: $(4 12) = 495$ .
Teams with no designer are teams of $4$ chosen from the $7$ developers: $(4 7) = 35$ .
By the complement trick, teams with at least one designer number $495 - 35 = 460$ .
The direct route confirms it: $(1 5) (3 7) + (2 5) (2 7) + (3 5) (1 7) + (4 5) (0 7) = 175 + 210 + 70 + 5 = 460$ .

□

Example 4.22 (Bit strings with a fixed weight). How many bit strings of length $16$ contain exactly $5$ ones? How many contain at most $2$ ones?

Solution.

A string is determined by the set of positions carrying a one, so strings of weight $5$ correspond bijectively to $5$ -subsets of $[16]$ : $(5 16) = 4368$ .
"At most two" splits into three disjoint cases by the theorem Sum rule: $(0 16) + (1 16) + (2 16) = 1 + 16 + 120 = 137$ .

□

Sometimes the items being selected may be taken more than once — three coffees of four available kinds, or ten identical background jobs assigned to four servers. Order still does not matter; only how many of each kind were taken. The count is again a binomial coefficient, and the reason is a bijection worth seeing in full.

Theorem 4.23 (Combinations with repetition (stars and bars)). The number of ways to choose $k$ items from $n$ types, with repetition allowed and order irrelevant, is

(k n + k - 1) .

Equivalently, this is the number of solutions in non-negative integers of $x_{1} + x_{2} + \dots + x_{n} = k$ .

Proof. A selection is recorded by the multiplicities $(x_{1}, \dots, x_{n})$ , where $x_{i} \geq 0$ counts the copies taken of type $i$ ; two selections are the same exactly when their multiplicity vectors agree, and the total is $\sum_{i} x_{i} = k$ . So the two statements count the same set $X$ of solutions.

Let $W$ be the set of strings of length $n + k - 1$ over ${⋆, ∣}$ containing exactly $k$ stars and $n - 1$ bars. Define $Φ : X \to W$ by sending $(x_{1}, \dots, x_{n})$ to

x_{1} ⋆ \dots ⋆ ∣ x_{2} ⋆ \dots ⋆ ∣ \dots ∣ x_{n} ⋆ \dots ⋆,

that is, $x_{1}$ stars, a bar, $x_{2}$ stars, a bar, and so on, ending with $x_{n}$ stars. The string has $\sum_{i} x_{i} = k$ stars and exactly $n - 1$ bars, so $Φ (x) \in W$ .

$Φ$ is injective: from the string one recovers $x_{i}$ as the number of stars strictly between bar $i - 1$ and bar $i$ (with the ends of the string playing the role of bar $0$ and bar $n$ ). Two distinct vectors differ in some $x_{i}$ , hence the strings differ in that block.

$Φ$ is surjective: given any $w \in W$ , the $n - 1$ bars cut $w$ into $n$ blocks of stars; let $x_{i}$ be the length of block $i$ . Each $x_{i} \geq 0$ , the total is the number of stars, which is $k$ , so $(x_{1}, \dots, x_{n}) \in X$ , and applying $Φ$ to it rebuilds $w$ block by block.

Hence $∣ X ∣ = ∣ W ∣$ . Finally, a string in $W$ is determined by which $k$ of its $n + k - 1$ positions hold stars, so $∣ W ∣ = (k n + k - 1)$ by the definition Binomial coefficient.∎

Figure 4.24. Stars and bars: one arrangement of

k = 7

stars and

n - 1 = 3

bars encodes one solution of

x_{1} + x_{2} + x_{3} + x_{4} = 7

Example 4.25 (Distributing identical jobs). Ten identical background jobs are assigned to four distinct servers. How many assignments are there? How many give every server at least one job?

Solution.

An assignment is a solution of $x_{1} + x_{2} + x_{3} + x_{4} = 10$ in non-negative integers, so the theorem Combinations with repetition (stars and bars) gives $(10 10 + 4 - 1) = (10 13) = (3 13) = 286$ .
For "at least one each", set $y_{i} = x_{i} - 1 \geq 0$ . Then $y_{1} + y_{2} + y_{3} + y_{4} = 6$ , and $x \mapsto y$ is a bijection between the two solution sets. So the count is $(6 6 + 4 - 1) = (6 9) = (3 9) = 84$ .

□

Pitfall. Identical objects into distinct boxes is stars and bars; distinct objects into distinct boxes is the theorem Counting functions, giving $4^{10} = 1048576$ instead of $286$ . Ask first whether swapping two of the objects changes the outcome. Identical objects into identical boxes is a harder problem — the partition function — and belongs to the subject Combinatorics.

Exercises for §4.3 →

4.4Binomial Coefficients and the Binomial Theorem

The numbers $(k n)$ satisfy a dense web of identities. Each can be proved by manipulating factorials, and each can also be proved by counting one set in two different ways — a double counting or combinatorial proof. The second kind is preferred here, and not only for elegance: an algebraic proof verifies that two expressions agree, while a combinatorial proof explains why they agree, and the explanation generalises where the algebra does not.

Theorem 4.26 (Pascal's identity). For $1 \leq k \leq n - 1$ ,

(k n) = (k - 1 n - 1) + (k n - 1) .

Proof. Let $S$ be a set of $n$ elements and distinguish one of them, say $s \in S$ ; write $S^{'} = S ∖ {s}$ , so $∣ S^{'} ∣ = n - 1$ . The left side counts the $k$ -subsets of $S$ .

Partition those $k$ -subsets by whether they contain $s$ .

Subsets containing $s$ . Such a subset is ${s} \cup T$ where $T$ is a $(k - 1)$ -subset of $S^{'}$ , and distinct $T$ give distinct subsets, while every subset containing $s$ arises from exactly one $T$ , namely $T = (the subset) ∖ {s}$ . So there are $(k - 1 n - 1)$ of them.

Subsets not containing $s$ . Such a subset is exactly a $k$ -subset of $S^{'}$ , so there are $(k n - 1)$ of them.

The two classes are disjoint and together are all $k$ -subsets of $S$ , so the theorem Sum rule gives the identity.∎

Remark. The algebraic proof is available too, and is worth doing once to see how much less it tells you. With $1 \leq k \leq n - 1$ ,

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

using $\frac{1}{( k - 1 )!} = \frac{k}{k !}$ and $\frac{1}{( n - k - 1 )!} = \frac{n - k}{( n - k )!}$ to put the two fractions over a common denominator. Correct, but it does not mention the distinguished element $s$ , and it is the distinguished element that makes the identity memorable and transplantable.

Pascal's identity is a recurrence, so the whole table of binomial coefficients can be built from the boundary values $(0 n) = (n n) = 1$ by additions alone — no factorials, no division, no overflow from intermediate values that dwarf the answer. That table is Pascal's triangle.

Figure 4.27. Pascal's triangle. Each entry is the sum of the two above it, which is Pascal's identity read downwards.

Example 4.28 (Building a row by addition). Use Pascal's identity to extend the triangle to the row $n = 6$ , and read off $(2 6)$ .

Solution.

Row $5$ is $1, 5, 10, 10, 5, 1$ .
Each interior entry of row $6$ is the sum of its two neighbours above: $1, 1 + 5, 5 + 10, 10 + 10, 10 + 5, 5 + 1, 1$ , giving $1, 6, 15, 20, 15, 6, 1$ .
So $(2 6) = 15$ , which matches $\frac{6 !}{2 ! 4 !} = 15$ .

□

Theorem 4.29 (Binomial theorem). For any numbers $x, y$ and any integer $n \geq 0$ ,

(x + y)^{n} = k = 0 \sum n (k n) x^{k} y^{n - k} .

Proof. Write the power as a product of $n$ identical factors:

(x + y)^{n} = n factors (x + y) (x + y) \dots (x + y) .

Expanding by distributivity without collecting terms means: from each factor choose either the $x$ or the $y$ , multiply the $n$ chosen symbols, and sum over all choices. By the theorem Counting functions there are $2^{n}$ such choices, and each contributes one term.

A choice is determined by the set of factors from which $x$ was taken. If that set has size $k$ , the term is $x^{k} y^{n - k}$ , since the other $n - k$ factors contributed a $y$ . So the terms equal to $x^{k} y^{n - k}$ are in bijection with the $k$ -subsets of the $n$ factors, of which there are $(k n)$ by the definition Binomial coefficient.

Grouping the $2^{n}$ terms by the value of $k$ — a partition, so the theorem Sum rule applies — the coefficient of $x^{k} y^{n - k}$ is $(k n)$ , and $k$ ranges over $0, 1, \dots, n$ .∎

Example 4.30 (Extracting one coefficient). Find the coefficient of $x^{5}$ in $(2 x - 3)^{8}$ .

Solution.

Apply the theorem Binomial theorem with the two summands $2 x$ and $- 3$ : $(2 x - 3)^{8} = \sum_{k = 0}^{8} (k 8) (2 x)^{k} (- 3)^{8 - k}$ .
The term with $x^{5}$ is $k = 5$ : $(5 8) 2^{5} x^{5} (- 3)^{3}$ .
Compute: $(5 8) = 56$ , $2^{5} = 32$ , $(- 3)^{3} = - 27$ , so the coefficient is $56 \cdot 32 \cdot (- 27) = - 48384$ .

□

Corollary 4.31 (Row sums). For every $n \geq 0$ ,

k = 0 \sum n (k n) = 2^{n}, and for n \geq 1, k = 0 \sum n (- 1)^{k} (k n) = 0.

Proof. First identity, algebraically. Put $x = y = 1$ in the theorem Binomial theorem: the left side is $2^{n}$ and the right side is $\sum_{k} (k n)$ .

First identity, combinatorially. Count the subsets of an $n$ -set in two ways. The corollary Strings and subsets gives $2^{n}$ . Alternatively, partition the subsets by their size $k$ ; the class of size $k$ has $(k n)$ members by the definition Binomial coefficient, and $k$ ranges over $0$ to $n$ , so the theorem Sum rule gives $\sum_{k} (k n)$ . The two counts must agree.

Second identity. Put $x = - 1$ , $y = 1$ in the theorem Binomial theorem: the left side is $(- 1 + 1)^{n} = 0$ for $n \geq 1$ , and the right side is $\sum_{k} (- 1)^{k} (k n)$ .∎

Intuition. The second identity says an $n$ -set has as many even-sized subsets as odd-sized ones, for $n \geq 1$ . There is a bijection that proves it directly: fix an element $s$ and toggle it — add $s$ if absent, remove it if present. This changes the size by one, hence changes its parity, and applying it twice returns the original set, so it is a bijection between the even and odd families.

Theorem 4.32 (Vandermonde's identity). For non-negative integers $m, n, k$ ,

(k m + n) = j = 0 \sum k (j m) (k - j n) .

Proof. Let $A$ be a set of $m$ elements and $B$ a disjoint set of $n$ elements, so $∣ A \cup B ∣ = m + n$ by the theorem Sum rule. Count the $k$ -subsets of $A \cup B$ in two ways.

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

Alternatively, partition them by $j = ∣ T \cap A ∣$ , the number of chosen elements coming from $A$ ; then $∣ T \cap B ∣ = k - j$ . For a fixed $j$ , such a $T$ is determined by a $j$ -subset of $A$ together with a $(k - j)$ -subset of $B$ , freely and independently chosen, so the theorem Product rule gives $(j m) (k - j n)$ such subsets. Since $j$ can be anything from $0$ to $k$ (terms where $j > m$ or $k - j > n$ contribute $0$ by the convention in the definition Binomial coefficient), the theorem Sum rule gives the sum.∎

Corollary 4.33 (Sum of squares of a row). For every $n \geq 0$ , $j = 0 \sum n (j n)^{2} = (n 2 n)$ .

Proof. Take $m = n$ and $k = n$ in the theorem Vandermonde's identity: $(n 2 n) = \sum_{j = 0}^{n} (j n) (n - j n)$ . By the proposition Symmetry, $(n - j n) = (j n)$ , so each summand is $(j n)^{2}$ .∎

Theorem 4.34 (Hockey-stick identity). For integers $0 \leq r \leq n$ ,

i = r \sum n (r i) = (r + 1 n + 1) .

Proof. Count the $(r + 1)$ -subsets of ${1, 2, \dots, n + 1}$ by conditioning on their largest element.

If the largest element is $m$ , the remaining $r$ elements form an $r$ -subset of ${1, \dots, m - 1}$ , and conversely any such $r$ -subset together with $m$ gives an $(r + 1)$ -subset with largest element $m$ . So there are $(r m - 1)$ subsets with largest element $m$ .

The largest element is at least $r + 1$ (there must be $r$ smaller elements available) and at most $n + 1$ . These classes are disjoint and exhaust the $(r + 1)$ -subsets, so the theorem Sum rule gives

(r + 1 n + 1) = m = r + 1 \sum n + 1 (r m - 1) = i = r \sum n (r i)

after substituting $i = m - 1$ .∎

Remark. The name comes from the picture: the terms $(r r), (r r + 1), \dots, (r n)$ lie along a diagonal of Pascal's triangle and the answer $(r + 1 n + 1)$ sits just off the end of it, so the shaded cells look like a hockey stick. With $r = 1$ it reads $1 + 2 + \dots + n = (2 n + 1) = \frac{n ( n + 1 )}{2}$ , the schoolbook sum.

Example 4.35 (Summing a diagonal). Evaluate $(3 3) + (3 4) + (3 5) + (3 6) + (3 7)$ .

Solution.

This is the theorem Hockey-stick identity with $r = 3$ and $n = 7$ , so the sum is $(4 8)$ .
$(4 8) = 70$ .
Check term by term: $1 + 4 + 10 + 20 + 35 = 70$ .

□

Example 4.36 (Counting comparisons in a double loop). A program runs for i in 1..n: for j in i+1..n: and does one comparison in the body. How many comparisons are made?

Solution.

The body runs once for each pair $(i, j)$ with $1 \leq i < j \leq n$ — that is, once for each $2$ -element subset of $[n]$ , since a set ${i, j}$ determines the ordered pair with $i < j$ uniquely.
So the count is $(2 n) = \frac{n ( n - 1 )}{2}$ , the familiar quadratic cost of a naive all-pairs scan.

□

Exercises for §4.4 →

4.5The Pigeonhole Principle

So far counting has answered "how many?". The pigeonhole principle turns counting into a tool for proving that something exists, without producing it. It is almost insultingly obvious in statement, and the skill it demands lies entirely in choosing what the pigeons are and what the holes are.

Theorem 4.37 (Pigeonhole principle). If $n + 1$ or more objects are placed into $n$ boxes, then some box contains at least two objects. Equivalently: if $∣ A ∣ > ∣ B ∣$ then no function $f : A \to B$ is injective.

Proof. Suppose, for contradiction, that every box contains at most one object. Let $B_{1}, \dots, B_{n}$ be the sets of objects in each box. These are pairwise disjoint and their union is the whole collection, so the theorem Sum rule gives

number of objects = ∣ B_{1} ∣ + \dots + ∣ B_{n} ∣ \leq n 1 + 1 + \dots + 1 = n .

That contradicts there being at least $n + 1$ objects. Hence some box holds two or more.

For the restatement, take the boxes to be the elements of $B$ and place each $a \in A$ into box $f (a)$ . A box with two objects is a pair $a \neq = a^{'}$ with $f (a) = f (a^{'})$ , which is a failure of injectivity.∎

Theorem 4.38 (Generalised pigeonhole principle). If $N$ objects are placed into $n$ boxes, then some box contains at least $⌈ N / n ⌉$ objects.

Proof. Suppose every box held at most $⌈ N / n ⌉ - 1$ objects. Summing over the boxes as in the theorem Pigeonhole principle,

N \leq n (⌈ \frac{N}{n} ⌉ - 1) < n ((\frac{N}{n} + 1) - 1) = N,

using the bound $⌈ x ⌉ < x + 1$ . This gives $N < N$ , a contradiction.∎

Example 4.39 (Shared birth months). A lecture hall holds $100$ students. What is the largest $m$ for which you can guarantee that $m$ of them share a birth month?

Solution.

Take the students as objects and the $12$ months as boxes.
The theorem Generalised pigeonhole principle gives a month shared by at least $⌈ 100/12 ⌉ = ⌈ 8.33 ⌉ = 9$ students.
No better guarantee is possible: four months with $9$ students and eight with $8$ totals $36 + 64 = 100$ with no month exceeding $9$ . So $m = 9$ .

□

Pitfall. The principle guarantees existence, never location. It says some month is shared by nine students; it does not say which, and it gives no way to find it short of looking. This is the price of an argument that never examines the objects.

The next two results are the reason the principle is worth a name. In each, the difficulty is entirely in inventing the boxes.

Proposition 4.40 (Two people with the same number of friends). At any gathering of $n \geq 2$ people, where friendship is mutual and nobody is their own friend, two people have exactly the same number of friends present.

Proof. Assign to each person the number of friends they have at the gathering. Each such number lies in ${0, 1, \dots, n - 1}$ , which is $n$ possible values for $n$ people — not yet a pigeonhole.

But the values $0$ and $n - 1$ cannot both occur. A person with $n - 1$ friends is a friend of everybody else present, so nobody present has $0$ friends; conversely a person with $0$ friends is nobody's friend, so nobody has $n - 1$ . Hence the friend counts actually lie in one of the two sets ${0, 1, \dots, n - 2}$ or ${1, 2, \dots, n - 1}$ , each of size $n - 1$ .

Now $n$ people are assigned values from a set of $n - 1$ values, so the theorem Pigeonhole principle gives two people with the same count.∎

Proposition 4.41 (Coprime pairs among n+1 integers). Let $n \geq 1$ and choose any $n + 1$ distinct integers from ${1, 2, \dots, 2 n}$ . Then two of the chosen integers are coprime.

Proof. Partition ${1, \dots, 2 n}$ into the $n$ consecutive pairs

{1, 2}, {3, 4}, {5, 6}, \dots, {2 n - 1, 2 n},

and take these as the boxes, placing each chosen integer into the box containing it. With $n + 1$ chosen integers and $n$ boxes, the theorem Pigeonhole principle puts two chosen integers in the same box.

Two integers in the same box are consecutive, say $m$ and $m + 1$ . Any common divisor $d$ of $m$ and $m + 1$ divides their difference $(m + 1) - m = 1$ , so $d = 1$ and the two are coprime.∎

Remark. The same ${1, \dots, 2 n}$ set with $n + 1$ choices yields a second gem by a different choice of box: write each chosen integer as $2^{a} q$ with $q$ odd. There are only $n$ odd numbers available in ${1, \dots, 2 n}$ , so two chosen integers share the same odd part $q$ , say $2^{a} q$ and $2^{b} q$ with $a < b$ — and then the first divides the second. Both statements are sharp: the set ${2, 4, 6, \dots, 2 n}$ of size $n$ contains no coprime pair, so $n + 1$ choices really are needed.

Example 4.42 (Sock drawer and a stronger guarantee). A drawer holds socks of $4$ colours, mixed at random in the dark. How many socks must be drawn to guarantee a matching pair? To guarantee three of one colour?

Solution.

Four socks might be four different colours, so four is not enough; with $5$ socks and $4$ colours the theorem Pigeonhole principle forces a repeated colour. The answer is $5$ .
For three of one colour, $8$ socks might be two of each colour. With $N = 9$ the theorem Generalised pigeonhole principle gives a colour used at least $⌈ 9/4 ⌉ = 3$ times. The answer is $9$ .
The pattern: to force $m$ of one of $c$ types, draw $c (m - 1) + 1$ .

□

Exercises for §4.5 →

4.6Inclusion-Exclusion Principle

The theorem Sum rule needs disjointness. When the sets overlap, adding their sizes counts each overlap more than once, and inclusion–exclusion is the exact correction: add the sets, subtract the pairwise intersections, add back the triples, and so on in alternating signs.

Theorem 4.43 (Inclusion-exclusion for two sets). For finite sets $A$ and $B$ ,

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

Proof. Split $A \cup B$ into three pairwise disjoint pieces: $A ∖ B$ , $B ∖ A$ , and $A \cap B$ . Every element of the union lies in exactly one of them, according to whether it belongs to $A$ only, to $B$ only, or to both, so the theorem 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,

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

∎

Figure 4.44. Two overlapping sets. Adding

∣ A ∣ = 47

and

∣ B ∣ = 40

counts the

12

elements of the overlap twice, so one copy is subtracted.

Example 4.45 (Divisible by 3 or by 5). How many integers in ${1, 2, \dots, 1000}$ are divisible by $3$ or by $5$ ?

Solution.

Let $A$ be the multiples of $3$ and $B$ the multiples of $5$ . Then $∣ A ∣ = ⌊ 1000/3 ⌋ = 333$ and $∣ B ∣ = ⌊ 1000/5 ⌋ = 200$ .
An integer lies in $A \cap B$ exactly when it is divisible by $15$ , so $∣ A \cap B ∣ = ⌊ 1000/15 ⌋ = 66$ .
By the theorem Inclusion-exclusion for two sets, $∣ A \cup B ∣ = 333 + 200 - 66 = 467$ .

□

Theorem 4.46 (Inclusion-exclusion for 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 theorem Inclusion-exclusion for two sets to the two sets $A \cup B$ and $C$ :

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

Expand the first term by the same theorem: $∣ 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 applying the two-set theorem once more,

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

Substituting both expansions and collecting signs gives the stated formula.∎

Example 4.47 (Three-language survey). Of $200$ students, $120$ know Python, $90$ know Java, $70$ know C; $50$ know Python and Java, $40$ Python and C, $30$ Java and C, and $20$ know all three. How many know none of the three?

Solution.

By the theorem Inclusion-exclusion for three sets, the number knowing at least one is

120 + 90 + 70 - 50 - 40 - 30 + 20 = 180.

The remaining students know none, so the answer is $200 - 180 = 20$ .
Sanity check on the innermost regions: all three, $20$ ; exactly Python and Java, $50 - 20 = 30$ ; exactly Python and C, $20$ ; exactly Java and C, $10$ ; Python only, $120 - 30 - 20 - 20 = 50$ ; Java only, $90 - 30 - 10 - 20 = 30$ ; C only, $70 - 20 - 10 - 20 = 20$ . These seven disjoint regions total $180$ .

□

Theorem 4.48 (Inclusion-exclusion, general form). For finite sets $A_{1}, \dots, A_{n}$ ,

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

Proof. Both sides count elements of the union, so it suffices to show that each element $x$ of the union contributes the same amount to each side.

Fix $x \in ⋃_{i} A_{i}$ and let $m \geq 1$ be the number of indices $i$ with $x \in A_{i}$ ; write $M \subseteq [n]$ for that set of indices, so $∣ M ∣ = m$ . On the left, $x$ contributes exactly $1$ .

On the right, $x$ is counted by the term for $J$ precisely when $x \in ⋂_{i \in J} A_{i}$ , which happens exactly when $J \subseteq M$ . The non-empty subsets $J \subseteq M$ of size $j$ number $(j m)$ by the definition Binomial coefficient, and each contributes $(- 1)^{j + 1}$ . So the total contribution of $x$ to the right side is

j = 1 \sum m (- 1)^{j + 1} (j m) = - j = 1 \sum m (- 1)^{j} (j m) = - (j = 0 \sum m (- 1)^{j} (j m) - 1) = - (0 - 1) = 1,

where the alternating sum vanishes by the corollary Row sums, valid since $m \geq 1$ .

Every element of the union therefore contributes $1$ to each side, and elements outside the union contribute $0$ to both, so the two sides are equal.∎

Corollary 4.49 (Counting derangements). Let $D_{n}$ be the number of permutations of $[n]$ with no fixed point — no element mapped to itself. Then

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

Proof. Let $A_{i}$ be the set of permutations fixing $i$ . A permutation has some fixed point exactly when it lies in $A_{1} \cup \dots \cup A_{n}$ , so $D_{n} = n! - ∣ A_{1} \cup \dots \cup A_{n} ∣$ .

For $J \subseteq [n]$ with $∣ J ∣ = j \geq 1$ , a permutation in $⋂_{i \in J} A_{i}$ fixes every element of $J$ and permutes the remaining $n - j$ elements arbitrarily, so $⋂_{i \in J} A_{i} = (n - j)!$ by the corollary Permutations of an $n$ -set. There are $(j n)$ such $J$ , so the theorem Inclusion-exclusion, general form gives

∣ A_{1} \cup \dots \cup A_{n} ∣ = j = 1 \sum n (- 1)^{j + 1} (j n) (n - j)! = j = 1 \sum n (- 1)^{j + 1} \frac{n !}{j !} .

Therefore

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

the last step absorbing $n! = n! \cdot \frac{( - 1 ) ^{0}}{0 !}$ into the sum.∎

Intuition. The sum is the truncated series for $e^{- 1}$ , so $D_{n} / n! \to 1/ e \approx 0.3679$ very fast — already correct to four decimals at $n = 7$ . Shuffle a deck of any size and hand the cards back to their owners at random: the chance that nobody gets their own card is essentially $37%$ , independent of the number of people.

Example 4.50 (A derangement count). Five students hand in five assignments, which are then returned at random, one to each student. In how many ways does nobody get their own back?

Solution.

This is $D_{5}$ . By the corollary Counting derangements, $D_{5} = 5! (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120})$ .
The bracket is $\frac{60 - 20 + 5 - 1}{120} = \frac{44}{120}$ , so $D_{5} = 120 \cdot \frac{44}{120} = 44$ .
So $44$ of the $120$ possible returns are deranged, a fraction $0.3667$ , already close to $1/ e$ .

□

Example 4.51 (Counting surjections). How many functions from a $5$ -element set onto a $3$ -element set are surjective?

Solution.

Let $A_{i}$ be the functions missing the $i$ -th target value. A function fails to be surjective exactly when it lies in $A_{1} \cup A_{2} \cup A_{3}$ .
A function avoiding a fixed set of $j$ targets maps into the remaining $3 - j$ values, so by the theorem Counting functions there are $(3 - j)^{5}$ of them, and there are $(j 3)$ such index sets.
The theorem Inclusion-exclusion, general form gives $∣ A_{1} \cup A_{2} \cup A_{3} ∣ = 3 \cdot 2^{5} - 3 \cdot 1^{5} + 1 \cdot 0^{5} = 96 - 3 = 93$ .
Total functions: $3^{5} = 243$ . Surjections: $243 - 93 = 150$ .

□

Remark. The same computation in general gives the number of surjections from an $n$ -set onto a $k$ -set as $\sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}$ , and dividing by $k!$ gives the Stirling number of the second kind — the count of ways to partition an $n$ -set into $k$ unlabelled non-empty blocks. Those numbers, and the generating functions that tame them, belong to the subject Combinatorics.

Exercises for §4.6 →

Common Mistakes

Applying the sum rule to overlapping cases. "Divisible by $3$ or by $5$ " is not $333 + 200$ . If the cases can both happen, either make them disjoint by conditioning, or use the theorem Inclusion-exclusion for two sets.
Applying the product rule when the option count varies. If the number of choices at step two depends on what happened at step one, split into cases first and multiply inside each case. A product of averages is not a count.
Confusing ordered with unordered. "President, secretary, treasurer" is $P (12, 3)$ ; "three-member committee" is $(3 12)$ . The tell is whether swapping two chosen items gives a different outcome.
Dividing away a non-uniform overcount. Dividing by $k!$ is legitimate only when every outcome was produced exactly $k!$ times. When different outcomes are overcounted different numbers of times, the division is meaningless — and a non-integer answer is the symptom.
Confusing $n^{k}$ with $(k n + k - 1)$ . Distinct objects into distinct boxes is the theorem Counting functions; identical objects into distinct boxes is the theorem Combinations with repetition (stars and bars). Ask whether swapping two objects changes anything.
Forgetting the complement trick. "At least one" almost always means total minus none. Summing over exactly one, exactly two, … is correct but invites arithmetic slips.
Double-counting in stars and bars. The bars are indistinguishable from one another and so are the stars; what is distinguishable is the positions. If you find yourself multiplying by $(n - 1)!$ to order the bars, you have left the bijection.
Reading the pigeonhole principle as a construction. It proves a box with two objects exists; it never says which box, and no amount of restating it will produce one.
Off-by-one in pigeonhole thresholds. To force $m$ objects in one of $c$ boxes you need $c (m - 1) + 1$ objects, not $c m$ . Always check the extremal arrangement that just fails.
Misusing $0! = 1$ . It is not a special case to be worked around; formulas like $(0 n) = 1$ and $P (n, n) = n! /0!$ depend on it. Writing $0! = 0$ makes $(n n)$ undefined.

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