Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 36 ยท Applications

Combinatorics in Algorithms

Put counting to work in code: compute binomials modulo a prime with factorial tables and Lucas' theorem, rank and unrank permutations, next permutation and grid-path DP.

Counting formulas are most useful when a program can evaluate them quickly and exactly. This lesson collects the standard techniques: modular binomials for huge answers, Lucas' theorem when the modulus is small, ranking and unranking permutations (the bridge between objects and numbers), next permutation for enumeration in lexicographic order, and grid DP for counting constrained paths.

Binomials modulo a prime

Contest and production code usually reports counts mod p with p = 998244353 or 10^9 + 7, because binom(100000, 50000) has tens of thousands of digits. The method:

  1. Precompute fact[i] = i! mod p for i <= N.
  2. Precompute inverse factorials: inv_fact[N] = fact[N]^(p-2) mod p (Fermat's little theorem), then inv_fact[i-1] = inv_fact[i] * i.
  3. nCr(n, r) = fact[n] * inv_fact[r] * inv_fact[n-r] mod p.

After O(N) setup each query is O(1).

Lucas' theorem for a small prime modulus

If p is a small prime but n is enormous (such as 10^12), factorial tables are impossible and n! contains the factor p, so inverses fail. Lucas' theorem writes n and r in base p with digits n_i, r_i and says:

binom(n, r) = product over i of binom(n_i, r_i) (mod p).

If any digit r_i > n_i the binomial coefficient is divisible by p.

Python nCr mod p and Lucas' theorem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

nCr(100, 50) mod 998244353 is 198626801, matching Python's exact big integer. The Lucas call for binom(10^12, 5*10^11) mod 13 is 0 (a digit of the lower number exceeds the upper one), and binom(1000, 300) mod 7 = 1 matches the exact value.

Ranking and unranking permutations

A rank assigns each permutation of n a unique number in 0 .. n!-1 (its position in lexicographic order); unranking inverts it. The rank is built from the Lehmer code: for each position i, count how many later entries are smaller, multiply by (n-1-i)!, and add. This is the factorial number system, and it lets you pick the 1,000,000th permutation of 10 items without generating the first 999,999.

next_permutation generates them in order: find the rightmost position i with a[i] < a[i+1], swap a[i] with the smallest larger entry to its right, and reverse the suffix.

Python Rank, unrank, next permutation, grid paths

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The permutation [2, 0, 3, 1] has rank 13, and rank 14 of 4 items is [2, 1, 0, 3]. The check over all 120 permutations of 5 items confirms the two functions are inverse and agree with itertools order. next_permutation visits exactly 4! = 24 arrangements. The last block counts monotone paths across a 5 x 5 grid with two blocked cells: 18 (without blockers it would be binom(8,4) = 70).

Grid paths with obstacles

When cells can be blocked, no binomial formula applies, but the recurrence paths(i,j) = paths(i-1,j) + paths(i,j-1) (set to 0 on blocked cells) does, in O(RC) time. This is the standard "number of unique paths with obstacles" dynamic program; it is a recurrence over two indices.

flowchart LR
    A["Need a count"] --> B{"Closed form exists?"}
    B -->|"yes"| C["Formula + modular factorial table"]
    B -->|"no, local structure"| D["Recurrence / DP"]
    B -->|"need the objects themselves"| E["Generate: backtracking, next_permutation"]
    B -->|"need the k-th object"| F["Rank / unrank"]

Choosing the right computational technique.

Practical advice

  • Python big integers are exact, so use math.comb, math.perm, math.factorial when numbers stay moderate; use modular tables when you need speed or a modulus.
  • Use itertools.permutations, combinations, product to test your fast code against brute force on small input.
  • Division mod p means multiplication by the modular inverse; never use floating point for counts.

Fermat inverses a^(p-2) mod p only work when p is prime and a is not a multiple of p. For n >= p use Lucas' theorem instead.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why precompute factorials and inverse factorials modulo p?

    nCr = fact[n] * inv_fact[r] * inv_fact[n-r] mod p.
  2. 2. When is Lucas' theorem the right tool?

    Lucas works digit by digit in base p, so n can be astronomically large.
  3. 3. The Lehmer-code rank of a permutation uses which numbers?

    Each digit of the factorial number system is the number of later entries that are smaller.
  4. 4. A 5x5 grid has no blocked cells. How many right/down paths from corner to corner?

    binom(8, 4) = 70.

Summary

  • Modular binomials: factorial table plus inverse factorials via Fermat; Lucas for small primes.
  • Rank and unrank permutations with the Lehmer code; enumerate with next_permutation.
  • Obstacle-aware paths: a two-index recurrence in O(RC).
  • Cross-check fast code against itertools brute force.

Next: Project: A Counting Library