Combinatorics & Counting

Modular exponentiation and, through Fermat's little theorem, the modular inverse $a^{- 1} \equiv a^{p - 2} (mod p)$ underlie most of practical combinatorics: almost every counting answer is a ratio of factorials, and a ratio modulo a prime is a product with an inverse. This lesson covers the counting tools (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: inclusion–exclusion for counting unions, and the Chinese Remainder Theorem for combining 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$ .

permutations_combinations.pypython

def factorial(number: int) -> int:
  """
    The product n! = n * (n-1) * ... * 1, with 0! = 1.\n
    Raises ValueError on a negative argument.\n
  """
  if number < 0:
    raise ValueError("factorial is undefined for negative integers")

  # multiply the integers 2 .. number into a running product.
  result: int = 1
  for factor in range(2, number + 1):
    result *= factor

  return result


def permutations_count(total: int, chosen: int) -> int:
  """
    nPr = n! / (n-r)! — the number of ordered arrangements of `chosen`\n
    objects drawn from `total` distinct objects.\n
    Zero when `chosen` exceeds `total` or either argument is negative.\n
  """
  if chosen < 0 or total < 0 or chosen > total:
    return 0

  # multiply the top `chosen` factors of total! directly: no division needed.
  result: int = 1
  for factor in range(total, total - chosen, -1):
    result *= factor
  return result


def binomial(total: int, chosen: int) -> int:
  """
    The binomial coefficient C(n, r) = n! / (r! (n-r)!) — the number of\n
    `chosen`-element subsets of a `total`-element set.\n
    Zero when `chosen` is out of the range [0, total].\n
  """
  if chosen < 0 or chosen > total or total < 0:
    return 0

  # exploit symmetry C(n, r) = C(n, n-r) to keep the loop short.
  chosen = min(chosen, total - chosen)
  numerator: int = 1
  denominator: int = 1
  for step in range(chosen):
    numerator *= total - step
    denominator *= step + 1
  return numerator // denominator

Pascal's rule

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

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)$ ).

pascals_triangle.pypython

def pascals_triangle(rows: int) -> list[list[int]]:
  """
    The first `rows` rows of Pascal's triangle (rows 0 .. rows-1).\n
    Row n holds the coefficients C(n, 0) .. C(n, n); each interior entry is\n
    the sum of the two directly above it.\n
    Raises ValueError when `rows` is negative.\n
  """
  if rows < 0:
    raise ValueError("number of rows must be non-negative")

  # each row starts all-ones, then interior cells sum the two cells above.
  triangle: list[list[int]] = []
  for row_index in range(rows):
    row: list[int] = [1 for _ in range(row_index + 1)]
    previous: list[int] = triangle[row_index - 1] if row_index > 0 else []
    for position in range(1, row_index):
      row[position] = previous[position - 1] + previous[position]
    triangle.append(row)

  return triangle


def pascal_row(row_index: int) -> list[int]:
  """
    A single row C(n, 0) .. C(n, n) of Pascal's triangle, built in place by\n
    sweeping right-to-left so each cell still sees its old left neighbour.\n
    Raises ValueError when `row_index` is negative.\n
  """
  if row_index < 0:
    raise ValueError("row index must be non-negative")

  # build up to row n in place, each pass sweeping right-to-left.
  row: list[int] = [1 for _ in range(row_index + 1)]
  for filled in range(1, row_index + 1):
    for position in range(filled - 1, 0, -1):
      row[position] = row[position] + row[position - 1]

  return row

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 name binomial coefficient comes from the expansion of $(x + y)^{n}$ .

Setting $x = y = 1$ gives $\sum_{k} (k n) = 2^{n}$ : the number of subsets of an $n$ -set, counted by size.

pascals_triangle.pypython

def binomial_expansion(power: int) -> list[int]:
  """
    The coefficients of (x + y)^power, in order of decreasing x-exponent:\n
    the term C(power, k) x^(power-k) y^k sits at index k. By the binomial\n
    theorem this is exactly row `power` of Pascal's triangle.\n
    Raises ValueError when `power` is negative.\n
  """
  if power < 0:
    raise ValueError("power must be non-negative")
  return pascal_row(power)

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?

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)

permutations_combinations.pypython

def stars_and_bars(items: int, bins: int) -> int:
  """
    The number of ordered non-negative solutions of\n
    x_1 + x_2 + ... + x_bins = items, equivalently the number of multisets\n
    of size `items` drawn from `bins` distinct types.\n
    By the bars-between-stars bijection this is C(items + bins - 1, bins - 1).\n
  """
  if bins <= 0:
    # with no bins there is one empty solution only when nothing to place.
    return 1 if items == 0 and bins == 0 else 0
  if items < 0:
    return 0
  return binomial(items + bins - 1, bins - 1)

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 what Number of Music Playlists and Count Anagrams need, since both reduce to products and ratios of factorials modulo $1 0^{9} + 7$ .

binomial_mod_p.pypython

class BinomialModP:
  """
    Precomputed factorial tables for evaluating C(n, k) mod a prime p.\n
    Construct once for a ceiling N, then query any C(n, k) with\n
    0 <= k <= n <= N in constant time.\n
  """

  def __init__(self, max_n: int, prime: int = 1_000_000_007) -> None:
    """
      Build factorial and inverse-factorial tables for indices 0 .. max_n\n
      modulo `prime`. The single modular exponentiation is the Fermat\n
      inverse of the top factorial; smaller inverses peel down from it.\n
    """
    if max_n < 0:
      raise ValueError("table size must be non-negative")
    self.prime: int = prime

    # forward pass: factorial[i] = i! mod p.
    self.factorial: list[int] = [1 for _ in range(max_n + 1)]
    for index in range(1, max_n + 1):
      self.factorial[index] = self.factorial[index - 1] * index % prime

    # one Fermat inverse for the largest factorial, by a^(p-2) = a^-1.
    self.inverse_factorial: list[int] = [1 for _ in range(max_n + 1)]
    self.inverse_factorial[max_n] = pow(self.factorial[max_n], prime - 2, prime)

    # each smaller inverse factorial is the next one times the peeled factor.
    for index in range(max_n, 0, -1):
      self.inverse_factorial[index - 1] = (
        self.inverse_factorial[index] * index % prime
      )

  def binomial(self, total: int, chosen: int) -> int:
    """
      C(total, chosen) mod p, as fact[n] * invfact[k] * invfact[n-k].\n
      Zero when `chosen` falls outside [0, total].\n
    """
    if chosen < 0 or chosen > total or total < 0:
      return 0
    return (
      self.factorial[total]
      * self.inverse_factorial[chosen]
      % self.prime
      * self.inverse_factorial[total - chosen]
      % self.prime
    )

  def permutations(self, total: int, chosen: int) -> int:
    """
      nPr = fact[n] * invfact[n-r] mod p — ordered arrangements modulo p.\n
    """
    if chosen < 0 or chosen > total or total < 0:
      return 0
    return (
      self.factorial[total]
      * self.inverse_factorial[total - chosen]
      % self.prime
    )

def lucas(total: int, chosen: int, prime: int) -> int:
  """
    C(total, chosen) mod `prime` by Lucas' theorem, valid even when total or\n
    chosen exceed `prime`. Writing both in base p, the answer is the product\n
    of the digit-wise small binomials C(total_digit, chosen_digit) mod p.\n
    Each small binomial is computed directly from factorials below p.\n
  """
  if chosen < 0 or chosen > total or total < 0:
    return 0

  # multiply digit-wise small binomials across the base-p digits of n and k.
  result: int = 1
  while total > 0 or chosen > 0:
    total_digit: int = total % prime
    chosen_digit: int = chosen % prime

    # a digit of chosen exceeding the matching digit of total: zero overall.
    if chosen_digit > total_digit:
      return 0

    # fold this digit's binomial in and shift both numbers down one base-p place.
    result = result * _small_binomial(total_digit, chosen_digit, prime) % prime
    total //= prime
    chosen //= prime

  return result

def _small_binomial(total: int, chosen: int, prime: int) -> int:
  """
    C(total, chosen) mod `prime` for 0 <= chosen <= total < prime, via a\n
    short product and one modular inverse of the denominator.\n
  """
  if chosen < 0 or chosen > total:
    return 0

  # exploit symmetry C(n, k) = C(n, n-k) to keep the product short.
  chosen = min(chosen, total - chosen)

  # accumulate numerator and denominator products modulo p.
  numerator: int = 1
  denominator: int = 1
  for step in range(chosen):
    numerator = numerator * ((total - step) % prime) % prime
    denominator = denominator * (step + 1) % prime

  # divide by the denominator via its Fermat modular inverse.
  return numerator * pow(denominator, prime - 2, prime) % prime

Worked example ( $(3 10)$ modulo a small prime). Take $p = 13$ and compute $(3 10) = 120$ , which is $120 mod 13 = 3$ . Build the factorial table $fact [i] = i! mod 13$ : $1, 1, 2, 6, 24 \equiv 11, 120 \equiv 3, 720 \equiv 5, \dots$ , giving $fact [10] \equiv 6 (mod 13)$ . We need the two inverse factorials $invfact [3]$ and $invfact [7]$ . Fermat gives $invfact [10] = fact [10]^{11} mod 13$ , and the downward peel fills the rest; the entries we want come out to $invfact [3] \equiv 11$ (since $3! = 6$ and $6 \cdot 11 = 66 \equiv 1 (mod 13)$ ) and $invfact [7] \equiv 12$ (since $7! \equiv 5040 \equiv 12$ and $12 \cdot 12 = 144 \equiv 1$ ). Then

(3 10) \equiv fact [10] \cdot invfact [3] \cdot invfact [7] \equiv 6 \cdot 11 \cdot 12 \equiv 792 \equiv 3 (mod 13),

matching $120 mod 13 = 3$ . The single Fermat inverse plus a linear peel is all the division the whole computation ever does.

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!$ .

Worked example (derangements of four items). How many permutations of ${1, 2, 3, 4}$ leave no element fixed? Let $A_{i}$ be the permutations fixing position $i$ . There are $(j 4) (4 - j)!$ ways to fix a chosen set of $j$ positions and permute the rest, so inclusion–exclusion gives

D_{4} = 4! - (1 4) 3! + (2 4) 2! - (3 4) 1! + (4 4) 0! = 24 - 24 + 12 - 4 + 1 = 9.

Those nine derangements are the permutations that leave no number in its own slot — for instance $2143$ , $2341$ , $3412$ — and the ratio $D_{4} /4! = 9/24 = 0.375$ is already close to the limiting value $1/ e \approx 0.368$ that $D_{n} / n!$ approaches, since the alternating sum is the truncated series for $e^{- 1}$ .

inclusion_exclusion.pypython

from collections.abc import Hashable, Sequence
from itertools import combinations
from typing import TypeVar

Element = TypeVar("Element", bound=Hashable)

def union_size(sets: Sequence[set[Element]]) -> int:
  """
    The size of the union of `sets`, by explicit inclusion-exclusion over\n
    every non-empty subset of the family: a subset of `size` sets contributes\n
    its intersection size with sign (-1)^(size+1).\n
    O(2^len(sets)) — for small families. Empty family gives 0.\n
  """
  # alternating sum over every non-empty subset of the family.
  total: int = 0
  count: int = len(sets)
  for size in range(1, count + 1):
    sign: int = 1 if size % 2 == 1 else -1

    # each subset contributes its intersection size with the size's sign.
    for chosen in combinations(sets, size):
      intersection: set[Element] = set(chosen[0])
      for member in chosen[1:]:
        intersection &= member
      total += sign * len(intersection)

  return total

def count_divisible_by_none(limit: int, divisors: Sequence[int]) -> int:
  """
    How many integers in [1, limit] are divisible by none of `divisors`.\n
    Inclusion-exclusion on "divisible by d_i": a subset contributes\n
    floor(limit / lcm(subset)) with the alternating sign, then we subtract\n
    that union from `limit`. Divisors that are zero are ignored.\n
  """
  if limit <= 0:
    return 0
  effective: list[int] = [value for value in divisors if value != 0]

  # alternating sum of floor(limit / lcm(subset)) gives the divisible union.
  divisible_union: int = 0
  for size in range(1, len(effective) + 1):
    sign: int = 1 if size % 2 == 1 else -1
    for chosen in combinations(effective, size):
      multiple: int = _lcm_of(chosen)
      divisible_union += sign * (limit // multiple)

  # whatever is left over is divisible by none.
  return limit - divisible_union

def derangements(count: int) -> int:
  """
    The number of permutations of `count` items with no fixed point,\n
    D_n = (n-1) * (D_{n-1} + D_{n-2}), seeded D_0 = 1, D_1 = 0 — the\n
    recurrence equivalent to the inclusion-exclusion sum n! * sum (-1)^j/j!.\n
    Raises ValueError when `count` is negative.\n
  """
  if count < 0:
    raise ValueError("count must be non-negative")
  if count == 0:
    return 1

  # roll the two-term recurrence forward from the seeds D_0 = 1, D_1 = 0.
  previous: int = 1   # D_0
  current: int = 0    # D_1
  for index in range(2, count + 1):
    previous, current = current, (index - 1) * (current + previous)

  return current

def _lcm_of(values: Sequence[int]) -> int:
  """
    The least common multiple of `values`, folded pairwise via gcd.\n
  """
  from math import gcd

  # fold one value at a time: lcm(a, b) = a // gcd(a, b) * b.
  result: int = 1
  for value in values:
    magnitude: int = abs(value)
    result = result // gcd(result, magnitude) * magnitude

  return result

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$

chinese_remainder.pypython

from collections.abc import Sequence

def extended_gcd(left: int, right: int) -> tuple[int, int, int]:
  """
    The extended Euclidean algorithm: returns (g, x, y) with\n
    left * x + right * y = g = gcd(left, right).\n
  """
  # track Bezout coefficients alongside the Euclidean remainders.
  remainder_x: int = 1
  remainder_y: int = 0
  next_x: int = 0
  next_y: int = 1

  # each step reduces the pair and carries the coefficients in lockstep.
  while right != 0:
    quotient: int = left // right
    left, right = right, left - quotient * right
    remainder_x, next_x = next_x, remainder_x - quotient * next_x
    remainder_y, next_y = next_y, remainder_y - quotient * next_y

  return left, remainder_x, remainder_y

def mod_inverse(value: int, modulus: int) -> int:
  """
    The inverse of `value` modulo `modulus`, in [0, modulus), via the\n
    extended gcd. Raises ValueError when no inverse exists (not coprime).\n
  """
  divisor, coefficient, _ = extended_gcd(value % modulus, modulus)
  if divisor != 1:
    raise ValueError("value has no inverse: it is not coprime to the modulus")
  return coefficient % modulus

def chinese_remainder(
  residues: Sequence[int], moduli: Sequence[int]
) -> int:
  """
    The unique x in [0, M) with x = residues[i] (mod moduli[i]) for every i,\n
    where M is the product of the moduli, which must be pairwise coprime.\n
    Computed as sum a_i * M_i * (M_i^-1 mod m_i) reduced modulo M.\n
    Raises ValueError on length mismatch or non-coprime moduli.\n
  """
  if len(residues) != len(moduli):
    raise ValueError("residues and moduli must have equal length")
  if not moduli:
    return 0

  # M is the product of all moduli; the answer is unique modulo M.
  product: int = 1
  for modulus in moduli:
    product *= modulus

  # sum one selector per congruence: a_i * M_i * (M_i^-1 mod m_i).
  solution: int = 0
  for residue, modulus in zip(residues, moduli):
    partial: int = product // modulus
    inverse: int = mod_inverse(partial % modulus, modulus)
    solution = (solution + residue * partial * inverse) % product

  return solution % product

CRT lets us compute modulo a large composite $M$ by working independently in each prime-power factor and reassembling the results.

Catalan numbers, generating functions, and symmetry

The four tools above cover most counting problems, but a few structural ideas from enumerative combinatorics recur often enough to name.

Catalan numbers. The count $C_{n} = \frac{1}{n + 1} (n 2 n)$ answers many distinct-looking questions: balanced-parenthesis strings of $n$ pairs, binary trees on $n$ nodes, triangulations of an $(n + 2)$ -gon, and monotone lattice paths that stay below the diagonal. All reduce to the same recurrence $C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i}$ , whose closed form is the ratio of binomials above — so with the factorial tables already built, any Catalan count is one $O (1)$ query.⁵ The reflection-principle proof (count all paths, subtract the bad ones by reflecting across the boundary) explains the $\frac{1}{n + 1}$ factor.

Generating functions. Treating a counting sequence $a_{0}, a_{1}, \dots$ as the coefficients of a formal power series $A (x) = \sum a_{n} x^{n}$ turns recurrences into algebra: the Fibonacci generating function is the rational $x / (1 - x - x^{2})$ , and stars-and-bars is just the coefficient extraction $[x^{n}] (1 - x)^{- k} = (k - 1 n + k - 1)$ . Products of generating functions are convolutions, which is why the Fast Fourier Transform later in this module multiplies two counting sequences in $O (n log n)$ .⁶

Counting up to symmetry (Burnside). When arrangements that differ by a rotation or reflection should count once — necklaces, colorings of a cube's faces — naive counting over-counts by the symmetry group. Burnside's lemma says the number of distinct arrangements equals the average number of arrangements fixed by each symmetry, $\frac{1}{∣ G ∣} \sum_{g \in G} ∣ Fix (g) ∣$ , and Pólya enumeration packages this into generating functions.⁷ These are the standard route to count the distinct colorings problems that inclusion–exclusion alone cannot handle.

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. ↩
R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999 (Catalan numbers, Exercise 6.19 and its 66+ interpretations). ↩
H. S. Wilf, generatingfunctionology, 2nd ed., Academic Press, 1994 — the standard treatment of ordinary and exponential generating functions. ↩
N. G. de Bruijn, Pólya's theory of counting, in Applied Combinatorial Mathematics (Beckenbach, ed.), 1964; the counting-by-group-action lemma is also in Skiena, § — Combinatorics. ↩

Permutations and combinations

Pascal's rule

The binomial theorem

Combinations with repetition: stars and bars

Computing (kn​)modp

Inclusion–exclusion

The Chinese Remainder Theorem

Catalan numbers, generating functions, and symmetry

Takeaways

Footnotes

Computing $(k n) mod p$