3.7Catalan, Stirling and Bell numbers
The idea
Three famous families keep showing up: Catalan numbers (trees, brackets, triangulations), Stirling numbers of the second kind (partitions into blocks) and Bell numbers (all partitions).
Think of it like this: Catalan: ways to bracket a long product. Stirling and Bell: ways to split guests into tables or groups.
Why it exists
Questions disguise them: "number of binary trees with n nodes" is Cₙ, "number of equivalence relations on n elements" is Bₙ.
How it works
- Cₙ = C(2n, n)/(n+1): 1, 1, 2, 5, 14, 42, 132.
- Cₙ counts binary trees with n nodes, balanced parenthesisations, triangulations of an (n+2)-gon, Dyck paths.
- S(n, k) = partitions of an n-set into k non-empty blocks; S(n,k) = k·S(n−1,k) + S(n−1,k−1); S(n,2) = 2ⁿ⁻¹ − 1.
- Bell Bₙ = Σ S(n, k) = 1, 1, 2, 5, 15, 52, 203.
Worked example: Binary trees with 4 nodes
C₄ = C(8,4)/5 = 70/5 = 14.
Now play with it
- →Compare the Catalan and Bell rows in the lab.
- →Read S(4, 2) = 7 in the Stirling triangle.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Cₙ | 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 | 4862 | 16796 |
Cₙ = C(2n, n)/(n+1). It counts: binary trees with n nodes, balanced parenthesisations of n pairs, triangulations of an (n+2)-gon, monotone lattice paths that never cross the diagonal, and the ways to fully parenthesise a product of n+1 matrices.
| Sequence | First values | Counts |
|---|---|---|
| Catalan Cₙ | 1, 1, 2, 5, 14, 42 | binary trees, parenthesisations, triangulations, Dyck paths |
| Bell Bₙ | 1, 1, 2, 5, 15, 52, 203 | partitions of an n-set = equivalence relations |
| Derangements Dₙ | 1, 0, 1, 2, 9, 44, 265 | permutations with no fixed point |
| Fibonacci Fₙ | 0, 1, 1, 2, 3, 5, 8 | tilings with 1s and 2s, strings with no two 1s |
| Stirling S(n,2) | 0, 1, 3, 7, 15, 31 | 2ⁿ⁻¹ − 1 partitions into two blocks |
| Factorial n! | 1, 1, 2, 6, 24, 120 | permutations |
Recognising which sequence a question is secretly asking about is half the work.
Check yourself
The number of ways to triangulate a convex hexagon (6 sides) is
Exam notes (the dense version)
Catalan Cₙ = C(2n,n)/(n+1): 1, 1, 2, 5, 14, 42, 132. It counts binary trees with n nodes, balanced parentheses, triangulations of an (n+2)-gon, and monotone paths below the diagonal. Stirling S(n,k) (second kind): partitions of an n-set into k blocks; S(n,2) = 2ⁿ⁻¹ − 1, S(n,n−1) = C(n,2). Bell Bₙ = Σ S(n,k): 1, 1, 2, 5, 15, 52.
Previous year questions: Combinatorics & Recurrences (17)
PYQs are grouped by topic, so this is the full set for Combinatorics & Recurrences; try the ones that match this subtopic. Open all 17 on the topic page.