Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 63 ยท Math for Contests

Counting and Combinatorics

Count fast under a modulus: factorial tables, nCr mod p, stars and bars, inclusion-exclusion with derangements, and Catalan numbers, each verified against brute force.

"How many ways are there to...?" is one of the most common questions in contests, and the answer is usually huge, so it comes with "print it modulo 10^9 + 7". If you know a handful of counting tools, many of these problems reduce to a single formula. This lesson builds the toolkit: a fast binomial coefficient nCr mod p, stars and bars for distributing identical items, inclusion-exclusion for "at least one of" and "none of" counts, and Catalan numbers for balanced structures.

You will need the modular tools from Modular Arithmetic, in particular the modular inverse. The pure-math background is in Combinatorics. Everything here is checked by comparing the formula against a brute force on small cases, which is exactly how you should verify a counting formula during a contest.

Factorial tables and nCr mod p

The number of ways to choose r items from n is n! / (r! (n - r)!). Under a prime modulus, division becomes multiplication by the inverse. If you will ask many queries, precompute once:

  1. fact[i] = i! mod p for i up to N.
  2. inv_fact[N] = pow(fact[N], -1, p), a single modular inverse.
  3. Fill inv_fact downward with inv_fact[i - 1] = inv_fact[i] * i.

Then each query costs three multiplications, O(1). The backward trick works because 1 / (i-1)! = i / i!, so one expensive pow covers the whole table.

This needs N < p. If n is as large as the prime itself, the factorial contains the factor p and has no inverse. Contest limits with 10^9 + 7 keep n around 10^6 to 10^7, so it is safe.

Python A factorial table and nCr

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.

Always make nCr return 0 for out-of-range arguments. Many formulas call it with arguments that can be negative or too large, and returning 0 is the correct count in those cases.

Stars and bars

How many ways can you split n identical candies among k children, where a child may get none? Picture the candies as n stars in a row and k - 1 bars that separate the children. Any arrangement of the stars and bars is a distribution, so the count is the number of ways to place the bars:

TEXT
x1 + x2 + ... + xk = n,  xi >= 0     ->   C(n + k - 1, k - 1)

If child i must receive at least m_i, give them that amount first and distribute the rest: replace n by n - sum(m_i). If the extra amount is negative the answer is 0.

flowchart LR
    A["n identical items, k boxes"] --> B["Subtract minimums from n"]
    B --> C["n' = n - sum of minimums"]
    C --> D["Answer C(n' + k - 1, k - 1)"]

Reduce lower bounds first, then count placements of bars among stars.

Python Stars and bars against 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.

Inclusion-exclusion

To count objects that have at least one of several properties, adding the counts for each property counts overlaps more than once. Inclusion-exclusion fixes this with alternating signs:

TEXT
|A1 โˆช A2 โˆช ... โˆช Ak| = sum over non-empty subsets S of (-1)^(|S|+1) * |โˆฉ of Ai in S|

Two classic uses:

  • Divisibility. How many integers from 1 to N are divisible by at least one of the numbers d1, ..., dk? A subset's intersection is "divisible by the lcm of the subset", which has N // lcm elements. With k up to about 20, enumerating all 2^k subsets is fine.
  • Derangements. A permutation with no fixed point. Count all permutations minus those fixing at least one position: D(n) = sum_{j=0..n} (-1)^j * C(n, j) * (n - j)!.
Python Inclusion-exclusion: divisibility and derangements

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.

For derangements you also see the recurrence D(n) = (n - 1) * (D(n - 1) + D(n - 2)), which is O(n) and avoids factorial tables completely. Choose whichever is easier to get right.

Catalan numbers

The Catalan numbers 1, 1, 2, 5, 14, 42, ... count many things: balanced parentheses sequences with n pairs, binary trees with n nodes, and paths that stay on one side of a diagonal. The closed form is

TEXT
Cat(n) = C(2n, n) / (n + 1) = C(2n, n) - C(2n, n + 1)

The subtraction form avoids a modular division, which is convenient. The recurrence Cat(n) = sum Cat(i) * Cat(n - 1 - i) is the same counting split by the position of the first closing bracket.

Python Catalan numbers three 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.

Habits for counting problems

  • Verify the formula on small cases with a brute force before building the fast version.
  • Return 0 for impossible arguments inside nCr rather than guarding every call.
  • Prefer subtraction over division when a formula has both forms, as with Catalan numbers.
  • Break the problem into independent choices and multiply, or into disjoint cases and add; use inclusion-exclusion only when cases overlap.
  • Mind the limits: factorial tables need N below the modulus, and the table size must cover n + k - 1-style arguments, not just n.

Next, Number Theory Toolkit adds the gcd, sieves and divisor tricks that these formulas often depend on.

Counting labelled trees: Prufer codes and Cayley's formula

How many different trees can you draw on n labelled vertices? The answer is Cayley's formula: n^(n-2). The proof is also an algorithm. A Prufer code turns a labelled tree into a sequence of n - 2 numbers, each between 1 and n, and the map works in both directions, so trees and sequences are in one-to-one correspondence.

  • Encode: repeat n - 2 times: remove the leaf with the smallest label and write down the label of its neighbor.
  • Decode: a vertex appears in the code exactly degree - 1 times. Repeat for each code entry v: connect v to the smallest vertex whose remaining degree is 1 (a current leaf). At the end join the last two leaves.

The degree fact gives a second counting formula for free: the number of labelled trees in which vertex i has degree d_i is the multinomial (n - 2)! / ((d_1 - 1)! ... (d_n - 1)!). That is how contest problems of the type "count trees where vertex 1 has degree exactly k" are solved.

For counting spanning trees of an arbitrary graph, use Kirchhoff's matrix-tree theorem: build the Laplacian matrix (degrees on the diagonal, minus the edge multiplicities elsewhere), delete one row and the same column, and take the determinant. The complete graph gives Cayley's number back. With a modulus, the determinant uses Gaussian elimination over a prime field (see Gaussian elimination).

Python Prufer codes, Cayley's formula and the matrix-tree 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.

Every sequence decodes to a distinct tree, and encoding undoes decoding: that round trip on all sequences for n up to 6 is the proof by exhaustive check. The last test compares the determinant against explicit enumeration of edge subsets on 100 random graphs.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why do we compute inv_fact[N] with one pow and then fill the table downward?

    inv_fact[i-1] = inv_fact[i] * i. This replaces N modular inverses (each O(log p)) by a single one and N multiplications.
  2. 2. How many ways can 7 identical items be placed into 4 boxes (boxes may be empty)?

    Stars and bars gives C(n + k - 1, k - 1) = C(7 + 4 - 1, 3) = C(10, 3) = 120.
  3. 3. In the inclusion-exclusion count of integers divisible by at least one of d1..dk, how many numbers up to N are divisible by every number in a subset S?

    A number is divisible by all members of S exactly when it is divisible by their lcm. Using the product overcounts when the numbers share factors.
  4. 4. What does Cat(3) equal?

    C(6, 3) / 4 = 20 / 4 = 5. The Catalan sequence starts 1, 1, 2, 5, 14.
  5. 5. What should nCr(n, r) return when r is greater than n?

    There are no ways to choose more items than exist. Returning 0 lets formulas combine such terms without special cases.

Summary

  • Precompute factorials and inverse factorials for O(1) nCr mod p; return 0 when arguments are out of range.
  • Stars and bars: C(n + k - 1, k - 1) ways to split n identical items into k boxes; subtract lower bounds first.
  • Inclusion-exclusion handles "at least one" with alternating signs; divisibility uses the lcm of each subset.
  • Derangements: sum (-1)^j C(n, j) (n - j)!, or the recurrence (n - 1)(D(n - 1) + D(n - 2)).
  • Catalan numbers: C(2n, n) - C(2n, n + 1) avoids division.
  • Always check a counting formula against a brute force on small inputs.
  • Prufer codes biject trees on n labelled vertices with sequences of length n - 2 (Cayley: n^(n-2)); the matrix-tree theorem counts spanning trees of any graph.

Next: Number Theory Toolkit