🔢 Combinatorics

Probability on a finite, equally likely space is just counting: $P(A)=\frac{|A|}{|\Omega|}$. This page builds the counting toolkit from two questions, does order matter? and can I reuse items?, then adds three power tools: stars and bars, inclusion–exclusion, and lattice paths.

Permutations & combinations

Permutations: order matters

Arrange $k$ of $n$ distinct items in a row. There are $n$ choices for the first slot, $n-1$ for the second, …, and $n-k+1$ for the $k$-th:

$$P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}$$

With $k=n$ this is $n!$, the number of orderings of all $n$ items.

Combinations: order doesn't matter

Choose a set of $k$ items from $n$ (a committee, a poker hand):

$$\binom nk=\frac{n!}{k!\,(n-k)!}=\frac{P(n,k)}{k!}$$

Handy identities (and why they're true)

• $\binom nk=\binom n{n-k}$: choosing who's in is the same as choosing who's out.
• $\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$ (Pascal): either item $n$ is chosen or it isn't.
• $\sum_k\binom nk=2^n$: each item is in or out.
• $\sum_k\binom mk\binom{n}{r-k}=\binom{m+n}{r}$ (Vandermonde): choose $r$ people from $m$ men and $n$ women by splitting on the number of men.

The four ways to pick $k$ from $n$

Almost every counting question is one cell of this table. Decide (1) whether the order of your picks matters and (2) whether an item can be picked more than once.

	without replacement	with replacement
order matters	$P(n,k)=\dfrac{n!}{(n-k)!}$ podium finishes, passwords with distinct characters	$n^k$ PIN codes, sequences of die rolls
order doesn't matter	$\dbinom nk$ committees, poker hands	$\dbinom{n+k-1}{k}$ buying $k$ donuts from $n$ flavors (stars & bars)

Arrangements with repeated items (multinomial)

How many ways are there to arrange $n$ objects when there are $n_1$ identical objects of type 1, $n_2$ of type 2, …, $n_m$ of type $m$?

$$\binom{n}{n_1,\dots,n_m}=\frac{n!}{n_1!\,n_2!\cdots n_m!}$$

Second view: choose positions type by type

Choose positions for type 1, then for type 2 among the rest, and so on:

$$\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots\binom{n_m}{n_m}=\frac{n!}{n_1!(n-n_1)!}\cdot\frac{(n-n_1)!}{n_2!(n-n_1-n_2)!}\cdots=\frac{n!}{n_1!\cdots n_m!}.$$

With two types this is just $\binom n{n_1}$. For example, arranging $k$ H's and $n-k$ T's gives $\binom nk$ sequences, which is where the binomial PMF comes from.

Stars and bars

Question: how many ways can you write $n$ as an ordered sum of $k$ non-negative integers, $x_1+x_2+\dots+x_k=n$ with each $x_i\ge0$?

Line up $n$ stars and drop $k-1$ bars among them. The bars cut the stars into $k$ groups, and the group sizes are $x_1,\dots,x_k$. For example, with $n=5$ and $k=3$:

$$\star\star\,|\,\,|\,\star\star\star \;\longleftrightarrow\; (2,0,3) \qquad\qquad |\,\star\star\star\star\,|\,\star \;\longleftrightarrow\; (0,4,1)$$

Every arrangement of $n$ stars and $k-1$ bars gives exactly one solution and vice versa. So count arrangements: there are $n+k-1$ symbols, and we choose which $k-1$ of them are bars:

Combination with replacement = stars and bars

Choosing $k$ items from $n$ types with replacement, order irrelevant is the same problem. Let $x_i$ be how many of type $i$ you take, so $x_1+\dots+x_n=k$. That gives $k$ stars and $n-1$ bars:

$$\binom{n+k-1}{k}$$

Example: 3 donuts from 4 flavors gives $\binom{6}{3}=20$ boxes. Note the roles swap: in "sum of $k$ integers to $n$", $n$ is the number of stars, while in "choose $k$ from $n$ types", $k$ is.

Inclusion–exclusion

$$P(A\cup B)=P(A)+P(B)-P(A\cap B)$$ $$P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C)$$

The same formula holds for counts:

$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$

Why the general formula counts each element exactly once

General form: $\big|\bigcup_{i=1}^n A_i\big|=\sum_{\emptyset\neq S\subseteq[n]}(-1)^{|S|+1}\big|\bigcap_{i\in S}A_i\big|$.

Take an element that lies in exactly $r\ge1$ of the sets. It appears in $\binom rj$ of the $j$-fold intersections, so its total count is

$$\binom r1-\binom r2+\binom r3-\dots=1-(1-1)^r=1.$$

Elements in none of the sets are never counted. ∎

Derangements

A derangement is a permutation with no fixed points: nothing ends up in its original position. In the classic story, $n$ people check their hats, the hats are handed back at random, and nobody gets their own hat. Write $D_n$ for the number of derangements of $n$ items.

So $P(\text{random permutation has no fixed point})=\frac{D_n}{n!}\to\frac1e\approx0.3679$, and it converges very fast. Already at $n=5$ it is $0.3667$. First values: $D_1..D_8 = 0, 1, 2, 9, 44, 265, 1854, 14833$, with $D_0=1$.

Proof of the formula via inclusion–exclusion

Let $A_i$ be the set of permutations fixing $i$. Then $|A_{i_1}\cap\dots\cap A_{i_k}|=(n-k)!$, since the $k$ points are pinned and the rest are free. There are $\binom nk$ such intersections, so

$$|A_1\cup\dots\cup A_n|=\sum_{k=1}^n(-1)^{k+1}\binom nk(n-k)!=\sum_{k=1}^n(-1)^{k+1}\frac{n!}{k!}.$$ $$D_n=n!-|A_1\cup\dots\cup A_n|=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\;\xrightarrow{\;n\to\infty\;}\;\frac{n!}{e},$$

because $\sum_k (-1)^k/k!$ is the Taylor series of $e^{-1}$. The tail after $k=n$ is smaller than $\frac1{(n+1)!}$, so $|D_n-n!/e|<\frac1{n+1}\le\frac12$. That is why rounding works.

Proof of the recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$

Where does item 1 go? It goes to some position $j\neq1$, and there are $n-1$ choices. Now look at item $j$:

• Item $j$ goes to position 1 (a swap). Remove 1 and $j$. The other $n-2$ items must form a derangement: $D_{n-2}$.
• Item $j$ does not go to position 1. Then position 1 acts like a "forbidden spot" for $j$, playing the role of $j$'s own spot. The $n-1$ items other than 1 must avoid their (relabeled) spots: $D_{n-1}$.

Total: $(n-1)(D_{n-1}+D_{n-2})$. Check: $D_4=3(2+1)=9$ ✓.

Path counting

Question: how many paths go from $(0,0)$ to $(m,n)$ on a grid if each step moves one unit right (R) or one unit up (U)?

• Every path has exactly $m$ R-steps and $n$ U-steps, so $m+n$ steps in total.
• A path is uniquely specified by choosing which of the $m+n$ steps are R's. For example, RRURU ↔ R's at steps $\{1,2,4\}$.