Combinatorial DP — binomial coefficient, Catalan number, derangements, count balanced BSTs of height h

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}