Skip to content
Tutorials Center
My learning

Topics

Lesson 183 of 225 ยท Math and Bit Manipulation

Lucas' Theorem, Stirling, Bell and Catalan Numbers

Compute nCr mod a small prime with Lucas' theorem, then count set partitions and balanced structures with Stirling, Bell and Catalan numbers in Python.

The usual way to compute nCr mod p needs factorials and modular inverses, and it breaks when n >= p: the factorial n! becomes a multiple of p, so it has no inverse. Lucas' theorem repairs this for a small prime p by splitting n and r into base-p digits.

This lesson also introduces three counting sequences that pop up again and again: Stirling numbers (splitting a set into groups), Bell numbers (all ways to partition a set) and Catalan numbers (balanced parentheses, binary trees and many more). All of them come from short recurrences that you can code in a few lines. If you need a refresher on ordinary combinations, see Combinatorics and Counting.

Lucas' theorem

Let p be prime. Write n and r in base p:

TEXT
n = n_k * p^k + ... + n_1 * p + n_0
r = r_k * p^k + ... + r_1 * p + r_0

Then

TEXT
C(n, r)  =  C(n_k, r_k) * ... * C(n_1, r_1) * C(n_0, r_0)    (mod p)

where C(a, b) = 0 when b > a. Each factor involves numbers smaller than p, so a small table of factorials up to p - 1 is enough. If any digit of r exceeds the matching digit of n, the whole answer is 0.

Example: C(10, 3) mod 7. In base 7, 10 = 13 and 3 = 03, so the result is C(1, 0) * C(3, 3) = 1. Check: C(10, 3) = 120 = 17 * 7 + 1.

Python nCr mod p with 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.

Complexity. Precomputation is O(p). Each query takes O(log_p n) digit steps. This is ideal when p is small (say up to a few million) and n is astronomically big. For a large prime with n < p, plain factorial tables are better.

Lucas needs a prime modulus. For composite moduli, split into prime powers and combine with the Chinese Remainder Theorem; prime powers need a more advanced generalization.

Stirling numbers of the second kind

S(n, k) counts the ways to split n distinguishable items into exactly k non-empty, unlabeled groups. For three items {a, b, c} and two groups: {b,c}, {a,c}, {a,b}, so S(3, 2) = 3.

The recurrence considers the last item. Either it forms its own group (S(n-1, k-1) ways), or it joins one of the k existing groups of an arrangement of the first n-1 items (k * S(n-1, k) ways):

TEXT
S(n, k) = S(n-1, k-1) + k * S(n-1, k)
S(0, 0) = 1,   S(n, 0) = S(0, k) = 0 otherwise

This is a 2D dynamic-programming table, O(n*k) time. See DP basics for the table-filling habit.

Python Stirling numbers by DP, checked by brute force

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.

Each row sums to the next number in our list: the Bell number.

Bell numbers

B(n) = S(n,1) + S(n,2) + ... + S(n,n) is the number of all set partitions of n items, with B(0) = 1. The sequence begins 1, 1, 2, 5, 15, 52, 203, 877. A compact alternative is the Bell triangle: start a row with the last number of the previous row, then each entry is the previous entry in the row plus the entry above-left. The first entry of each row is a Bell number.

Python Bell numbers two ways

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 triangle needs only O(n^2) additions and no multiplications, and it uses a single row at a time, so O(n) memory if you keep only the current row.

Catalan numbers

The Catalan numbers are 1, 1, 2, 5, 14, 42, 132, ... and the n-th one counts:

  • balanced strings of n pairs of parentheses,
  • binary trees with n nodes (different shapes),
  • ways to triangulate a convex polygon with n + 2 sides,
  • monotone paths in an n x n grid that never cross the diagonal,
  • ways to fully parenthesize a product of n + 1 factors.

Two formulas:

TEXT
C(n) = C(2n, n) / (n + 1)                       closed form
C(n) = sum over i of C(i) * C(n-1-i)            recurrence

The recurrence says: choose where the first pair closes, with i pairs inside and n - 1 - i after it. That is why the same numbers appear in so many "split into left and right" problems, for example counting binary trees and the matrix chain style DP.

Python Catalan numbers: formula, recurrence and brute force

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 lines show the modular version with factorial tables: C(n) = (2n)! / (n! (n+1)!). The DP runs in O(n^2), the formula in O(n) after factorials.

Which tool when?

Question Tool Time
C(n, r) mod p, p small, n huge Lucas O(p + log_p n)
C(n, r) mod p, n < p factorial and inverse tables O(n) setup, O(1) query
Split n items into k groups S(n, k) DP O(n k)
All partitions of n items Bell triangle O(n^2)
Balanced or tree-shaped structures Catalan formula or DP O(n) or O(n^2)

Common mistakes: using Lucas with a composite modulus, forgetting that S(n, k) counts unlabeled groups (multiply by k! for labeled, non-empty ones), and using the closed Catalan formula without a modular inverse of n + 1.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the plain factorial formula for nCr fail when n >= p (p prime) and we work mod p?

    Once n >= p, the product 12...*n includes p itself, so n! is divisible by p and zero modulo p. Dividing by it is impossible.
  2. 2. Using Lucas' theorem, what is C(10, 3) mod 7?

    In base 7, 10 is digits (1,3) and 3 is digits (0,3). The product C(1,0) * C(3,3) is 1, and indeed 120 mod 7 is 1.
  3. 3. Which recurrence defines the Stirling numbers of the second kind?

    The last item either starts a new group (S(n-1,k-1)) or joins one of the k existing groups (k times S(n-1,k)).
  4. 4. The sequence 1, 2, 5, 14, 42 counts which of these?

    These are the Catalan numbers C(1) to C(5). Bell numbers go 1, 2, 5, 15, 52.

Summary

  • Lucas' theorem gives C(n, r) mod p as a product of small binomials of base-p digits, in O(log_p n) steps after an O(p) table.
  • S(n, k) = S(n-1, k-1) + k * S(n-1, k) counts partitions of n items into k non-empty groups.
  • Bell numbers are the row sums of Stirling numbers and can be built with the Bell triangle.
  • Catalan numbers C(2n, n) / (n+1) count balanced parentheses, binary trees and triangulations; the recurrence splits into left and right parts.
  • Always use a prime modulus with Lucas and modular inverses for division.

Next: Burnside's Lemma and Counting Necklaces