Choosing k from n
The binomial coefficient, written n choose k, counts the number of ways to pick k items from n when order does not matter. It equals n factorial divided by the product of k factorial and n minus k factorial.
Computing it safely
Using factorials directly overflows quickly because factorials grow explosively. Better approaches:
- Multiplicative formula: build the result by multiplying n, then n minus one, and dividing by one, two, and so on. Each partial product is an integer, so you avoid giant intermediates.
- Pascal's triangle: each entry is the sum of the two entries above it. Filling a table needs only additions and no division, which is ideal under a modulus.
Exploit the symmetry that n choose k equals n choose n minus k, so always use the smaller of k and n minus k to do less work.
Under a modulus
When you need the value modulo a prime, division becomes multiplication by a modular inverse, computed with the extended Euclidean algorithm or via Fermat's little theorem. Precomputing factorials and their inverses answers many queries fast.
Key idea
Compute n choose k with the multiplicative formula or Pascal's triangle to dodge factorial overflow; use symmetry to minimize work, and modular inverses when working under a prime modulus.