Sign in to watch this lesson
Algorithms - Recursion, Backtracking and Combinatorics · 5:04
Binomial Coefficients
Counting monotone grid paths by listing them gets hopeless fast (a 16 x 16 grid took about 6 s to enumerate here, and 18 x 18 has 15 times more), so we count them instead: a path is a choice of which steps go right, n choose k. We build Pascal's triangle from 'left plus above', see why it works under any modulus, avoid factorial overflow with the multiplicative formula and a 128-bit product, and then precompute factorials and inverse factorials modulo a prime (Fermat once, then a backward walk) so every C(n, k) is three lookups.
You will learn
- Recognise a counting problem as choosing k of n and compute C(n, k) with Pascal's rule in O(n^2) additions, under any modulus
- Compute exact C(n, k) with the multiplicative formula without overflow, using C(n, k) = C(n, n-k) and a 128-bit intermediate
- Precompute factorials and inverse factorials modulo a prime p > n (one Fermat inverse plus a backward walk) and answer each query in O(1)
- Spot the traps: unreduced products of residues, factorial overflow, and a modulus that is not prime or not larger than n