Combinations and Pascal’s triangle

How many ways are there to choose 3 coaches out of 8? Counting questions like this come up whenever an algorithm’s cost depends on how many cases there are, and as problems in their own right. This lesson builds the main counting tool, the number of combinations, and shows how to compute it exactly, modulo a prime, and for huge numbers.

Choosing k of n

n factorial, written n!, is 1 · 2 · … · n, the number of orders of n different items: n choices for the first place, n − 1 for the second, and so on. By agreement 0! = 1 (there is one order of no items). The number of ways to fill k places in order from n items is n · (n − 1) · … · (n − k + 1), which is n! / (n − k)!.

If the order does not matter, each set of k items has been counted once for each of its k! orders. So the number of ways to choose k items from n, read “n choose k” and written C(n, k) here, is

C(5, 2) = 120 / (2 · 6) = 10, and C(8, 3) = 56. Choosing k items to take is the same as choosing n − k to leave, so C(n, k) = C(n, n − k). Python has math.comb(n, k), math.perm(n, k) (ordered, so math.perm(5, 2) is 20) and math.factorial(n), all exact.

def comb(n, k):
    if not 0 <= k <= n:
        return 0
    k = min(k, n - k)
    c = 1
    for i in range(k):
        c = c * (n - i) // (i + 1)   # always a whole number
    return c

After step i, c is C(n, i + 1), a whole number, so the division is always exact. Multiplying before dividing keeps it so.

Pascal’s rule

Why? Look at one particular item, the last one. A choice of k items from n either takes it, and then the other k − 1 come from the other n − 1 items, or leaves it, and then all k come from those n − 1. Every choice is in exactly one of the two groups. Written as a table, each number is the sum of the one above it and the one above-left: Pascal’s triangle.

Row n adds up to 2ⁿ, because together the row counts every subset of n items (BITS-5). The rows are also the numbers in (x + y)ⁿ written out: (x + y)³ = x³ + 3x²y + 3xy² + y³, with 1, 3, 3, 1 from row 3. This is the binomial theorem, and it is why C(n, k) is also called a binomial coefficient.

The rule uses only addition, so it works modulo any m, prime or not. Building the table up to row n costs O(n²), which is fine for n up to a few thousand:

def pascal_mod(n, m):
    C = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        C[i][0] = 1 % m
        for k in range(1, i + 1):
            C[i][k] = (C[i - 1][k - 1] + C[i - 1][k]) % m
    return C

Counts modulo a prime

For n up to a million, the table has too many cells. Use the factorial formula instead, modulo a prime p that is bigger than n. Lesson 2 says you cannot simply divide remainders, but lesson 5 says that dividing by a means multiplying by its inverse. So

Work out the factorials 0!, 1!, …, N! modulo p once, and their inverses with lesson 5’s method (one pow for N!, then down). After that, each C(n, k) is two multiplications. That is O(N) to prepare and O(1) per question. MATH-P6 asks for it. Why must p be bigger than n? If p ≤ n, then p divides n!, so n! leaves 0 and has no inverse.

Huge n, small p

When n is 10¹⁸ and p is small, factorials are out of reach. Lucas’s theorem (Édouard Lucas, 1878) helps: write n and k in base p, as digits n₀, n₁, … and k₀, k₁, …. Then

Each small C(nᵢ, kᵢ) has both numbers below p, so the method above handles it. For p = 2 the digits are bits, and C(1, 0) = C(1, 1) = C(0, 0) = 1 while C(0, 1) = 0. So C(n, k) is odd exactly when no bit of k is 1 where n has a 0, that is, when k & n == k. The second version of the figure shows the pattern this makes.

Counting patterns

• Paths in a grid. A path that goes r steps down and c steps right is a choice of which r of its r + c steps go down: C(r + c, r). DYNP-5 counted the same paths with a table, which also handles blocked cells.
• Sharing out. The ways to give n identical sweets to k children are C(n + k − 1, k − 1). Write the sweets as n dots in a row; the k − 1 dividers between the children go in any of the n + k − 1 places.
• Brackets and trees. The number of search-tree shapes with n keys (DYNP-P1) is the Catalan number C(2n, n) / (n + 1).
• Counting with overlaps. To count the items in A or B, add the two counts and take away the items counted twice. Writing |A| for the number of items in A: |A or B| = |A| + |B| − |A and B|. This is the start of inclusion–exclusion.

Now try MATH-P6, Combinations modulo a prime.