Combinatorics / Binomial Coefficients

Combinatorics and Binomial Coefficients

Many competitive programming problems reduce to counting: paths through a grid, ways to arrange items, valid bracket sequences. The binomial coefficient C(n, k) is the foundation of most of these counts. Understanding how to compute it efficiently, especially under modular arithmetic, unlocks a large class of problems.

The Definition

$C(n, k)$, read "n choose k", counts the number of ways to select $k$ items from $n$ distinct items where order does not matter. The closed-form formula is:

C(n, k) = n! / (k! * (n - k)!)

For example, $C(5, 2) = 120 / (2 \times 6) = 10$. There are indeed 10 ways to pick 2 items from {A, B, C, D, E}.

Pascal's Triangle Recurrence

Before reaching for factorials, it helps to understand the recursive structure. Every binomial coefficient satisfies:

C(n, k) = C(n-1, k-1) + C(n-1, k)

This says: to choose k items from n, either you include item n (leaving you to choose k-1 from the remaining n-1) or you exclude it (choosing all k from the remaining n-1). Pascal's triangle is just this recurrence written out as a triangle, with C(n, 0) = C(n, n) = 1 as base cases.

For small n and k with no modular constraints, you can build a 2D table bottom-up:

def pascal_table(max_n):
    C = [[0] * (max_n + 1) for _ in range(max_n + 1)]
    for n in range(max_n + 1):
        C[n][0] = 1
        for k in range(1, n + 1):
            C[n][k] = C[n-1][k-1] + C[n-1][k]
    return C

This takes $O(n^2)$ time and space, which is fine when n is a few hundred but breaks down at $n = 10^6$.

Modular Arithmetic: The Competitive Programming Standard

Most problems involving large n specify that the answer should be returned modulo a prime p (commonly $10^9 + 7$). Division modulo a prime requires modular inverses rather than ordinary division. The efficient approach precomputes factorials and their modular inverses up front.

Fermat's Little Theorem

For a prime p and any a not divisible by p, Fermat's little theorem states:

a^(p-1) ≡ 1 (mod p)

Rearranging: a^(-1) ≡ a^(p-2) (mod p). Python's built-in pow(a, p-2, p) computes this in $O(\log p)$ time using fast exponentiation. We use it to find the modular inverse of the largest factorial, then work backwards to fill in all smaller inverse factorials cheaply:

inv_fact[n] = pow(fact[n], mod - 2, mod)
inv_fact[i] = inv_fact[i+1] * (i+1) % mod

The backward recurrence works because inv_fact[i] = inv_fact[i+1] (i+1) follows directly from (i+1)! = (i+1) i!, so (i!)^(-1) = ((i+1)!)^(-1) * (i+1).

The Full Precomputation Template

def precompute(n, mod=10**9 + 7):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % mod
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], mod - 2, mod)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % mod
    return fact, inv_fact

def comb(n, k, fact, inv_fact, mod=10**9 + 7):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod

Precomputation is $O(n)$ time and space. After that, each C(n, k) query is $O(1)$. When a problem requires thousands of binomial coefficient lookups over values up to $10^6$, this is the only practical approach.

Grid Path Counting

A classic application: how many paths lead from the top-left corner of an m-by-n grid to the bottom-right corner, moving only right or down? Every such path makes exactly m down-moves and n right-moves in some order, a total of m+n moves. Choosing which m of those moves are "down" fully determines the path. The answer is:

paths = C(m + n, m)

For a $3 \times 7$ grid that is $C(10, 3) = 120$. With the precomputed tables above, this is a single $O(1)$ lookup.

Catalan Numbers

The nth Catalan number counts many combinatorial structures: valid sequences of n pairs of parentheses, the number of distinct binary search trees with n nodes, and paths that never cross the diagonal. It is defined as:

Cat(n) = C(2n, n) / (n + 1)

In modular arithmetic, dividing by (n+1) becomes multiplying by the modular inverse of (n+1):

def catalan(n, fact, inv_fact, mod=10**9 + 7):
    return comb(2*n, n, fact, inv_fact, mod) * pow(n + 1, mod - 2, mod) % mod

Catalan numbers grow roughly as $4^n / (n^{3/2} \cdot \sqrt{\pi})$, so they get large quickly, and modular arithmetic is almost always necessary.

Stars and Bars

Stars and bars answers the question: in how many ways can you distribute n identical items into k distinct bins, where each bin may receive zero or more items? The formula is:

C(n + k - 1, k - 1)

Think of it as placing $k-1$ dividers among $n$ stars. For example, distributing 5 apples among 3 people is $C(7, 2) = 21$. If each person must receive at least one apple, first give each one apple (reducing the problem to distributing $n-k$ items), yielding $C(n-1, k-1)$.

LeetCode Variants

• LeetCode 62. Unique Paths: paths from top-left to bottom-right of an m × n grid is exactly $C(m + n - 2, m - 1)$, a direct one-line answer with precomputed factorials.
• LeetCode 118. Pascal's Triangle and LeetCode 119. Pascal's Triangle II: build the table or a single row using the additive recurrence.
• LeetCode 920. Number of Music Playlists: a DP with inclusion-exclusion that ultimately leans on modular combinations.
• LeetCode 1359. Count All Valid Pickup and Delivery Options: the closed form is $\frac{(2n)!}{2^n}$, computed with modular inverses.
• LeetCode 96. Unique Binary Search Trees: the nth Catalan number.
• LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty and LeetCode 2954. Count the Number of Infection Sequences: both demand precomputed factorials and modular inverses to handle large n.

When to Reach for It

If a problem asks "how many ways" and the count grows combinatorially (n!, C(n, k), Catalan), reach for binomial coefficients. The signal strengthens when the answer must be taken modulo a large prime. That almost always means precomputed factorials plus Fermat's little theorem for inverses. If you find yourself writing a DP whose transitions look like Pascal's recurrence, you can often skip the table entirely and write the answer in closed form.

Complexity Summary

Precomputing factorials and inverse factorials up to N takes $O(N)$ time and $O(N)$ space. Each subsequent C(n, k) call is $O(1)$. If you only need a single row of Pascal's triangle, you can compute it iteratively using the recurrence $C(n, k) = C(n, k-1) \cdot (n-k+1) / k$, which avoids building the full table.

Recognizing this pattern

You're probably looking at combinatorics / binomial coefficients when:

• The question asks "how many ways" and the answer grows like n!, C(n, k), or a Catalan number.
• You're counting lattice paths in a grid where every step goes right or down.
• The DP you'd otherwise write has transitions that look like Pascal's recurrence C(n, k) = C(n-1, k-1) + C(n-1, k).
• The answer must be returned modulo a large prime, so precompute factorials and use Fermat's little theorem for inverses.

Common templates:

• Direct C(n, k) closed form: count paths or selections in one formula. Example: Unique Paths.
• Pascal's triangle row / table: build rows via the additive recurrence. Example: Pascal's Triangle.
• Factorial + inverse-factorial precompute mod prime: answer many C(n, k) mod p queries in O(1) each. Example: Count Anagrams.
• Catalan numbers: count balanced structures (parens, BSTs, triangulations). Example: Unique Binary Search Trees.