Contents / Combinatorics / Special Sequences

Chapter 4

Special Sequences

Fibonacci, Catalan, Stirling, Bell, Eulerian and the partition numbers — what each counts and how each is computed.

Introduction

Fibonacci, Catalan, Stirling, Bell, Eulerian and the partition numbers — what each counts and how each is computed.

4.1Linear Recurrences: Fibonacci and Lucas Numbers

The Fibonacci numbers are the smallest interesting example of a linear recurrence, and everything the general theory can say is already visible in them: a closed form built from the roots of a quadratic, a rational generating function, an exponential growth rate, and a supply of identities that all descend from a single matrix.

Definition 4.1 (Fibonacci and Lucas numbers). The Fibonacci numbers are defined by

F_{0} = 0, F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2} (n \geq 2),

and the Lucas numbers by the same recurrence with different seeds,

L_{0} = 2, L_{1} = 1, L_{n} = L_{n - 1} + L_{n - 2} (n \geq 2) .

The sequences begin

F : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots L : 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, \dots

Pitfall. Indexing conventions differ between books. Here $F_{0} = 0$ and $F_{1} = F_{2} = 1$ , so $F_{10} = 55$ . Sources that start the sequence at $F_{1} = 1, F_{2} = 2$ shift every index by one, and every identity below then acquires an off-by-one. Fix the convention first and check it against a known value — $F_{10} = 55$ is a convenient anchor — before using a formula you did not derive yourself.

Both sequences satisfy the same recurrence, and that recurrence is linear and homogeneous with constant coefficients. Such recurrences can be solved in complete generality, and it costs nothing to do the general case.

Theorem 4.2 (Solution of a second-order linear recurrence). Let $a, b$ be complex numbers with $b \neq = 0$ and suppose the characteristic polynomial $t^{2} - a t - b$ has two distinct roots $r \neq = s$ . Then a sequence $(u_{n})_{n \geq 0}$ satisfies

u_{n} = a u_{n - 1} + b u_{n - 2} (n \geq 2)

if and only if there are constants

A, B

with

u_{n} = A r^{n} + B s^{n}

for all

n \geq 0

. The constants are determined uniquely by

u_{0}

and

u_{1}

Proof. ( $\Leftarrow$ ) If $u_{n} = A r^{n} + B s^{n}$ then, because $r^{2} = a r + b$ and $s^{2} = a s + b$ ,

a u_{n - 1} + b u_{n - 2} = A r^{n - 2} (a r + b) + B s^{n - 2} (a s + b) = A r^{n} + B s^{n} = u_{n} .

( $\Rightarrow$ ) The recurrence determines $u_{n}$ for all $n$ from the two values $u_{0}, u_{1}$ , so it suffices to find $A, B$ matching those two values; the two sequences then agree everywhere by induction. The system

A + B = u_{0}, A r + B s = u_{1}

has determinant

s - r \neq = 0

, hence exactly one solution, namely

A = (u_{1} - s u_{0}) / (r - s)

and

B = (r u_{0} - u_{1}) / (r - s)

.∎

The characteristic polynomial of the Fibonacci recurrence is $t^{2} - t - 1$ , whose roots are the golden ratio and its conjugate,

φ = \frac{1 + 5}{2} \approx 1.6180, ψ = \frac{1 - 5}{2} = - \frac{1}{φ} \approx - 0.6180.

They satisfy

φ + ψ = 1

φ ψ = - 1

φ - ψ = 5

, and — the identity that does most of the work below —

φ^{2} = φ + 1

ψ^{2} = ψ + 1

Theorem 4.3 (Binet's formula). For all $n \geq 0$ ,

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}, L_{n} = φ^{n} + ψ^{n} .

Proof. Both sequences satisfy the recurrence with $a = b = 1$ , whose characteristic roots $φ \neq = ψ$ are distinct, so Theorem Solution of a second-order linear recurrence applies and it remains only to match two initial values for each sequence.

For $F$ : the proposed formula gives $(φ^{0} - ψ^{0}) / 5 = 0 = F_{0}$ and $(φ - ψ) / 5 = 5 / 5 = 1 = F_{1}$ .

For $L$ : it gives $φ^{0} + ψ^{0} = 2 = L_{0}$ and $φ + ψ = 1 = L_{1}$ .

Since the initial values match and both sides obey the same recurrence, the two sides agree for every $n$ .∎

That an integer sequence has a closed form built out of $5$ is less strange than it looks: the irrational parts of $φ^{n}$ and $ψ^{n}$ are equal and opposite, so they cancel in the difference. The formula is genuinely useful in practice, because the second term is tiny.

Corollary 4.4 (Rounding form and growth rate). For every $n \geq 0$ , $F_{n}$ is the nearest integer to $φ^{n} / 5$ . Consequently $F_{n + 1} / F_{n} \to φ$ as $n \to \infty$ .

Proof. By Binet, $F_{n} - φ^{n} / 5 = - ψ^{n} / 5$ , and $∣ ψ ∣ = 0.6180 \dots < 1$ , so

F_{n} - \frac{φ ^{n}}{5} = \frac{∣ ψ ∣ ^{n}}{5} \leq \frac{1}{5} < \frac{1}{2}

for all

n \geq 0

. An integer within distance

1/2

of a real number is the nearest integer to it.

For the ratio, divide Binet's formula for $F_{n + 1}$ by the one for $F_{n}$ and factor out $φ$ :

\frac{F _{n + 1}}{F _{n}} = φ \cdot \frac{1 - ( ψ / φ ) ^{n + 1}}{1 - ( ψ / φ ) ^{n}} (n \geq 1),

and

∣ ψ / φ ∣ = φ^{- 2} < 1

, so both correction factors tend to

1

.∎

Intuition. Binet's formula says the Fibonacci numbers are one geometric sequence with a vanishing tremor on top. The $φ^{n}$ term is the whole story; the $ψ^{n}$ term is a correction that alternates in sign and shrinks by a factor of $1.618$ each step. That is why $F_{n + 1} / F_{n}$ settles down to the golden ratio so fast — the ratio is already right to four decimal places at $F_{10} / F_{9} = 55/34$ .

Generating functions give a second derivation, and one that generalises to recurrences of any order.

Proposition 4.5 (Fibonacci and Lucas generating functions). As formal power series,

n \geq 0 \sum F_{n} x^{n} = \frac{x}{1 - x - x ^{2}}, n \geq 0 \sum L_{n} x^{n} = \frac{2 - x}{1 - x - x ^{2}} .

Proof. Write $F (x) = \sum_{n \geq 0} F_{n} x^{n}$ . Then

(1 - x - x^{2}) F (x) = n \geq 0 \sum F_{n} x^{n} - n \geq 0 \sum F_{n} x^{n + 1} - n \geq 0 \sum F_{n} x^{n + 2} = n \geq 0 \sum (F_{n} - F_{n - 1} - F_{n - 2}) x^{n},

with the convention

F_{- 1} = F_{- 2} = 0

. Every coefficient with

n \geq 2

vanishes by the recurrence; the

n = 0

coefficient is

F_{0} = 0

and the

n = 1

coefficient is

F_{1} - F_{0} = 1

. So

(1 - x - x^{2}) F (x) = x

. The Lucas computation is identical: the

n = 0

coefficient is

L_{0} = 2

and the

n = 1

coefficient is

L_{1} - L_{0} = - 1

.∎

The denominator $1 - x - x^{2}$ is the characteristic polynomial written backwards, and that is the general phenomenon: a sequence satisfies a linear recurrence with constant coefficients if and only if its generating function is a rational function whose denominator is the reversed characteristic polynomial.

The Fibonacci numbers are not merely an analytic object. They count something, and the combinatorial reading proves identities that would be tedious algebraically.

Theorem 4.6 (Fibonacci numbers count tilings). Let $t_{n}$ be the number of ways to tile a $1 \times n$ strip of unit cells with squares ( $1 \times 1$ ) and dominoes ( $1 \times 2$ ). Then $t_{n} = F_{n + 1}$ for all $n \geq 0$ . Equivalently, $F_{n + 1}$ is the number of compositions of $n$ into parts equal to $1$ and $2$ , and $F_{n + 2}$ is the number of subsets of $[n]$ containing no two consecutive integers.

Proof. For the tilings: $t_{0} = 1$ (the empty tiling of the empty strip) and $t_{1} = 1$ . For $n \geq 2$ , classify a tiling by its leftmost piece. If it is a square, the rest is an arbitrary tiling of the remaining $n - 1$ cells, and there are $t_{n - 1}$ of those; if it is a domino, the rest is an arbitrary tiling of $n - 2$ cells, giving $t_{n - 2}$ . The two cases are disjoint and exhaustive, so $t_{n} = t_{n - 1} + t_{n - 2}$ . With $t_{0} = 1 = F_{1}$ and $t_{1} = 1 = F_{2}$ , induction gives $t_{n} = F_{n + 1}$ .

Reading a tiling left to right as the sequence of its piece-lengths is a bijection with compositions of $n$ into $1$ s and $2$ s, which proves the second statement.

For the third, let $s_{n}$ be the number of subsets $S \subseteq [n]$ with no two consecutive elements and split on whether $n \in S$ . If $n \in / S$ , the rest is any such subset of $[n - 1]$ : $s_{n - 1}$ choices. If $n \in S$ , then $n - 1 \in / S$ and the rest is any such subset of $[n - 2]$ : $s_{n - 2}$ choices. So $s_{n} = s_{n - 1} + s_{n - 2}$ with $s_{0} = 1 = F_{2}$ and $s_{1} = 2 = F_{3}$ , whence $s_{n} = F_{n + 2}$ .∎

Intuition. "Split on the first piece" is the whole of the combinatorial proof, and it explains why the Fibonacci numbers appear whenever a structure is built left to right out of two kinds of step, one short and one long: binary strings with no two consecutive $1$ s, coin-flip sequences with no two heads in a row, ways up a staircase taking one or two steps at a time. They are all the same count wearing different clothes.

Example 4.7 (A staircase with a broken step). A staircase has $10$ steps and you climb one or two at a time. How many routes are there, and how many of them avoid landing on step $6$ , which is broken?

Solution. The number of routes up $n$ steps is the number of compositions of $n$ into $1$ s and $2$ s, which is $F_{n + 1}$ by Theorem Fibonacci numbers count tilings. For $n = 10$ this is $F_{11} = 89$ .

A route avoiding step $6$ must step from $5$ to $7$ , since a stride has length at most $2$ . So such a route consists of a route up to step $5$ , the stride $5 \to 7$ , and a route covering the remaining $3$ steps: $F_{6} \cdot F_{4} = 8 \cdot 3 = 24$ routes.

Sanity check: routes that do land on step $6$ number $F_{7} \cdot F_{5} = 13 \cdot 5 = 65$ , and $65 + 24 = 89$ ✓.□

The matrix form packages the recurrence so tightly that several classical identities fall out of a single determinant.

Proposition 4.8 (Matrix form). Let $Q = (1110)$ . Then for all $n \geq 1$ ,

Q^{n} = (F_{n + 1} F_{n} F_{n} F_{n - 1}) .

Proof. For $n = 1$ the right-hand side is $(F_{2} F_{1} F_{1} F_{0}) = (1110) = Q$ . Assuming the formula for $n$ ,

Q^{n + 1} = Q^{n} Q = (F_{n + 1} F_{n} F_{n} F_{n - 1}) (1110) = (F_{n + 1} + F_{n} F_{n} + F_{n - 1} F_{n + 1} F_{n}) = (F_{n + 2} F_{n + 1} F_{n + 1} F_{n}),

which is the formula for

n + 1

.∎

Corollary 4.9 (Cassini's identity). For all $n \geq 1$ , $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ .

Proof. Take determinants in Proposition Matrix form. Since $det Q = - 1$ and the determinant is multiplicative, $det (Q^{n}) = (- 1)^{n}$ , while the displayed matrix has determinant $F_{n + 1} F_{n - 1} - F_{n}^{2}$ .∎

Corollary 4.10 (Addition formula). For $m \geq 1$ and $n \geq 1$ ,

F_{m + n} = F_{m + 1} F_{n} + F_{m} F_{n - 1} .

In particular

F_{2 n} = F_{n} L_{n}

and

F_{2 n + 1} = F_{n + 1}^{2} + F_{n}^{2}

Proof. Compare the $(1, 2)$ entries in $Q^{m + n} = Q^{m} Q^{n}$ . On the left that entry is $F_{m + n}$ ; on the right it is

(F_{m + 1} F_{m} F_{m} F_{m - 1}) (F_{n + 1} F_{n} F_{n} F_{n - 1})_{1, 2} = F_{m + 1} F_{n} + F_{m} F_{n - 1} .

Setting $m = n$ gives $F_{2 n} = F_{n + 1} F_{n} + F_{n} F_{n - 1} = F_{n} (F_{n + 1} + F_{n - 1})$ , and $F_{n + 1} + F_{n - 1} = L_{n}$ by Lemma Lucas from Fibonacci. Keeping $m = n$ but replacing the second index $n$ by $n + 1$ gives $F_{2 n + 1} = F_{n + 1} F_{n + 1} + F_{n} F_{n}$ .∎

Lemma 4.11 (Lucas from Fibonacci). For all $n \geq 1$ , $L_{n} = F_{n - 1} + F_{n + 1}$ .

Proof. By Binet,

5 (F_{n - 1} + F_{n + 1}) = φ^{n - 1} + φ^{n + 1} - ψ^{n - 1} - ψ^{n + 1} = φ^{n - 1} (1 + φ^{2}) - ψ^{n - 1} (1 + ψ^{2}) .

Now $φ^{2} = φ + 1$ , so

1 + φ^{2} = φ + 2 = 2 φ^{2} - φ = φ (2 φ - 1) = φ 5,

using

2 φ - 1 = 5

. The same computation for the conjugate root gives

1 + ψ^{2} = ψ + 2 = - ψ 5,

since

2 ψ - 1 = - 5

. Therefore

5 (F_{n - 1} + F_{n + 1}) = φ^{n - 1} \cdot φ 5 + ψ^{n - 1} \cdot ψ 5 = 5 (φ^{n} + ψ^{n}) = 5 L_{n} .

∎

Proposition 4.12 (Summation identities). For $n \geq 1$ ,

i = 1 \sum n F_{i} = F_{n + 2} - 1, i = 1 \sum n F_{i}^{2} = F_{n} F_{n + 1}, i = 1 \sum n F_{2 i - 1} = F_{2 n} .

Proof. Each is a telescope. For the first, $F_{i} = F_{i + 2} - F_{i + 1}$ , so the sum collapses to $F_{n + 2} - F_{2} = F_{n + 2} - 1$ .

For the second, $F_{i}^{2} = F_{i} (F_{i + 1} - F_{i - 1}) = F_{i} F_{i + 1} - F_{i - 1} F_{i}$ , so the sum collapses to $F_{n} F_{n + 1} - F_{0} F_{1} = F_{n} F_{n + 1}$ .

For the third, $F_{2 i - 1} = F_{2 i} - F_{2 i - 2}$ , and the sum collapses to $F_{2 n} - F_{0} = F_{2 n}$ .∎

Theorem 4.13 (The Fibonacci numbers are a strong divisibility sequence). For all $m, n \geq 1$ , $g cd (F_{m}, F_{n}) = F_{g c d (m, n)}$ . In particular $F_{m} ∣ F_{n}$ whenever $m ∣ n$ .

Proof. First, consecutive Fibonacci numbers are coprime: a prime $p$ dividing both $F_{n}$ and $F_{n + 1}$ would divide $F_{n - 1} = F_{n + 1} - F_{n}$ , and descending, it would divide $F_{1} = 1$ . So $g cd (F_{n}, F_{n + 1}) = 1$ , and likewise $g cd (F_{n}, F_{n - 1}) = 1$ .

Next, by Corollary Addition formula, $F_{m + n} = F_{m + 1} F_{n} + F_{m} F_{n - 1}$ . Every common divisor of $F_{n}$ and $F_{m + n}$ therefore divides $F_{m} F_{n - 1}$ , and being coprime to $F_{n - 1}$ it divides $F_{m}$ ; conversely every common divisor of $F_{m}$ and $F_{n}$ divides $F_{m + n}$ . The two gcds thus divide each other:

g cd (F_{m + n}, F_{n}) = g cd (F_{m}, F_{n}) .

That is the step of the Euclidean algorithm transported to indices: iterating it reduces

g cd (F_{m}, F_{n})

g cd (F_{m mod n}, F_{n})

, and repeating the reduction terminates at

g cd (F_{0}, F_{d}) = F_{d}

with

d = g cd (m, n)

, using

F_{0} = 0

.∎

Example 4.14 (A divisibility question answered by indices). Compute $g cd (F_{24}, F_{36})$ without computing either number.

Solution. By Theorem The Fibonacci numbers are a strong divisibility sequence, $g cd (F_{24}, F_{36}) = F_{g c d (24, 36)} = F_{12} = 144$ .

Sanity check on a case where the numbers are visible: $g cd (F_{6}, F_{9}) = g cd (8, 34) = 2 = F_{3}$ , and indeed $g cd (6, 9) = 3$ ✓.□

Theorem 4.15 (Zeckendorf representation). Every integer $N \geq 1$ has exactly one representation as a sum of non-consecutive Fibonacci numbers drawn from $F_{2}, F_{3}, F_{4}, \dots$ : that is, $N = F_{k_{1}} + F_{k_{2}} + \dots + F_{k_{r}}$ with $k_{1} > k_{2} > \dots > k_{r} \geq 2$ and $k_{i} - k_{i + 1} \geq 2$ for every $i$ .

Proof. Existence, by strong induction on $N$ . Let $F_{k}$ be the largest Fibonacci number with $F_{k} \leq N$ , so $k \geq 2$ . If $N = F_{k}$ we are done. Otherwise set $N^{'} = N - F_{k} \geq 1$ ; since $N < F_{k + 1}$ we get $N^{'} < F_{k + 1} - F_{k} = F_{k - 1}$ , so by induction $N^{'}$ is a sum of non-consecutive Fibonacci numbers, all of them smaller than $F_{k - 1}$ and hence of index at most $k - 2$ . Prepending $F_{k}$ preserves the gap condition.

Uniqueness. We claim that a sum of non-consecutive Fibonacci numbers with largest term $F_{k}$ is strictly less than $F_{k + 1}$ . The largest such sum is $F_{k} + F_{k - 2} + F_{k - 4} + \dots$ , terminating at $F_{2}$ or $F_{3}$ ; using $F_{j} = F_{j + 1} - F_{j - 1}$ the sum telescopes to $F_{k + 1} - F_{1} = F_{k + 1} - 1$ in the first case and to $F_{k + 1} - F_{2} = F_{k + 1} - 1$ in the second, so every such sum is at most $F_{k + 1} - 1 < F_{k + 1}$ . Now suppose $N$ had two different representations. Their largest terms cannot differ, for if they were $F_{k}$ and $F_{k^{'}}$ with $k < k^{'}$ then the first representation would be at most $F_{k + 1} - 1 < F_{k^{'}} \leq N$ , contradicting that it equals $N$ . So the largest terms agree; subtract them and induct on the number of terms.∎

Example 4.16 (Zeckendorf in practice). Write $100$ as a sum of non-consecutive Fibonacci numbers.

Solution. Greedily subtract the largest Fibonacci number that fits, exactly as in the existence proof.

The largest Fibonacci number $\leq 100$ is $F_{11} = 89$ , leaving $11$ . The largest $\leq 11$ is $F_{6} = 8$ , leaving $3$ . And $3 = F_{4}$ , so we stop.

Hence $100 = 89 + 8 + 3 = F_{11} + F_{6} + F_{4}$ . The indices $11, 6, 4$ have gaps $5$ and $2$ , both at least $2$ ✓, and $89 + 8 + 3 = 100$ ✓.□

Exercises for §4.1 →

4.2Catalan Numbers and What They Count

The Fibonacci recurrence adds two earlier terms. The next step up in complexity is a recurrence that multiplies two earlier terms and sums over how the object splits — a convolution — and the sequence it produces is the Catalan sequence, the most ubiquitous in combinatorics after the binomial coefficients.

Definition 4.17 (Catalan number). For an integer $n \geq 0$ the $n$ th Catalan number is

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

The sequence begins

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, \dots

Proposition 4.18 (The subtraction form). For $n \geq 1$ , $C_{n} = (n 2 n) - (n - 1 2 n)$ .

Proof. Expanding factorials,

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

Hence

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

.∎

That $C_{n}$ is an integer at all is not obvious from the definition — $(n 2 n)$ need not be divisible by $n + 1$ for any structural reason one can see at a glance — but the subtraction form settles it immediately, since it is a difference of two integers. The reason behind both forms is a family of paths.

Definition 4.19 (Dyck path and Dyck word). A Dyck path of semilength $n$ is a sequence of $2 n$ steps, each $U = (1, 1)$ or $D = (1, - 1)$ , starting at the origin, ending at $(2 n, 0)$ , and never going below the horizontal axis. Writing $U$ as ( and $D$ as ) turns a Dyck path into a Dyck word: a string of $n$ opening and $n$ closing brackets in which every prefix has at least as many openings as closings.

Theorem 4.20 (Catalan objects). For every $n \geq 0$ the following families all have exactly $C_{n}$ members.

Dyck paths of semilength $n$ , equivalently balanced bracket strings with $n$ pairs.
Monotone lattice paths from $(0, 0)$ to $(n, n)$ using unit east and north steps that never rise strictly above the diagonal $y = x$ .
Plane binary trees with $n$ internal nodes (equivalently $n + 1$ leaves).
Triangulations of a convex $(n + 2)$ -gon by non-crossing diagonals.
Non-crossing partitions of $n$ points arranged on a circle.
Permutations of $[n]$ avoiding the pattern $231$ — equivalently, the stack-sortable permutations.

Proof. We prove that the six families all satisfy the same recurrence and the same initial value; Theorem The Catalan recurrence in the next section shows that this recurrence together with $C_{0} = 1$ determines the sequence, and the section after that identifies its solution with $\frac{1}{n + 1} (n 2 n)$ .

(1) $\leftrightarrow$ (2) is a relabelling: replace $U$ by east and $D$ by north — a path that stays weakly below $y = x$ is one whose every prefix has at least as many east steps as north steps.

(1) The first-return decomposition. A non-empty Dyck path begins with $U$ and has a first later moment at which it returns to height $0$ ; that return step is a $D$ . Cutting there writes the path uniquely as $U P D Q$ where $P$ is a Dyck path of some semilength $i \geq 0$ and $Q$ a Dyck path of semilength $n - 1 - i$ . The decomposition is reversible, so the count $c_{n}$ of Dyck paths satisfies $c_{n} = \sum_{i = 0}^{n - 1} c_{i} c_{n - 1 - i}$ with $c_{0} = 1$ .

(3) A plane binary tree with $n \geq 1$ internal nodes consists of a root together with an ordered pair of subtrees with $i$ and $n - 1 - i$ internal nodes; the same recurrence and the same initial value follow. (Explicitly, the bijection with (1) is: traverse the tree in preorder, writing $U$ at each internal node and $D$ at each leaf but the last.)

(4) Fix an edge $e$ of the convex $(n + 2)$ -gon as the base. In any triangulation exactly one triangle contains $e$ ; its apex $v$ is one of the remaining $n$ vertices, and $v$ splits the rest of the polygon into an $(i + 2)$ -gon and a $(j + 2)$ -gon with $i + j = n - 1$ , each triangulated independently. Again the same recurrence, with the $2$ -gon contributing the empty triangulation and counting as $C_{0} = 1$ .

(5) A non-crossing partition of the points $1, \dots, n$ on a circle decomposes by the block $B$ containing point $1$ : the arcs between consecutive elements of $B$ must each be partitioned among themselves, so the count is a convolution of the same shape. The bookkeeping gives $\sum_{i} c_{i} c_{n - 1 - i}$ once more; we omit the routine index chase.

(6) For $231$ -avoiding permutations, split $π$ at the position of the value $n$ . Avoiding $231$ forces every entry left of $n$ to be smaller than every entry right of $n$ — otherwise a larger left entry, $n$ , and a smaller right entry would form a $231$ pattern. So $π$ is determined by a $231$ -avoiding permutation of the $i$ smallest values on the left and one of the remaining $n - 1 - i$ values on the right, giving the convolution again. That the $231$ -avoiding permutations are exactly the stack-sortable ones is Knuth's theorem; we use it only as a name here, and its proof (an induction on the stack discipline) is left aside.∎

Figure 4.21. The first-return decomposition of a Dyck path of semilength

5

. The opening step and the step that first returns the path to the axis (both in orange) enclose a Dyck path

P

of semilength

1

; everything after the return is a Dyck path

Q

of semilength

3

. Every non-empty Dyck path splits this way exactly once, which is the whole content of the Catalan recurrence.

Intuition. All six families are secretly the same recursive shape: an object is an atom together with two smaller objects of the same kind, split in every possible way. A bracket string is a matched pair wrapping one object and followed by another; a tree is a root with a left and a right subtree; a triangulation is a triangle on the base edge with a polygon hanging off each of its two other sides. Once you see the shape, the fact that the counts agree is not a coincidence to be memorised but a single theorem with six costumes.

Example 4.22 (The five bracket strings). List the Dyck words of semilength $3$ and check the count against the formula.

Solution. The formula gives $C_{3} = \frac{1}{4} (3 6) = \frac{20}{4} = 5$ .

Now list the strings and verify each is balanced, tracking the running count of openings minus closings, which must stay $\geq 0$ and finish at $0$ :

$((()))$ — counts $1, 2, 3, 2, 1, 0$ ✓ $(() ())$ — counts $1, 2, 1, 2, 1, 0$ ✓ $(()) ()$ — counts $1, 2, 1, 0, 1, 0$ ✓ $() (())$ — counts $1, 0, 1, 2, 1, 0$ ✓ $() () ()$ — counts $1, 0, 1, 0, 1, 0$ ✓

There is no sixth: any other arrangement of three openings and three closings begins with ) or contains a prefix such as ())( whose running count reaches $- 1$ . So the count is $5$ ✓.□

Example 4.23 (Triangulating a hexagon). How many triangulations does a convex hexagon have?

Solution. A hexagon is the $(n + 2)$ -gon with $n = 4$ , so the answer is $C_{4}$ .

Using the recurrence from the proof of Theorem Catalan objects,

C_{4} = C_{0} C_{3} + C_{1} C_{2} + C_{2} C_{1} + C_{3} C_{0} = 1 \cdot 5 + 1 \cdot 2 + 2 \cdot 1 + 5 \cdot 1 = 14.

Cross-check against the closed form: $(4 8) = 70$ and $70/5 = 14$ ✓. Each triangulation of a hexagon uses exactly $3$ triangles and $3$ diagonals, which is the general fact that a triangulated $(n + 2)$ -gon has $n$ triangles and $n - 1$ diagonals.□

Pitfall. Only plane (ordered) binary trees are counted by $C_{n}$ . If the two children of a node are unordered, or if the tree is unrooted, the count is a different and much harder sequence — the unlabelled rooted trees are counted by Otter's sequence $1, 1, 2, 4, 9, 20, 48, \dots$ , which has no closed form. Likewise, $C_{n}$ counts triangulations of a convex polygon with labelled vertices; identifying triangulations that differ by a rotation gives smaller counts.

Remark. Several close relatives share the Catalan style of recursion and are easy to confuse with it. The Motzkin numbers $1, 1, 2, 4, 9, 21, 51, \dots$ count lattice paths with up, down and flat steps staying weakly above the axis; the large Schröder numbers $1, 2, 6, 22, 90, \dots$ allow a diagonal step; the Fine numbers count Dyck paths with no return to the axis after an initial ascent of height one. When a count is close to but not equal to a Catalan number, one of these is usually the correct sequence.

Exercises for §4.2 →

4.3The Reflection Principle and the Catalan Formula

The previous section established the recurrence and left the closed form unproved. There are three standard routes to $C_{n} = \frac{1}{n + 1} (n 2 n)$ : the reflection principle, the cycle lemma, and the generating function. All three are worth knowing, because each generalises in a different direction, and we give all three.

Theorem 4.24 (Reflection principle). Let $a, b$ be lattice points and let $ℓ$ be a horizontal line. The number of lattice paths from $a$ to $b$ with steps $U = (1, 1)$ and $D = (1, - 1)$ that touch $ℓ$ equals the total number of such paths from $a^{*}$ to $b$ , where $a^{*}$ is the reflection of $a$ in $ℓ$ , provided $a$ and $b$ lie strictly on the same side of $ℓ$ .

Proof. Let $T$ be the set of paths $a \to b$ touching $ℓ$ and $T^{*}$ the set of all paths $a^{*} \to b$ . Given $P \in T$ , let $τ$ be the first time $P$ touches $ℓ$ and reflect the portion of $P$ before time $τ$ in the line $ℓ$ , keeping the rest unchanged. The reflected initial portion is a legitimate path from $a^{*}$ to the touch point, since reflection in a horizontal line turns $U$ steps into $D$ steps and back, so the result is a path $a^{*} \to b$ : a member of $T^{*}$ .

The map is injective because reflecting the initial portion again recovers $P$ . It is surjective because any path $P^{*}$ from $a^{*}$ to $b$ must cross $ℓ$ — its endpoints lie on opposite sides — so it has a first touching time $τ$ , and reflecting its initial portion produces a path from $a$ to $b$ touching $ℓ$ at time $τ$ that the map sends back to $P^{*}$ . A bijection between $T$ and $T^{*}$ gives $∣ T ∣ = ∣ T^{*} ∣$ .∎

Theorem 4.25 (Closed form for the Catalan numbers). The number of Dyck paths of semilength $n$ is

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

Proof. A path of $n$ $U$ -steps and $n$ $D$ -steps in any order goes from $(0, 0)$ to $(2 n, 0)$ , and there are $(n 2 n)$ of them: choose which $n$ of the $2 n$ step positions are $U$ . Such a path fails to be a Dyck path exactly when it goes below the axis, that is, when it touches the line $ℓ : y = - 1$ .

By Theorem Reflection principle with $a = (0, 0)$ , $b = (2 n, 0)$ and $ℓ : y = - 1$ — both endpoints lie strictly above $ℓ$ — the number of bad paths equals the number of all paths from $a^{*} = (0, - 2)$ to $(2 n, 0)$ . Such a path has $2 n$ steps with a net rise of $2$ , so it has $u$ up-steps and $d$ down-steps with $u + d = 2 n$ and $u - d = 2$ , giving $u = n + 1$ ; there are $(n + 1 2 n) = (n - 1 2 n)$ of them.

Therefore the number of Dyck paths is $(n 2 n) - (n - 1 2 n)$ , which equals $\frac{1}{n + 1} (n 2 n)$ by Proposition The subtraction form.∎

Figure 4.26. Reflection at the first passage. The bad path (orange, then blue) dips to the forbidden line

y = - 1

at step

3

; reflecting everything before that moment in the line gives the green path from

(0, - 2)

, which is unconstrained. The map is reversible, so bad paths to

(6, 0)

are exactly as numerous as all paths from

(0, - 2)

(6, 0)

Intuition. The reflection is a trick mirror for counting cheaters. You cannot count the bad paths directly, but every bad path has a first moment of disgrace, and flipping everything that happened before that moment turns it into a path starting from a mirrored origin — a path with no constraint at all, and therefore easy to count. Nothing is lost, because flipping twice puts you back where you started. The whole content of the argument is that "first time it touches $ℓ$ " is a well-defined moment, which is why the principle is also called the reflection at the first passage.

Pitfall. Reflect in the forbidden line $y = - 1$ , not in the axis $y = 0$ itself. Reflecting in the axis is not a bijection onto anything useful, because a bad path may touch the axis many times and the axis is not forbidden. The rule is: the mirror is the first line the path is not allowed to reach.

The second route to the formula produces the factor $\frac{1}{n + 1}$ directly instead of as the outcome of a subtraction, and it is the one that generalises to $k$ -ary trees.

Theorem 4.27 (Cycle lemma). Let $a_{1}, \dots, a_{m}$ be integers with $a_{i} \leq 1$ for every $i$ and $a_{1} + \dots + a_{m} = k > 0$ . Then exactly $k$ of the $m$ cyclic shifts of the sequence have all their partial sums positive.

Proof. Extend the sequence periodically to an infinite sequence $(a_{i})_{i \geq 1}$ with $a_{i + m} = a_{i}$ , and let $s_{j} = a_{1} + \dots + a_{j}$ , so $s_{j + m} = s_{j} + k$ and the partial-sum path drifts upward with slope $k / m > 0$ . Call an index $j$ a record if $s_{i} < s_{j}$ for all $i < j$ . Because the path drifts up, records occur infinitely often, and because every step changes $s$ by at most $+ 1$ , each record exceeds the previous one by exactly $1$ : the record values are consecutive integers. In any window of $m$ consecutive indices the sum increases by exactly $k$ , so exactly $k$ records lie in each window of length $m$ .

Now the shift starting at index $j + 1$ has all partial sums positive precisely when $s_{i} > s_{j}$ for every $i > j$ with $i \leq j + m$ , which — using periodicity and the upward drift — happens precisely when $j + 1$ is a record. So the number of good shifts among any $m$ consecutive starting points is the number of records there, namely $k$ . Finally, distinct starting indices in a window give distinct shifts, since a repetition would force the period to divide $m$ properly and hence $k$ to be a proper multiple of itself.∎

Corollary 4.28 (Second proof of the closed form). The number of Dyck paths of semilength $n$ is $\frac{1}{2 n + 1} (n 2 n + 1) = \frac{1}{n + 1} (n 2 n)$ .

Proof. Consider sequences of $n + 1$ entries equal to $+ 1$ and $n$ entries equal to $- 1$ ; there are $(n 2 n + 1)$ of them, and each sums to $k = 1$ . By Theorem Cycle lemma with $m = 2 n + 1$ and $k = 1$ , exactly one cyclic shift of each has all partial sums positive, and the $2 n + 1$ shifts of a given sequence are distinct (a repeated shift would make the sum a proper multiple of $1$ times a divisor, impossible when $k = 1$ ). So the sequences with all partial sums positive number $(n 2 n + 1) / (2 n + 1)$ .

Deleting the first entry of such a sequence — necessarily $+ 1$ — leaves $n$ entries $+ 1$ and $n$ entries $- 1$ with all partial sums $\geq 0$ : a Dyck path. The map is a bijection, since prefixing $+ 1$ inverts it. Finally

\frac{1}{2 n + 1} (n 2 n + 1) = \frac{1}{2 n + 1} \cdot \frac{( 2 n + 1 )!}{n ! ( n + 1 )!} = \frac{( 2 n )!}{n ! ( n + 1 )!} = \frac{1}{n + 1} (n 2 n) .

∎

The third route is generating functions, and it is the one that shows where the square root in the Catalan generating function comes from.

Theorem 4.29 (The Catalan recurrence). With $C_{0} = 1$ , the Catalan numbers satisfy

C_{n} = i = 0 \sum n - 1 C_{i} C_{n - 1 - i} (n \geq 1),

and this recurrence together with

C_{0} = 1

determines the sequence uniquely.

Proof. The recurrence is the first-return decomposition established in the proof of Theorem Catalan objects, applied to the family of Dyck paths, which Theorem Closed form for the Catalan numbers identifies with $C_{n}$ . Uniqueness is immediate: the right-hand side involves only $C_{0}, \dots, C_{n - 1}$ , so the values are forced one at a time.∎

Theorem 4.30 (Catalan generating function). The formal power series $C (x) = \sum_{n \geq 0} C_{n} x^{n}$ satisfies $C (x) = 1 + x C (x)^{2}$ and

C (x) = \frac{1 - 1 - 4 x}{2 x} .

Proof. Multiplying the recurrence by $x^{n}$ and summing over $n \geq 1$ ,

C (x) - 1 = n \geq 1 \sum (i = 0 \sum n - 1 C_{i} C_{n - 1 - i}) x^{n} = x m \geq 0 \sum (i = 0 \sum m C_{i} C_{m - i}) x^{m} = x C (x)^{2},

because the inner sum is the coefficient of

x^{m}

in the Cauchy product

C (x)^{2}

. Solving the quadratic

x C^{2} - C + 1 = 0

for

C

gives

C (x) = \frac{1 \pm 1 - 4 x}{2 x} .

The sign must be

-

: with

+

, the numerator tends to

2

x \to 0

while the denominator tends to

0

, so the expression is unbounded, whereas

C (x) \to C_{0} = 1

To confirm that this really expands to the Catalan numbers, apply Newton's binomial series to $(1 - 4 x)^{1/2}$ . With $(n 1/2) = \frac{( 1/2 ) ( - 1/2 ) \dots ( 1/2 - n + 1 )}{n !}$ one computes, for $n \geq 1$ ,

(n 1/2) (- 4)^{n} = \frac{- 2}{n} (n - 1 2 n - 2),

1 - 1 - 4 x = n \geq 1 \sum \frac{2}{n} (n - 1 2 n - 2) x^{n}, \frac{1 - 1 - 4 x}{2 x} = n \geq 1 \sum \frac{1}{n} (n - 1 2 n - 2) x^{n - 1} = m \geq 0 \sum \frac{1}{m + 1} (m 2 m) x^{m},

which is

\sum_{m} C_{m} x^{m}

as claimed.∎

Example 4.31 (Parenthesising a product). In how many ways can the product $a_{1} a_{2} a_{3} a_{4} a_{5}$ of five factors be parenthesised, if the order of the factors is fixed and each multiplication combines two adjacent factors?

Solution. Each full parenthesisation corresponds to a plane binary tree whose $5$ leaves are the factors in order, and whose $4$ internal nodes are the multiplications. By Theorem Catalan objects(3), trees with $4$ internal nodes number $C_{4} = 14$ .

Check against the recurrence by splitting at the last multiplication performed, which separates the factors into a left block of $i$ and a right block of $5 - i$ :

C_{4} = C_{0} C_{3} + C_{1} C_{2} + C_{2} C_{1} + C_{3} C_{0} = 5 + 2 + 2 + 5 = 14 ✓

The

14

splits are:

1∣4

contributing

1 \cdot 5

2∣3

contributing

1 \cdot 2

3∣2

contributing

2 \cdot 1

, and

4∣1

contributing

5 \cdot 1

.□

Example 4.32 (The ballot problem). In an election candidate $A$ receives $p$ votes and candidate $B$ receives $q < p$ votes. If the ballots are counted in a uniformly random order, what is the probability that $A$ is strictly ahead throughout the count?

Solution. Encode the count as a path with $+ 1$ for each $A$ -vote and $- 1$ for each $B$ -vote: there are $(p p + q)$ orders, all equally likely, and we want those whose partial sums are all positive.

Every sequence here sums to $k = p - q > 0$ and has entries $\leq 1$ , so Theorem Cycle lemma applies with $m = p + q$ : exactly $p - q$ of the $p + q$ cyclic shifts of each sequence are good. Grouping the $(p p + q)$ sequences into cyclic classes, the proportion of good ones is therefore

\frac{p - q}{p + q},

which is Bertrand's ballot theorem. For

p = 5, q = 3

the probability is

2/8 = 1/4

; the count of good orders is

\frac{1}{4} (5 8) = \frac{56}{4} = 14

✓ (an integer, as it must be).□

Remark (Asymptotics). Applying Stirling's approximation $n! \sim 2 πn (n / e)^{n}$ to $(n 2 n)$ gives $(n 2 n) \sim 4^{n} / πn$ , and hence

C_{n} \sim \frac{4 ^{n}}{n ^{3/2} π} .

So the Catalan numbers grow like

4^{n}

up to a polynomial correction — slower than

(n 2 n)

by a factor of

n

, which is the price of the constraint. We take Stirling's approximation itself as known from analysis; it is not proved here.

Exercises for §4.3 →

4.4Stirling Numbers of the Second Kind

We move from sequences to triangles: two-parameter families $T (n, k)$ whose rows record a refinement of a count. The Stirling numbers of the second kind refine the count of set partitions by the number of blocks, and they are simultaneously the coefficients that convert ordinary powers into falling factorials — a coincidence that is really a theorem, and one of the most useful in the subject.

Definition 4.33 (Stirling number of the second kind). For integers $n, k \geq 0$ , $S (n, k)$ — also written ${k n}$ — is the number of set partitions of $[n]$ into exactly $k$ non-empty blocks. The blocks are unordered and unlabelled. By convention $S (0, 0) = 1$ , $S (n, 0) = 0$ for $n \geq 1$ , and $S (n, k) = 0$ for $k > n$ .

Theorem 4.34 (Recurrence). For $n, k \geq 1$ ,

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

Proof. Classify the partitions of $[n]$ into $k$ blocks by the fate of the element $n$ .

If ${n}$ is a block on its own, the remaining $n - 1$ elements form a partition into $k - 1$ blocks, and every such partition arises exactly once: $S (n - 1, k - 1)$ possibilities.

Otherwise $n$ sits in a block with other elements; deleting $n$ leaves a partition of $[n - 1]$ into $k$ blocks, and $n$ could have been inserted into any one of those $k$ blocks. Each (partition of $[n - 1]$ into $k$ blocks, choice of block) pair gives a distinct partition of $[n]$ , so this case contributes $k S (n - 1, k)$ .

The cases are disjoint and exhaustive.∎

The recurrence fills a triangle quickly.

$n \ k$	0	1	2	3	4	5	6
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1

Intuition. Think of handing $n$ distinct people into rooms that carry no names: all you record is who is with whom. $S (n, k)$ counts the ways to fill exactly $k$ rooms leaving none empty. The recurrence is the newcomer's decision: either they take a fresh room — which uses one of the $k$ rooms up and leaves the old crowd to fill $k - 1$ — or they join one of the $k$ rooms already occupied, and there are $k$ ways to do that. Painting names on the rooms afterwards multiplies every count by $k!$ , which is why $k! S (n, k)$ counts surjections onto a labelled set of size $k$ .

Proposition 4.35 (Surjections). For $n, k \geq 0$ the number of surjective functions $[n] \to [k]$ is $k! S (n, k)$ .

Proof. A surjection $f : [n] \to [k]$ determines the set partition of $[n]$ into the non-empty fibres $f^{- 1} (1), \dots, f^{- 1} (k)$ , which has exactly $k$ blocks. Conversely, a partition into $k$ blocks together with a bijection from its blocks to $[k]$ reconstructs $f$ , and there are $k!$ such bijections. So surjections correspond to (partition, labelling) pairs, of which there are $S (n, k) \cdot k!$ .∎

Theorem 4.36 (Explicit formula). For $n \geq 1$ and $k \geq 0$ ,

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

Proof. By Proposition Surjections it suffices to count surjections $[n] \to [k]$ by inclusion–exclusion. For $i \in [k]$ let $A_{i}$ be the set of functions $[n] \to [k]$ missing the value $i$ . A function is a surjection exactly when it lies in none of the $A_{i}$ . For a set $I \subseteq [k]$ of size $k - j$ , the functions avoiding all values in $I$ are the functions into the remaining $j$ values, and there are $j^{n}$ of them. Inclusion–exclusion gives

# {surjections} = I \subseteq [k] \sum (- 1)^{∣ I ∣} j^{n}_{j = k - ∣ I ∣} = j = 0 \sum k (- 1)^{k - j} (j k) j^{n},

since there are

(k - j k) = (j k)

sets

I

with

k - ∣ I ∣ = j

. Dividing by

k!

finishes the proof.∎

Example 4.37 (Two ways to $S (4, 2)$ ). Compute $S (4, 2)$ by classifying block shapes, and again from the explicit formula.

Solution. By shape. A partition of ${1, 2, 3, 4}$ into two blocks has block sizes $3 + 1$ or $2 + 2$ .

Sizes $3 + 1$ : the partition is determined by the singleton, so there are $(1 4) = 4$ . Sizes $2 + 2$ : the block containing $1$ is determined by choosing $1$ 's partner, $(1 3) = 3$ ways, and the other two elements form the second block; since the blocks are unlabelled this counts each partition once, giving $3$ .

Total $S (4, 2) = 4 + 3 = 7$ .

By formula. $S (4, 2) = \frac{1}{2} ((0 2) 0^{4} - (1 2) 1^{4} + (2 2) 2^{4}) = \frac{0 - 2 + 16}{2} = 7$ ✓.□

Example 4.38 (Distributing tasks). Five distinct tasks are assigned to three distinct employees so that nobody is idle. How many assignments are there?

Solution. The employees are distinguishable, so this counts surjections $[5] \to [3]$ , which by Proposition Surjections is $3! S (5, 3)$ .

From the table, $S (5, 3) = 25$ , so the answer is $6 \cdot 25 = 150$ .

Cross-check by inclusion–exclusion directly: $3^{5} - 3 \cdot 2^{5} + 3 \cdot 1^{5} = 243 - 96 + 3 = 150$ ✓.□

The following theorem explains why these numbers are called Stirling numbers at all: they were introduced as coefficients in a polynomial identity, and only later recognised as counting partitions.

Theorem 4.39 (Powers in terms of falling factorials). For every integer $n \geq 0$ , as an identity of polynomials in $x$ ,

x^{n} = k = 0 \sum n S (n, k) (x)_{k} .

Proof. Both sides are polynomials in $x$ of degree $n$ , so it is enough to prove that they agree at every positive integer $x = m$ ; a non-zero polynomial of degree $n$ has at most $n$ roots, so agreement at infinitely many points forces equality.

Fix $m \geq 1$ and count functions $f : [n] \to [m]$ . There are $m^{n}$ of them. Classify them by the size $k$ of the image. A function with image of size exactly $k$ is determined by the partition of $[n]$ into its $k$ fibres — $S (n, k)$ choices — together with an injection from those $k$ blocks into $[m]$ , of which there are $m (m - 1) \dots (m - k + 1) = (m)_{k}$ . Summing over $k$ gives $m^{n} = \sum_{k} S (n, k) (m)_{k}$ .∎

Example 4.40 (The identity at $n = 3$ ). Expand $x^{3}$ in falling factorials and verify at $x = 4$ .

Solution. Row $3$ of the table is $S (3, 1) = 1$ , $S (3, 2) = 3$ , $S (3, 3) = 1$ , so

x^{3} = (x)_{1} + 3 (x)_{2} + (x)_{3} = x + 3 x (x - 1) + x (x - 1) (x - 2) .

Expanding the right-hand side: $x + 3 x^{2} - 3 x + x^{3} - 3 x^{2} + 2 x = x^{3}$ ✓.

At $x = 4$ : $4 + 3 \cdot 12 + 24 = 4 + 36 + 24 = 64 = 4^{3}$ ✓. Read combinatorially, this says that the $64$ functions $[3] \to [4]$ split into $4$ with a $1$ -element image, $36$ with a $2$ -element image and $24$ injective ones.□

Proposition 4.41 (Exponential generating function of a column). For fixed $k \geq 0$ ,

n \geq 0 \sum S (n, k) \frac{x ^{n}}{n !} = \frac{( e ^{x} - 1 ) ^{k}}{k !} .

Proof. Substitute the explicit formula and exchange the two (absolutely convergent, for each fixed $x$ ) sums:

n \geq 0 \sum S (n, k) \frac{x ^{n}}{n !} = \frac{1}{k !} j = 0 \sum k (- 1)^{k - j} (j k) n \geq 0 \sum \frac{( j x ) ^{n}}{n !} = \frac{1}{k !} j = 0 \sum k (- 1)^{k - j} (j k) e^{j x} = \frac{( e ^{x} - 1 ) ^{k}}{k !},

the last step being the binomial theorem applied to

(e^{x} - 1)^{k}

. The

n = 0

term needs the convention

0^{0} = 1

in the explicit formula, which is consistent with

S (0, 0) = 1

.∎

Intuition. The generating function is the "set of $k$ blocks" recipe read off directly: $e^{x} - 1 = x + x^{2} /2! + \dots$ is the exponential generating function for a single non-empty block, raising it to the $k$ makes an ordered list of $k$ blocks, and dividing by $k!$ forgets the order. Every exponential generating function in this chapter is assembled from that one rule.

Pitfall. $S (n, k)$ already treats the blocks as indistinguishable, so do not divide by $k!$ a second time. The test question to ask is whether the containers have names. Balls into unlabelled boxes, no box empty: $S (n, k)$ . Balls into labelled boxes, no box empty: $k! S (n, k)$ . Balls into labelled boxes, empties allowed: $k^{n}$ . Three different answers to three questions that sound almost identical.

Exercises for §4.4 →

4.5Stirling Numbers of the First Kind

The second kind refines set partitions by block count. The first kind refines permutations by cycle count, and converts in the opposite direction: falling factorials back into powers.

Definition 4.42 (Stirling numbers of the first kind). For $n, k \geq 0$ , the unsigned Stirling number of the first kind $c (n, k)$ — also $[k n]$ — is the number of permutations of $[n]$ whose disjoint-cycle decomposition has exactly $k$ cycles, fixed points counting as $1$ -cycles. The signed Stirling numbers of the first kind are $s (n, k) = (- 1)^{n - k} c (n, k)$ . By convention $c (0, 0) = 1$ and $c (n, k) = 0$ for $k > n$ or ( $k = 0$ and $n \geq 1$ ).

Theorem 4.43 (Recurrence). For $n, k \geq 1$ ,

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

Proof. Classify permutations of $[n]$ with $k$ cycles by the cycle containing $n$ .

If $n$ is a fixed point, deleting it leaves a permutation of $[n - 1]$ with $k - 1$ cycles: $c (n - 1, k - 1)$ possibilities.

Otherwise $n$ lies in a cycle of length $\geq 2$ ; deleting $n$ from that cycle (splicing its neighbours together) leaves a permutation of $[n - 1]$ with $k$ cycles. To reverse this, $n$ must be inserted immediately after one of the $n - 1$ elements, and each of the $n - 1$ choices gives a different permutation. So this case contributes $(n - 1) c (n - 1, k)$ .∎

$n \ k$	1	2	3	4	5	6
1	1
2	1	1
3	2	3	1
4	6	11	6	1
5	24	50	35	10	1
6	120	274	225	85	15	1

Corollary 4.44 (Row sums). For $n \geq 1$ , $\sum_{k = 1}^{n} c (n, k) = n!$ .

Proof. Every permutation of $[n]$ has some number of cycles between $1$ and $n$ , and the classes are disjoint, so the row sums the whole symmetric group.∎

Theorem 4.45 (Rising factorials in terms of powers). For $n \geq 0$ , as polynomials in $x$ ,

x^{(n)} = x (x + 1) \dots (x + n - 1) = k = 0 \sum n c (n, k) x^{k}, (x)_{n} = k = 0 \sum n s (n, k) x^{k} .

Proof. Induct on $n$ . For $n = 0$ both sides are $1$ . Assume the first identity for $n - 1$ . Then

x^{(n)} = x^{(n - 1)} (x + n - 1) = (k \sum c (n - 1, k) x^{k}) (x + n - 1) = k \sum c (n - 1, k) x^{k + 1} + (n - 1) k \sum c (n - 1, k) x^{k} .

The coefficient of

x^{k}

on the right is

c (n - 1, k - 1) + (n - 1) c (n - 1, k)

, which is

c (n, k)

by Theorem Recurrence.

For the second identity, substitute $- x$ for $x$ in the first: $(- x)^{(n)} = (- x) (- x + 1) \dots (- x + n - 1) = (- 1)^{n} x (x - 1) \dots (x - n + 1) = (- 1)^{n} (x)_{n}$ , so

(x)_{n} = (- 1)^{n} k \sum c (n, k) (- x)^{k} = k \sum (- 1)^{n - k} c (n, k) x^{k} = k \sum s (n, k) x^{k} .

∎

Intuition. Every permutation is a set of loops: follow $1 \to σ (1) \to σ (σ (1)) \to \dots$ until you return, and you have traced a cycle. So $c (n, k)$ asks how many of the $n!$ permutations break into exactly $k$ loops. At $n = 3$ : the identity is three $1$ -loops, each of the three transpositions is one $2$ -loop plus a fixed point, and each of the two $3$ -cycles is a single loop — giving $c (3, 3) = 1$ , $c (3, 2) = 3$ , $c (3, 1) = 2$ , summing to $6 = 3!$ as the row sum demands.

Example 4.46 (Counting permutations with two cycles). Show that $c (4, 2) = 11$ by direct enumeration of cycle shapes.

Solution. Two cycles covering four elements have lengths $3 + 1$ or $2 + 2$ .

Shape $3 + 1$ : choose the fixed point in $(1 4) = 4$ ways; the remaining three elements can be arranged into a cycle in $(3 - 1)! = 2$ ways. That is $4 \cdot 2 = 8$ permutations.

Shape $2 + 2$ : split four elements into two unordered pairs in $\frac{1}{2} (2 4) = 3$ ways, and each pair determines its transposition uniquely: $3$ permutations.

Total $8 + 3 = 11$ ✓, matching the table.

Row check: $6 + 11 + 6 + 1 = 24 = 4!$ ✓.□

Proposition 4.47 (Boundary entries). For $n \geq 1$ ,

c (n, n) = 1, c (n, n - 1) = (2 n), c (n, 1) = (n - 1)!, c (n, 2) = (n - 1)! H_{n - 1} .

Proof. $c (n, n) = 1$ : the only permutation with $n$ cycles is the identity. $c (n, n - 1)$ : a permutation with $n - 1$ cycles has exactly one $2$ -cycle and the rest fixed, so it is a transposition, and there are $(2 n)$ of them. $c (n, 1)$ : a single $n$ -cycle can be written starting from the element $1$ , after which the other $n - 1$ elements appear in any order, so there are $(n - 1)!$ of them.

For $c (n, 2)$ , use the recurrence: $c (n, 2) = (n - 1) c (n - 1, 2) + c (n - 1, 1) = (n - 1) c (n - 1, 2) + (n - 2)!$ . Dividing by $(n - 1)!$ ,

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

With the value

c (2, 2) /1! = 1 = H_{1}

n = 2

, induction gives

c (n, 2) / (n - 1)! = H_{n - 1}

.∎

Harmonic numbers enter here for a reason, not by accident, and they recur throughout the analysis of permutations. Their asymptotic behaviour is worth stating precisely.

Theorem 4.48 (Harmonic asymptotics). The sequence $γ_{n} = H_{n} - ln n$ converges as $n \to \infty$ to a constant $γ = 0.5772 \dots$ , the Euler–Mascheroni constant. Hence $H_{n} = ln n + γ + o (1)$ , and in particular $H_{n} \to \infty$ like $ln n$ .

Proof. Since $1/ t$ is decreasing, for each $j \geq 1$ ,

\frac{1}{j + 1} \leq \int_{j}^{j + 1} \frac{d t}{t} \leq \frac{1}{j} .

The sequence is non-increasing. Using the left inequality with $j = n$ ,

γ_{n} - γ_{n + 1} = (ln (n + 1) - ln n) - \frac{1}{n + 1} = \int_{n}^{n + 1} \frac{d t}{t} - \frac{1}{n + 1} \geq 0.

The sequence is bounded below. Summing the right inequality over $j = 1, \dots, n - 1$ gives $ln n \leq H_{n - 1} \leq H_{n}$ , hence $γ_{n} = H_{n} - ln n \geq 0$ .

A non-increasing sequence bounded below converges, and its limit is by definition $γ$ .

The sharper expansion $H_{n} = ln n + γ + \frac{1}{2 n} - \frac{1}{12 n ^{2}} + O (n^{- 4})$ follows from the Euler–Maclaurin summation formula and is beyond the scope of this chapter; we use only the statement proved above.∎

Theorem 4.49 (Cycles of a random permutation). Let $σ$ be a uniformly random permutation of $[n]$ and let $cyc (σ)$ be its number of cycles. Then

E [cyc (σ)] = H_{n} = ln n + γ + o (1) .

Proof. By Theorem Rising factorials in terms of powers, the polynomial $P_{n} (x) = \sum_{k} c (n, k) x^{k}$ equals $x (x + 1) \dots (x + n - 1)$ . Since the row sums to $n!$ , the expectation is

E [cyc (σ)] = \frac{1}{n !} k \sum k c (n, k) = \frac{P _{n}^{'} ( 1 )}{n !} = \frac{P _{n}^{'} ( 1 )}{P _{n} ( 1 )},

using

P_{n} (1) = 1 \cdot 2 \dots n = n!

. Logarithmic differentiation of the product form gives

\frac{P _{n}^{'} ( x )}{P _{n} ( x )} = j = 0 \sum n - 1 \frac{1}{x + j}, so \frac{P _{n}^{'} ( 1 )}{P _{n} ( 1 )} = j = 0 \sum n - 1 \frac{1}{1 + j} = H_{n} .

The asymptotic form is Theorem Harmonic asymptotics.∎

Example 4.50 (How many cycles in a shuffled deck?). Estimate the expected number of cycles of a random permutation of $52$ cards, and compare with the expected number of cycles of a random permutation of $10$ objects.

Solution. By Theorem Cycles of a random permutation the expectation is $H_{52} = ln 52 + γ + o (1) \approx 3.951 + 0.577 = 4.53$ ; the exact value $H_{52} = 4.538 \dots$ confirms the estimate.

For $n = 10$ , $H_{10} = 2.9290$ , and $ln 10 + γ = 2.3026 + 0.5772 = 2.8798$ , about $0.05$ low — the discrepancy is the $1/ (2 n) = 0.05$ term of the sharper expansion ✓.

The moral is that cycle counts grow only logarithmically: a shuffled deck typically decomposes into a handful of long cycles, not into many short ones.□

Pitfall. Three sign and labelling traps live in this section. First, $s (n, k)$ and $c (n, k)$ differ by $(- 1)^{n - k}$ ; a formula quoted for "the Stirling numbers of the first kind" may mean either. Second, the first kind counts cycles in permutations and the second counts blocks in set partitions — the names carry no mnemonic, so check against $c (3, 2) = 3$ versus $S (3, 2) = 3$ , which unhelpfully agree, and then against $c (4, 2) = 11$ versus $S (4, 2) = 7$ , which do not. Third, the unsigned first-kind triangle uses multiplier $n - 1$ in its recurrence while the second-kind triangle uses $k$ ; swapping them silently produces a plausible-looking wrong triangle.

Exercises for §4.5 →

4.6The Two Triangles Are Inverse

The two Stirling triangles convert between the same two bases of the polynomial ring, in opposite directions. That single observation gives an orthogonality relation, an inversion formula for sums, and a clean way to move between ordinary and factorial moments in probability.

Theorem 4.51 (Stirling orthogonality). For all $n, m \geq 0$ ,

k \sum S (n, k) s (k, m) = δ_{nm} = k \sum s (n, k) S (k, m),

where

δ_{nm}

1

n = m

and

0

otherwise.

Proof. The polynomials $1, x, x^{2}, \dots$ and $(x)_{0}, (x)_{1}, (x)_{2}, \dots$ are both bases of the vector space of polynomials in $x$ over $Q$ : the second family is a triangular combination of the first with all leading coefficients $1$ .

Theorem Powers in terms of falling factorials says the matrix $(S (n, k))$ is the change-of-basis matrix expressing $x^{n}$ in the falling-factorial basis, and Theorem Rising factorials in terms of powers says $(s (n, k))$ expresses $(x)_{n}$ in the power basis. Composing the two change-of-basis maps in either order is the identity, which is exactly the two displayed identities.

Explicitly, for the first: substituting the second identity into the first,

x^{n} = k \sum S (n, k) (x)_{k} = k \sum S (n, k) m \sum s (k, m) x^{m} = m \sum (k \sum S (n, k) s (k, m)) x^{m},

and comparing coefficients of

x^{m}

in a polynomial identity forces the inner sum to be

δ_{nm}

.∎

Corollary 4.52 (Stirling inversion). For sequences $(f_{n})$ and $(g_{n})$ ,

f_{n} = k \sum S (n, k) g_{k} for all n ⟺ g_{n} = k \sum s (n, k) f_{k} for all n .

Proof. Assume the left identity and compute, using Theorem Stirling orthogonality,

k \sum s (n, k) f_{k} = k \sum s (n, k) m \sum S (k, m) g_{m} = m \sum (k \sum s (n, k) S (k, m)) g_{m} = m \sum δ_{nm} g_{m} = g_{n} .

The reverse implication is the same computation with the roles of the two triangles exchanged. (All sums are finite, since

S (n, k) = s (n, k) = 0

for

k > n

.)∎

Theorem 4.53 (Bell numbers are Stirling row sums). For every $n \geq 0$ the number $B_{n}$ of set partitions of $[n]$ satisfies

B_{n} = k = 0 \sum n S (n, k) .

Proof. Every set partition of $[n]$ has exactly one number of blocks $k$ with $0 \leq k \leq n$ , and the partitions with $k$ blocks number $S (n, k)$ by definition. Summing over the disjoint classes gives every partition exactly once. (For $n = 0$ the empty partition is the unique one, and the sum is $S (0, 0) = 1$ .)∎

Example 4.54 (Reading off $B_{4}$ and $B_{5}$ ). Compute $B_{4}$ and $B_{5}$ from the second-kind table.

Solution. Row $4$ is $0, 1, 7, 6, 1$ , so $B_{4} = 1 + 7 + 6 + 1 = 15$ .

Row $5$ is $0, 1, 15, 25, 10, 1$ , so $B_{5} = 1 + 15 + 25 + 10 + 1 = 52$ .

Sanity check against the known Bell sequence $1, 1, 2, 5, 15, 52, 203, \dots$ ✓. Row $6$ gives $B_{6} = 1 + 31 + 90 + 65 + 15 + 1 = 203$ ✓.□

Ordering the blocks instead of forgetting their order produces a different and equally classical sequence.

Definition 4.55 (Fubini numbers). The $n$ th Fubini number (or ordered Bell number) $a_{n}$ is the number of ordered set partitions of $[n]$ — equivalently the number of ways to rank $n$ candidates allowing ties, or the number of weak orderings of an $n$ -set:

a_{n} = k = 0 \sum n k! S (n, k) .

The sequence begins

1, 1, 3, 13, 75, 541, 4683, \dots

Proposition 4.56 (Fubini recurrence). For $n \geq 1$ , $a_{n} = \sum_{k = 1}^{n} (k n) a_{n - k}$ , with $a_{0} = 1$ .

Proof. Classify an ordered set partition by its first block, which is a non-empty subset of $[n]$ of some size $k$ . There are $(k n)$ choices of that block, and the remaining $n - k$ elements carry an arbitrary ordered set partition, of which there are $a_{n - k}$ .∎

Example 4.57 (Ranking with ties). Three runners finish a race; ties are possible. How many outcomes are there?

Solution. An outcome is an ordered set partition of the three runners: the blocks are the groups tied at each place, and the order of the blocks is the finishing order. So the answer is $a_{3} = 13$ .

Check by the formula. $a_{3} = 0! S (3, 0) + 1! S (3, 1) + 2! S (3, 2) + 3! S (3, 3) = 0 + 1 + 2 \cdot 3 + 6 \cdot 1 = 13$ ✓.

Check by the recurrence: $a_{3} = (1 3) a_{2} + (2 3) a_{1} + (3 3) a_{0} = 3 \cdot 3 + 3 \cdot 1 + 1 \cdot 1 = 13$ ✓, using $a_{2} = 3$ (the outcomes $A B$ , $B A$ , and the tie).□

The change of basis also has a probabilistic reading that is used constantly in applications.

Proposition 4.58 (Moments and factorial moments). Let $X$ be a random variable with finite moments up to order $n$ . Then

E [X^{n}] = k = 0 \sum n S (n, k) E [(X)_{k}],

where

(X)_{k} = X (X - 1) \dots (X - k + 1)

is the

k

th factorial moment. In particular, if

X \sim Poisson (λ)

then

E [(X)_{k}] = λ^{k}

and hence

E [X^{n}] = \sum_{k} S (n, k) λ^{k}

Proof. Apply Theorem Powers in terms of falling factorials pointwise to the random variable $X$ and take expectations, which is legitimate because the sum is finite and every term is integrable.

For the Poisson case, $E [(X)_{k}] = \sum_{j \geq k} j (j - 1) \dots (j - k + 1) e^{- λ} λ^{j} / j! = e^{- λ} λ^{k} \sum_{j \geq k} λ^{j - k} / (j - k)! = λ^{k}$ .∎

Intuition. Factorial moments are the natural currency for counting variables: $E [(X)_{k}]$ is the expected number of ordered $k$ -tuples of distinct successes, which is usually a one-line computation, while $E [X^{n}]$ rarely is. The Stirling numbers of the second kind are the exchange rate, and the fact that $E [X^{n}] = \sum_{k} S (n, k) λ^{k}$ for a Poisson variable with $λ = 1$ makes $E [X^{n}] = B_{n}$ — which is the probabilistic face of Dobinski's formula in the next section.

Exercises for §4.6 →

4.7Bell Numbers and Dobinski's Formula

Definition 4.59 (Bell number). The $n$ th Bell number $B_{n}$ is the number of set partitions of $[n]$ , equivalently the number of equivalence relations on an $n$ -element set. By convention $B_{0} = 1$ . The sequence begins

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, \dots

Intuition. For three people $A, B, C$ the groupings are: all together ( $1$ way); one pair and a loner ( $3$ ways: $A B ∣ C$ , $A C ∣ B$ , $BC ∣ A$ ); all separate ( $1$ way). That is $5 = B_{3}$ . What makes the count grow so fast is that nothing is fixed in advance — not the number of groups, not their sizes.

Theorem 4.60 (Bell recurrence). For $n \geq 0$ , with $B_{0} = 1$ ,

B_{n + 1} = k = 0 \sum n (k n) B_{k} .

Proof. Classify the partitions of $[n + 1]$ by the block $T$ containing the element $n + 1$ . Write $∣ T ∣ = n + 1 - k$ , so that $T$ consists of $n + 1$ together with $n - k$ of the other $n$ elements, chosen in $(n - k n) = (k n)$ ways. The remaining $k$ elements carry an arbitrary partition, of which there are $B_{k}$ . Since $n + 1$ lies in exactly one block, each partition is counted exactly once, and summing over $k = 0, \dots, n$ exhausts the possibilities.∎

Example 4.61 (Climbing the recurrence). Compute $B_{4}$ and $B_{5}$ from the recurrence.

Solution. Starting from $B_{0} = 1$ , $B_{1} = 1$ , $B_{2} = 2$ , $B_{3} = 5$ :

B_{4} = (0 3) B_{0} + (1 3) B_{1} + (2 3) B_{2} + (3 3) B_{3} = 1 + 3 + 3 \cdot 2 + 5 = 15.

B_{5} = (0 4) B_{0} + (1 4) B_{1} + (2 4) B_{2} + (3 4) B_{3} + (4 4) B_{4} = 1 + 4 + 6 \cdot 2 + 4 \cdot 5 + 15 = 52.

Both agree with the Stirling row sums computed earlier ✓.□

Theorem 4.62 (Exponential generating function).

n \geq 0 \sum B_{n} \frac{x ^{n}}{n !} = exp (e^{x} - 1) .

Proof. Let $B (x) = \sum_{n \geq 0} B_{n} x^{n} / n!$ . All manipulations below are identities of formal power series, where convergence plays no role.

Differentiating term by term, $B^{'} (x) = \sum_{n \geq 0} B_{n + 1} x^{n} / n!$ . On the other hand, the product of two exponential generating functions is the binomial convolution:

e^{x} B (x) = n \geq 0 \sum (k = 0 \sum n (k n) B_{k} \cdot 1) \frac{x ^{n}}{n !} = n \geq 0 \sum B_{n + 1} \frac{x ^{n}}{n !}

by Theorem Bell recurrence. So

B^{'} = e^{x} B

, whence

(ln B)^{'} = e^{x}

and

B (x) = exp (e^{x} + c)

for a constant

c

; the initial condition

B (0) = B_{0} = 1

forces

e^{1 + c} = 1

, that is

c = - 1

.∎

Intuition. Read $exp (e^{x} - 1)$ as a recipe. The series $e^{x} - 1 = x + x^{2} /2! + x^{3} /3! + \dots$ is the exponential generating function of "one non-empty block", since there is exactly one way to make a single block out of a given set of labels. Wrapping a generating function in $exp (\cdot)$ is the exponential formula's way of saying "take an unordered collection of these" — and an unordered collection of non-empty blocks covering the labels is precisely a set partition.

Theorem 4.63 (Dobinski's formula). For every $n \geq 0$ ,

B_{n} = \frac{1}{e} k = 0 \sum \infty \frac{k ^{n}}{k !} .

Proof. The series converges absolutely, since $k^{n} / k! \leq k^{n} 2^{- k + 1}$ for large $k$ and $\sum k^{n} 2^{- k}$ converges by the ratio test; so rearrangement below is legitimate.

By Theorem Powers in terms of falling factorials, $k^{n} = \sum_{j = 0}^{n} S (n, j) (k)_{j}$ for every integer $k \geq 0$ . Therefore

k \geq 0 \sum \frac{k ^{n}}{k !} = j = 0 \sum n S (n, j) k \geq 0 \sum \frac{( k ) _{j}}{k !} .

In the inner sum the terms with

k < j

vanish because

(k)_{j} = 0

there, and for

k \geq j

we have

(k)_{j} / k! = 1/ (k - j)!

. Substituting

m = k - j

k \geq 0 \sum \frac{( k ) _{j}}{k !} = m \geq 0 \sum \frac{1}{m !} = e .

Hence

\sum_{k \geq 0} k^{n} / k! = e \sum_{j} S (n, j) = e B_{n}

by Theorem Bell numbers are Stirling row sums. Divide by

e

.∎

Example 4.64 (Dobinski numerically). Verify Dobinski's formula for $n = 3$ by summing enough terms.

Solution. The terms $k^{3} / k!$ for $k = 0, 1, 2, \dots$ are

0, 1, \frac{8}{2} = 4, \frac{27}{6} = 4.5, \frac{64}{24} \approx 2.6667, \frac{125}{120} \approx 1.0417, \frac{216}{720} = 0.3, \frac{343}{5040} \approx 0.0681, \dots

The partial sum through $k = 8$ is $0 + 1 + 4 + 4.5 + 2.6667 + 1.0417 + 0.3 + 0.0681 + 0.0127 \approx 13.589$ , and the remaining terms contribute about $0.0021$ . Dividing by $e = 2.71828$ : $13.5911/2.71828 \approx 5.0000$ .

And $B_{3} = 5$ ✓. Notice how concentrated the sum is: the terms peak near $k = 3$ , which is the analytic shadow of the fact that a random partition of a small set has few blocks.□

Remark (Probabilistic restatement). Dobinski's formula says exactly that $B_{n} = E [X^{n}]$ for $X \sim Poisson (1)$ , since that expectation is $\sum_{k} k^{n} e^{- 1} / k!$ . Proposition Moments and factorial moments gives the same conclusion from a different direction: $E [X^{n}] = \sum_{k} S (n, k) λ^{k}$ , which at $λ = 1$ is the Bell row sum. The two derivations are genuinely independent and agree, which is a useful check on both.

Method 4.65 (The Bell triangle). The Bell numbers can be generated without binomial coefficients.

Start the first row with the single entry $1$ .
Begin each new row with the last entry of the previous row.
Fill each subsequent entry by adding the entry to its left and the entry above-left (the entry in the previous row in the same relative position).
The first entry of each row — equivalently the last entry of the previous row — is a Bell number.

112523751015

Reading the left column gives $1, 1, 2, 5, 15, \dots$ — the Bell numbers.

Note. The triangle is Aitken's array (also attributed to Peirce and to Bell). That its left column really is the Bell sequence can be proved by identifying the entry in position $k$ of row $n$ with a count of partitions of $[n + 1]$ subject to a restriction on where the largest elements sit; we take the construction here as a verified computational device and do not prove it. Everything the chapter uses about Bell numbers is proved from Theorem Bell recurrence instead.

Pitfall. $B_{n}$ counts partitions of a set whose elements are distinguishable. If the $n$ objects are identical, the count is the integer-partition number $p (n)$ of the next section, which is vastly smaller: $B_{6} = 203$ but $p (6) = 11$ . And if the blocks are to be labelled or ordered, the counts are $k! S (n, k)$ and the Fubini number $a_{n}$ respectively — $a_{6} = 4683$ . Four different questions, four different answers.

Exercises for §4.7 →

4.8Partitions of a Set and of an Integer

Counting set partitions by their shape connects the Bell numbers to the other kind of partition: partitions of the integer $n$ . The two are linked by one formula, and then the integer partitions take on a life of their own.

Definition 4.66 (Partition of an integer). A partition of a positive integer $n$ is a weakly decreasing sequence $λ = (λ_{1} \geq λ_{2} \geq \dots \geq λ_{r} > 0)$ of positive integers, the parts, with $λ_{1} + \dots + λ_{r} = n$ . We write $λ ⊢ n$ , and $p (n)$ for the number of partitions of $n$ , with $p (0) = 1$ . The sequence begins

p (1), p (2), \dots = 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, \dots

Theorem 4.67 (Set partitions of a given shape). Let $λ ⊢ n$ have $m_{j}$ parts equal to $j$ for each $j \geq 1$ . Then the number of set partitions of $[n]$ whose multiset of block sizes is $λ$ equals

\frac{n !}{\prod _{j \geq 1} ( j ! ) ^{m_{j}} m _{j} !} .

Consequently

B_{n} = \sum_{λ ⊢ n} \frac{n !}{\prod _{j} ( j ! ) ^{m_{j}} m _{j} !}

Proof. Write the elements of $[n]$ in a row: $n!$ orders. Cut the row into consecutive segments of the sizes prescribed by $λ$ , taking the sizes in a fixed order. Every set partition of shape $λ$ arises this way, but each arises many times: the elements within a block of size $j$ can be permuted in $j!$ ways without changing the block, accounting for the factor $\prod_{j} (j!)^{m_{j}}$ , and the $m_{j}$ blocks of the same size $j$ can be permuted among themselves, accounting for $\prod_{j} m_{j}!$ . Dividing by the total overcount gives the formula. Summing over all shapes counts every set partition once, which is the second statement.∎

Example 4.68 ( $B_{4}$ by shapes). Recompute $B_{4} = 15$ by summing over the five partitions of $4$ .

Solution.

shape $λ$	count $n! / \prod (j!)^{m_{j}} m_{j}!$	value
$4$	$4! / (4! \cdot 1!)$	$1$
$3 + 1$	$4! / (3! \cdot 1! \cdot 1! \cdot 1!)$	$4$
$2 + 2$	$4! / ((2!)^{2} \cdot 2!)$	$3$
$2 + 1 + 1$	$4! / (2! \cdot 1! \cdot (1!)^{2} \cdot 2!)$	$6$
$1 + 1 + 1 + 1$	$4! / ((1!)^{4} \cdot 4!)$	$1$

Total: $1 + 4 + 3 + 6 + 1 = 15 = B_{4}$ ✓. Note that the five shapes are the $p (4) = 5$ integer partitions of $4$ , and the $15$ set partitions are the $B_{4}$ of the previous section — the same computation displays both numbers at once.□

Definition 4.69 (Ferrers diagram and conjugate). The Ferrers diagram of $λ = (λ_{1}, \dots, λ_{r})$ is the left-justified array of dots with $λ_{i}$ dots in row $i$ . The conjugate partition $λ^{'}$ is obtained by reading the diagram in columns: $λ_{j}^{'} = # {i : λ_{i} \geq j}$ .

Figure 4.70. Conjugation reads a Ferrers diagram in columns instead of rows. The left diagram is

λ = (4, 2, 2, 1) ⊢ 9

; its column heights are

4, 3, 1, 1

, which is the diagram on the right. The four rows of

λ

have become the largest part of

λ^{'}

, and conjugating a second time restores

λ

Theorem 4.71 (Conjugation). Conjugation is an involution on the partitions of $n$ . Consequently, for every $k$ , the number of partitions of $n$ into at most $k$ parts equals the number of partitions of $n$ into parts each at most $k$ ; and the number of partitions of $n$ into exactly $k$ parts equals the number whose largest part is exactly $k$ .

Proof. Reflecting a Ferrers diagram in its main diagonal exchanges rows and columns, so it sends the diagram of $λ$ to that of $λ^{'}$ ; the reflected array is still left-justified with weakly decreasing row lengths, so $λ^{'}$ is a partition of the same $n$ , and reflecting twice restores $λ$ . Hence conjugation is a bijection of ${λ ⊢ n}$ with itself and is its own inverse.

Under conjugation the number of rows of $λ$ becomes the largest part of $λ^{'}$ and vice versa. So "at most $k$ rows" corresponds to "largest part at most $k$ ", and "exactly $k$ rows" to "largest part exactly $k$ ".∎

Example 4.72 (Conjugating a partition). Conjugate $λ = (4, 2, 2, 1) ⊢ 9$ and check the involution.

Solution. The diagram of $λ$ has rows of lengths $4, 2, 2, 1$ . Column lengths: column $1$ meets all $4$ rows, column $2$ meets rows $1, 2, 3$ (length $3$ ), column $3$ meets only row $1$ , column $4$ meets only row $1$ .

So $λ^{'} = (4, 3, 1, 1)$ , and $4 + 3 + 1 + 1 = 9$ ✓.

Conjugating again: the rows of $λ^{'}$ are $4, 3, 1, 1$ ; column $1$ meets $4$ rows, column $2$ meets $2$ , column $3$ meets $2$ , column $4$ meets $1$ , giving $(4, 2, 2, 1) = λ$ ✓.

Consistent with Theorem Conjugation: $λ$ has $4$ parts and $λ^{'}$ has largest part $4$ ✓.□

Theorem 4.73 (Euler's generating function). As formal power series in $q$ ,

n \geq 0 \sum p (n) q^{n} = k \geq 1 \prod \frac{1}{1 - q ^{k}} .

More generally, the partitions with parts restricted to a set

A

of allowed sizes are generated by

\prod_{k \in A} (1 - q^{k})^{- 1}

, and those with distinct parts by

\prod_{k \geq 1} (1 + q^{k})

Proof. Expand each factor as a geometric series, $\frac{1}{1 - q ^{k}} = 1 + q^{k} + q^{2 k} + q^{3 k} + \dots$ , the term $q^{m_{k} k}$ recording that the part $k$ is used $m_{k}$ times. Multiplying the factors and collecting the coefficient of $q^{n}$ selects all families $(m_{k})_{k \geq 1}$ of non-negative integers with $\sum_{k} k m_{k} = n$ — precisely the partitions of $n$ . The product is a legitimate formal power series because only the factors with $k \leq n$ can contribute to the coefficient of $q^{n}$ , so each coefficient is a finite sum.

The restricted versions are the same argument with the same factors omitted or truncated: keeping only $k \in A$ forbids the other parts, and replacing $(1 - q^{k})^{- 1}$ by $(1 + q^{k})$ allows each part at most once.∎

Theorem 4.74 (Euler: odd parts and distinct parts). For every $n \geq 0$ , the number of partitions of $n$ into odd parts equals the number of partitions of $n$ into distinct parts.

Proof. By Theorem Euler's generating function the two counts are generated by $\prod_{k \geq 1} (1 - q^{2 k - 1})^{- 1}$ and $\prod_{k \geq 1} (1 + q^{k})$ respectively, so it suffices to show these products are equal. Using $1 + q^{k} = \frac{1 - q ^{2 k}}{1 - q ^{k}}$ ,

k \geq 1 \prod (1 + q^{k}) = k \geq 1 \prod \frac{1 - q ^{2 k}}{1 - q ^{k}} = \frac{\prod _{k \geq 1} ( 1 - q ^{2 k} )}{\prod _{k \geq 1} ( 1 - q ^{k} )} .

The numerator is the product over even exponents, so it cancels the even factors of the denominator and leaves

k \geq 1 \prod (1 + q^{k}) = \frac{1}{\prod _{k \geq 1} ( 1 - q ^{2 k - 1} )},

which is the generating function for partitions into odd parts. (All manipulations are of formal power series with constant term

1

, where inversion is defined and each coefficient involves finitely many factors.)∎

Example 4.75 (Checking Euler's theorem at $n = 7$ ). List both families for $n = 7$ .

Solution. Odd parts (only $1, 3, 5, 7$ are available): $7$ ; $5 + 1 + 1$ ; $3 + 3 + 1$ ; $3 + 1 + 1 + 1 + 1$ ; $1 + 1 + 1 + 1 + 1 + 1 + 1$ . That is $5$ partitions.

Distinct parts: $7$ ; $6 + 1$ ; $5 + 2$ ; $4 + 3$ ; $4 + 2 + 1$ . That is $5$ partitions.

Both counts are $5$ ✓, and note that they are different partitions — the theorem asserts equality of counts, and the bijection behind it (Glaisher's: repeatedly merge equal parts) is not the identity.□

Theorem 4.76 (Euler's pentagonal number theorem). As formal power series,

k \geq 1 \prod (1 - q^{k}) = j = - \infty \sum \infty (- 1)^{j} q^{j (3 j - 1) /2} = 1 - q - q^{2} + q^{5} + q^{7} - q^{12} - q^{15} + \dots

The exponents

j (3 j - 1) /2

for

j = 1, - 1, 2, - 2, \dots

are the generalised pentagonal numbers

1, 2, 5, 7, 12, 15, \dots

Proof. Sketch (Franklin's involution). Expanding the product, the coefficient of $q^{n}$ is the number of partitions of $n$ into an even number of distinct parts minus the number into an odd number of distinct parts. Franklin's involution pairs off almost all such partitions: given a partition into distinct parts, let $s$ be its smallest part and $σ$ the length of the maximal run of consecutive parts starting from the largest. If $s \leq σ$ , remove the smallest part and add $1$ to each of the $s$ largest parts; if $s > σ$ , do the reverse. Each move changes the number of parts by one and so flips the sign, and the two moves are mutually inverse wherever both are defined. They fail to be defined exactly for the partitions where the smallest part sits inside the top run and $s = σ$ or $s = σ + 1$ , which forces $n = j (3 j \mp 1) /2$ and leaves a single unpaired partition of sign $(- 1)^{j}$ . That is the stated right-hand side. The full case analysis is in any treatment of partitions and we do not reproduce it here.∎

Corollary 4.77 (A fast recurrence for $p (n)$ ). For $n \geq 1$ ,

p (n) = j \geq 1 \sum (- 1)^{j - 1} [p (n - \frac{j ( 3 j - 1 )}{2}) + p (n - \frac{j ( 3 j + 1 )}{2})],

where

p (m) = 0

for

m < 0

and the sum has only

O (n)

non-zero terms.

Proof. Multiply Theorem Euler's generating function by Theorem Euler's pentagonal number theorem: the product of $\sum p (n) q^{n}$ and $\prod (1 - q^{k})$ is $1$ . Reading off the coefficient of $q^{n}$ for $n \geq 1$ gives $0 = \sum_{j} (- 1)^{j} p (n - g_{j})$ over generalised pentagonal numbers $g_{j}$ , with the $j = 0$ term equal to $p (n)$ ; rearranging gives the statement. The number of $g_{j} \leq n$ is $O (n)$ because $g_{j}$ grows quadratically in $j$ .∎

Example 4.78 (Computing $p (10)$ ). Use the pentagonal recurrence to compute $p (10)$ from earlier values.

Solution. The generalised pentagonal numbers up to $10$ are $1, 2, 5, 7$ , with signs $+, +, -, -$ in the recurrence's alternating pattern $(- 1)^{j - 1}$ : $j = 1$ contributes $+ [p (n - 1) + p (n - 2)]$ and $j = 2$ contributes $- [p (n - 5) + p (n - 7)]$ .

Using $p (0..9) = 1, 1, 2, 3, 5, 7, 11, 15, 22, 30$ :

p (10) = p (9) + p (8) - p (5) - p (3) = 30 + 22 - 7 - 3 = 42.

Sanity check with the same recurrence one step earlier: $p (9) = p (8) + p (7) - p (4) - p (2) = 22 + 15 - 5 - 2 = 30$ ✓.□

Remark (The size of $p (n)$ ). The partition numbers grow sub-exponentially: Hardy and Ramanujan proved

p (n) \sim \frac{1}{4 n 3} exp (π \frac{2 n}{3}),

the founding result of the circle method in analytic number theory. Its proof requires the modular transformation behaviour of Dedekind's

η

-function and is far beyond this chapter; we state it only to fix the growth rate, roughly

e^{c n}

, which is slower than any exponential and vastly slower than the Bell numbers.

Pitfall. Keep the three "partition" words apart. A composition of $n$ is ordered ( $4 = 3 + 1$ and $4 = 1 + 3$ are different, and there are $2^{n - 1}$ of them). An integer partition of $n$ is unordered ( $p (4) = 5$ ). A set partition of $[n]$ groups labelled elements ( $B_{4} = 15$ ). Compositions are exponential, integer partitions are sub-exponential, set partitions are super-exponential — and a problem that mixes them up is usually off by orders of magnitude, not by a constant.

Exercises for §4.8 →

4.9Derangements, Eulerian Numbers and Growth Rates

The last two families refine the count of permutations in two further ways — by fixed points, and by descents — and the section closes by putting every sequence in the chapter on a single scale.

Definition 4.79 (Derangement). A derangement of $[n]$ is a permutation with no fixed point. The number of derangements is $D_{n}$ (also written $! n$ ), with $D_{0} = 1$ . The sequence begins

1, 0, 1, 2, 9, 44, 265, 1854, 14833, \dots

The derangement numbers admit two derivations that share nothing but the answer: one sieves, one recurs. Having both is worth the space, because the sieve gives the closed form and the recurrence gives the arithmetic.

Theorem 4.80 (First derivation: inclusion–exclusion). For $n \geq 0$ ,

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

Proof. For $i \in [n]$ let $A_{i}$ be the set of permutations of $[n]$ fixing $i$ . A permutation is a derangement exactly when it lies in no $A_{i}$ . For a subset $I \subseteq [n]$ with $∣ I ∣ = k$ , the permutations fixing every element of $I$ are the arbitrary permutations of the other $n - k$ elements, so $∣ ⋂_{i \in I} A_{i} ∣ = (n - k)!$ , a number depending only on $k$ . Inclusion–exclusion gives

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

∎

Theorem 4.81 (Second derivation: a recurrence). For $n \geq 2$ ,

D_{n} = (n - 1) (D_{n - 1} + D_{n - 2}),

with

D_{0} = 1

and

D_{1} = 0

. Consequently

D_{n} = n D_{n - 1} + (- 1)^{n}

for

n \geq 1

Proof. Let $σ$ be a derangement of $[n]$ and let $j = σ (n) \neq = n$ ; there are $n - 1$ choices of $j$ . Split into two cases according to whether $σ (j) = n$ .

If $σ (j) = n$ , then $n$ and $j$ form a $2$ -cycle and the rest of $σ$ is a derangement of the other $n - 2$ elements: $D_{n - 2}$ possibilities.

If $σ (j) \neq = n$ , delete $n$ and define $σ^{'}$ on $[n - 1]$ by $σ^{'} (i) = σ (i)$ for $i \neq = σ^{- 1} (n)$ and $σ^{'} (σ^{- 1} (n)) = j$ . Then $σ^{'}$ is a permutation of $[n] ∖ {n}$ with no fixed point — the only candidate for a new fixed point would be $σ^{- 1} (n) = j$ , excluded precisely by the case assumption $σ (j) \neq = n$ — and the construction is reversible given $j$ . So this case contributes $D_{n - 1}$ .

Multiplying by the $n - 1$ choices of $j$ proves the first recurrence. For the second, rewrite it as $D_{n} - n D_{n - 1} = - (D_{n - 1} - (n - 1) D_{n - 2})$ and induct: the quantity $D_{n} - n D_{n - 1}$ flips sign at each step and equals $D_{1} - 1 \cdot D_{0} = - 1$ at $n = 1$ , hence equals $(- 1)^{n}$ .∎

The two derivations agree, as they must: $n! \sum_{k \leq n} (- 1)^{k} / k!$ satisfies $D_{n} = n D_{n - 1} + (- 1)^{n}$ by inspection of the partial sums. The closed form immediately gives the famous limit.

Corollary 4.82 (The hat-check probability). For $n \geq 1$ , $D_{n} - \frac{n !}{e} < \frac{1}{n + 1}$ , so $D_{n}$ is the nearest integer to $n! / e$ ; and the probability that a uniformly random permutation of $[n]$ is a derangement satisfies

\frac{D _{n}}{n !} ⟶ \frac{1}{e} = 0.367879 \dots

Proof. The series $e^{- 1} = \sum_{k \geq 0} (- 1)^{k} / k!$ is alternating with terms decreasing in absolute value, so truncating after $k = n$ commits an error smaller than the first omitted term:

\frac{D _{n}}{n !} - \frac{1}{e} = k > n \sum \frac{( - 1 ) ^{k}}{k !} < \frac{1}{( n + 1 )!} .

Multiplying by

n!

gives

∣ D_{n} - n! / e ∣ < 1/ (n + 1) \leq 1/2

for

n \geq 1

, which identifies

D_{n}

as the nearest integer. Letting

n \to \infty

in the displayed inequality gives the limit.∎

Intuition. The striking fact is that the derangement probability barely depends on $n$ : it is $0.3333$ at $n = 3$ , $0.3667$ at $n = 5$ , and $0.367879 \dots$ for every $n \geq 8$ to six decimal places. The reason is the sieve: fixing a particular point costs a factor of about $1/ n$ , and there are about $n$ points to fix, so the corrections at each order are $(k n) / n^{k} \approx 1/ k!$ , independent of $n$ . The answer is the sum of that series — a Poisson probability with mean $1$ , and indeed the number of fixed points of a random permutation converges in distribution to $Poisson (1)$ .

Proposition 4.83 (Permutations with a prescribed number of fixed points). The number of permutations of $[n]$ with exactly $k$ fixed points is $(k n) D_{n - k}$ , and $\sum_{k = 0}^{n} (k n) D_{n - k} = n!$ . The expected number of fixed points of a uniformly random permutation is $1$ for every $n \geq 1$ .

Proof. Choose the set of fixed points in $(k n)$ ways and derange the rest in $D_{n - k}$ ways; the two choices are independent and reconstruct the permutation. Summing over $k$ counts every permutation once.

For the expectation, write the number of fixed points as $\sum_{i = 1}^{n} 1 [σ (i) = i]$ . Each indicator has expectation $1/ n$ because $σ (i)$ is uniform on $[n]$ , so by linearity the expectation is $n \cdot \frac{1}{n} = 1$ , regardless of $n$ .∎

Example 4.84 (The hat-check problem). Five guests check five distinct hats and receive them back at random. What is the probability that nobody gets their own hat, and what is the probability that exactly two guests do?

Solution. Total permutations: $5! = 120$ .

Nobody: $D_{5} = 44$ by the recurrence, $D_{5} = 4 (D_{4} + D_{3}) = 4 (9 + 2) = 44$ . The probability is $44/120 = 11/30 \approx 0.3667$ . Compare $1/ e \approx 0.3679$ ✓, and $5! / e = 44.15$ , whose nearest integer is $44$ ✓.

Exactly two: $(2 5) D_{3} = 10 \cdot 2 = 20$ , probability $20/120 = 1/6$ .

Check the whole distribution: $(0 5) D_{5} + (1 5) D_{4} + (2 5) D_{3} + (3 5) D_{2} + (4 5) D_{1} + (5 5) D_{0} = 44 + 45 + 20 + 10 + 0 + 1 = 120$ ✓.□

Descents are the other classical permutation statistic, and they generate the Eulerian triangle.

Definition 4.85 (Eulerian numbers). A descent of a permutation $π = π_{1} π_{2} \dots π_{n}$ of $[n]$ is a position $i < n$ with $π_{i} > π_{i + 1}$ . The Eulerian number $A (n, k)$ , also written $⟨ k n ⟩$ , is the number of permutations of $[n]$ with exactly $k$ descents, for $0 \leq k \leq n - 1$ .

$n$	$A (n, 0)$	$A (n, 1)$	$A (n, 2)$	$A (n, 3)$	$A (n, 4)$
1	1
2	1	1
3	1	4	1
4	1	11	11	1
5	1	26	66	26	1

Theorem 4.86 (Eulerian recurrence and symmetry). For $n \geq 2$ and $0 \leq k \leq n - 1$ ,

A (n, k) = (k + 1) A (n - 1, k) + (n - k) A (n - 1, k - 1),

with

A (1, 0) = 1

. Moreover

A (n, k) = A (n, n - 1 - k)

, and

\sum_{k} A (n, k) = n!

Proof. Build a permutation of $[n]$ by inserting the value $n$ into a permutation $π$ of $[n - 1]$ , at any of the $n$ available positions (before the first entry, between two entries, or after the last). Since $n$ is the largest value, inserting it into an existing descent position, or at the very end, keeps the number of descents unchanged: there are $k$ descents to insert into plus the final position, so $k + 1$ positions preserve the descent count. Inserting $n$ anywhere else — into one of the $(n - 2) - (k)$ ascent positions of $π$ or at the front — creates exactly one new descent; there are $n - (k + 1)$ such positions when $π$ has $k$ descents, but the bookkeeping is cleaner stated the other way: to obtain $k$ descents we either start from $π$ with $k$ descents and use one of the $k + 1$ neutral positions, or start from $π$ with $k - 1$ descents and use one of the $n - k$ descent-creating positions. Summing the two disjoint cases gives the recurrence.

Symmetry: reversing a permutation, $π \mapsto π_{n} π_{n - 1} \dots π_{1}$ , turns every descent into an ascent and vice versa. A permutation of $[n]$ has $n - 1$ consecutive positions in all, so a permutation with $k$ descents maps to one with $n - 1 - k$ descents, and the map is an involution.

The row sum is $n!$ because every permutation has a well-defined number of descents.∎

Theorem 4.87 (Worpitzky's identity). For every $n \geq 1$ , as polynomials in $x$ ,

x^{n} = k = 0 \sum n - 1 A (n, k) (n x + k) .

Proof. Both sides are polynomials of degree $n$ , so it suffices to verify the identity at every positive integer $x = m$ , and there we may count.

Count the $m^{n}$ words $w = (w_{1}, \dots, w_{n}) \in [m]^{n}$ . To each word associate the permutation $π$ of $[n]$ that sorts it: list the positions in increasing order of their values, breaking ties by putting the smaller position first, so that $w_{π (1)} \leq w_{π (2)} \leq \dots \leq w_{π (n)}$ and the inequality is strict at every descent of $π$ — for if $π (i) > π (i + 1)$ while $w_{π (i)} = w_{π (i + 1)}$ , the tie-break would have ordered them the other way.

Conversely, given $π$ with $d = des (π)$ descents, the words sorted by $π$ correspond to the chains $1 \leq a_{1} \leq a_{2} \leq \dots \leq a_{n} \leq m$ that are strict at the $d$ descent positions. Subtracting $1$ from $a_{i + 1}, \dots, a_{n}$ for each descent position $i$ turns those $d$ strict inequalities into weak ones and lowers the ceiling from $m$ to $m - d$ , so such chains are in bijection with weakly increasing sequences in $[m - d]$ , of which there are $(n m - d + n - 1)$ .

Therefore $m^{n} = \sum_{π} (n m + n - 1 - des ( π )) = \sum_{k} A (n, k) (n m + n - 1 - k)$ . Finally apply the symmetry $A (n, k) = A (n, n - 1 - k)$ of Theorem Eulerian recurrence and symmetry and substitute $k \mapsto n - 1 - k$ to rewrite the right-hand side as $\sum_{k} A (n, k) (n m + k)$ .∎

Example 4.88 (Worpitzky at $n = 3$ ). Verify $x^{3} = (3 x) + 4 (3 x + 1) + (3 x + 2)$ at $x = 2$ and $x = 3$ .

Solution. Row $3$ of the Eulerian triangle is $1, 4, 1$ , so the claim is as displayed.

At $x = 2$ : $(3 2) + 4 (3 3) + (3 4) = 0 + 4 + 4 = 8 = 2^{3}$ ✓.

At $x = 3$ : $(3 3) + 4 (3 4) + (3 5) = 1 + 16 + 10 = 27 = 3^{3}$ ✓.

Row check: $1 + 4 + 1 = 6 = 3!$ ✓, as Theorem Eulerian recurrence and symmetry requires.□

Example 4.89 (Building the Eulerian row for $n = 4$ ). Derive row $4$ from row $3$ .

Solution. Row $3$ is $A (3, 0) = 1$ , $A (3, 1) = 4$ , $A (3, 2) = 1$ , and the recurrence is $A (4, k) = (k + 1) A (3, k) + (4 - k) A (3, k - 1)$ .

$A (4, 0) = 1 \cdot 1 + 4 \cdot 0 = 1$ . $A (4, 1) = 2 \cdot 4 + 3 \cdot 1 = 11$ . $A (4, 2) = 3 \cdot 1 + 2 \cdot 4 = 11$ . $A (4, 3) = 4 \cdot 0 + 1 \cdot 1 = 1$ .

Row: $1, 11, 11, 1$ , which sums to $24 = 4!$ ✓ and is symmetric ✓. Note that $A (4, 1) = 11 = c (4, 2)$ is a numerical coincidence between two different triangles — a good reminder to check which statistic is being counted.□

Intuition. Eulerian numbers describe how "shuffled" a permutation is. Exactly one permutation of $[n]$ has no descent (the identity) and exactly one has $n - 1$ (the reversal), and the bulk of the $n!$ permutations sit near the middle with about $(n - 1) /2$ descents. The triangle is the discrete ancestor of the bell curve for this statistic, and Worpitzky's identity is what lets one convert a sum like $\sum_{j \leq m} j^{n}$ into a sum of binomial coefficients, which telescopes.

Summary (Where the sequences sit). All the sequences of this chapter counted at $n = 10$ , together with their growth laws:

sequence	meaning	value at $n = 10$	growth
$p (n)$	integer partitions	$42$	$e^{c n}$ , $c = π 2/3$
$F_{n}$	Fibonacci	$55$	$φ^{n} / 5$ , $φ \approx 1.618$
$2^{n - 1}$	compositions of $n$	$512$	$2^{n}$
$C_{n}$	Catalan	$16796$	$4^{n} n^{- 3/2} π^{- 1/2}$
$B_{n}$	set partitions	$115975$	super-exponential, sub-factorial
$D_{n}$	derangements	$1334961$	$n! / e$
$n!$	permutations	$3628800$	$2 πn (n / e)^{n}$
$a_{n}$	ordered set partitions	$102247563$	$n! / (2 (ln 2)^{n + 1})$

The one genuinely delicate entry is $B_{n}$ , which sits strictly between exponential and factorial: from Dobinski's formula a saddle-point analysis gives

B_{n} \sim n^{- 1/2} λ (n)^{n + 1/2} e^{λ (n) - n - 1}, λ (n) ln λ (n) = n,

so that

ln B_{n} = n ln n - n ln ln n - n + O (n ln ln n / ln n)

. That asymptotic is quoted, not proved; the saddle-point method is beyond this chapter.

Example 4.90 (Ordering the growth rates). Without computing large values, order $C_{n}$ , $B_{n}$ , $D_{n}$ and $2^{n}$ by eventual size, and say which comparison is not settled by an elementary argument.

Solution. $2^{n} < C_{n}$ for large $n$ , since $C_{n} \sim 4^{n} n^{- 3/2} π^{- 1/2}$ and $4^{n} / 2^{n} = 2^{n}$ swamps the polynomial factor.

$C_{n} < B_{n}$ eventually: $C_{n} < 4^{n}$ while $B_{n} \geq S (n, ⌈ n /2 ⌉)$ , which already exceeds $4^{n}$ for large $n$ — more cleanly, $ln B_{n} \sim n ln n$ grows faster than the linear $ln C_{n} \sim n ln 4$ .

$B_{n} < D_{n}$ eventually, since $D_{n} \sim n! / e$ and $ln (n!) = n ln n - n + O (ln n)$ while $ln B_{n} = n ln n - n ln ln n - n + \dots$ , and the $- n ln ln n$ term is the decisive deficit.

So the order is $2^{n} < C_{n} < B_{n} < D_{n}$ for all large $n$ . The last comparison is the one that needs the quoted saddle-point asymptotic for $B_{n}$ ; the others follow from Stirling's approximation alone.□

Exercises for §4.9 →

Common Mistakes

Forgetting the $1/ (n + 1)$ in the Catalan formula. $(n 2 n)$ counts all sequences of $n$ ups and $n$ downs; $C_{n}$ counts only the ones that stay non-negative. If your answer is off by a factor of roughly $n$ , this is why.
Reflecting in the wrong line. In Theorem Reflection principle the mirror is the first forbidden line, $y = - 1$ for Dyck paths, not the axis $y = 0$ . Reflecting in the axis is not injective onto anything you can count.
Off-by-one in Catalan indexing. $C_{n}$ goes with $n$ bracket pairs, $n$ internal tree nodes, an $(n + 2)$ -gon and $n + 1$ factors in a product. Anchor on $C_{3} = 5$ before trusting an index.
Confusing the two kinds of Stirling number. First kind counts cycles in permutations, second kind counts blocks in set partitions. They are not two notations for one triangle: $c (4, 2) = 11$ while $S (4, 2) = 7$ .
Dividing by $k!$ twice. $S (n, k)$ already has unlabelled blocks. Surjections onto a labelled $k$ -set are $k! S (n, k)$ ; functions with empties allowed are $k^{n}$ .
Mixing up sign conventions for $s (n, k)$ . The signed numbers $s (n, k) = (- 1)^{n - k} c (n, k)$ are the ones that expand the falling factorial; the unsigned ones expand the rising factorial. A formula that produces a negative count has used the wrong family.
Treating $B_{n}$ and $p (n)$ as the same thing. Bell numbers partition a set of distinguishable elements; $p (n)$ partitions an integer. $B_{6} = 203$ but $p (6) = 11$ .
Losing the empty object. $C_{0} = 1$ , $B_{0} = 1$ , $D_{0} = 1$ , $p (0) = 1$ and $S (0, 0) = 1$ . Every recurrence in this chapter breaks at its first step if the empty object is dropped.
Assuming a derangement probability depends on $n$ . It is $\approx 1/ e$ from $n = 4$ onwards. If your answer drifts with $n$ , you have probably counted permutations with at least one fixed point by summing over fixed points without inclusion–exclusion.
Using $F_{n}$ where the count is $F_{n + 1}$ . The tiling and composition counts are shifted by one from the Fibonacci index; check against $n = 1$ , where there is exactly one tiling and $F_{2} = 1$ .

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