Pattern Guide
Catalan Numbers
"C(n) counts balanced parentheses, BST shapes, polygon triangulations, and more."
Catalan numbers Cₙ = C(2n,n)/(n+1) count many combinatorial structures: valid parenthesizations of n+1 factors, binary trees with n+1 leaves, triangulations of (n+2)-gon, non-crossing partitions, monotone paths below diagonal. Recurrence: Cₙ = Σ Cᵢ × Cₙ₋₁₋ᵢ. Appear in DP problems where you split into two independent subproblems.
Problems you can solve with this pattern
4 problems · click any to start solving
// Method 1: DP recurrence — O(n²)
function catalanDP(n) {
const C = new Array(n + 1).fill(0);
C[0] = C[1] = 1;
for (let i = 2; i <= n; i++)
for (let j = 0; j < i; j++)
C[i] += C[j] * C[i - 1 - j];
return C[n];
}
// Method 2: Binomial coefficient formula — O(n)
function catalan(n) {
// C(n) = C(2n, n) / (n + 1)
let result = 1;
for (let i = 0; i < n; i++) {
result = result * (2 * n - i) / (i + 1);
}
return Math.round(result / (n + 1));
}
// Method 3: Recurrence C(n) = C(n-1) * 2*(2n-1) / (n+1)
function catalanSeq(maxN) {
const C = [1n];
for (let n = 1; n <= maxN; n++)
C.push(C[n-1] * BigInt(2*(2*n-1)) / BigInt(n+1));
return C;
}
// Common Catalan appearances:
// - Valid parenthesizations of n+1 factors: C(n)
// - Binary trees with n nodes: C(n)
// - Non-decreasing paths from (0,0) to (n,n) not crossing diagonal: C(n)
// - Ways to triangulate (n+2)-gon: C(n)Catalan numbers: C₀=1, C₁=1, C₂=2, C₃=5, C₄=14, C₅=42, ... Formula: Cₙ = C(2n,n)/(n+1). The key recurrence: Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ × Cₙ₋₁₋ᵢ (split any Catalan structure at its "root"). This recurrence appears in DP for: number of valid BSTs with n nodes, number of full binary trees, number of ways to triangulate a polygon, and many others.
// Method 1: DP recurrence — O(n²)
function catalanDP(n) {
const C = new Array(n + 1).fill(0);
C[0] = C[1] = 1;
for (let i = 2; i <= n; i++)
for (let j = 0; j < i; j++)
C[i] += C[j] * C[i - 1 - j];
return C[n];
}
// Method 2: Binomial coefficient formula — O(n)
function catalan(n) {
// C(n) = C(2n, n) / (n + 1)
let result = 1;
for (let i = 0; i < n; i++) {
result = result * (2 * n - i) / (i + 1);
}
return Math.round(result / (n + 1));
}
// Method 3: Recurrence C(n) = C(n-1) * 2*(2n-1) / (n+1)
function catalanSeq(maxN) {
const C = [1n];
for (let n = 1; n <= maxN; n++)
C.push(C[n-1] * BigInt(2*(2*n-1)) / BigInt(n+1));
return C;
}
// Common Catalan appearances:
// - Valid parenthesizations of n+1 factors: C(n)
// - Binary trees with n nodes: C(n)
// - Non-decreasing paths from (0,0) to (n,n) not crossing diagonal: C(n)
// - Ways to triangulate (n+2)-gon: C(n)- n pairs of balanced parentheses: C(n)
- Binary trees with n+1 leaves: C(n)
- Triangulations of (n+2)-gon: C(n)
- Monotone paths from (0,0) to (n,n) not crossing y=x: C(n)
- Stack-sortable permutations of 1..n: C(n)
Recognition tip: If your DP recurrence looks like dp[n] = Σᵢ dp[i] × dp[n-1-i], you're computing Catalan numbers.
Key formula: Cₙ = C(2n,n) / (n+1). First few: 1, 1, 2, 5, 14, 42, 132, 429, 1430...