Combinatorics

Combinatorics counts structured arrangements and selections. It underpins problems about paths through grids, valid parenthesizations, ways to partition a number, and much more. A dozen core formulas and techniques cover the vast majority of interview-level combinatorics.

Permutations and Combinations

Concept	Formula	Meaning	Example
nPr (permutation)	n! / (n-r)!	Ordered selection of r from n	5P3 = 60
nCr (combination)	n! / (r! × (n-r)!)	Unordered selection of r from n	5C3 = 10
Multiset permutation	n! / (k1! × k2! × …)	Arrange with repeated elements	AABB: 4!/2!2! = 6
Stars and bars	C(n+k-1, k-1)	Put n identical items into k buckets	C(n+k-1,k-1)

// Permutation nPr
function nPr(n: number, r: number): number {
  if (r > n) return 0;
  let result = 1;
  for (let i = n; i > n - r; i--) result *= i;
  return result;
}

// Combination nCr (iterative, avoids large factorials)
function nCr(n: number, r: number): number {
  if (r > n) return 0;
  r = Math.min(r, n - r);  // use smaller r for fewer iterations
  let result = 1;
  for (let i = 0; i < r; i++) {
    result = result * (n - i) / (i + 1);
  }
  return result;
}

console.log(nPr(5, 3));  // 60   = 5×4×3
console.log(nCr(5, 3));  // 10   = 60 / 6
console.log(nCr(10, 0)); // 1
console.log(nCr(10, 10));// 1

Pascal's Triangle

Pascal's triangle computes all nCr values using the recurrence C(n, k) = C(n-1, k-1) + C(n-1, k). Each entry is the sum of the two directly above it. This DP approach avoids large intermediate factorials and handles modular arithmetic naturally.

// Pascal's triangle — all nCr up to size rows
function pascalTriangle(size: number): number[][] {
  const C: number[][] = Array.from({ length: size }, () => new Array(size).fill(0));
  for (let n = 0; n < size; n++) {
    C[n][0] = 1;
    for (let k = 1; k <= n; k++) {
      C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
    }
  }
  return C;
}

const C = pascalTriangle(7);
// Row 0: [1]
// Row 1: [1, 1]
// Row 2: [1, 2, 1]
// Row 3: [1, 3, 3, 1]
// Row 4: [1, 4, 6, 4, 1]
// Row 5: [1, 5, 10, 10, 5, 1]
// Row 6: [1, 6, 15, 20, 15, 6, 1]

console.log(C[6][3]); // 20

// With modular arithmetic — prevents overflow for large n
const MOD = 1_000_000_007;
function pascalMod(size: number): number[][] {
  const C: number[][] = Array.from({ length: size }, () => new Array(size).fill(0));
  for (let n = 0; n < size; n++) {
    C[n][0] = 1;
    for (let k = 1; k <= n; k++) {
      C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % MOD;
    }
  }
  return C;
}

Counting Paths in a Grid

From the top-left to the bottom-right of an m×n grid, moving only right or down, the number of paths is C(m+n-2, m-1) — you must make exactly (m-1) down moves and (n-1) right moves, in any order.

// Paths in m×n grid — closed form
function gridPaths(m: number, n: number): number {
  return nCr(m + n - 2, m - 1);
}

console.log(gridPaths(3, 3));  // 6  (C(4,2))
console.log(gridPaths(3, 7));  // 28 (C(8,2))

// DP approach when obstacles are involved
function uniquePathsWithObstacles(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  for (let i = 0; i < m && !grid[i][0]; i++) dp[i][0] = 1;
  for (let j = 0; j < n && !grid[0][j]; j++) dp[0][j] = 1;
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      if (!grid[i][j]) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  return dp[m - 1][n - 1];
}

Stars and Bars

"In how many ways can you distribute n identical balls into k distinct boxes?"

The answer is C(n + k - 1, k - 1). Imagine n stars and k-1 vertical bars separating them into groups — choosing where to place the bars determines the distribution.

// Ways to distribute n items into k buckets (0 items per bucket allowed)
function starsAndBars(n: number, k: number): number {
  return nCr(n + k - 1, k - 1);
}

// Distribute 5 identical candies among 3 kids
console.log(starsAndBars(5, 3));  // C(7, 2) = 21

// Each kid must get at least 1: subtract 1 from each bucket first → n' = n - k
function starsAndBarsAtLeastOne(n: number, k: number): number {
  if (n < k) return 0;
  return nCr(n - 1, k - 1);
}
console.log(starsAndBarsAtLeastOne(5, 3));  // C(4, 2) = 6

Inclusion-Exclusion Principle

Count elements in a union by adding individual set sizes, subtracting pairwise intersections, adding triple intersections, and so on.

|A ∪ B| = |A| + |B| - |A ∩ B|

|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

// How many integers in [1, n] are divisible by a OR b?
function divisibleByAOrB(n: number, a: number, b: number): number {
  function lcm(x: number, y: number): number {
    return (x / gcd(x, y)) * y;
  }
  function gcd(x: number, y: number): number {
    return y === 0 ? x : gcd(y, x % y);
  }
  // |A| + |B| - |A ∩ B|  where A ∩ B = multiples of lcm(a,b)
  return Math.floor(n / a) + Math.floor(n / b) - Math.floor(n / lcm(a, b));
}

// Integers in [1, 100] divisible by 3 or 5 (LeetCode FizzBuzz variant)
console.log(divisibleByAOrB(100, 3, 5)); // 47

Catalan Numbers

The nth Catalan number counts a surprising variety of combinatorial structures:

Valid sequences of n pairs of matching parentheses
Number of distinct BSTs with n keys
Number of mountain paths across a grid (monotonic lattice paths)
Number of ways to triangulate a convex polygon with n+2 vertices
Number of full binary trees with n+1 leaves

The formula: C(n) = C(2n, n) / (n + 1). The first few values: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862.

// Catalan number using the binomial coefficient formula
function catalan(n: number): number {
  return nCr(2 * n, n) / (n + 1);
}

// Catalan via DP recurrence: C(n) = sum of C(i) * C(n-1-i) for i in [0, n-1]
function catalanDP(n: number): number[] {
  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;
}

console.log(catalan(0)); // 1
console.log(catalan(3)); // 5   (5 valid parenthesizations of 3 pairs)
console.log(catalan(4)); // 14

// LC 96 — Unique Binary Search Trees (counts using Catalan)
function numTrees(n: number): number {
  return catalan(n);
}
console.log(numTrees(3));  // 5  (5 structurally distinct BSTs with keys 1,2,3)
console.log(numTrees(4));  // 14

Derangements

A derangement is a permutation where no element appears in its original position. The count D(n) satisfies: D(n) = (n-1)(D(n-1) + D(n-2)) with D(0)=1, D(1)=0.

function derangement(n: number): number {
  if (n === 0) return 1;
  if (n === 1) return 0;
  let prev2 = 1, prev1 = 0;
  for (let i = 2; i <= n; i++) {
    const curr = (i - 1) * (prev1 + prev2);
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

// D(4) = 9: out of 24 permutations of [1,2,3,4], 9 have no fixed point
console.log(derangement(4)); // 9

Tip

When a problem asks "how many ways" with constraints, classify it: ordered selection → nPr, unordered selection → nCr, distributing identical objects → stars and bars, structures without crossing constraints → often Catalan numbers. Write down what is being counted before reaching for a formula.