Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 63 ยท Math for Contests

nCr Mod p with Lucas, Catalan and Stirling Numbers

Contest counting templates in Python: nCr mod a small prime with Lucas, lattice paths and brackets by reflection, surjections and Stirling numbers.

The earlier lesson on combinatorics for contests gave you factorial tables, stars and bars, inclusion-exclusion and Catalan numbers. This lesson fills the gaps that show up one step later in contest sets: what to do when n is larger than the modulus, how to count paths and bracket sequences under a boundary constraint, and how to count surjections and partitions into groups with Stirling numbers.

Each template is short and each one is checked against brute force. For the theory behind Lucas' theorem and the Stirling recurrence see the DSA lesson Lucas, Stirling, Bell and Catalan.

nCr mod a small prime with Lucas

The factorial method fails when n >= p, because n! contains p and is 0 modulo p. In contests this appears as "compute C(n, r) mod p for n up to 10^18 but p up to 10^6". Lucas' theorem splits n and r into base-p digits and multiplies small binomials:

TEXT
C(n, r) = product of C(n_i, r_i)   (mod p),  digits taken in base p

For many queries, build the factorial and inverse factorial table of size p once.

Python Lucas template for many queries

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.

Inverse factorials are computed in O(p) by one modular power and a backward loop, which is the standard speed trick.

For a composite modulus, Lucas does not apply directly. Split the modulus into prime powers, solve each, and merge with the Chinese Remainder Theorem. If the modulus is 10^9 + 7 (a large prime) and n < p, use plain factorials instead.

Paths with a boundary: the reflection principle

How many monotone lattice paths from (0, 0) to (a, b) (steps right or up) never go above the diagonal (y <= x at every point)? Counting all paths is C(a + b, a). A path that touches the line y = x + 1 is "bad". Reflect the part of a bad path before its first touch across that line: the start (0, 0) becomes (-1, 1), and bad paths correspond one-to-one with all paths from (-1, 1) to (a, b). So

TEXT
good = C(a + b, a) - C(a + b, a + 1)        (for b <= a)

For a = b = n this is the n-th Catalan number. The same reflection idea counts bracket sequences that never go below zero (the ballot problem), and sequences with a fixed final height.

Python Constrained paths and bracket sequences by reflection

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 last line uses exact big integers, which is fine for n = 2000; for n near 10^6 or more, switch to factorial tables mod 10^9 + 7 instead. When the boundary is y <= x + k for another offset, reflect across that line instead: the subtracted term becomes C(a + b, a + k + 1).

Surjections and Stirling numbers

How many ways to assign n labeled items to k labeled boxes so that no box is empty? Count all assignments k^n, then subtract those missing at least one box with inclusion-exclusion:

TEXT
surj(n, k) = sum for j = 0..k of  (-1)^j * C(k, j) * (k - j)^n

This takes O(k log n) with fast powers and a factorial table, and it handles n = 10^18 easily. The number of ways to split n items into k unlabeled non-empty groups is the Stirling number S(n, k) = surj(n, k) / k!.

Python Surjections and Stirling numbers mod p

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.

Where each formula fits:

Problem Formula
n labeled items into k labeled boxes, none empty surj(n, k) by inclusion-exclusion
n items into k unlabeled non-empty groups S(n, k) = surj(n, k) / k!
Partitions of n items into any number of groups (Bell) sum of S(n, k) over k, or the Bell triangle
Monotone paths not crossing a line C(total, a) - C(total, a + offset) by reflection
C(n, r) mod p, n >= p, p small Lucas

Habits for counting problems

  • Test every formula against a brute force on n <= 8 before using it on big inputs.
  • Check edge cases: n = 0, k > n, r > n, and k = 0.
  • Know which modulus you have: prime and large (factorials), prime and small (Lucas), composite (split and CRT).
  • Remember the inverse of k! appears when you go from labeled to unlabeled.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can't you use plain factorials for C(n, r) mod p when n >= p?

    Once n >= p, the product 1..n includes p. The inverse of a multiple of p does not exist mod p, so Lucas' digit-by-digit method is used.
  2. 2. By the reflection principle, how many monotone paths from (0,0) to (n,n) never go above y = x?

    All paths minus the bad ones, which biject with paths ending at the reflected point. This is the Catalan number.
  3. 3. How many ways can 4 labeled items be placed into 2 labeled non-empty boxes?

    Inclusion-exclusion: 2^4 - 2 * 1^4 + 0^4 = 16 - 2 = 14.
  4. 4. How is S(n, k), the Stirling number of the second kind, related to surjections?

    Surjections label the boxes, and the k! orderings of the boxes are not distinguished for unlabeled groups.

Summary

  • For n >= p with small prime p, use Lucas: multiply C(n_i, r_i) over base-p digits, with factorial tables of size p.
  • Paths and bracket sequences with a boundary are counted by reflection: total minus the reflected count.
  • Surjections use inclusion-exclusion in O(k log n); divide by k! for unlabeled groups (Stirling numbers).
  • Always verify against brute force and check edge cases such as k > n.

Next: Probability and Expected Value