1. One-Liner
The n-th Catalan number counts dozens of equivalent structures (balanced parentheses, binary trees, polygon triangulations) and satisfies C_n = Σ C_i·C_{n-1-i} with DP in O(n²) or closed form.
2. The Problem It Solves
You need the number of well-formed length-2n parenthesis strings, or full binary trees with n+1 leaves, etc.—all counted by Catalan numbers.
3. The Core Idea
First split decomposition: choose where the matching closing paren pairs with the first open—left and right subproblems are independent smaller Catalan instances → convolution recurrence.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1 | C0=1 |
| 2 | C_n = Σ_{i=0}^{n-1} C_i·C_{n-1-i} |
| 3 | Fill 0..n increasing |
| 4 | Optional: C_n = (1/(n+1))·binom(2n,n) |
5. Dry Run Example
C0=1, C1=1, C2=2, C3=5 — five parenthesis strings for n=3.
6. Key Properties
| Property | Value |
|---|---|
| Growth | Roughly ~4ⁿ |
| Mod | Often compute modulo prime |
7. Where It Is Used
| Domain | Use |
|---|---|
| Competitive programming | Grid paths not crossing diagonal |
| CS theory | Enumeration of structures |
8. Interview Tips
Derive recurrence from BST count or parentheses; know modular inverse for closed form under modulo.
9. Comparison with Other Algorithms
| Approach | Cost |
|---|---|
| DP recurrence | O(n²) |
| Closed form | O(n) with binomial |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n²) DP |
| Space | O(n) |
Implementation Example (PYTHON)
def catalan(n: int) -> int:
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for k in range(2, n + 1):
for i in range(k):
dp[k] += dp[i] * dp[k - 1 - i]
return dp[n]