Contents / Combinatorics / Basic Counting

Chapter 1

Basic Counting

Permutations, combinations and the binomial coefficients, with the identities that follow and the models they each apply to.

Introduction

Permutations, combinations and the binomial coefficients, with the identities that follow and the models they each apply to.

1.1Counting as a Bijection

Counting a finite set means comparing it with a standard set. That comparison is the primitive notion from which everything else in this chapter is derived, so we start there rather than with formulas.

Notation (The standard finite sets). For a positive integer $n$ write $[n] = {1, 2, \dots, n}$ , and $[0] = \emptyset$ . For a finite set $S$ , $∣ S ∣$ denotes its cardinality: the unique $n$ for which a bijection $[n] \to S$ exists.

Definition 1.1 (Enumerative combinatorics). Enumerative combinatorics is the study of the cardinalities of finite sets that are specified by a description rather than by a list — typically a family $S_{0}, S_{1}, S_{2}, \dots$ indexed by a parameter, whose cardinality $∣ S_{n} ∣$ is sought as a formula, a recurrence, or an asymptotic in $n$ .

That "unique $n$ " in the notation box deserves a word: it is a theorem, not a convention, that no bijection $[m] \to [n]$ exists when $m \neq = n$ (the pigeonhole principle in its cleanest form). We take it as known. What we will use constantly is its companion, which turns every counting problem into a search for a bijection.

Theorem 1.2 (Bijection principle). Let $S$ and $T$ be finite sets. If there is a bijection $f : S \to T$ , then $∣ S ∣ = ∣ T ∣$ .

Proof. Let $n = ∣ T ∣$ , so there is a bijection $g : [n] \to T$ . Then $g^{- 1} \circ f : S \to [n]$ is a composition of bijections, hence a bijection, and so is its inverse $f^{- 1} \circ g : [n] \to S$ . Therefore $∣ S ∣ = n = ∣ T ∣$ .∎

The principle is trivial to prove and is the most powerful tool in the chapter. Every identity established below — the formula for $(k n)$ , stars and bars, Pascal's rule, Vandermonde's identity — is ultimately an instance of it: two descriptions of the same collection of objects, matched up one for one.

Intuition. To count the seats in a full theatre you do not count seats; you count the people, because "sit in a seat" is a bijection. Combinatorics is the discipline of noticing which map is the bijection.

The trick is that the easy side is not always the side the problem hands you. A good bijection replaces "arrangements of letters with these constraints" by "binary strings", or "committees with a designated chair" by "chairs with a committee around them", and the new description is one you already know how to count.

There is one more counting move that is not a bijection but a controlled failure of one. It appears whenever a symmetry makes several distinct-looking constructions produce the same object.

Theorem 1.3 (Division principle). Let $f : S \to T$ be a surjection between finite sets such that every fibre has the same size $d \geq 1$ , that is $∣ f^{- 1} (t) ∣ = d$ for every $t \in T$ . Then

∣ T ∣ = \frac{∣ S ∣}{d} .

Proof. The fibres $f^{- 1} (t)$ , for $t \in T$ , are pairwise disjoint (a point of $S$ has exactly one image) and their union is $S$ (every point has an image). So $∣ S ∣ = \sum_{t \in T} ∣ f^{- 1} (t) ∣ = \sum_{t \in T} d = d ∣ T ∣$ . Divide by $d$ .∎

This is sometimes called the shepherd's principle: to count sheep, count legs and divide by four. It is exactly what licenses "divide by $k!$ because order does not matter" and "divide by $n$ because rotations of a circle give the same arrangement" — two steps often performed on faith. They are not faith; they are the division principle, and they are valid precisely when every object is over-counted the same number of times.

Pitfall. The division principle fails silently when the fibres have different sizes. Counting the distinct arrangements of the letters of LEVEL as $5! /2!$ is wrong: $5!$ counts arrangements of five labelled letters, and the correct divisor must account for both the two L's and the two E's, giving $5! / (2! 2!) = 30$ . Likewise, counting bracelets by dividing $n!$ by $2 n$ is wrong in general, because an arrangement fixed by a reflection is over-counted fewer than $2 n$ times. When a symmetry can fix an object, naive division is invalid and one needs Burnside's lemma instead — a result beyond this chapter, resting on the orbit–stabiliser theorem from group theory.

Example 1.4 (Two descriptions of the same set). Show that the number of subsets of $[n]$ equals the number of binary strings of length $n$ , without computing either.

Solution. Define $f$ from subsets of $[n]$ to strings in ${0, 1}^{n}$ by sending $A \subseteq [n]$ to its indicator string $f (A) = (a_{1}, \dots, a_{n})$ with $a_{i} = 1$ if $i \in A$ and $a_{i} = 0$ otherwise.

$f$ is injective: if $f (A) = f (B)$ then for every $i$ we have $i \in A ⟺ a_{i} = 1 ⟺ i \in B$ , so $A = B$ . It is surjective: given a string $(a_{1}, \dots, a_{n})$ , the set $A = {i : a_{i} = 1}$ has $f (A)$ equal to that string.

So $f$ is a bijection and the two counts agree by the bijection principle. We have not yet computed either one — that comes from the product rule in the next section, and gives $2^{n}$ . The point is the shape of the argument: define the map, check injective, check surjective, invoke the principle. Every bijective proof in this chapter has that skeleton.□

Example 1.5 (Counting by over-counting). A round table has $6$ seats and $6$ distinct guests. Two seatings are the same if one is a rotation of the other. Count the seatings using the division principle explicitly.

Solution. Let $S$ be the set of the $6! = 720$ ways to place the guests in six labelled chairs, let $T$ be the set of seatings-up-to-rotation, and let $f : S \to T$ send a labelled placement to its rotation class.

Every class contains exactly $6$ labelled placements: rotating a placement by $0, 1, \dots, 5$ positions gives six labelled placements, and they are distinct because a nontrivial rotation moves every guest to a different chair. So each fibre has size $d = 6$ , and $f$ is onto by construction. Hence

∣ T ∣ = \frac{720}{6} = 120 = 5! .

Sanity check: equivalently, fix one guest in a reference chair to remove the rotational freedom and arrange the other five, giving $5! = 120$ . The two routes agree, as they must.□

Exercises for §1.1 →

1.2The Four Counting Rules

Every elementary count is assembled from a small number of rules. Two of them are structural (sum and product), one is the division principle already proved, and one repairs the sum rule when the cases overlap. The trigger words are OR (disjoint alternatives → add) versus AND THEN (successive choices → multiply).

Theorem 1.6 (Addition rule). Let $A_{1}, \dots, A_{m}$ be pairwise disjoint finite sets, i.e. $A_{i} \cap A_{j} = \emptyset$ whenever $i \neq = j$ . Then

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

Proof. It suffices to do $m = 2$ ; the general case follows by induction on $m$ , since $A_{1} \cup \dots \cup A_{m} = (A_{1} \cup \dots \cup A_{m - 1}) \cup A_{m}$ and the first bracket is disjoint from $A_{m}$ . For $m = 2$ , let $g : [a] \to A_{1}$ and $h : [b] \to A_{2}$ be bijections, where $a = ∣ A_{1} ∣$ and $b = ∣ A_{2} ∣$ . Define $F : [a + b] \to A_{1} \cup A_{2}$ by $F (i) = g (i)$ for $i \leq a$ and $F (i) = h (i - a)$ for $i > a$ . Injectivity uses disjointness (an element of $A_{1}$ is never an element of $A_{2}$ ), surjectivity is clear, so $F$ is a bijection and $∣ A_{1} \cup A_{2} ∣ = a + b$ .∎

Theorem 1.7 (Product rule). For finite sets $A_{1}, \dots, A_{m}$ ,

∣ A_{1} \times A_{2} \times \dots \times A_{m} ∣ = ∣ A_{1} ∣ \cdot ∣ A_{2} ∣ \dots ∣ A_{m} ∣.

Equivalently, in process form: if an object is built by $m$ successive choices, and for every way of making the first $i - 1$ choices there are exactly $n_{i}$ options for the $i$ -th choice, then the number of objects is $n_{1} n_{2} \dots n_{m}$ .

Proof. Again it suffices to treat $m = 2$ and induct. Write $A_{1} = {x_{1}, \dots, x_{a}}$ . Then

A_{1} \times A_{2} = i = 1 ⋃ a ({x_{i}} \times A_{2}),

and the $a$ sets in this union are pairwise disjoint (they differ in the first coordinate). Each has $∣ A_{2} ∣ = b$ elements, since $y \mapsto (x_{i}, y)$ is a bijection $A_{2} \to {x_{i}} \times A_{2}$ . The addition rule gives $∣ A_{1} \times A_{2} ∣ = a b + \dots + b = ab$ .

For the process form, the objects are no longer literal tuples from fixed sets — the options at step $i$ may depend on earlier choices. Induct on $m$ : group the objects by their first choice. There are $n_{1}$ groups, pairwise disjoint, and each group is a set of objects built by $m - 1$ successive choices with option counts $n_{2}, \dots, n_{m}$ , so each has $n_{2} \dots n_{m}$ elements by the inductive hypothesis. The addition rule finishes it.∎

The process form is the version worth memorising, and its hypothesis is the whole content of the rule: the number of options at each step must be the same no matter how the earlier steps went. The options themselves may differ; only their count must be constant.

Pitfall. "Independent choices" does not mean the later choice is unaffected by the earlier one. When dealing a second card from a deck, which cards remain depends entirely on the first card dealt — but how many remain is $51$ regardless, so the product rule applies and gives $52 \cdot 51$ . Conversely, "choose a committee of $3$ from $10$ people, then choose a chair from outside the committee" has constant counts ( $(3 10)$ then $7$ ) and is fine, whereas "choose a nonempty subset $A$ of $[4]$ , then choose an element of $A$ " is not a product: the second count is $∣ A ∣$ , which varies from $1$ to $4$ . That one needs casework or a double count, not multiplication.

Intuition. Product: a shirt (5 colours) AND THEN trousers (3 styles) gives $15$ outfits, because each of the 5 shirts opens a fresh menu of 3.

Sum: desserts $=$ cakes (4) $+$ pies (3) $+$ ice creams (5) $= 12$ , because you take exactly one item and the three menus do not overlap.

Division: $120$ rotationally distinct round-table seatings of 6 guests, because the $720$ labelled seatings fall into groups of 6.

The addition rule needs disjointness. When the cases overlap, the repair is inclusion–exclusion; we state the two- and three-set versions here, which cover almost all elementary uses.

Theorem 1.8 (Inclusion–exclusion for two and three sets). For finite sets $A, B, C$ ,

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

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

Proof. Count the contribution of an arbitrary element $x \in A \cup B \cup C$ to each side; since both sides are sums of cardinalities, it suffices that every such $x$ contributes exactly $1$ to the right-hand side (it contributes $1$ to the left by definition).

Say $x$ lies in exactly $j \geq 1$ of the three sets. It is counted $j$ times in the single terms, $(2 j)$ times in the pairwise intersections, and $(3 j)$ times in the triple intersection, so its total contribution is

(1 j) - (2 j) + (3 j) .

For $j = 1$ this is $1 - 0 + 0 = 1$ ; for $j = 2$ it is $2 - 1 + 0 = 1$ ; for $j = 3$ it is $3 - 3 + 1 = 1$ . An element outside $A \cup B \cup C$ contributes $0$ to both sides. The two-set identity is the same computation with the $j = 3$ column deleted.∎

These two cases cover almost every elementary use. The principle for $n$ sets, its complementary form, the Bonferroni truncations and the applications to sieves, derangements and surjections are the subject of Counting Principles.

A fifth move is not a new rule but a habit: complementary counting. If the objects you want are hard to describe but their complement inside an easy universe is easy, count the universe and subtract. "At least one" is the standing signal for it.

Example 1.9 (When to add, when to multiply). Licence plates consist of $3$ letters (A–Z) followed by $3$ digits (0–9). (a) How many are there if repetition is allowed? (b) How many if no letter may repeat? (c) How many contain at least one digit $7$ ?

Solution. (a) Six successive choices, with constant counts $26, 26, 26, 10, 10, 10$ because repetition is allowed:

2 6^{3} \cdot 1 0^{3} = 17576 \cdot 1000 = 17576 000.

(b) The letter counts now shrink as letters are used up, but they shrink predictably: whatever the first letter was, exactly $25$ remain. So the process form applies with counts $26, 25, 24, 10, 10, 10$ :

26 \cdot 25 \cdot 24 \cdot 1 0^{3} = 15600 \cdot 1000 = 15600 000.

(c) "At least one 7" is a union of three overlapping events (digit 1 is a 7, digit 2 is, digit 3 is), so the addition rule does not apply directly. Complementary counting does: plates with no 7 have $9$ options in each digit slot, so

17576000 - 2 6^{3} \cdot 9^{3} = 17576000 - 17576 \cdot 729 = 17576000 - 12812904 = 4763 096.

Sanity checks: (b) is smaller than (a), as forbidding repeats must reduce the count; and (c) is a fraction $1 - (9/10)^{3} = 0.271$ of (a), matching $4763 096/17 576000$ .□

Example 1.10 (Inclusion–exclusion in place). Of $100$ students, $52$ take French, $45$ take German, $38$ take Spanish, $20$ take French and German, $15$ take French and Spanish, $12$ take German and Spanish, and $5$ take all three. How many take none of the three?

Solution. By the three-set inclusion–exclusion formula,

∣ F \cup G \cup S ∣ = 52 + 45 + 38 - 20 - 15 - 12 + 5 = 93.

Complementary counting then gives $100 - 93 = 7$ students taking none.

Sanity check by reconstructing the seven disjoint regions: all three, $5$ ; exactly F and G, $20 - 5 = 15$ ; exactly F and S, $15 - 5 = 10$ ; exactly G and S, $12 - 5 = 7$ ; only F, $52 - 15 - 10 - 5 = 22$ ; only G, $45 - 15 - 7 - 5 = 18$ ; only S, $38 - 10 - 7 - 5 = 16$ . These sum to $5 + 15 + 10 + 7 + 22 + 18 + 16 = 93$ , and all seven are non-negative, so the data are consistent.□

Exercises for §1.2 →

1.3Choosing the Right Model

Almost every mistake in elementary counting is a modelling mistake: the arithmetic is fine but the formula answers a different question. This section is the map. It is placed before the formulas are derived on purpose — you should know what you are aiming at while deriving it.

Two binary questions classify the four basic selection models. Given a pool of $n$ distinguishable objects from which $k$ are taken:

Does order matter? Is the outcome a sequence or a set?
May an object be taken more than once? With or without replacement?

Note (The four selection models). Taking $k$ objects from a pool of $n$ distinguishable objects:

	order matters	order does not matter
repetition allowed	$n^{k}$	$(k n + k - 1)$
repetition forbidden	$P (n, k) = \frac{n !}{( n - k )!}$	$(k n) = \frac{n !}{k ! ( n - k )!}$

Each entry is derived in a later section: $n^{k}$ and $P (n, k)$ in the permutation sections, $(k n)$ and $(k n + k - 1)$ in the section on unordered selections.

Note the asymmetry of the table: the two left entries differ by shrinking factors, and the two right entries are obtained from the left ones by dividing by $k!$ — but only the bottom row division is exact. This is the single most important structural fact in the table.

Pitfall. The "divide by $k!$ " step converts ordered selections into unordered ones only when repetition is forbidden. With repetition allowed, $n^{k} / k!$ is usually not even an integer, and it is never the right answer: the fibres of "forget the order" have different sizes, because a multiset with repeated entries has fewer distinct orderings than one with all entries different. For $n = k = 2$ the multisets are ${a, a}$ , ${a, b}$ , ${b, b}$ — three of them — whereas $n^{k} / k! = 4/2 = 2$ . The division principle is not applicable, which is exactly why combinations with repetition need their own argument (stars and bars) rather than a division.

Pitfall. A problem that sounds unordered may be ordered in disguise, and vice versa. The test is: would swapping two chosen items give a different outcome? "Choose 3 of 10 people to serve on a committee" — no, so $(3 10)$ . "Choose 3 of 10 people to be president, treasurer and secretary" — yes, so $P (10, 3)$ . "Choose 3 of 10 flavours for a three-scoop cone where scoops may repeat and the stacking order is visible" — yes, and with repetition, so $1 0^{3}$ . Same three numbers in the sentence, three different answers: $120$ , $720$ , $1000$ .

The selection models are a special case of a more general and more useful classification: distributing balls into boxes. Every counting problem in this chapter can be phrased this way, and the phrasing makes the modelling decisions explicit, because it forces you to say whether the balls are labelled and whether the boxes are labelled.

Definition 1.11 (The distribution problem). Let $n$ balls be placed into $k$ boxes. The count depends on three independent binary choices:

the balls are distinguishable (labelled $1, \dots, n$ ) or indistinguishable;
the boxes are distinguishable or indistinguishable;
the map is unrestricted, injective (at most one ball per box), or surjective (no box empty).

The resulting $2 \times 2 \times 3 = 12$ counts are the twelvefold way.

Read as functions, this is the classification of maps $f : B \to X$ with $∣ B ∣ = n$ , $∣ X ∣ = k$ : "ball $b$ goes into box $f (b)$ ". Indistinguishable balls means counting maps up to permutation of the domain; indistinguishable boxes, up to permutation of the codomain.

Theorem 1.12 (The twelvefold way). With $n$ balls and $k$ boxes, the number of distributions is:

balls	boxes	any	injective ( $\leq 1$ per box)	surjective (none empty)
dist.	dist.	$k^{n}$	$\frac{k !}{( k - n )!}$	$k! S (n, k)$
indist.	dist.	$(n n + k - 1)$	$(n k)$	$(k - 1 n - 1)$
dist.	indist.	$j = 0 \sum k S (n, j)$	$[n \leq k]$	$S (n, k)$
indist.	indist.	$j = 0 \sum k p_{j} (n)$	$[n \leq k]$	$p_{k} (n)$

Here $S (n, k)$ is the Stirling number of the second kind (the number of partitions of an $n$ -set into exactly $k$ non-empty unlabelled blocks), $p_{k} (n)$ is the number of partitions of the integer $n$ into exactly $k$ positive parts, and $[P]$ is $1$ if $P$ holds and $0$ otherwise.

Proof. The six entries in the first two rows are proved in this chapter. Row 1: $k^{n}$ is the count of sequences with repetition, and $k! / (k - n)! = P (k, n)$ the count without, both established in the permutation sections — a distribution of labelled balls into labelled boxes is the sequence $(f (1), \dots, f (n))$ of box labels. Row 2: identical balls in labelled boxes are recorded only by the occupancy vector $(x_{1}, \dots, x_{k})$ with $x_{i} \geq 0$ and $\sum x_{i} = n$ , counted by stars and bars as $(n n + k - 1)$ ; requiring $x_{i} \leq 1$ means choosing which $n$ of the $k$ boxes are occupied, i.e. $(n k)$ ; requiring $x_{i} \geq 1$ is stars and bars for positive solutions, $(k - 1 n - 1)$ .

Rows 3 and 4 are a different matter. $S (n, k)$ and $p_{k} (n)$ have no closed product formula; they are defined by the counts in the surjective column, and the "any" column follows by the addition rule, splitting on the number $j$ of non-empty boxes. The relation $k! S (n, k)$ in row 1 holds because a surjection onto $k$ labelled boxes is a partition into $k$ unlabelled blocks together with a bijection from the blocks to the labels, and there are $k!$ such bijections — the product rule. The injective entries are immediate: with indistinguishable balls and boxes, an injective placement is determined by nothing at all, so the count is $1$ when $n \leq k$ and $0$ otherwise.

$S (n, k)$ does satisfy a closed alternating sum, $S (n, k) = \frac{1}{k !} \sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}$ , which comes from inclusion–exclusion over the set of boxes left empty; and the partition numbers $p_{k} (n)$ have no closed form at all, only generating functions and the Hardy–Ramanujan asymptotic. Both are beyond this chapter and are quoted, not proved, here.∎

Intuition. "Distinguishable" means the objects carry names you care about. Six labelled dice rolled at once are distinguishable (die 3 showing a 5 is different news from die 1 showing a 5); six identical marbles poured into cups are not.

A quick way to decide: imagine two of the objects swapping places. If the result is a genuinely different outcome for the purpose of the problem, they are distinguishable. If nobody could tell, they are not — and you are in one of the bottom rows.

Example 1.13 (One sentence, four models). Ten items are to be placed into four boxes. Count the distributions when (a) items and boxes are both labelled; (b) items are identical and boxes labelled; (c) items are identical, boxes labelled, and no box may be empty; (d) items are labelled, boxes labelled, and no box may be empty.

Solution. (a) Each of the $10$ labelled items independently picks one of $4$ labelled boxes: $4^{10} = 1048576$ .

(b) Only the occupancy vector $(x_{1}, x_{2}, x_{3}, x_{4})$ with $x_{i} \geq 0$ and $\sum x_{i} = 10$ matters. By stars and bars,

(10 10 + 4 - 1) = (10 13) = (3 13) = \frac{13 \cdot 12 \cdot 11}{6} = 286.

(c) Now $x_{i} \geq 1$ . Substituting $y_{i} = x_{i} - 1 \geq 0$ with $\sum y_{i} = 6$ gives $(6 6 + 3) = (3 9) = 84$ ; equivalently $(k - 1 n - 1) = (3 9) = 84$ .

(d) This is $4! S (10, 4)$ , equal by inclusion–exclusion to

j = 0 \sum 4 (- 1)^{j} (j 4) (4 - j)^{10} = 4^{10} - 4 \cdot 3^{10} + 6 \cdot 2^{10} - 4 \cdot 1^{10} = 1048576 - 236196 + 6144 - 4 = 818 520.

Sanity check on the ordering: (d) counts a subset of the objects counted in (a), and indeed $818520 < 1048576$ ; the ratio $0.781$ is plausible since with $10$ balls in only $4$ boxes an empty box is unlikely. And (c) counts a subset of (b): $84 < 286$ . ✓□

Combinatorial counts are the engine of discrete probability: in a finite sample space where all outcomes are equally likely, $P (E) = ∣ E ∣/∣Ω∣$ , so every such probability question is two counting questions. They also govern algorithm analysis (how many comparisons does a sorting algorithm make?), coding theory (how many codewords of a given weight?), and statistical mechanics (how many microstates realise a macrostate?) — the last being literally row 2 and row 4 of the twelvefold way, known there as Maxwell–Boltzmann, Bose–Einstein and Fermi–Dirac statistics.

Example 1.14 (Counting for a probability). Five cards are dealt from a standard $52$ -card deck. What is the probability that the hand is a "full house" (three cards of one rank, two of another)?

Solution. The sample space is the set of unordered $5$ -card hands — order of dealing is irrelevant — so $∣Ω∣ = (5 52) = 2598960$ .

Build a full house by successive choices with constant counts: choose the rank appearing three times ( $13$ ), choose its three suits ( $(3 4) = 4$ ), choose the different rank appearing twice ( $12$ ), choose its two suits ( $(2 4) = 6$ ). By the product rule,

13 \cdot 4 \cdot 12 \cdot 6 = 3744, P = \frac{3744}{2 598 960} \approx 0.00144.

Sanity check: the equivalent route "choose the two ranks, then decide which is the triple" gives $(2 13) \cdot 2 = 78 \cdot 2 = 156 = 13 \cdot 12$ for the rank part, and the same $4 \cdot 6 = 24$ for the suits. ✓□

Pitfall. In the full-house count the rank part is $13 \cdot 12$ and must not be divided by $2!$ . The two ranks play different roles — one is the triple, the other the pair — so swapping them gives a genuinely different hand, and the division principle does not apply. Divide by $k!$ only when the chosen objects are interchangeable in the finished object.

Exercises for §1.3 →

1.4Factorials and Ordered Selections

We now derive the left column of the selection table. Order matters throughout this section.

Definition 1.15 (Factorial). For an integer $n \geq 0$ , the factorial $n!$ is defined recursively by

0! = 1, n! = n \cdot (n - 1)! for n \geq 1,

so that $n! = n (n - 1) (n - 2) \dots 2 \cdot 1$ for $n \geq 1$ .

The value $0! = 1$ is not a quirk. It is the empty product, and it is forced by every formula in which it appears: the recursion $1! = 1 \cdot 0!$ requires it, and so does the statement "there is exactly one arrangement of no objects" (namely the empty arrangement).

Definition 1.16 (Permutation). A permutation of a finite set $S$ is a bijection $S \to S$ , equivalently a linear arrangement of the elements of $S$ in a row. A $k$ -permutation of $S$ (for $0 \leq k \leq ∣ S ∣$ ) is an injective map $[k] \to S$ , equivalently an ordered selection of $k$ distinct elements of $S$ . Their number is written $P (n, k)$ , where $n = ∣ S ∣$ .

Theorem 1.17 (Arrangements of distinct objects). There are exactly $n!$ permutations of a set of $n$ distinct objects.

Proof. Induction on $n$ . For $n = 0$ there is one permutation of the empty set (the empty map), and $0! = 1$ . Suppose the claim holds for $n - 1$ . An arrangement of $n$ objects is built by choosing the occupant of the first position ( $n$ options, whatever else will follow) and then arranging the remaining $n - 1$ objects in the remaining $n - 1$ positions. The second stage has $(n - 1)!$ outcomes by the inductive hypothesis, and this count does not depend on which object went first. The process form of the product rule gives $n \cdot (n - 1)! = n!$ .∎

Theorem 1.18 (Falling factorial). For integers $0 \leq k \leq n$ ,

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

The product on the left has exactly $k$ factors and is called the falling factorial, written $n^{\underline{k}}$ .

Proof. Fill the $k$ positions in order. Position $1$ admits any of the $n$ objects; once $i - 1$ positions are filled, exactly $i - 1$ objects are used up, so position $i$ admits $n - (i - 1)$ objects — a count independent of which objects were used. The product rule gives $\prod_{i = 1}^{k} (n - i + 1) = n (n - 1) \dots (n - k + 1)$ .

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

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

Note the extreme cases: $P (n, 0) = 1$ (the empty selection, consistent with an empty product) and $P (n, n) = n! /0! = n!$ , recovering the previous theorem.∎

Corollary 1.19 (Counting injections). The number of injective maps $[k] \to [n]$ is $P (n, k)$ , which is $0$ when $k > n$ .

Proof. An injective map $[k] \to [n]$ is precisely an ordered selection of $k$ distinct elements of $[n]$ : the list $(f (1), \dots, f (k))$ , whose entries are distinct exactly because $f$ is injective. This correspondence is a bijection between injections and $k$ -permutations, so the counts agree by the bijection principle. When $k > n$ no injection exists (pigeonhole), and the falling factorial $n (n - 1) \dots (n - k + 1)$ then contains the factor $n - n = 0$ , so the formula remains correct.∎

Intuition. $n!$ grows with terrifying speed: $10! = 3628800$ already, and $52!$ exceeds $8 \times 1 0^{67}$ — which is why "a well-shuffled deck is almost certainly in an order no deck has ever been in before" is literally true.

$P (n, k)$ is $n!$ with its tail cut off. Reading it as " $k$ factors counting down from $n$ " is faster and safer in practice than computing two factorials and dividing.

The growth rate deserves a precise statement, since it is quoted constantly in algorithm analysis and in probability.

Theorem 1.20 (Stirling's approximation). As $n \to \infty$ ,

n! \sim 2 πn (\frac{n}{e})^{n},

meaning the ratio of the two sides tends to $1$ . More precisely, $2 πn (n / e)^{n} < n! < 2 πn (n / e)^{n} e^{1/ (12 n)}$ for all $n \geq 1$ .

Remark. The proof of Stirling's approximation is analytic, not combinatorial: it rests on comparing $lo g n! = \sum_{j = 1}^{n} lo g j$ with $\int_{1}^{n} lo g x d x$ to obtain the shape $n^{n} e^{- n}$ , and then on Wallis's product (or a Laplace-method estimate of $Γ (n + 1) = \int_{0}^{\infty} x^{n} e^{- x} d x$ ) to pin down the constant $2 π$ . Neither step is within the scope of this chapter, so we quote the result and use it only for estimates.

Example 1.21 (Ordered codes). How many $3$ -letter codes can be formed from the letters A–F if (a) letters may not repeat, (b) letters may repeat, (c) letters may not repeat and the code must contain the letter A?

Solution. (a) An ordered selection of $3$ distinct letters from $6$ :

P (6, 3) = 6 \cdot 5 \cdot 4 = 120.

(b) Each of the $3$ slots independently takes any of $6$ letters: $6^{3} = 216$ .

(c) Choose the position of A ( $3$ ways), then fill the other two positions with distinct letters from the remaining five, in order: $P (5, 2) = 5 \cdot 4 = 20$ . By the product rule, $3 \cdot 20 = 60$ .

Sanity check on (c) by complementary counting: codes with no A are $P (5, 3) = 5 \cdot 4 \cdot 3 = 60$ , so codes containing A number $120 - 60 = 60$ . ✓ And (a) $<$ (b), as forbidding repetition must reduce the count.□

Example 1.22 (Arrangements with an adjacency constraint). In how many orders can $7$ distinct books be shelved if three particular volumes of one work must stand together, in any order among themselves?

Solution. Glue the three volumes into a single block. There are then $5$ objects to arrange (the block plus the $4$ other books), giving $5! = 120$ arrangements, and within the block the three volumes may be permuted in $3! = 6$ ways. These two stages have constant counts, so the product rule applies:

5! \cdot 3! = 120 \cdot 6 = 720.

Sanity check: the answer must be smaller than the unrestricted $7! = 5040$ , and the ratio $720/5040 = 1/7$ is exactly the probability that three specified books land consecutively — plausible, and independently verifiable as $5 \cdot 3! \cdot 4! /7! = 5 \cdot 6 \cdot 24/5040 = 1/7$ . ✓□

Exercises for §1.4 →

1.5Sequences with Repetition

Removing the injectivity requirement changes the model completely, and gives the simplest formula in the chapter.

Theorem 1.23 (Sequences with repetition). The number of sequences of length $k$ whose entries come from an $n$ -element set, repetitions allowed, is

n^{k} .

Equivalently, the number of functions $[k] \to [n]$ is $n^{k}$ .

Proof. A sequence is an element of the Cartesian product $A \times A \times \dots \times A$ ( $k$ factors) where $∣ A ∣ = n$ , so the product rule gives $n \cdot n \dots n = n^{k}$ . In process form: nothing is used up, so every one of the $k$ positions has the full $n$ options available regardless of the earlier positions.

For the function statement, the map sending $f : [k] \to [n]$ to the sequence $(f (1), \dots, f (k))$ is a bijection — a function on a finite ordered domain is exactly its list of values — so the counts agree.∎

Corollary 1.24 (Number of subsets). A set with $n$ elements has exactly $2^{n}$ subsets.

Proof. By the earlier example, subsets of $[n]$ correspond bijectively to binary strings of length $n$ via the indicator string. By the theorem with $n \to 2$ symbols and length $k \to n$ , there are $2^{n}$ such strings.∎

The contrast with the previous section is worth stating numerically, because it is the whole difference between "with replacement" and "without".

Remark. Compare $n^{k} = n \cdot n \dots n$ with $P (n, k) = n (n - 1) \dots (n - k + 1)$ : the same number of factors, but the second has each factor reduced. Hence $P (n, k) \leq n^{k}$ always, with equality only when $k \leq 1$ . For $n = 365$ and $k = 23$ the ratio $P (365, 23) /36 5^{23} \approx 0.4927$ is below one half — this is the birthday paradox, and it is nothing but the gap between these two rows of the table.

Pitfall. The phrase "how many ways to choose $k$ from $n$ with repetition" is ambiguous in ordinary English and the two readings have very different answers. If the outcome is a sequence (a PIN, a dice roll recorded die by die, a word) the answer is $n^{k}$ . If the outcome is a multiset (a handful of coins, an unordered scoop selection, the multiset of values shown by identical dice) the answer is $(k n + k - 1)$ , derived later. Three dice thrown together give $6^{3} = 216$ equally likely outcomes but only $(3 8) = 56$ distinguishable multisets — and those $56$ are not equally likely, which is why using the wrong model quietly ruins a probability calculation.

Intuition. With repetition each slot has amnesia: it does not know or care what the previous slots took, so the menu never shrinks. Passwords, PINs and dice rolls work this way.

Without repetition the pool is a deck: every draw removes a card, so the menu shrinks by exactly one each time.

Example 1.25 (PINs and numbers). (a) How many $4$ -digit PINs are there, $0000$ allowed? (b) How many $4$ -digit numbers are there (no leading zero)? (c) How many $4$ -digit PINs have all digits distinct? (d) How many have at least two equal digits?

Solution. (a) Four slots, $10$ options each: $1 0^{4} = 10000$ .

(b) The leading slot is restricted to $1$ – $9$ ; the other three are unrestricted: $9 \cdot 1 0^{3} = 9000$ . Check: these are the integers $1000$ through $9999$ , and $9999 - 1000 + 1 = 9000$ . ✓

(c) No repetition, order matters: $P (10, 4) = 10 \cdot 9 \cdot 8 \cdot 7 = 5040$ .

(d) Complementary counting against (a) and (c): $10000 - 5040 = 4960$ .

Note that (d) could not be done directly by a product rule — "at least two equal" is not a sequence of choices with constant counts — which is exactly the situation complementary counting exists for.□

Example 1.26 (Counting functions with a constraint). How many functions $f : [5] \to [3]$ satisfy $f (1) \neq = f (2)$ ?

Solution. Choose the values in order. $f (1)$ has $3$ options; $f (2)$ then has $2$ (anything but $f (1)$ — a count of $2$ whatever $f (1)$ was); and $f (3), f (4), f (5)$ have $3$ each. Constant counts at every stage, so

3 \cdot 2 \cdot 3^{3} = 6 \cdot 27 = 162.

Sanity check: the total number of functions is $3^{5} = 243$ , and those with $f (1) = f (2)$ number $3 \cdot 3^{3} = 81$ (pick the common value, then the last three freely). Indeed $243 - 81 = 162$ . ✓□

Exercises for §1.5 →

1.6Circular Arrangements and Multiset Permutations

Both topics in this section are applications of the division principle: we count something easy that over-counts, then divide by the size of the over-count. In both cases the hypothesis of the division principle — constant fibre size — has to be checked, and in one notorious case it fails.

Definition 1.27 (Circular arrangement). A circular arrangement of $n$ distinct objects is an arrangement of them around a circle in which two arrangements are identified when one is a rotation of the other; only the cyclic order matters.

Theorem 1.28 (Circular permutations). The number of circular arrangements of $n \geq 1$ distinct objects is $(n - 1)!$ .

Proof. Let $S$ be the set of the $n!$ arrangements in $n$ labelled seats around the circle and $T$ the set of circular arrangements, with $f : S \to T$ the quotient map. $f$ is surjective. Each fibre is the set of the $n$ rotations of a given arrangement, and these $n$ labelled arrangements are pairwise distinct: a rotation by $j \neq \equiv 0 (mod n)$ moves the object in seat $1$ to seat $1 + j \neq = 1$ , so it changes the labelled arrangement. Hence every fibre has size exactly $n$ , and the division principle gives $∣ T ∣ = n! / n = (n - 1)!$ .∎

Pitfall. If the circle may also be flipped over — a bracelet or necklace rather than a seating plan — then reflections are identified too, and the naive answer $n! / (2 n)$ is wrong in general, because the division principle no longer applies: an arrangement that is symmetric under some reflection has a fibre of size $n$ , not $2 n$ . For $n \geq 3$ with all beads distinct no arrangement is reflection-symmetric, so $n! / (2 n) = (n - 1)! /2$ is in fact correct there; but for $n \leq 2$ , or as soon as beads repeat, the fibres genuinely differ in size and the count requires Burnside's lemma. Always check whether a symmetry can fix an object before dividing by the size of the symmetry group.

Definition 1.29 (Multiset and multiset permutation). A multiset on a set of $r$ types is an assignment of a multiplicity $k_{i} \geq 0$ to each type $i$ ; its size is $n = k_{1} + \dots + k_{r}$ . A multiset permutation (or word) is a linear arrangement of the $n$ objects of such a multiset, two arrangements being the same when they agree position by position as sequences of types.

Theorem 1.30 (Permutations of a multiset). The number of distinct arrangements in a row of $n$ objects of $r$ types, with $k_{i}$ objects of type $i$ and $k_{1} + \dots + k_{r} = n$ , is

(k _{1} , k _{2} , \dots , k _{r} n) := \frac{n !}{k _{1} ! k _{2} ! \dots k _{r} !} .

Proof. First proof (division principle). Temporarily label the objects of each type $1, 2, \dots, k_{i}$ so that all $n$ are distinct; there are $n!$ arrangements of these labelled objects. Let $f$ send a labelled arrangement to the word obtained by forgetting the labels. $f$ is surjective. Given a word $w$ , a labelled arrangement mapping to it is obtained by distributing the labels of type $i$ among the $k_{i}$ positions where type $i$ occurs, independently for each type, in $k_{1}! k_{2}! \dots k_{r}!$ ways. So every fibre has this same size and the division principle applies.

Second proof (successive choices). Build the word by deciding which positions each type occupies. Choose the $k_{1}$ positions for type $1$ from the $n$ available, in $(k _{1} n)$ ways; then the $k_{2}$ positions for type $2$ from the $n - k_{1}$ remaining, in $(k _{2} n - k _{1})$ ways; and so on. The counts at each stage depend only on the $k_{i}$ , not on which positions were chosen, so the product rule gives

(k _{1} n) (k _{2} n - k _{1}) \dots (k _{r} n - k _{1} - \dots - k _{r - 1}) = \frac{n !}{k _{1} ! ( n - k _{1} )!} \cdot \frac{( n - k _{1} )!}{k _{2} ! ( n - k _{1} - k _{2} )!} \dots = \frac{n !}{k _{1} ! \dots k _{r} !},

the intermediate factorials cancelling telescopically.∎

Definition 1.31 (Multinomial coefficient). The quantity $(k _{1} , \dots , k _{r} n) = \frac{n !}{k _{1} ! \dots k _{r} !}$ , defined for non-negative integers $k_{i}$ summing to $n$ , is the multinomial coefficient. For $r = 2$ it reduces to the binomial coefficient: $(k , n - k n) = (k n)$ .

Corollary 1.32 (Ordered set partitions). The number of ways to split a set of $n$ distinct objects into an ordered list of $r$ labelled groups of prescribed sizes $k_{1}, \dots, k_{r}$ (with $\sum k_{i} = n$ ) is $(k _{1} , \dots , k _{r} n)$ .

Proof. The second proof above is exactly this count: choosing the positions of type $i$ is choosing which objects go into group $i$ . Formally, the map sending a word to the tuple of sets $({$ positions of type $1}, \dots)$ is a bijection between multiset permutations and ordered size-prescribed partitions of $[n]$ .∎

Intuition. The multinomial coefficient answers "deal $n$ cards into hands of sizes $k_{1}, \dots, k_{r}$ ", and the two proofs are the two natural ways to do the deal: shuffle then cut ( $n!$ divided by the internal shuffles you cannot see), or deal hand by hand (a product of binomials).

Because the second proof is a product of ordinary binomials, you never need the multinomial formula to compute — but you do need to recognise the situation, which is: more than two categories.

Pitfall. When the groups are unlabelled and of equal size, divide further. Splitting $6$ people into three labelled teams of $2$ gives $(2 , 2 , 2 6) = 90$ ; splitting them into three unlabelled pairs gives $90/3! = 15$ , because each set of three pairs arises from $3!$ orderings of the teams. The extra division is legitimate here because all the group sizes are equal, so every set of pairs is over-counted exactly $3!$ times. If the group sizes were $3, 2, 1$ , no further division is right at all — the sizes themselves tell the groups apart.

Example 1.33 (MISSISSIPPI). How many distinct arrangements are there of the letters of MISSISSIPPI? How many of them have all four S's adjacent?

Solution. The multiset is $1$ M, $4$ I, $4$ S, $2$ P, of size $11$ . By the multiset permutation theorem,

\frac{11 !}{1 ! 4 ! 4 ! 2 !} = \frac{39 916 800}{1 \cdot 24 \cdot 24 \cdot 2} = \frac{39 916 800}{1152} = 34 650.

For the second question, glue the four S's into a single block. The objects to arrange are the block, $1$ M, $4$ I, $2$ P — a multiset of size $8$ with multiplicities $1, 1, 4, 2$ :

\frac{8 !}{1 ! 1 ! 4 ! 2 !} = \frac{40 320}{48} = 840.

Sanity check: $840/34 650 \approx 0.0242$ is the probability that a random arrangement has the S's together; a crude estimate — $8$ starting positions for the block out of $(4 11) = 330$ position-sets for the S's — gives $8/330 = 0.0242$ exactly. ✓□

Example 1.34 (Circular seating with a constraint). Six people, including Ana and Ben, sit at a round table; rotations are identified. In how many arrangements are Ana and Ben not adjacent?

Solution. Total circular arrangements: $(6 - 1)! = 120$ .

Count the arrangements where they are adjacent and subtract. Glue Ana and Ben into a block; we then have $5$ objects in a circle, giving $(5 - 1)! = 24$ circular arrangements, and the block has $2! = 2$ internal orders, so $24 \cdot 2 = 48$ adjacent arrangements.

120 - 48 = 72.

Sanity check by a direct argument: fix Ana's seat (killing the rotations). Of the $5$ remaining seats, $2$ are adjacent to Ana and $3$ are not, so Ben has $3$ allowed seats, and the other four people fill the rest in $4! = 24$ ways: $3 \cdot 24 = 72$ . ✓□

Exercises for §1.6 →

1.7Unordered Selections and Stars and Bars

We now derive the right-hand column of the selection table. Both entries count sets or multisets rather than sequences, and the two proofs are of very different characters: the first is a division, the second is a bijection.

Definition 1.35 (Combination). A $k$ -combination of an $n$ -set $S$ is a $k$ -element subset of $S$ : which elements are taken matters, the order in which they are taken does not, and no element may be taken twice. The number of $k$ -combinations of an $n$ -set is written $(k n)$ , read " $n$ choose $k$ ".

Theorem 1.36 (Combination formula). For integers $0 \leq k \leq n$ ,

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

Proof. Let $S$ be the set of $k$ -permutations of $[n]$ , so $∣ S ∣ = P (n, k)$ , and let $T$ be the set of $k$ -subsets. Let $f : S \to T$ send an ordered selection to the set of its entries. $f$ is surjective: any $k$ -subset can be listed in some order. Every fibre has size exactly $k!$ : the ordered selections mapping to a given $k$ -set $A$ are precisely the orderings of $A$ , of which there are $k!$ by the arrangements theorem — and crucially this number is the same for every $A$ , because the entries of a $k$ -permutation are distinct. The division principle gives

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

∎

Remark. The third expression, $\frac{n ( n - 1 ) \dots ( n - k + 1 )}{k !}$ , is the one to compute with: $(3 50) = \frac{50 \cdot 49 \cdot 48}{6} = 19600$ takes seconds, while $50! / (3! 47!)$ invites a calculator overflow. It also makes visible that $(k n)$ is a polynomial in $n$ of degree $k$ , which is how the definition is extended to non-integer upper arguments later on.

Intuition. A committee is a set; a lineup is a sequence. Going from lineups to committees loses exactly the information of the internal order, and there are $k!$ internal orders, so you divide by $k!$ .

This also reads in reverse and is often more useful: to count ordered things, first count the unordered thing and then multiply back by $k!$ . Many problems are far easier in that direction.

Now the second entry: selections in which repetition is allowed but order is not. The outcome of such a selection is a multiset, so the object to be counted is a multiset of size $k$ on $n$ types.

Theorem 1.37 (Combinations with repetition (stars and bars)). The number of multisets of size $k$ drawn from $n$ types equals the number of integer solutions of

x_{1} + x_{2} + \dots + x_{n} = k, x_{i} \geq 0,

and both equal

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

Proof. The first equality is a bijection: a multiset is determined by, and determines, its multiplicity vector $(x_{1}, \dots, x_{n})$ , where $x_{i} \geq 0$ counts the copies of type $i$ and $\sum x_{i} = k$ because the multiset has size $k$ .

For the second, encode a solution as a string of $k$ stars and $n - 1$ bars: write $x_{1}$ stars, a bar, $x_{2}$ stars, a bar, …, a bar, then $x_{n}$ stars. For example with $n = 4$ , $k = 6$ , the solution $(2, 0, 3, 1)$ becomes

⋆ ⋆ ∣ ∣ ⋆ ⋆ ⋆ ∣ ⋆ .

This map sends solutions to strings of length $k + (n - 1)$ over ${⋆, ∣}$ containing exactly $n - 1$ bars. It is injective: the string determines every $x_{i}$ , namely the number of stars between bar $i - 1$ and bar $i$ . It is surjective: given any such string, reading off the gaps between consecutive bars produces non-negative integers summing to $k$ (the total number of stars), and these map back to the string. So it is a bijection.

Finally, a string of $k + n - 1$ symbols with exactly $n - 1$ bars is determined by choosing which $n - 1$ of the $k + n - 1$ positions hold the bars — equivalently which $k$ hold the stars — so by the combination formula there are $(n - 1 n + k - 1) = (k n + k - 1)$ of them.∎

Figure 1.38. The stars-and-bars bijection for

n = 4

types and

k = 6

items: the string encodes the solution

(2, 0, 3, 1)

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

. The

n - 1 = 3

bars cut the row of

k = 6

stars into

n = 4

blocks, and

x_{i}

is the number of stars in block

i

— so an empty block is a variable equal to zero, which is why two adjacent bars are legal and why the count is over all

(3 9)

placements of the bars among the nine positions.

Corollary 1.39 (Positive solutions). The number of integer solutions of $x_{1} + \dots + x_{n} = k$ with every $x_{i} \geq 1$ is

(n - 1 k - 1),

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

Proof. Substitute $y_{i} = x_{i} - 1$ . Then $y_{i} \geq 0$ and $\sum y_{i} = k - n$ , and the substitution is a bijection between the two solution sets (its inverse is $x_{i} = y_{i} + 1$ ). By the theorem, the number of such $y$ is $(n - 1 ( k - n ) + n - 1) = (n - 1 k - 1)$ . If $k < n$ the sum $k - n$ is negative and no solution exists; the binomial coefficient $(n - 1 k - 1)$ is then $0$ by the convention for $k - 1 < n - 1$ . In bars-and-stars language: lay out the $k$ stars in a row and choose $n - 1$ of the $k - 1$ internal gaps to place bars in, at most one per gap so that no part is empty.∎

Pitfall. Stars and bars counts non-negative solutions and requires the types (boxes, variables) to be distinguishable and the items (stars) to be indistinguishable. It is row 2 of the twelvefold way. If the items are distinguishable, the answer is $n^{k}$ , not $(k n + k - 1)$ ; if the types are indistinguishable, the answer is a partition number with no closed form. Before applying the formula, say out loud which of the four boxes-and-balls cases you are in.

Example 1.40 (Doughnuts). A shop sells $5$ varieties of doughnut. How many ways are there to buy a dozen, if varieties may repeat and the order in the box does not matter? How many if at least one of each variety is required?

Solution. This is a multiset of size $k = 12$ on $n = 5$ types, so by stars and bars

(12 12 + 5 - 1) = (4 16) = \frac{16 \cdot 15 \cdot 14 \cdot 13}{24} = 1820.

With at least one of each, the positive-solution corollary gives

(5 - 1 12 - 1) = (4 11) = \frac{11 \cdot 10 \cdot 9 \cdot 8}{24} = 330.

Sanity check on the second by the substitution directly: after setting aside one of each variety, $7$ free doughnuts remain, giving $(4 7 + 4) = (4 11) = 330$ . ✓ And $330 < 1820$ , as a constraint must reduce the count.□

Example 1.41 (Bounded variables). How many integer solutions does $x_{1} + x_{2} + x_{3} = 10$ have with $0 \leq x_{i} \leq 5$ for each $i$ ?

Solution. Count the unrestricted non-negative solutions and remove the bad ones by inclusion–exclusion. Unrestricted:

(2 10 + 2) = (2 12) = 66.

Let $A_{i}$ be the set of solutions with $x_{i} \geq 6$ . Substituting $x_{i}^{'} = x_{i} - 6$ turns the condition into a free non-negative solution of a sum equal to $4$ , so

∣ A_{i} ∣ = (2 4 + 2) = (2 6) = 15 for each i .

Two variables cannot both be at least $6$ , since $12 > 10$ , so all pairwise intersections are empty. By inclusion–exclusion,

66 - 3 \cdot 15 + 0 = 66 - 45 = 21.

Sanity check by direct enumeration over $x_{1}$ : for $x_{1} = 0, 1, 2, 3, 4, 5$ the remaining pair must sum to $10, 9, 8, 7, 6, 5$ within $[0, 5]$ each, admitting $1, 2, 3, 4, 5, 6$ solutions respectively. Total $1 + 2 + 3 + 4 + 5 + 6 = 21$ . ✓□

Example 1.42 (Ordered versus unordered, side by side). From $8$ distinct flavours, count (a) three-scoop cones where order on the cone matters and flavours may repeat; (b) three-scoop cups where order does not matter and flavours may repeat; (c) three-scoop cups with all flavours distinct; (d) three-scoop cones with all flavours distinct.

Solution. Each is one cell of the selection table with $n = 8$ , $k = 3$ .

(a) Ordered, with repetition: $8^{3} = 512$ . (b) Unordered, with repetition: $(3 8 + 3 - 1) = (3 10) = 120$ . (c) Unordered, without repetition: $(3 8) = 56$ . (d) Ordered, without repetition: $P (8, 3) = 8 \cdot 7 \cdot 6 = 336$ .

Sanity checks on the relations between them: $(d) = 3! \cdot (c)$ , and indeed $6 \cdot 56 = 336$ ✓ — the division by $k!$ is exact without repetition. But $(a) /3! = 512/6 = 85.33$ , which is not $(b) = 120$ and is not even an integer: with repetition the division is meaningless, as the pitfall in the modelling section warned. Note also the ordering $(c) < (a)$ and $(c) < (b) < (d) < (a)$ , all as expected.□

Exercises for §1.7 →

1.8Notation, Conventions and Symmetry

The binomial coefficient is used far beyond the counting of subsets — as a polynomial coefficient, as a probability weight, as an entry of a triangle — and each use wants slightly different conventions. This section fixes them.

Notation (Binomial coefficient conventions). For integers $n \geq 0$ and any integer $k$ ,

(k n) = ⎩ ⎨ ⎧ \frac{n !}{k ! ( n - k )!}, 0, 0 \leq k \leq n, k < 0 or k > n .

In particular $(0 n) = (n n) = 1$ (one way to choose nothing, one way to choose everything) and $(1 n) = (n - 1 n) = n$ .

The convention $(k n) = 0$ outside the range is not laziness; it makes identities true without side conditions. Pascal's rule, for instance, holds for all integers $k$ once the convention is in force, which is what allows the recursion to be iterated mechanically.

Definition 1.43 (Generalised binomial coefficient). For an arbitrary real (or complex) number $α$ and an integer $k \geq 0$ ,

(k α) = \frac{α ( α - 1 ) \dots ( α - k + 1 )}{k !} = \frac{α ^{\underline{k}}}{k !}, (0 α) = 1,

and $(k α) = 0$ for $k < 0$ . For $α = n$ a non-negative integer this agrees with the previous definition, since the falling factorial then contains the factor $n - n = 0$ as soon as $k > n$ .

Proposition 1.44 (Symmetry). For all integers $n \geq 0$ and $k$ ,

(k n) = (n - k n) .

Proof. Complementation $A \mapsto [n] ∖ A$ is a map from $k$ -subsets of $[n]$ to $(n - k)$ -subsets, and it is its own inverse, hence a bijection. The bijection principle gives the identity. Algebraically the same thing: $\frac{n !}{k ! ( n - k )!}$ is unchanged when $k$ is replaced by $n - k$ . For $k$ outside $[0, n]$ both sides are $0$ .∎

Pitfall. Symmetry is a statement about the integer binomial coefficients only. $(k α) = (α - k α)$ is meaningless for non-integer $α$ — the right-hand side has a non-integer lower index — and false as soon as one tries to make sense of it. The generalised coefficient keeps Pascal's rule and the binomial series, but not symmetry.

Proposition 1.45 (Absorption identity). For integers $1 \leq k \leq n$ ,

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

Proof. Count in two ways the pairs $(A, x)$ where $A \subseteq [n]$ has $∣ A ∣ = k$ and $x \in A$ — a "committee of size $k$ with a designated chair". Choosing the committee first and then the chair from within it gives $(k n) \cdot k$ . Choosing the chair first from all $n$ people and then the remaining $k - 1$ members from the other $n - 1$ gives $n \cdot (k - 1 n - 1)$ . The two counts are of the same set, so they agree.∎

This is the prototype of a double count: a single set counted by two different schemes yields an identity for free, and the identity is explained rather than merely verified. Nearly all the identities in the last two sections have such a proof.

Proposition 1.46 (Unimodality and log-concavity). For fixed $n$ , the sequence $(0 n), (1 n), \dots, (n n)$ increases up to the middle and decreases after it: $(k - 1 n) < (k n)$ for $k \leq n /2$ and $(k n) > (k + 1 n)$ for $k \geq n /2$ . Its maximum is $(⌊ n /2 ⌋ n)$ .

Proof. From the formula, the ratio of consecutive entries is

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

which exceeds $1$ exactly when $n - k + 1 > k$ , i.e. $k < (n + 1) /2$ , equals $1$ when $n$ is odd and $k = (n + 1) /2$ , and is less than $1$ beyond. So the sequence rises strictly, possibly repeats one value at the centre of an odd row, then falls strictly; the maximum sits at $k = ⌊ n /2 ⌋$ (and also at $⌈ n /2 ⌉$ ). Symmetry confirms the shape is a mirror image about the centre.∎

Figure 1.47. Row

10

of Pascal's triangle drawn to scale:

(k 10)

against

k

. The ratio of consecutive bars is

(n - k + 1) / k

, which is above

1

to the left of the centre and below it to the right — so the row rises strictly, peaks once at

k = 5

, and falls strictly, with the mirror symmetry

(k 10) = (10 - k 10)

visible as the left–right reflection. The single central bar holds

252

of the

2^{10} = 1024

subsets, nearly a quarter of the whole row, while the two end bars hold one each.

Intuition. Row $n$ of Pascal's triangle is a single hump: small at the ends, largest in the middle. That shape is why "about half heads" is overwhelmingly the most likely outcome of many coin tosses — the middle binomial coefficient dwarfs the ends. Stirling's approximation quantifies it: $(m 2 m) \sim 4^{m} / πm$ , so the central term is a $Θ (1/ m)$ fraction of the whole row sum $4^{m}$ .

Example 1.48 (Computing efficiently). Evaluate $(17 20)$ and $(5 12)$ , and verify the absorption identity for $n = 12$ , $k = 5$ .

Solution. Use symmetry to reduce the lower index first: $(17 20) = (3 20) = \frac{20 \cdot 19 \cdot 18}{6} = 1140$ — three factors instead of seventeen.

(5 12) = \frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{120} = \frac{95 040}{120} = 792.

Absorption: the left side is $5 \cdot 792 = 3960$ ; the right side is $12 (4 11) = 12 \cdot \frac{11 \cdot 10 \cdot 9 \cdot 8}{24} = 12 \cdot 330 = 3960$ . ✓ Both count the $3960$ five-person committees with a designated chair drawn from twelve people.□

Exercises for §1.8 →

1.9Pascal's Rule and Subset Identities

The identities in this section all have the same two-line shape: describe a set, count it twice. They are the working vocabulary of combinatorial proof.

Theorem 1.49 (Pascal's rule). For all integers $n \geq 1$ and all integers $k$ ,

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

Proof. Fix the element $n \in [n]$ and split the $k$ -subsets of $[n]$ into two disjoint classes according to whether they contain $n$ .

Those that contain $n$ are determined by their other $k - 1$ elements, chosen from $[n - 1]$ : there are $(k - 1 n - 1)$ of them. Those that do not contain $n$ are $k$ -subsets of $[n - 1]$ : there are $(k n - 1)$ . The two classes are disjoint and exhaust all $k$ -subsets, so the addition rule gives the identity.

The edge cases are covered by the zero convention: for $k \leq 0$ or $k > n$ both sides reduce to the same value ( $1 = 1 + 0$ at $k = 0$ , $0 = 0 + 0$ beyond the range).∎

Proposition 1.50 (Total number of subsets). For every integer $n \geq 0$ ,

k = 0 \sum n (k n) = 2^{n} .

Proof. Both sides count the subsets of $[n]$ . The right side does so by the power-set corollary (each element independently in or out). The left side classifies the subsets by their size $k$ — the classes are disjoint and exhaust the power set — and the addition rule sums the class sizes.∎

Proposition 1.51 (Alternating sum). For every integer $n \geq 1$ ,

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

equivalently an $n$ -set has as many even-sized subsets as odd-sized ones, namely $2^{n - 1}$ of each.

Proof. Exhibit a bijection between even and odd subsets. Fix the element $1$ and define $φ (A) = A △ {1}$ , i.e. remove $1$ from $A$ if present and adjoin it otherwise. Then $φ$ changes $∣ A ∣$ by exactly $\pm 1$ , so it swaps parity, and $φ (φ (A)) = A$ , so it is a bijection. Hence the even-sized and odd-sized subsets are equinumerous; since together they number $2^{n}$ , each class has $2^{n - 1}$ members, and the alternating sum — which is (evens) minus (odds) — vanishes. The hypothesis $n \geq 1$ is needed for the element $1$ to exist; for $n = 0$ the sum is $1$ , not $0$ .∎

Proposition 1.52 (Weighted subset sum). For every integer $n \geq 1$ ,

k = 0 \sum n k (k n) = n 2^{n - 1} .

Proof. Double count the pairs $(A, x)$ with $A \subseteq [n]$ and $x \in A$ — a subset with a designated leader, of any size. Grouping by the size $k$ of $A$ gives $\sum_{k} k (k n)$ . Grouping instead by the leader gives: $n$ choices of $x$ , then any subset of the remaining $n - 1$ elements to complete $A$ , that is $n 2^{n - 1}$ . Equating the two counts proves the identity. (Alternatively, sum the absorption identity $k (k n) = n (k - 1 n - 1)$ over $k$ and apply the subset sum to row $n - 1$ .)∎

Intuition. The rhythm of a double count is always the same: name a set of pairs (or of decorated objects), then count it by deciding the two coordinates in either order. "Committee with a chair" proves absorption; "subset with a leader" proves the weighted sum; "choose the first-year members, then the rest" will prove Vandermonde.

This is why combinatorial proofs feel like explanations rather than verifications: the identity is true because both sides are names for the same objects.

Example 1.53 (Pascal's rule at work). Verify Pascal's rule for $n = 5$ , $k = 2$ , and use the rule alone to compute $(3 6)$ from row $4$ of Pascal's triangle ( $1, 4, 6, 4, 1$ ).

Solution. Verification: $(2 5) = \frac{5 \cdot 4}{2} = 10$ , while $(1 4) + (2 4) = 4 + 6 = 10$ . ✓

Row $5$ from row $4$ by adding adjacent pairs and capping with $1$ s: $1, 1 + 4 = 5, 4 + 6 = 10, 6 + 4 = 10, 4 + 1 = 5, 1$ . So row $5$ is $1, 5, 10, 10, 5, 1$ . Then $(3 6) = (2 5) + (3 5) = 10 + 10 = 20$ .

Sanity check against the formula. $(3 6) = \frac{6 \cdot 5 \cdot 4}{6} = 20$ ✓, and row $5$ sums to $32 = 2^{5}$ ✓.□

Example 1.54 (Counting with a parity condition). How many subsets of $[10]$ have an odd number of elements? How many have at least $8$ elements?

Solution. By the alternating-sum proposition, exactly half of the $2^{10} = 1024$ subsets are odd-sized: $2^{9} = 512$ .

For the second, sum the top three terms of row $10$ :

(8 10) + (9 10) + (10 10) = 45 + 10 + 1 = 56.

Sanity check on the first by direct summation: $(1 10) + (3 10) + (5 10) + (7 10) + (9 10) = 10 + 120 + 252 + 120 + 10 = 512$ . ✓□

Exercises for §1.9 →

1.10Pascal's Triangle and Lattice Paths

Definition 1.55 (Pascal's triangle). Pascal's triangle is the infinite triangular array whose $n$ -th row (rows indexed from $0$ ) is

(0 n), (1 n), \dots, (n n) .

By Pascal's rule each interior entry is the sum of the two entries above it, and each row begins and ends with $1$ .

The array can therefore be generated by addition alone, with no factorials and no multiplication:

11112113311464115101051

Reading the triangle in different directions recovers the identities of the previous section as visual facts: rows are symmetric (symmetry of $(k n)$ ), row sums are $1, 2, 4, 8, \dots$ (the subset sum), the alternating sum of any row from row $1$ down is zero, and the second diagonal $1, 3, 6, 10, \dots$ consists of the triangular numbers $(2 m) = m (m - 1) /2$ .

Intuition. Each entry is the sum of its two parents because a $k$ -subset of $[n]$ either takes the new element $n$ (left parent) or does not (right parent). The triangle is the recursion made visible.

Every counting question of the form "how many ways to choose $k$ from $n$ " for small $n$ can be read off the triangle faster than any formula can be evaluated.

Binomial coefficients also count paths on a grid, and this reading makes several identities geometrically obvious.

Theorem 1.56 (Lattice paths). The number of paths in the integer lattice from $(0, 0)$ to $(a, b)$ using only unit steps right ( $R$ ) and up ( $U$ ) is

(a a + b) = (b a + b) .

Proof. A path consists of exactly $a + b$ steps, of which exactly $a$ are $R$ and $b$ are $U$ (each $R$ raises the first coordinate by $1$ and each $U$ the second, and the endpoint requires those totals). Encode a path as the word of its steps, a string in ${R, U}^{a + b}$ with $a$ letters $R$ . This encoding is a bijection: the word determines the path step by step, and the path determines the word.

By the combination formula, the number of such words is the number of ways to choose which $a$ of the $a + b$ positions carry an $R$ , namely $(a a + b)$ ; equivalently a multiset permutation, $\frac{( a + b )!}{a ! b !}$ , which is the same number.∎

Figure 1.57. Pascal's triangle laid on the lattice. The number written at each node is the count of right/up paths reaching it from the origin, which is

(i i + j)

(i, j)

. Every interior node's number is the sum of the node to its left and the node below it, because a path arrives by a final step from exactly one of those two — that is Pascal's rule, drawn. The highlighted route is one of the

(2 5) = 10

paths to

(3, 2)

Corollary 1.58 (Pascal's rule, geometrically). The lattice-path count satisfies $(a a + b) = (a - 1 a + b - 1) + (a a + b - 1)$ , since every path to $(a, b)$ arrives by its last step either from $(a - 1, b)$ or from $(a, b - 1)$ , and the two cases are disjoint.

Proof. Classify paths to $(a, b)$ by their final step. If the final step is $R$ , the rest of the path is an arbitrary path to $(a - 1, b)$ , and there are $(a - 1 a + b - 1)$ of those. If it is $U$ , the rest is a path to $(a, b - 1)$ , of which there are $(a a + b - 1)$ . Disjoint and exhaustive, so the addition rule applies. This is Pascal's rule with $n = a + b$ , $k = a$ .∎

Example 1.59 (Blocked grid). A city grid runs $6$ blocks east and $4$ blocks north. How many shortest routes from the south-west corner to the north-east corner (a) in total, (b) pass through the point $3$ east and $2$ north, (c) avoid that point?

Solution. (a) $(4 6 + 4) = (4 10) = 210$ .

(b) A route through $(3, 2)$ splits uniquely into a route to $(3, 2)$ and a route from $(3, 2)$ onward, and the two halves can be chosen independently:

(2 5) \cdot (2 5) = 10 \cdot 10 = 100.

(c) Complementary counting: $210 - 100 = 110$ .

Sanity check on (b): the split is a bijection between full routes through the point and pairs (first half, second half), which is what licenses the multiplication; and $100 < 210$ as it must be.□

Example 1.60 (Words and paths are the same object). Count the binary strings of length $9$ with exactly $4$ ones, and interpret the count as a path.

Solution. Choose which $4$ of the $9$ positions hold a one:

(4 9) = \frac{9 \cdot 8 \cdot 7 \cdot 6}{24} = 126.

Reading a one as a step up and a zero as a step right, each string is a lattice path from $(0, 0)$ to $(5, 4)$ , and $(4 9) = (5 9) = 126$ ✓ — the symmetry of the binomial coefficient is the symmetry of swapping the roles of the two coordinates.□

Exercises for §1.10 →

1.11The Binomial and Multinomial Theorems

The binomial coefficients were defined by counting subsets. The following theorem is the reason they are called binomial: they are exactly the coefficients that appear when a two-term sum is raised to a power.

Theorem 1.61 (Binomial theorem). For all elements $x, y$ of a commutative ring (in particular all real or complex numbers) and every integer $n \geq 0$ ,

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

Proof. Combinatorial proof. Write the left side as a product of $n$ identical factors

(x + y) (x + y) \dots (x + y) .

Expanding by distributivity without collecting terms produces exactly one summand for each way of choosing one term — either $x$ or $y$ — from each of the $n$ factors; there are $2^{n}$ such summands, and each is a product of $n$ letters. A summand equals $x^{n - k} y^{k}$ precisely when $y$ was chosen from exactly $k$ of the factors, and the set of those $k$ factors may be any $k$ -subset of the $n$ factors. By the combination formula there are $(k n)$ such choices, so after collecting like terms the coefficient of $x^{n - k} y^{k}$ is $(k n)$ . Commutativity is what allows the letters within a summand to be reordered into the form $x^{n - k} y^{k}$ .

Second proof, by induction on $n$ . For $n = 0$ both sides are $1$ . Assume the formula for $n - 1$ . Then

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

In the second sum substitute $k = j + 1$ , and in the first write $k = j$ ; the coefficient of $x^{n - k} y^{k}$ in the total is then $(k n - 1) + (k - 1 n - 1)$ , which equals $(k n)$ by Pascal's rule (the zero convention handles $k = 0$ and $k = n$ ).∎

Corollary 1.62 (Specialisations). Setting $x = y = 1$ gives $\sum_{k} (k n) = 2^{n}$ ; setting $x = 1$ , $y = - 1$ gives $\sum_{k} (- 1)^{k} (k n) = 0$ for $n \geq 1$ ; setting $x = 1$ , $y = t$ gives the generating polynomial $(1 + t)^{n} = \sum_{k} (k n) t^{k}$ .

Proof. Each is a direct substitution into the theorem. Note that the first two re-prove, by algebra, the subset sum and alternating sum established combinatorially earlier — a good illustration that identities of this kind usually admit both a counting proof and an algebraic one.∎

Intuition. $(1 + t)^{n} = \sum_{k} (k n) t^{k}$ says: the polynomial $(1 + t)^{n}$ is a catalogue of the subsets of $[n]$ , in which the coefficient of $t^{k}$ records how many have size $k$ . Algebraic manipulation of the polynomial then becomes manipulation of the whole family of counts at once. That idea, pushed further, is the theory of generating functions.

Pitfall. In the term $(k n) x^{n - k} y^{k}$ the index $k$ is the exponent on the second letter. When asked for "the coefficient of $x^{3}$ in $(2 x - 5)^{7}$ ", identify the roles first: here $x$ plays the role of the second letter (exponent $3$ , so $k = 3$ counted from the constant term) — safest is to write the expansion explicitly as $\sum_{k} (k 7) (2 x)^{k} (- 5)^{7 - k}$ and read off $k = 3$ , giving $(3 7) \cdot 2^{3} \cdot (- 5)^{4} = 35 \cdot 8 \cdot 625 = 175000$ . Forgetting to raise the numerical factors $2$ and $- 5$ to their powers is the single most common slip in these questions.

The generalisation to more than two terms uses the multinomial coefficients of the earlier section.

Theorem 1.63 (Multinomial theorem). For commuting $x_{1}, \dots, x_{r}$ and an integer $n \geq 0$ ,

(x_{1} + x_{2} + \dots + x_{r})^{n} = k_{1} + \dots + k_{r} = n k_{i} \geq 0 \sum (k _{1} , k _{2} , \dots , k _{r} n) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{r}^{k_{r}} .

Proof. Expand the product of $n$ factors $(x_{1} + \dots + x_{r})$ by distributivity. Each summand is obtained by choosing one of the $r$ letters from each factor, so the summands correspond bijectively to the words of length $n$ over the alphabet ${x_{1}, \dots, x_{r}}$ . A word contributes $x_{1}^{k_{1}} \dots x_{r}^{k_{r}}$ exactly when it uses letter $i$ precisely $k_{i}$ times, and the number of such words is the multiset permutation count $\frac{n !}{k _{1} ! \dots k _{r} !}$ by the multiset theorem. Collecting like terms gives the stated coefficient. For $r = 2$ this is the binomial theorem.∎

Corollary 1.64 (Number of monomials and the total). The expansion has $(n n + r - 1)$ distinct monomials, and setting every $x_{i} = 1$ gives $\sum (k _{1} , \dots , k _{r} n) = r^{n}$ .

Proof. The monomials correspond to the exponent vectors $(k_{1}, \dots, k_{r})$ with $k_{i} \geq 0$ and $\sum k_{i} = n$ , counted by stars and bars as $(n n + r - 1)$ . The second statement is the theorem evaluated at $x_{i} = 1$ , whose left side is $r^{n}$ — equivalently, the total number of words of length $n$ over an $r$ -letter alphabet, classified by their letter multiplicities.∎

Theorem 1.65 (Newton's generalised binomial series). For any real $α$ and any real $t$ with $∣ t ∣ < 1$ ,

(1 + t)^{α} = k = 0 \sum \infty (k α) t^{k},

the series converging absolutely. When $α$ is a non-negative integer, all terms with $k > α$ vanish and the series is the finite binomial expansion.

Remark. This is an analytic statement, not a combinatorial one: the proof requires Taylor's theorem with a remainder estimate (or the theory of ordinary differential equations applied to $f (t) = (1 + t)^{α}$ , which satisfies $(1 + t) f^{'} = α f$ ), together with a convergence argument on $∣ t ∣ < 1$ . Neither is in scope here, so we state it without proof and record only the combinatorially useful case $α = - m$ for a positive integer $m$ , where

(k - m) = (- 1)^{k} (k m + k - 1),

so that $(1 - t)^{- m} = \sum_{k \geq 0} (k m + k - 1) t^{k}$ — a generating function whose coefficients are exactly the stars-and-bars counts. That is not a coincidence: it is the statement that distributing $k$ identical items among $m$ boxes is the $k$ -th coefficient of the $m$ -fold product $(1 + t + t^{2} + \dots)^{m}$ .

Example 1.66 (Expansion and a single coefficient). (a) Expand $(a + b)^{4}$ . (b) Find the coefficient of $x^{5} y^{3}$ in $(2 x - y)^{8}$ . (c) Find the coefficient of $x^{2} y^{3} z$ in $(x + y + z)^{6}$ .

Solution. (a) Row $4$ of Pascal's triangle is $1, 4, 6, 4, 1$ , so

(a + b)^{4} = a^{4} + 4 a^{3} b + 6 a^{2} b^{2} + 4 a b^{3} + b^{4} .

Check: at $a = b = 1$ both sides are $16 = 2^{4}$ ✓, and each term's exponents sum to $4$ ✓.

(b) Write $(2 x - y)^{8} = \sum_{k} (k 8) (2 x)^{8 - k} (- y)^{k}$ . The term with $y^{3}$ has $k = 3$ , and then $x$ carries exponent $5$ as required:

(3 8) \cdot 2^{5} \cdot (- 1)^{3} = 56 \cdot 32 \cdot (- 1) = - 1792.

(c) By the multinomial theorem with $(k_{1}, k_{2}, k_{3}) = (2, 3, 1)$ :

(2 , 3 , 1 6) = \frac{6 !}{2 ! 3 ! 1 !} = \frac{720}{12} = 60.

Sanity check on (c): the sum of all multinomial coefficients for $n = 6$ , $r = 3$ is $3^{6} = 729$ , and $60$ is a plausible share of it; the exponents $2 + 3 + 1 = 6$ ✓.□

Exercises for §1.11 →

1.12Vandermonde, the Hockey Stick, and Double Counting

This closing section collects the two identities that appear most often in applications, and proves both by double counting. The pattern to internalise is that the proof strategy — describe a set, classify its elements, count each class — is more valuable than either identity.

Theorem 1.67 (Vandermonde's identity). For non-negative integers $m, n$ and any integer $r \geq 0$ ,

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

Proof. Let $M$ be a set of $m$ women and $N$ a set of $n$ men, disjoint, so $∣ M \cup N ∣ = m + n$ . Count the $r$ -element subsets of $M \cup N$ in two ways.

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

By classification: sort the $r$ -subsets according to how many of their elements come from $M$ , say $j$ of them, where $0 \leq j \leq r$ . The classes are pairwise disjoint and exhaust all $r$ -subsets. A subset in class $j$ is determined by choosing its $j$ elements from $M$ ( $(j m)$ ways) and its remaining $r - j$ elements from $N$ ( $(r - j n)$ ways), independently, so the class has $(j m) (r - j n)$ members by the product rule. The addition rule over $j$ gives the sum.

The zero convention makes the formula correct even when $r > m$ or $r > n$ : the impossible terms simply vanish.∎

Corollary 1.68 (Sum of squares of a row). For every integer $n \geq 0$ ,

k = 0 \sum n (k n)^{2} = (n 2 n) .

Proof. Apply Vandermonde with $m = n$ and $r = n$ :

(n 2 n) = k = 0 \sum n (k n) (n - k n) = k = 0 \sum n (k n)^{2},

the last step by the symmetry $(n - k n) = (k n)$ .∎

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

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

Proof. Count the $(r + 1)$ -element subsets of $[m + 1]$ by their largest element. Every such subset has a unique largest element, so the classes are disjoint and exhaustive. If the largest element is $i + 1$ (which requires $i + 1 \geq r + 1$ , i.e. $i \geq r$ , and $i + 1 \leq m + 1$ , i.e. $i \leq m$ ), the remaining $r$ elements form an arbitrary $r$ -subset of ${1, \dots, i}$ , of which there are $(r i)$ . Summing over the possible largest elements gives $\sum_{i = r}^{m} (r i)$ , and the total is $(r + 1 m + 1)$ .∎

Figure 1.70. The hockey stick for

r = 2

m = 5

. The shaft runs down a diagonal of constant lower index —

(2 2), (2 3), (2 4), (2 5) = 1, 3, 6, 10

— and the blade is the entry one step down and across,

(3 6) = 20

, which is their sum. The bend matters: the total does not lie at the diagonal's continuation (

15

) but on the other side, because the classification is by the largest element chosen, and adjoining that element shifts both indices.

Intuition. The name comes from the picture: the summands $(r r), (r r + 1), \dots, (r m)$ lie along a diagonal of Pascal's triangle (the shaft of the stick) and the answer $(r + 1 m + 1)$ sits one step off the end, in the row below and to the side (the blade).

The special case $r = 1$ is the schoolroom formula $1 + 2 + \dots + m = (2 m + 1) = \frac{m ( m + 1 )}{2}$ , and $r = 2$ sums the triangular numbers.

Pitfall. The hockey-stick sum runs down a diagonal with the lower index fixed, not across a row. The superficially similar $\sum_{i = r}^{m} (i m)$ — a partial row sum — has no closed form at all; only the complete row sums to $2^{m}$ . Confusing the two is common; check which index is moving before reaching for the identity.

Example 1.71 (Vandermonde in a committee problem). A department has $7$ mathematicians and $5$ statisticians. How many committees of $4$ can be formed? Verify the answer by splitting on the number of mathematicians.

Solution. Directly: $(4 12) = \frac{12 \cdot 11 \cdot 10 \cdot 9}{24} = 495$ .

By Vandermonde with $m = 7$ , $n = 5$ , $r = 4$ , classifying by the number $j$ of mathematicians:

j = 0 \sum 4 (j 7) (4 - j 5) = 1 \cdot 5 + 7 \cdot 10 + 21 \cdot 10 + 35 \cdot 5 + 35 \cdot 1 = 5 + 70 + 210 + 175 + 35 = 495. ✓

The classification is also the efficient route to constrained versions: committees with at least one of each specialty are $495 - (4 7) - (4 5) = 495 - 35 - 5 = 455$ .□

Example 1.72 (Hockey stick and a running total). Evaluate $\sum_{i = 2}^{6} (2 i)$ , and use the identity to find $1 + 3 + 6 + 10 + 15 + 21 + 28$ .

Solution. By the hockey-stick identity with $r = 2$ , $m = 6$ :

i = 2 \sum 6 (2 i) = (3 7) = \frac{7 \cdot 6 \cdot 5}{6} = 35.

Direct check: $1 + 3 + 6 + 10 + 15 = 35$ . ✓

The second sum is the first seven triangular numbers, that is $\sum_{i = 2}^{8} (2 i)$ , so it equals $(3 9) = \frac{9 \cdot 8 \cdot 7}{6} = 84$ . Direct check: $1 + 3 + 6 + 10 + 15 + 21 + 28 = 84$ . ✓□

Example 1.73 (A double count with no formula in sight). Prove that $\sum_{k = 0}^{n} k^{2} (k n) = n (n + 1) 2^{n - 2}$ for $n \geq 2$ .

Solution. Double count the triples $(A, x, y)$ with $A \subseteq [n]$ , $x \in A$ and $y \in A$ , where $x$ and $y$ may coincide — "a subset with a chair and a secretary, possibly the same person".

Grouping by the size $k$ of $A$ : there are $(k n)$ subsets of size $k$ and $k \cdot k = k^{2}$ choices of the ordered pair $(x, y)$ inside it, giving $\sum_{k} k^{2} (k n)$ .

Grouping instead by whether $x = y$ :

If $x = y$ : choose the common person ( $n$ ways) and any subset of the remaining $n - 1$ elements to complete $A$ ( $2^{n - 1}$ ), giving $n 2^{n - 1}$ .
If $x \neq = y$ : choose the ordered pair ( $n (n - 1)$ ways) and any subset of the remaining $n - 2$ elements ( $2^{n - 2}$ ), giving $n (n - 1) 2^{n - 2}$ .

Adding the two disjoint cases,

n 2^{n - 1} + n (n - 1) 2^{n - 2} = 2^{n - 2} (2 n + n^{2} - n) = n (n + 1) 2^{n - 2} .

Sanity check at $n = 3$ : the left side is $1 \cdot 3 + 4 \cdot 3 + 9 \cdot 1 = 24$ , and $n (n + 1) 2^{n - 2} = 3 \cdot 4 \cdot 2 = 24$ . ✓□

Summary (The identities of this chapter).

Symmetry: $(k n) = (n - k n)$ .
Pascal: $(k n) = (k - 1 n - 1) + (k n - 1)$ .
Absorption: $k (k n) = n (k - 1 n - 1)$ .
Row sum: $\sum_{k} (k n) = 2^{n}$ ; alternating: $\sum_{k} (- 1)^{k} (k n) = 0$ for $n \geq 1$ .
Weighted: $\sum_{k} k (k n) = n 2^{n - 1}$ .
Vandermonde: $\sum_{j} (j m) (r - j n) = (r m + n)$ ; squares: $\sum_{k} (k n)^{2} = (n 2 n)$ .
Hockey stick: $\sum_{i = r}^{m} (r i) = (r + 1 m + 1)$ .
Binomial theorem: $(x + y)^{n} = \sum_{k} (k n) x^{n - k} y^{k}$ ; multinomial: coefficients $\frac{n !}{k _{1} ! \dots k _{r} !}$ .

Exercises for §1.12 →

Common Mistakes

Multiplying when the option count varies. The product rule needs the number of options at each stage to be constant, not the options themselves. "Pick a non-empty subset, then pick a member of it" is not $15 \cdot ∣ A ∣$ ; it needs a sum over subset sizes (and equals $n 2^{n - 1}$ ).
Adding overlapping cases. "Red cars OR fast cars" double-counts the fast red ones; inclusion–exclusion subtracts the overlap back out.
Dividing by a symmetry that fixes something. $n! / (2 n)$ for bracelets and $n! /2!$ for LEVEL are both invalid divisions — the fibres are not all the same size. Check before dividing.
Assuming $0! = 0$ . It is $1$ , the empty product, and every formula here ( $P (n, n)$ , $(0 n)$ , the recursion $n! = n (n - 1)!$ ) breaks without it.
Treating "with repetition" as a single model. With repetition and order gives $n^{k}$ ; with repetition and no order gives $(k n + k - 1)$ ; the two differ wildly and no division converts one into the other.
Reaching for a formula before fixing the model. Decide first: ordered or not, repetition or not, labelled boxes or not. The formula follows from the model; guessing the formula first is how $n^{k}$ , $P (n, k)$ , $(k n)$ and $(k n + k - 1)$ get interchanged.
Dividing $n^{k}$ by $k!$ to "remove the order". Invalid whenever repetition is allowed, because multisets with repeats have fewer orderings than those without. Use stars and bars.
Using stars and bars on distinguishable items. $(k n + k - 1)$ counts identical items in labelled boxes. Labelled items in labelled boxes is $k^{n}$ ; identical items in identical boxes is a partition number with no closed form.
Forgetting the zero convention. $(k n) = 0$ for $k > n$ or $k < 0$ is what makes Pascal's rule, Vandermonde and the hockey stick true without case analysis.
Misreading the index in the binomial theorem. In $(k n) x^{n - k} y^{k}$ the index $k$ is the exponent on the second letter, and numerical factors inside the letters must be raised to their powers too.
Confusing a diagonal sum with a row sum. $\sum_{i = r}^{m} (r i) = (r + 1 m + 1)$ is a diagonal; a partial row sum $\sum_{i \leq j} (i m)$ has no closed form.

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