Counting Without Listing
In short: C(n, r), "n choose r", counts how many r-item subsets an
n-item set has, without ever listing them. Two ways to compute it: Pascal's
triangle, where every cell is the sum of the two cells above it — the
first dynamic-programming table most people meet, often years before they'd
call it that — and the factorial formula n! / (r! · (n-r)!), which
needs a modular inverse to divide under a modulus, since there's no /
in modular arithmetic. Quarry's hash kernel uses both: Pascal's triangle to
explain where the numbers come from, and the factorial-and-inverse route to
compute C(n, r) mod p for huge n without building a triangle that big.
Splitting a bill among friends, the counting version
Eight friends split into a table of 3 and a table of 5 for a trip's two
cars. How many different groups of 3 could go in the first car? That's
C(8, 3) — order inside the car doesn't matter, only who's in it.
This works for small n, but num is a product of r numbers close to
n — for n in the millions, num becomes an enormous integer before
the division ever happens. That's fine in Python's big-int arithmetic, but
slow, and it's exactly the kind of growth Quarry's hash kernel needs to
avoid when counting collisions over billions of keys.
Pascal's triangle: the first DP table
Every entry in Pascal's triangle is the sum of the two entries above it,
with 1s down both edges. C(n, r) is row n, position r (both starting
at 0). This is the recurrence C(n, r) = C(n-1, r-1) + C(n-1, r) — choosing
whether item n is in the group or not.
Row n, position r of Pascal's triangle is C(n, r). The diag and above pointers show the two cells each new cell sums — include item n, or don't.
Dividing under a modulus
C(52, 5) — five-card poker hands from a 52-card deck — is 2,598,960,
small enough to compute directly. Quarry needs C(n, r) mod p for n up to
billions, where the plain numerator would be a number with thousands of
digits. The factorial formula still works: C(n, r) = n! / (r! · (n-r)!).
The problem is there's no division in modular arithmetic — / isn't one
of the operations % respects. The fix is a modular inverse: a number
inv such that x * inv ≡ 1 (mod p), so multiplying by inv acts like
dividing by x. When p is prime, Fermat's little theorem gives it in one
line: inv(x) = pow(x, p - 2, p).
pow(x, mod - 2, mod) is Python's built-in fast modular exponentiation —
the same binary-exponentiation idea from the bits section, just reused
here, not re-derived.
MOD = 1_000_000_007
def modinv(x, mod=MOD):
return pow(x, mod - 2, mod)
def ncr_mod(n, r, mod=MOD):
if r < 0 or r > n:
return 0
num = 1
den = 1
for i in range(r):
num = num * ((n - i) % mod) % mod
den = den * (i + 1) % mod
return num * modinv(den, mod) % mod
print(ncr_mod(5, 2), ncr_mod(6, 7))Counting without listing: grid paths
A delivery bot on a rows × cols grid can only move right or down, from the
top-left corner to the bottom-right. Every path is a sequence of rows
"down" moves and cols "right" moves in some order — so the number of paths
is just "how many ways to place the down moves among all the moves", which
is C(rows + cols, rows).
Listing routes directly would be 2^(rows+cols) work in the worst case, one
branch per move. C(n, r) counts them in O(r) — no path is ever built.
Quick practice
def ncr_pascal_row(n):
row = [1]
for k in range(1, n + 1):
row.append(row[-1] * (n - k + 1) // k)
return row
print(ncr_pascal_row(4))With mod 1,000,000,007 this happened to print the right answer, because num never wrapped. With the smaller prime 1009 it prints 3, not 785 — the wraparound breaks plain division. Fix it into a true modular computation.
What it costs
| approach | cost | when to use |
|---|---|---|
| Pascal's triangle up to row n | O(n²) time and space | small n, or you need every C(i, j) along the way |
| multiplicative row formula | O(n) per row | one row, no modulus needed |
| factorial + modular inverse | O(r) per query after an O(n) precompute of factorials | many queries, large n, answers mod a prime |
🎯 Your turn
Build ncr_mod(n, r, mod): C(n, r) mod p, using the factorial-style
numerator and a modular inverse for the denominator — no //, no building a
full Pascal's triangle.
ncr_mod(5, 2, 1000000007)→10ncr_mod(52, 5, 1000000007)→2598960ncr_mod(6, 7, 1000000007)→0
Hint: multiply r shrinking terms into num and 1..r into den,
modding both every step, then return
num * pow(den, mod - 2, mod) % mod.
Press ▶ Run, then ✓ Check.