---
title: Combinatorics & Counting
module: Mathematical Algorithms
moduleNumber: 10
lessonNumber: 4
order: 1004
summary: |
  Counting is the arithmetic of finite sets. We build up from permutations
  $n!$ and combinations $\binom{n}{k}$, prove Pascal's rule by a bijection,
  and count multisets with stars and bars. The practical core is computing
  $\binom{n}{k}\bmod p$ in $O(1)$ from precomputed factorials and inverse
  factorials. We close with inclusion–exclusion and the Chinese Remainder
  Theorem, both of which lean on the modular inverse from the previous lesson.
topics: [Number Theory]
sources:
  - book: CLRS
    ref: "Appendix C — Counting and Probability"
  - book: Skiena
    ref: "§ — Combinatorics"
  - book: Erickson
    ref: "Ch. — (counting)"
practice:
  - title: 'Unique Paths'
    slug: unique-paths
    difficulty: Medium
  - title: "Pascal's Triangle II"
    slug: pascals-triangle-ii
    difficulty: Easy
  - title: 'Number of Music Playlists'
    slug: number-of-music-playlists
    difficulty: Hard
  - title: 'Count Anagrams'
    slug: count-anagrams
    difficulty: Hard
---

[Modular exponentiation](/algorithms/mathematical-algorithms/modular-exponentiation-and-primality) and, through Fermat's little
theorem, the **modular inverse** $a^{-1} \equiv a^{p-2} \pmod 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) \cdots 2 \cdot 1, \qquad 0! = 1.
$$

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

$$
nPr = \frac{n!}{(n-r)!} = n(n-1)\cdots(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 $nPr$ by $r!$ removes the
overcount:

$$
\binom{n}{r} = \frac{nPr}{r!} = \frac{n!}{r!\,(n-r)!}.
$$

The quantity $\binom{n}{r}$, read "$n$ choose $r$," is the **binomial coefficient**.[^clrs-count]
It is symmetric, $\binom{n}{r} = \binom{n}{n-r}$ (choosing which $r$ to include is the
same as choosing which $n-r$ to exclude), and the two boundary values are
$\binom{n}{0} = \binom{n}{n} = 1$.

::impl{algo="permutations_combinations#factorial+permutations_count+binomial"}

### Pascal's rule

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

> **Lemma (Pascal's rule).** For $0 < k < n$,
> $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$$

> **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 $\binom{n-1}{k-1}$ of them. Those that omit $n$ choose all $k$ elements
> from the other $n-1$, giving $\binom{n-1}{k}$. The two cases are disjoint and
> exhaustive, so their counts add. $\qed$

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

$$
% caption: Pascal's triangle — each cell $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=8mm, inner sep=0, font=\small},
  x=11mm, y=12mm]
  \definecolor{acc}{HTML}{2348F2}
  % row 0
  \node (n00) at (0,0) {$1$};
  % row 1
  \node (n10) at (-0.5,-1) {$1$};
  \node (n11) at (0.5,-1) {$1$};
  % row 2
  \node (n20) at (-1,-2) {$1$};
  \node (n21) at (0,-2) {$2$};
  \node (n22) at (1,-2) {$1$};
  % row 3
  \node (n30) at (-1.5,-3) {$1$};
  \node (n31) at (-0.5,-3) {$3$};
  \node (n32) at (0.5,-3) {$3$};
  \node (n33) at (1.5,-3) {$1$};
  % row 4 - highlight the 6 = 3 + 3 cell
  \node (n40) at (-2,-4) {$1$};
  \node (n41) at (-1,-4) {$4$};
  \node[draw=acc, fill=acc!15, very thick] (n42) at (0,-4) {$6$};
  \node (n43) at (1,-4) {$4$};
  \node (n44) at (2,-4) {$1$};
  % the two parents feeding the highlighted cell (derivation arrows in red)
  \draw[->, red!75!black, thick, shorten >=1pt] (n31) -- (n42);
  \draw[->, red!75!black, thick, shorten >=1pt] (n32) -- (n42);
\end{tikzpicture}
$$

The highlighted cell is $\binom{4}{2} = 6 = 3 + 3 = \binom{3}{1} + \binom{3}{2}$.
Because each entry needs only the row above, the whole triangle up to row $n$ is an
$O(n^2)$ [dynamic program](/algorithms/dynamic-programming/principles), 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 $\binom{m+n-2}{\,m-1\,}$).

::impl{algo="pascals_triangle#pascals_triangle+pascal_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 $\binom{4}{2}=6$.

$$
% caption: Lattice paths on a $3\times 3$ grid: each node sums its left and top neighbour;
%          corner is $\binom{4}{2}=6$
\begin{tikzpicture}[every node/.style={font=\small}, x=14mm, y=14mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % grid edges as shortened unit segments so they sit in the gaps, clear of the digits
  \foreach \i in {0,1,2}{
    \foreach \j in {0,1}{
      \draw[black, shorten >=4mm, shorten <=4mm] (\j,-\i) -- (\j+1,-\i);
      \draw[black, shorten >=4mm, shorten <=4mm] (\i,-\j) -- (\i,-\j-1);
    }
  }
  \foreach \c/\r/\v/\hl in {
    0/0/1/0, 1/0/1/0, 2/0/1/0,
    0/1/1/0, 1/1/2/0, 2/1/3/0,
    0/2/1/0, 1/2/3/0, 2/2/6/1}{
    \ifnum\hl=1
      \node[draw=acc, circle, fill=acc!15, very thick, minimum size=8mm, inner sep=0] at (\c,-\r) {$\v$};
    \else
      \node[draw, circle, fill=black!6, minimum size=7mm, inner sep=0] at (\c,-\r) {$\v$};
    \fi
  }
  \node[acc, font=\footnotesize] at (1,-2.55) {start top-left, only \texttt{right}/\texttt{down} moves};
\end{tikzpicture}
$$

### The binomial theorem

The name "binomial coefficient" comes from the expansion of $(x+y)^n$.

> **Theorem (Binomial theorem).** For every $n \ge 0$,
> $$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k}\, x^{k}\, y^{\,n-k}.$$

> **Proof.** Expanding the product $(x+y)(x+y)\cdots(x+y)$ of $n$ factors, each
> term picks either $x$ or $y$ from each factor. A term equals $x^k y^{n-k}$
> exactly when $x$ is chosen from $k$ of the $n$ factors, and there are
> $\binom{n}{k}$ ways to make that choice, so $x^k y^{n-k}$ appears with
> coefficient $\binom{n}{k}$. $\qed$

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

::impl{algo="pascals_triangle#binomial_expansion"}

## 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 \ge 0$? Equivalently,
how many multisets of size $n$ can we draw from $k$ distinct types?

> **Lemma (Stars and bars).** The number of such solutions is
> $$\binom{n + k - 1}{\,k - 1\,}.$$

> **Proof.** 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$,
> $$\star\,\star \mid\; \mid \star\,\star\,\star \quad\longleftrightarrow\quad 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
> $\binom{n+k-1}{k-1}$. $\qed$

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
$\binom{7}{2}=21$.

$$
% caption: Stars and bars: $5$ stars and $2$ bars in $7$ slots encode
%          $(x_1,x_2,x_3)=(2,0,3)$
\begin{tikzpicture}[every node/.style={font=\small}, x=9mm, y=9mm]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i in {1,...,7}{
    \draw (\i-0.45,-0.45) rectangle (\i+0.45,0.45);
  }
  \foreach \i in {1,2,5,6,7}{ \node at (\i,0) {$\star$}; }
  \foreach \i in {3,4}{ \fill[acc!15] (\i-0.45,-0.45) rectangle (\i+0.45,0.45); \draw[draw=acc, very thick] (\i-0.45,-0.45) rectangle (\i+0.45,0.45); \draw[acc, very thick] (\i,-0.28) -- (\i,0.28); }
  \draw[thick] (0.55,-0.65) -- (2.45,-0.65);
  \node[font=\footnotesize] at (1.5,-1.1) {$x_1 = 2$};
  \node[font=\footnotesize] at (3.5,-1.1) {$x_2 = 0$};
  \draw[thick] (4.55,-0.65) -- (7.45,-0.65);
  \node[font=\footnotesize] at (6,-1.1) {$x_3 = 3$};
  \node[acc, font=\footnotesize] at (4,1.25) {choose 2 of 7 slots for bars: C(7, 2) = 21};
\end{tikzpicture}
$$

::impl{algo="permutations_combinations#stars_and_bars"}

## Computing $\binom{n}{k} \bmod p$

Competitive and large-scale problems ask for counts modulo a
prime $p$ (typically $10^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](/algorithms/mathematical-algorithms/number-theory-basics). Since $p$ is prime,
Fermat gives $a^{-1} \equiv a^{p-2} \pmod p$ for any $a \not\equiv 0$, computed by the
modular exponentiation routine.

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

```algorithm
caption: $\textsc{Precompute-Factorials}(N, p)$ — $O(N)$ tables for $O(1)$ queries
$\text{fact}[0] \gets 1$
for $i \gets 1$ to $N$ do
  $\text{fact}[i] \gets \text{fact}[i-1] \cdot i \bmod p$
$\text{invfact}[N] \gets \textsc{Mod-Pow}(\text{fact}[N],\, p-2,\, p)$ // one Fermat inverse
for $i \gets N$ downto $1$ do
  $\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 $\text{invfact}[N]$;
each smaller inverse factorial follows from $(i-1)!^{-1} = i!^{-1}\cdot i$. Then each
query is constant time:

$$
\binom{n}{k} \equiv \text{fact}[n]\cdot\text{invfact}[k]\cdot\text{invfact}[n-k] \pmod p,
\qquad 0 \le k \le n \le 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 $10^9 + 7$.

::impl{algo="binomial_mod_p"}

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

> **Theorem (Lucas').** When $n$ and $k$ can exceed $p$ itself, the factorial tables
> break (they contain factors of $p$, hence zeros). Lucas reduces the problem to
> digits in base $p$: writing $n = \sum n_i p^i$ and $k = \sum k_i p^i$,
> $\binom{n}{k} \equiv \prod_i \binom{n_i}{k_i} \pmod p$, a product of small binomial
> coefficients each computable from a table of size $p$.[^lucas]

## 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:

$$
\Bigl|\,\bigcup_{i=1}^{n} A_i\,\Bigr| =
\sum_i |A_i| \;-\; \sum_{i<j} |A_i \cap A_j| \;+\; \sum_{i<j<k} |A_i \cap A_j \cap A_k|
\;-\; \cdots \;+\; (-1)^{n+1}\Bigl|\bigcap_i A_i\Bigr|.
$$

> **Lemma (Alternating-sign principle).** Add the sizes of all single sets, subtract all
> pairwise intersections, add all triple intersections, and so on. An element lying
> in exactly $m$ of the sets is counted $\sum_{j=1}^{m}(-1)^{j+1}\binom{m}{j} = 1$
> time in total, exactly once, as it should be.[^clrs-ie]

$$
% caption: Inclusion–exclusion — add singles, subtract pairs, add the triple (in acc)
\begin{tikzpicture}[
  every node/.style={font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % three overlapping circles
  \draw[thick] (0,0) circle (1.5cm);
  \draw[thick] (2,0) circle (1.5cm);
  \draw[thick] (1,1.7) circle (1.5cm);
  % triple overlap marked with a small dot, label pulled below-right with a leader
  \fill[acc] (1,0.57) circle (1.3pt);
  \draw[acc, thin] (1,0.57) .. controls (2.7,-0.6) .. (3.2,-2.0);
  \node[acc, right] at (3.2,-2.05) {+ (A and B and C)};
  % set labels
  \node at (-1.22,-1.34) {$A$};
  \node at (3.22,-1.34) {$B$};
  \node at (1,3.52) {$C$};
  % singles
  \node at (-0.65,-0.15) {+A};
  \node at (2.65,-0.15) {+B};
  \node at (1,2.45) {+C};
  % pairwise overlaps
  \node at (1,-0.15) {-};
  \node at (-0.05,1.0) {-};
  \node at (2.05,1.0) {-};
\end{tikzpicture}
$$

**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| = \lfloor 30/6\rfloor = 5,\ |A\cap C| = 3,\ |B\cap C| = 2$; and
$|A\cap B\cap C| = \lfloor 30/30\rfloor = 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 $\binom{4}{j}(4-j)!$ ways to fix a chosen set of $j$
positions and permute the rest, so inclusion–exclusion gives
$$
D_4 = 4! - \binom{4}{1}3! + \binom{4}{2}2! - \binom{4}{3}1! + \binom{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}$.

::impl{algo="inclusion_exclusion"}

## The Chinese Remainder Theorem

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

$$
x \equiv a_1 \pmod{m_1},\quad x \equiv a_2 \pmod{m_2},\quad\dots,\quad x \equiv a_n \pmod{m_n}
$$

with the moduli **pairwise coprime**, CRT guarantees a **unique** solution modulo
$M = \prod_i m_i$.[^clrs-crt] The construction is explicit and again uses the modular
inverse. Let $M_i = M / m_i = \prod_{j\ne 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^{\,\varphi(m_i)-1}$ (or $M_i^{m_i-2}$ when $m_i$ is prime). Then

$$
x \equiv \sum_{i=1}^{n} a_i\, M_i\, M_i^{-1} \pmod{M}.
$$

Each term $a_i M_i M_i^{-1}$ is $\equiv a_i \pmod{m_i}$ (since $M_i M_i^{-1}\equiv 1$
there) and $\equiv 0$ modulo every other $m_j$ (since $m_j \mid 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\pmod{15}$ one congruence at a time.

$$
% caption: CRT as a sum of selectors: each $a_iM_iM_i^{-1}$ hits its own residue and is
%          $0$ modulo the other, so the terms add to $x\equiv 8\pmod{15}$.
\begin{tikzpicture}[every node/.style={font=\small}, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-3.6,1.2) rectangle (4.0,-3.5);
  % column headers
  \node[font=\footnotesize] at (1.4,0.7) {$\bmod 3$};
  \node[font=\footnotesize] at (3.0,0.7) {$\bmod 5$};
  \draw[thick] (-3.4,0.35) -- (3.7,0.35);
  % row 1: term for m=3
  \node[anchor=west] at (-3.4,0) {a\textsubscript{1} M\textsubscript{1} (M\textsubscript{1} inv) = 20};
  \node[acc] at (1.4,0) {$2$};
  \node[black] at (3.0,0) {$0$};
  % row 2: term for m=5
  \node[anchor=west] at (-3.4,-0.9) {a\textsubscript{2} M\textsubscript{2} (M\textsubscript{2} inv) = 18};
  \node[black] at (1.4,-0.9) {$0$};
  \node[acc] at (3.0,-0.9) {$3$};
  \draw (-3.4,-1.35) -- (3.7,-1.35);
  % sum row
  \node[anchor=west] at (-3.4,-1.8) {sum = 38 = 8 (mod 15)};
  \node[draw=acc, fill=acc!15, very thick, minimum size=7mm, inner sep=1pt] at (1.4,-1.8) {$2$};
  \node[draw=acc, fill=acc!15, very thick, minimum size=7mm, inner sep=1pt] at (3.0,-1.8) {$3$};
  \node[acc, font=\footnotesize, align=center] at (0.1,-2.85)
    {each term is a selector: $1$ on its own modulus, $0$ on the other};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{CRT}(a[\,], m[\,])$ — combine congruences with pairwise-coprime moduli
$M \gets \prod_i m_i$
$x \gets 0$
for $i \gets 1$ to $n$ do
  $M_i \gets M / m_i$
  $y_i \gets \textsc{Mod-Inverse}(M_i \bmod m_i,\; m_i)$
  $x \gets (x + a_i \cdot M_i \cdot y_i) \bmod M$
return $x$
```

::impl{algo="chinese_remainder"}

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 = \tfrac{1}{n+1}\binom{2n}{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.[^stanley] The reflection-principle proof (count all paths, subtract
the "bad" ones by reflecting across the boundary) explains
the $\tfrac{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} = \binom{n+k-1}{k-1}$. Products of generating functions are
convolutions, which is why the [Fast Fourier
Transform](/algorithms/mathematical-algorithms/fast-fourier-transform) later in this
module multiplies two counting sequences in $O(n\log n)$.[^wilf]

**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, $\tfrac{1}{|G|}\sum_{g\in G}|\text{Fix}(g)|$, and **Pólya enumeration**
packages this into generating functions.[^burnside] These are the standard route to
"count the distinct colorings" problems that inclusion–exclusion alone cannot handle.

## Takeaways

- **Permutations** count orderings ($n!$, or $nPr = n!/(n-r)!$); **combinations**
  count subsets, $\binom{n}{r} = n!/(r!\,(n-r)!)$, dividing out the $r!$ orderings.
- **Pascal's rule** $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (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
  $\binom{n+k-1}{k-1}$, via the bars-between-stars bijection.
- To compute $\binom{n}{k}\bmod 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} \bmod M$, the inverse again coming
  from Fermat or the extended gcd.

[^clrs-count]: **CLRS**, Appendix C — Counting and Probability (§C.1): permutations, combinations, and the binomial coefficient $\binom{n}{r} = n!/(r!\,(n-r)!)$.
[^clrs-ie]: **CLRS**, Appendix C — Counting and Probability (§C.1): the inclusion–exclusion principle and the alternating-sign correction for unions.
[^clrs-crt]: **CLRS**, Ch. 31 — Number-Theoretic Algorithms (§31.5): the Chinese Remainder Theorem and the constructive $\sum a_i M_i M_i^{-1}$ formula.
[^lucas]: **Skiena**, § — Combinatorics: Lucas' theorem reduces $\binom{n}{k}\bmod p$ to a product of base-$p$ digit binomials when $n, k$ exceed $p$.
[^stanley]: R. P. Stanley, _Enumerative Combinatorics_, Vol. 2, Cambridge University Press, 1999 (Catalan numbers, Exercise 6.19 and its 66+ interpretations).
[^wilf]: H. S. Wilf, _generatingfunctionology_, 2nd ed., Academic Press, 1994 — the standard treatment of ordinary and exponential generating functions.
[^burnside]: 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.