CombinatoricsCounting

01Why it exists

Reach for it when you see:Choose k from n, order does not matter, counting paths across a grid, identical items into distinct boxes (stars and bars), probability as favourable outcomes over all outcomes, counting problems with the answer taken mod 10⁹+7, many queries of C(n, k).

02The core idea

Two basic counting formulas. A permutation, P(n, k) = n! / (n − k)!, picks k of n distinct items in order, so a different order counts as a different result. A combination, C(n, k) = n! / (k! · (n − k)!), ignores order, which is why you divide out the k! ways of arranging each chosen group. Plenty of problems turn out to be binomial coefficients once you tilt your head: the number of grid paths made of a steps right and b steps down is C(a + b, a), because all you decide is which of the a + b steps go right; and spreading n identical items across k boxes (empties allowed) is C(n + k − 1, k − 1), which amounts to placing k − 1 dividers among the n items — the stars and bars trick.

How you compute it depends on the size and on the modulus. The first way is Pascal's triangle: C(n, k) = C(n − 1, k − 1) + C(n − 1, k), which holds because asking whether the n-th item is chosen splits every selection into two non-overlapping classes. The whole table costs O(n²) time and space and uses nothing but addition, so any modulus works, and it suits n up to a few thousand. The second is the multiplicative formula for exact values, C(n, k) = ∏ (n − k + i) / i for i from 1 to k, where every intermediate result is C(n − k + i, i) and therefore an integer, at O(min(k, n − k)); but a 64-bit integer in C++ overflows once n passes roughly 60, so exact values need big integers or Python.

The third way is the standard one when the modulus is a prime p: precompute a factorial table fact[i] = i! mod p and an inverse factorial table inv_fact[i] = (i!)⁻¹ mod p, after which C(n, k) = fact[n] · inv_fact[k] · inv_fact[n − k] answers each query in O(1). The inverse table needs no fast exponentiation per cell: do it once for n!, then sweep right to left with inv_fact[i − 1] = inv_fact[i] · i, because (i − 1)! = i! / i. Building both tables costs O(n + log p) time and O(n) space. The precondition is n < p — from p! onward every factorial carries p as a factor, collapses to 0 under the modulus and has no inverse. When n exceeds p, reach for Lucas's theorem instead.

The usual traps: the answer is 0 when k < 0 or k > n, and skipping that guard walks off the end of the table; computing n! and then dividing overflows 64 bits at 21!; writing the multiplicative formula as res * ((n − k + i) / i) is wrong because integer division truncates first; a factorial table sized only to n gets queried past its end; Fermat's little theorem gets applied to a modulus that is not prime; and computing probabilities by multiplying binomials in floating point overflows or loses precision almost immediately, where adding and subtracting ln(n!) is the right move. How this sits with its neighbours: the previous lesson, Modular Arithmetic, supplies the inverses; Pascal's triangle is exactly the table-filling of Memoization & Tabulation; and Backtracking's Combinations actually enumerates all C(n, k) of them, with the binomial coefficient telling you how big that search will get.

03The algorithm

1. 1Decide first whether you are counting permutations or combinations and whether the items are identical, then restate the problem as C(n, k) or P(n, k) — grid paths are C(a + b, a), stars and bars is C(n + k − 1, k − 1).
2. 2For n up to a few thousand, or when the modulus is not prime: fill in Pascal's triangle with C[n][k] = C[n − 1][k − 1] + C[n − 1][k].
3. 3For a prime modulus p with n < p: build fact[0..n] using fact[i] = fact[i − 1] · i mod p.
4. 4inv_fact[n] = fact[n]^(p − 2) mod p, then sweep right to left with inv_fact[i − 1] = inv_fact[i] · i mod p.
5. 5On a query, return 0 when k < 0 or k > n; otherwise return fact[n] · inv_fact[k] · inv_fact[n − k] mod p.

04Interactive demo

The control at the top switches between the two methods. "Pascal's triangle" starts from the 1s at each end and fills rows 0 through 6 one cell at a time: blue is the cell being computed, amber marks the two cells above that feed it, and the note on the first cell breaks down why it is "the n-th item included" plus "the n-th item excluded". Row 6 comes out as 1, 6, 15, 20, 15, 6, 1, summing to 64 = 2⁶, and the green C(6, 2) = 15 is also the number of paths made of 4 steps right and 2 steps down. "Factorial table mod 13" computes C(8, 3) mod 13: it fills 0! through 8! left to right, applies Fermat's little theorem exactly once to 8! = 7 to get the inverse 2, then fills the inverse table right to left by multiplying each cell by i, with a check at every step. The query multiplies the three green cells, 7 × 11 × 9 ≡ 4, which matches 56 mod 13. The final step explains why n has to stay below the modulus.

05Code

The Python side has the Binomial class with its factorial and inverse-factorial tables plus the multiplicative formula for exact values, and puts them to work on the lottery, grid-path and stars-and-bars examples. The C++ side has the same Binomial struct, Pascal's triangle for when the modulus is not prime, and the lgamma-based log form used for probabilities.

MOD = 1_000_000_007


class Binomial:
    """Precompute factorials and their inverses so every later C(n, k) mod p is O(1). Requires n_max < p"""

    def __init__(self, n_max, p=MOD):
        self.p = p
        self.fact = [1] * (n_max + 1)
        for i in range(1, n_max + 1):
            self.fact[i] = self.fact[i - 1] * i % p
        self.inv_fact = [1] * (n_max + 1)
        self.inv_fact[n_max] = pow(self.fact[n_max], p - 2, p)   # the only fast exponentiation in the whole setup
        for i in range(n_max, 0, -1):
            self.inv_fact[i - 1] = self.inv_fact[i] * i % p     # inverse of (i-1)! = inverse of i! * i

    def C(self, n, k):
        if k < 0 or k > n:                      # nothing to choose, so 0; guard first to avoid an out-of-range index
            return 0
        return self.fact[n] * self.inv_fact[k] % self.p * self.inv_fact[n - k] % self.p


def comb_exact(n, k):
    """Exact value, O(min(k, n-k)). Step i holds C(n-k+i, i), always an integer, so multiplying before dividing leaves no remainder.
    From Python 3.8 onward math.comb does this for you"""
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)
    res = 1
    for i in range(1, k + 1):
        res = res * (n - k + i) // i
    return res


if __name__ == "__main__":
    print(Binomial(8, 13).C(8, 3), comb_exact(8, 3))   # 4 56: the demo's C(8, 3) mod 13
    print(comb_exact(49, 6))                    # 13983816: ways to draw 6 lottery numbers from 49
    print(comb_exact(4 + 2, 2))                 # 15: paths made of 4 steps right and 2 steps down
    print(comb_exact(10 + 4 - 1, 4 - 1))        # 286: 10 identical machines across 4 data centres (stars and bars)
    print(Binomial(200000).C(200000, 100000))   # 879467333

06Practice

• LeetCode 118Pascal's TriangleEasy
• LeetCode 1641Count Sorted Vowel Strings (stars and bars)Medium
• LeetCode 2400Number of Ways to Reach a Position After Exactly k Steps (decide how many steps go right)Medium
• LeetCode 1735Count Ways to Make Array With Product (factorise, then stars and bars for each prime)Hard
• LeetCode 1569Number of Ways to Reorder Array to Get Same BST (interleave the subtrees, C(n − 1, size of left subtree))Hard
• LeetCode 1916Count Ways to Build Rooms in an Ant Colony (factorial table plus inverses)Hard