Combinatorial DP — binomial coefficient, Catalan number, derangements, count balanced BSTs of height h
Problem
Counting problems solved with recurrences, usually modulo 1e9 + 7:
Binomial coefficient C(n, r) (and the permutation coefficient P(n, r)). The nth Catalan number — the number of BSTs with n keys, or of valid parenthesis strings. Derangements — permutations where no element stays in its original position. The number of balanced binary trees of height h.
Example 1
Input: C(5, 2), Catalan(4), derangements(4) Output: 10, 14, 9
Also asked as: Binomial CoefficientProblem · Permutation CoefficientProblem · Program for nth Catalan Number · Count Derangements (Permutation such that no element appears in its original position) · Count Balanced Binary Trees of Height h
Test cases
Case 1
Input: 5, 2 Expected: 10
Case 2
Input: 10, 3 Expected: 120
Case 3
Input: 5, 5 Expected: 1
Case 4
Input: 5, 0 Expected: 1
View solutionHide solution1 approach
1. Pascal's triangle / recurrences
Time O(n·k) / O(n²) / O(n)Space O(n·k) / O(n)
C(n,k) = C(n−1,k−1) + C(n−1,k). Catalan Cₙ = Σ Cᵢ·Cₙ₋₁₋ᵢ (or C(2n,n)/(n+1)). Derangements Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂). Balanced BSTs of height h: count(h) = 2·count(h−1)·count(h−2) + count(h−1)².
function binomial(n, k) { const dp = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(0)); for (let i = 0; i <= n; i++) { dp[i][0] = 1; for (let j = 1; j <= Math.min(i, k); j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } return dp[n][k];}function catalan(n) { const c = new Array(n + 1).fill(0); c[0] = 1; for (let i = 1; i <= n; i++) for (let j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j]; return c[n];}function derangements(n) { if (n <= 1) return n === 0 ? 1 : 0; let a = 1, b = 0; // D0, D1 for (let i = 2; i <= n; i++) [a, b] = [b, (i - 1) * (a + b)]; return b;}function countBalancedBST(h, MOD = 1_000_000_007n) { let a = 1n, b = 1n; // count(0), count(1) if (h === 0 || h === 1) return 1; for (let i = 2; i <= h; i++) { const cur = (2n * a * b + b * b) % MOD; a = b; b = cur; } return Number(b);}