Counting and combinatorics

The binomial coefficient

The number of ways to choose $k$ items from $n$ when order does not matter.

The multinomial coefficient

The number of ways to split $n$ distinct items into labelled groups of sizes $n_1, \ldots, n_r$ — equivalently, the number of distinct arrangements of a word with repeated letters. The binomial coefficient is the case $r = 2$.

Onto assignments

The number of ways to assign $k$ distinct items to $n$ distinct boxes so that no box is empty. It is inclusion–exclusion over the set of boxes left empty, and it is the count behind "every desk gets at least one order" questions.

The central coefficient

The largest entry of row $2n$, and the one that turns up in random-walk and coin-flip questions.

The binomial theorem, and the sums it gives for free

Substituting values of $x$ produces the row identities at once: $x = 1$ gives $\sum_k \binom{n}{k} = 2^n$; $x = -1$ gives $\sum_k (-1)^k\binom{n}{k} = 0$, so even- and odd-sized subsets are equally numerous; differentiating and setting $x = 1$ gives $\sum_k k\binom{n}{k} = n2^{n-1}$.

The multinomial theorem

Each term picks, from each of the $n$ factors, one of the $r$ variables; the coefficient counts the ways to make a given choice of exponents.

Estimating the central coefficient

From Stirling’s formula. It is within about $1\%$ by $n = 10$ and improves from there, and it is the reason the chance of an exact tie in $2n$ fair flips falls like $1/\sqrt{\pi n}$.

Inclusion–exclusion

Add the singles, subtract the pairs, add the triples, alternating. Each element ends up counted exactly once.

Derangements without the alternating sum

Condition on where item one goes, say to position $j$ ($n - 1$ choices). Either item $j$ goes back to position one, leaving a derangement of $n - 2$, or it does not, which behaves like a derangement of $n - 1$. The rounding formula is exact for $n \ge 1$.

Euler’s totient as inclusion–exclusion

The number of integers up to $n$ sharing no factor with $n$ — inclusion–exclusion over its prime divisors, collapsed into a product. $\varphi(60) = 60 \times \tfrac{1}{2} \times \tfrac{2}{3} \times \tfrac{4}{5} = 16$.

The generalised pigeonhole principle

Put $n$ items in $k$ boxes and at least one box holds $\lceil n/k \rceil$. To guarantee $r$ items in some box you need $k(r - 1) + 1$ items.

The ballot problem

Candidate A finishes with $a$ votes and B with $b < a$. Counting the votes in random order, this is the chance A leads throughout.

Catalan numbers

Paths of $n$ ups and $n$ downs that never go below zero — and, by bijection, a great many other things.

The Catalan recurrence

Split a good path at its first return to zero: the part before is an elevated good path of some length, the part after is any good path. Every Catalan family has a first-return decomposition like this, and recognising the recurrence is often faster than finding the bijection.

Returning to the start

For a symmetric $\pm 1$ walk, the chance of being back at zero after $2n$ steps. It decays slowly, so returns keep happening — the one-dimensional walk is recurrent — even though each is individually less likely.