Combinatorics & Generating Functions

Dyck paths $\leftrightarrow$ balanced parentheses $\leftrightarrow$ triangulations (Catalan, $C_n = \tfrac{1}{n+1}\binom{2n}{n}$, $C_5 = 42$, proved by the reflection bijection). Compositions of $n$ $\leftrightarrow$ subsets of $n - 1$ gaps ($2^{n-1}$). Stars and bars: nonnegative solutions of $x_1 + \cdots + x_k = n$ $\leftrightarrow$ arrangements of $n$ stars and $k - 1$ bars. A bijection is a proof; a formula is a claim.

Domino tilings of $2\times n$: $t_n = t_{n-1} + t_{n-2}$ (Fibonacci; $t_{10} = 89$). Derangements: $D_n = (n-1)(D_{n-1} + D_{n-2})$, or by inclusion–exclusion $n!\sum\tfrac{(-1)^k}{k!}$ ($D_6 = 265$). Generating functions multiply when choices are independent: $(1 + x + x^2 + \cdots)^k = (1-x)^{-k}$ is stars and bars, $\prod(1 + x^i)$ counts partitions into distinct parts, and Vandermonde $\sum\binom ak\binom{b}{n-k} = \binom{a+b}{n}$ is $(1+x)^a(1+x)^b$.

PIE counts surjections, derangements, and "no two adjacent" arrangements. Extremal: among finitely many points not all collinear, a pair at minimum distance... ; in a tournament, the vertex with maximum out-degree...; the longest path in a graph has endpoints whose neighbors all lie on it. Pigeonhole with $kn + 1$ objects forces $k + 1$ in a box; the Erdős–Szekeres theorem ($n^2 + 1$ reals contain a monotone subsequence of length $n + 1$) is pigeonhole plus extremal, and it is a Putnam regular.

$1000 - (500 + 333 + 200) + (166 + 100 + 66) - 33 = 1000 - 1033 + 332 - 33 = 266$. (Approximately $1000\cdot\tfrac12\cdot\tfrac23\cdot\tfrac45 = 266.7$ ✓.)

All paths: $\binom{2n}{n}$. A BAD path touches the line $y = x + 1$; reflect the portion after its first touch across that line — it now ends at $(n - 1, n + 1)$. This is a bijection between bad paths and all paths to $(n-1, n+1)$, of which there are $\binom{2n}{n-1}$. Good paths: $\binom{2n}{n} - \binom{2n}{n-1} = \tfrac{1}{n+1}\binom{2n}{n}$. $\blacksquare$ Significance: the reflection principle also solves the ballot problem and gambler's ruin — one bijection, three theorems.

Label each term $a_i$ with $(u_i, d_i)$ = lengths of the longest increasing and longest decreasing subsequence ENDING at $a_i$. For $i < j$: if $a_i < a_j$ then $u_j > u_i$; if $a_i > a_j$ then $d_j > d_i$ — so the labels are all distinct. If every $u_i, d_i \le n$ there are only $n^2$ possible labels for $n^2 + 1$ terms: pigeonhole. $\blacksquare$ Significance: the proof is the template "assign labels that are forced to be distinct, then count labels" — a pigeonhole pattern that recurs across Putnam combinatorics.

Step 1 — let $c_n$ count such compositions; the first part is $1$, $2$, or $3$: $c_n = c_{n-1} + c_{n-2} + c_{n-3}$ (tribonacci), $c_0 = 1$, $c_1 = 1$, $c_2 = 2$.

Step 2 — the generating function is $\sum c_nx^n = \dfrac{1}{1 - x - x^2 - x^3}$ (each composition is a word in the "alphabet" $x + x^2 + x^3$).

Step 3 — run the recurrence: $1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415$: $c_{20} = 121415$.

Step 4 — growth rate $\approx 1.839$, the real root of $x^3 = x^2 + x + 1$ — the generating function's smallest pole.

Step 1 — take $T$ with the MAXIMUM number of wins.

Step 2 — suppose some team $S$ is not reachable in $\le 2$ steps: $S$ beat $T$, and $S$ beat every team that $T$ beat.

Step 3 — then $S$ has at least (wins of $T$) $+ 1$ wins — the teams $T$ beat, plus $T$ itself — contradicting maximality. $\blacksquare$ Choosing the extreme object made the contradiction one sentence long; that is the extremal principle at its cleanest.