What are Catalan Numbers and Their Applications?
Learn Catalan number recurrence, its DP computation, and real applications like BST counting and balanced parentheses.
Expected Interview Answer
Catalan numbers are a sequence C(n) = (2n choose n) / (n+1), computed recursively as the sum over i from 0 to n-1 of C(i)*C(n-1-i), and they count a surprising range of recursively-structured combinatorial objects such as the number of valid binary search trees on n keys, balanced parenthesis arrangements, and ways to triangulate a convex polygon.
The recurrence C(n) = sum of C(i)*C(n-1-i) arises whenever a structure of size n splits into an independent left part of size i and right part of size n-1-i for every possible split point, which is exactly the shape of building a binary search tree by choosing which key is the root, or splitting a balanced parenthesis sequence around its first matched pair. Computed via dynamic programming this takes O(n^2) time and O(n) space, filling C(0)=1 up through C(n) using previously computed smaller values, though a closed-form using binomial coefficients gives O(n) time if factorials are precomputed. Concrete applications include: number of structurally distinct BSTs with n nodes, number of ways to fully parenthesize n+1 factors in a matrix chain product, number of ways to triangulate a convex polygon with n+2 sides, and number of valid sequences of n balanced push/pop stack operations. Recognizing the “split into two independent recursively-structured halves that sum over all split points” pattern is the key interview signal for Catalan numbers.
- Single recurrence explains many seemingly unrelated counting problems
- O(n^2) DP or O(n) closed form via binomial coefficient
- Recognizing the pattern avoids re-deriving DP from scratch for BSTs, parentheses, triangulations
- Grows super-exponentially, useful for reasoning about search space size
AI Mentor Explanation
A tournament organizer counting the number of distinct ways to seed a single-elimination bracket so that games are always played between adjacent seed groups discovers the same number shows up whether counting valid bracket shapes, valid ways to order a batting lineup into nested partnerships, or valid ways to split a long innings summary into balanced open/close commentary segments. Each of these problems splits into a left group and a right group at every possible split point, and the count for size n is the sum over all split points of the count for the left size times the count for the right size. This is the Catalan number recurrence: whenever a cricket-related structure recursively splits into two independent halves summed over every split, the same C(n) sequence appears no matter which specific structure you're counting.
Step-by-Step Explanation
Step 1
Recognize the recursive split pattern
A structure of size n splits into an independent left part of size i and right part of size n-1-i, for every i from 0 to n-1.
Step 2
Write the recurrence
C(n) = sum over i=0..n-1 of C(i) * C(n-1-i), with base case C(0) = 1.
Step 3
Compute bottom-up
Build C(0), C(1), ..., C(n) in order, using previously computed smaller values; O(n^2) time, O(n) space.
Step 4
Map to the concrete application
Identify what “left part” and “right part” mean in context (e.g. left/right BST subtree, or matched parenthesis interior/exterior).
What Interviewer Expects
- State the recurrence C(n) = sum of C(i)*C(n-1-i) and derive it from a concrete example (usually BST count)
- Name at least 2-3 applications: BST count, balanced parentheses, polygon triangulation, matrix chain parenthesization count
- Give the O(n^2) DP complexity and mention the O(n) closed-form alternative
- Recognize the “sum over all split points of left*right” pattern as the general Catalan signature
Common Mistakes
- Confusing Catalan numbers with simple binomial coefficients without the /(n+1) or recursive split structure
- Forgetting the base case C(0) = 1
- Only knowing one application (usually BST count) and unable to generalize the pattern to others
- Miscounting the split range, e.g. off-by-one in the sum bounds
Best Answer (HR Friendly)
“Catalan numbers are a sequence that shows up whenever you're counting structures that split recursively into two independent halves, like how many different binary search trees you can build with a set of keys, or how many ways to correctly balance a set of parentheses. I recognize the pattern by noticing the problem always breaks into a left part and a right part at every possible split point, and I compute the count with a simple dynamic programming table.”
Code Example
def catalan(n):
C = [0] * (n + 1)
C[0] = 1
for i in range(1, n + 1):
total = 0
for j in range(i):
total += C[j] * C[i - 1 - j]
C[i] = total
return C[n]
def count_unique_bsts(n):
# number of structurally distinct BSTs with n keys equals C(n)
return catalan(n)
print(catalan(5)) # 42
print(count_unique_bsts(5)) # 42Follow-up Questions
- How would you compute Catalan numbers in O(n) using the closed-form binomial coefficient formula?
- How does the balanced-parentheses application map onto the same recurrence?
- How many ways can a convex polygon with n+2 sides be triangulated, and why does that equal C(n)?
- How would you generate all valid parenthesizations, not just count them?
MCQ Practice
1. What is the base case of the Catalan number recurrence?
C(0) = 1 represents the single empty structure, anchoring the recurrence for all n >= 1.
2. How many structurally distinct binary search trees can be formed with 3 distinct keys?
C(3) = 5, matching the Catalan number for 3 keys (root choice creates 5 distinct BST shapes).
3. What is the time complexity of computing C(n) with the standard bottom-up DP?
Filling C(0) through C(n), each C(i) sums over i terms, giving O(n^2) total time.
Flash Cards
What is the Catalan number recurrence? — C(n) = sum over i=0..n-1 of C(i)*C(n-1-i), with C(0) = 1.
Name three applications of Catalan numbers. — Count of distinct BSTs on n keys, count of balanced parenthesis sequences, count of convex polygon triangulations.
What is the closed-form formula for C(n)? — C(n) = (2n choose n) / (n+1), computable in O(n) with precomputed factorials.
What is the general “signature” pattern for a Catalan problem? — A structure that recursively splits into two independent halves, summed over every possible split point.