Combinatorics & Counting

Modular exponentiation and, through Fermat's little theorem, the modular inverse $a^{- 1} \equiv a^{p - 2} (mod p)$ are the hinge on which all of practical combinatorics swings: almost every counting answer is a ratio of factorials, and a ratio modulo a prime is a product with an inverse. This lesson assembles the counting toolkit (permutations, combinations, Pascal's rule, stars and bars) and then shows how to evaluate those quantities modulo a prime in constant time after a linear precompute. We finish with two structural principles that recur everywhere: inclusion–exclusion for counting unions, and the Chinese Remainder Theorem for stitching together congruences.

Permutations and combinations

A permutation is an ordering of distinct objects. There are $n$ choices for the first position, $n - 1$ for the second, and so on, giving

n! = n \cdot (n - 1) \dots 2 \cdot 1, 0! = 1.

If we order only $r$ of the $n$ objects, we stop the product after $r$ factors:

n P r = \frac{n !}{( n - r )!} = n (n - 1) \dots (n - r + 1) .

A combination counts subsets of size $r$ , where orderings no longer matter. Each $r$ -subset can be ordered in $r!$ ways, so dividing $n P r$ by $r!$ removes the overcount:

(r n) = \frac{n P r}{r !} = \frac{n !}{r ! ( n - r )!} .

The quantity $(r n)$ , read $n$ choose $r$ , is the binomial coefficient.¹ It is symmetric, $(r n) = (n - r n)$ (choosing which $r$ to include is the same as choosing which $n - r$ to exclude), and the two boundary values are $(0 n) = (n n) = 1$ .

Pascal's rule

Binomial coefficients satisfy a recurrence that lets us build them additively, with no division at all:

Combinatorial proof. Fix a distinguished element $n$ . Every $k$ -subset of ${1, \dots, n}$ either contains $n$ or does not. Those that contain $n$ are formed by choosing the remaining $k - 1$ elements from the other $n - 1$ , giving $(k - 1 n - 1)$ of them. Those that omit $n$ choose all $k$ elements from the other $n - 1$ , giving $(k n - 1)$ . The two cases are disjoint and exhaustive, so their counts add. $□$

Arranging these values in rows is Pascal's triangle: each interior entry is the sum of the two directly above it.

Pascal's triangle — each cell

(k n) = (k - 1 n - 1) + (k n - 1)

The highlighted cell is $(2 4) = 6 = 3 + 3 = (1 3) + (2 3)$ . Because each entry needs only the row above, the whole triangle up to row $n$ is an $O (n^{2})$ dynamic program, the right approach when $n$ is small or when no modulus is involved (and the basis for Pascal's Triangle II and grid-path problems like Unique Paths, whose answer is exactly $(m - 1 m + n - 2)$ ).

That grid-path count is Pascal's rule in disguise: label each lattice node with the number of monotone (right/down) paths reaching it, and each node is the sum of its left and top neighbours, exactly the additive recurrence. On a $3 \times 3$ grid of nodes the corner reads $(2 4) = 6$ .

Lattice paths on a

3 \times 3

grid: each node sums its left and top neighbour; corner is

(2 4) = 6

The binomial theorem

The coefficients earn their name from the expansion

(x + y)^{n} = k = 0 \sum n (k n) x^{k} y^{n - k},

since each term of the product picks $x$ from $k$ of the $n$ factors and $y$ from the rest, and there are $(k n)$ ways to make that choice. Setting $x = y = 1$ gives $\sum_{k} (k n) = 2^{n}$ : the number of subsets of an $n$ -set, counted by size.

Combinations with repetition: stars and bars

How many ways can we write a non-negative integer $n$ as an ordered sum of $k$ non-negative parts, $n = x_{1} + x_{2} + \dots + x_{k}$ with each $x_{i} \geq 0$ ? Equivalently, how many multisets of size $n$ can we draw from $k$ distinct types?

Bijection. Lay out $n$ identical stars in a row and insert $k - 1$ bars among them; the bars cut the stars into $k$ ordered groups, the $i$ -th group's size being $x_{i}$ . For example with $n = 5$ , $k = 3$ :

⋆ ⋆ ∣ ∣ ⋆ ⋆ ⋆ ⟷ x_{1} = 2, x_{2} = 0, x_{3} = 3.

Every arrangement of $n$ stars and $k - 1$ bars in a line of $n + k - 1$ symbols yields exactly one solution and vice versa, so the count is the number of ways to choose which $k - 1$ of the $n + k - 1$ positions hold bars, namely $(k - 1 n + k - 1)$ . $□$

Concretely, with $n = 5$ and $k = 3$ there are $n + k - 1 = 7$ slots; choosing the $2$ of them that hold bars fixes the three part sizes at once, so the count is $(2 7) = 21$ .

Stars and bars:

5

stars and

2

bars in

7

slots encode

(x_{1}, x_{2}, x_{3}) = (2, 0, 3)

Computing $(k n) mod p$

Competitive and large-scale problems ask for counts modulo a prime $p$ (typically $1 0^{9} + 7$ ) because the true values are astronomically large. The factorial formula has a division by $r! (n - r)!$ , and division is not defined modulo $p$ ; what stands in for it is multiplication by a modular inverse. Since $p$ is prime, Fermat gives $a^{- 1} \equiv a^{p - 2} (mod p)$ for any $a \neq \equiv 0$ , computed by the modular exponentiation routine.

The plan: precompute the factorials $fact [i] = i! mod p$ for all $i \leq N$ , and the inverse factorials $invfact [i] = (i!)^{- 1} mod p$ . With both tables in hand, every binomial coefficient is a single product.

Algorithm:

\textsc{Precompute-Factorials}(N, p)

—

O(N)

tables for

O(1)

queries

1
$\text{fact}[0] \gets 1$
2
for $i \gets 1$ to $N$ do
3
$\text{fact}[i] \gets \text{fact}[i-1] \cdot i \bmod p$
4
$\text{invfact}[N] \gets \textsc{Mod-Pow}(\text{fact}[N],\, p-2,\, p)$
one Fermat inverse
5
for $i \gets N$ downto $1$ do
6
$\text{invfact}[i-1] \gets \text{invfact}[i] \cdot i \bmod p$
peel a factor

The downward loop is the trick that keeps the precompute at $O (N)$ rather than $O (N log p)$ : only one modular exponentiation is needed, for $invfact [N]$ ; each smaller inverse factorial follows from $(i - 1)!^{- 1} = i!^{- 1} \cdot i$ . Then each query is constant time:

(k n) \equiv fact [n] \cdot invfact [k] \cdot invfact [n - k] (mod p), 0 \leq k \leq n \leq N .

This $O (N)$ -precompute, $O (1)$ -query scheme is exactly what Number of Music Playlists and Count Anagrams need, since both reduce to products and ratios of factorials modulo $1 0^{9} + 7$ .

Inclusion–exclusion

To count a union of overlapping sets we cannot simply add their sizes, since elements in several sets get counted several times. Inclusion–exclusion corrects the overcount with alternating signs:

i = 1 ⋃ n A_{i} = i \sum ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + i < j < k \sum ∣ A_{i} \cap A_{j} \cap A_{k} ∣ - \dots + (- 1)^{n + 1} i ⋂ A_{i} .

Inclusion–exclusion — add singles, subtract pairs, add the triple (in acc)

Worked example (counting coprime-to-a-set integers). How many integers in $[1, 30]$ are divisible by none of ${2, 3, 5}$ ? Let $A, B, C$ be the multiples of $2, 3, 5$ respectively. Then $∣ A ∣ = 15, ∣ B ∣ = 10, ∣ C ∣ = 6$ ; $∣ A \cap B ∣ = ⌊ 30/6 ⌋ = 5, ∣ A \cap C ∣ = 3, ∣ B \cap C ∣ = 2$ ; and $∣ A \cap B \cap C ∣ = ⌊ 30/30 ⌋ = 1$ . So

∣ A \cup B \cup C ∣ = (15 + 10 + 6) - (5 + 3 + 2) + 1 = 22,

leaving $30 - 22 = 8$ integers divisible by none of $2, 3, 5$ , which are exactly $1, 7, 11, 13, 17, 19, 23, 29$ . The same alternating sum, applied with $A_{i}$ = maps position $i$ to itself, counts derangements $D_{n} = n! \sum_{j = 0}^{n} (- 1)^{j} / j!$ .

The Chinese Remainder Theorem

Inclusion–exclusion combines counts; the Chinese Remainder Theorem (CRT) combines congruences. Given a system

x \equiv a_{1} (mod m_{1}), x \equiv a_{2} (mod m_{2}), \dots, x \equiv a_{n} (mod m_{n})

with the moduli pairwise coprime, CRT guarantees a unique solution modulo $M = \prod_{i} m_{i}$ .⁴ The construction is explicit and again uses the modular inverse. Let $M_{i} = M / m_{i} = \prod_{j \neq = i} m_{j}$ . Because the $m_{j}$ are coprime to $m_{i}$ , so is $M_{i}$ , hence $M_{i}$ has an inverse modulo $m_{i}$ ; call it $M_{i}^{- 1} \equiv M_{i}^{φ (m_{i}) - 1}$ (or $M_{i}^{m_{i} - 2}$ when $m_{i}$ is prime). Then

x \equiv i = 1 \sum n a_{i} M_{i} M_{i}^{- 1} (mod M) .

Each term $a_{i} M_{i} M_{i}^{- 1}$ is $\equiv a_{i} (mod m_{i})$ (since $M_{i} M_{i}^{- 1} \equiv 1$ there) and $\equiv 0$ modulo every other $m_{j}$ (since $m_{j} ∣ M_{i}$ ), so the sum satisfies all $n$ congruences simultaneously. Concretely, to solve $x \equiv 2 (3)$ and $x \equiv 3 (5)$ each term acts as a selector: one lands on its own residue and vanishes modulo the other, so adding them assembles the answer $x \equiv 8 (mod 15)$ one congruence at a time.

CRT as a sum of selectors: each

a_{i} M_{i} M_{i}^{- 1}

hits its own residue and is

0

modulo the other, so the terms add to

x \equiv 8 (mod 15)

Algorithm:

\textsc{CRT}(a[\,], m[\,])

— combine congruences with pairwise-coprime moduli

1
$M \gets \prod_i m_i$
2
$x \gets 0$
3
for $i \gets 1$ to $n$ do
4
$M_i \gets M / m_i$
5
$y_i \gets \textsc{Mod-Inverse}(M_i \bmod m_i,\; m_i)$
6
$x \gets (x + a_i \cdot M_i \cdot y_i) \bmod M$
7
return $x$

CRT is what lets us compute modulo a large composite $M$ by working independently in each prime-power factor and reassembling, the structural twin of how stars-and-bars or inclusion–exclusion decompose a hard count into manageable pieces.

Takeaways

Permutations count orderings ( $n!$ , or $n P r = n! / (n - r)!$ ); combinations count subsets, $(r n) = n! / (r! (n - r)!)$ , dividing out the $r!$ orderings.
Pascal's rule $(k n) = (k - 1 n - 1) + (k n - 1)$ (element $n$ in or out) builds the triangle additively in $O (n^{2})$ with no division.
Stars and bars: the ordered non-negative solutions of $x_{1} + \dots + x_{k} = n$ number $(k - 1 n + k - 1)$ , via the bars-between-stars bijection.
To compute $(k n) mod p$ , precompute factorials and inverse factorials (one Fermat inverse, then peel factors) in $O (n)$ , giving $O (1)$ per query; use Lucas' theorem when $n, k > p$ .
Inclusion–exclusion counts unions by alternating add/subtract over all intersections; the alternating signs make each element net-counted exactly once.
The Chinese Remainder Theorem uniquely solves a system of congruences with coprime moduli via $x = \sum_{i} a_{i} M_{i} M_{i}^{- 1} mod M$ , the inverse again coming from Fermat or the extended gcd.

CLRS, Appendix C — Counting and Probability (§C.1): permutations, combinations, and the binomial coefficient $(r n) = n! / (r! (n - r)!)$ . ↩
Skiena, § — Combinatorics: Lucas' theorem reduces $(k n) mod p$ to a product of base- $p$ digit binomials when $n, k$ exceed $p$ . ↩
CLRS, Appendix C — Counting and Probability (§C.1): the inclusion–exclusion principle and the alternating-sign correction for unions. ↩
CLRS, Ch. 31 — Number-Theoretic Algorithms (§31.5): the Chinese Remainder Theorem and the constructive $\sum a_{i} M_{i} M_{i}^{- 1}$ formula. ↩

Permutations and combinations

Pascal's rule

The binomial theorem

Combinations with repetition: stars and bars

Computing (kn​)modp

Inclusion–exclusion

The Chinese Remainder Theorem

Takeaways

Footnotes

Computing $(k n) mod p$