Combinatorics

Last updated: August 2026

Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.

Contents

  1. Counting principles: the bijective principle
  2. Binomial coefficients: Pascal and the Binomial Theorem
  3. Inclusion-Exclusion and derangements
  4. Generating functions: solving Fibonacci exactly
  5. Catalan numbers via the reflection principle
  6. Pigeonhole and the Erdős–Szekeres theorem
  7. Ramsey's theorem: $R(3,3)=6$
  8. Burnside's Lemma
  9. Computation
  10. Common pitfalls
  11. Connections
  12. References

1. Counting principles: the bijective principle

Principle

If finite sets $A,B$ are in bijection, $|A|=|B|$. Consequently: $|A\sqcup B|=|A|+|B|$ (disjoint union — partition the union and count each part), and $|A\times B|=|A||B|$ (partition $A\times B$ into $|A|$ copies of $B$, one per first coordinate).

Every counting formula in this note is, underneath, an explicit or implicit bijection between the objects being counted and some other set whose size is already known — this is the single idea the rest of the note keeps reusing, not a separate technique per formula.

2. Binomial coefficients: Pascal and the Binomial Theorem

Definition

$\binom nr$ is the number of $r$-element subsets of an $n$-element set.

Theorem (Pascal's identity)

$\binom nr=\binom{n-1}{r-1}+\binom{n-1}{r}$.

Proof. Partition the $r$-subsets of $\{1,\ldots,n\}$ by whether they contain $n$. Those that do correspond bijectively (remove $n$) to $(r-1)$-subsets of $\{1,\ldots,n-1\}$: $\binom{n-1}{r-1}$ of them. Those that don't are exactly the $r$-subsets of $\{1,\ldots,n-1\}$: $\binom{n-1}{r}$. The bijective principle (Section 1) sums these disjoint counts. ∎
Theorem (Binomial Theorem)

$(1+x)^n=\sum_{r=0}^n\binom nrx^r$.

Proof. Expand $(1+x)^n=(1+x)(1+x)\cdots(1+x)$ ($n$ factors) by picking, from each factor, either the term $1$ or the term $x$, and summing over all $2^n$ such choices. A choice contributes $x^r$ exactly when it picks $x$ from $r$ of the $n$ factors; the number of choices doing so is exactly the number of ways to choose which $r$ factors contribute $x$ — $\binom nr$. Collecting all choices by their power of $x$ gives the stated sum. ∎

Setting $x=1$: $\sum_r\binom nr=2^n$ (the number of subsets of an $n$-set, counted by size). Setting $x=-1$: $\sum_r(-1)^r\binom nr=0$ for $n>0$ — an identity Section 3 uses directly.

3. Inclusion-Exclusion and derangements

Theorem (Inclusion-Exclusion)

$\displaystyle\left|\bigcup_{i=1}^nA_i\right|=\sum_{k=1}^n(-1)^{k+1}\sum_{|S|=k}\left|\bigcap_{i\in S}A_i\right|$.

Proof. Fix any element $x$ in the union, belonging to exactly $j\geq1$ of the sets $A_i$. Its contribution to the right side is $\sum_{k=1}^n(-1)^{k+1}\binom jk$ (a $k$-fold intersection contains $x$ exactly when all $k$ chosen sets are among the $j$ containing $x$, giving $\binom jk$ such intersections — and $0$ contribution when $k>j$). By the Binomial Theorem (Section 2) with $x=-1$: $\sum_{k=0}^j(-1)^k\binom jk=0$, so $\sum_{k=1}^j(-1)^{k+1}\binom jk=-\left[\sum_{k=1}^j(-1)^k\binom jk\right]=-[0-1]=1$. So every element of the union contributes exactly $1$ to the right side — matching the left side's count of $1$ per element — and elements outside every $A_i$ contribute $0$ to both. ∎
Application (Derangements)

The number of permutations of $\{1,\ldots,n\}$ with no fixed point is $D_n=n!\sum_{i=0}^n\dfrac{(-1)^i}{i!}$.

Proof. Let $A_i$ be the permutations with $\sigma(i)=i$; $D_n=n!-\left|\bigcup A_i\right|$. For any $k$ specific positions, the permutations fixing all $k$ (free on the rest) number $(n-k)!$, and there are $\binom nk$ such position-sets, so the $k$-th inclusion-exclusion term is $\binom nk(n-k)!=\frac{n!}{k!}$. So $\left|\bigcup A_i\right|=\sum_{k=1}^n(-1)^{k+1}\frac{n!}{k!}$, giving $D_n=n!-\sum_{k=1}^n(-1)^{k+1}\frac{n!}{k!}=n!\left[1-\sum_{k=1}^n\frac{(-1)^{k+1}}{k!}\right]=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$. ∎

Section 9's numbers show $D_n/n!\to1/e\approx0.3679$ rapidly — a permutation chosen uniformly at random is a derangement with probability converging to $1/e$, essentially independent of $n$ once $n$ is even moderately large, since $\sum_{k=0}^n(-1)^k/k!$ is the truncated Taylor series for $e^{-1}$.

4. Generating functions: solving Fibonacci exactly

For a sequence $(a_n)$, its (ordinary) generating function is the formal power series $G(x)=\sum_{n\geq0}a_nx^n$ — a bookkeeping device that turns recurrences into algebra.

Theorem (Binet's formula, derived)

For $F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}$: $\displaystyle F_n=\frac{\phi^n-\psi^n}{\sqrt5}$, where $\phi=\frac{1+\sqrt5}2,\psi=\frac{1-\sqrt5}2$.

Proof. Let $G(x)=\sum_{n\geq0}F_nx^n$. Using the recurrence for $n\geq2$: $G(x)-F_0-F_1x=\sum_{n\geq2}F_nx^n=\sum_{n\geq2}(F_{n-1}+F_{n-2})x^n=x\sum_{n\geq2}F_{n-1}x^{n-1}+x^2\sum_{n\geq2}F_{n-2}x^{n-2}=xG(x)+x^2G(x)$ (using $F_0=0$ so the shifted sums start cleanly at $G(x)$). With $F_0=0,F_1=1$: $G(x)-x=(x+x^2)G(x)$, so $G(x)=\dfrac{x}{1-x-x^2}$. Since $\phi,\psi$ satisfy $t^2-t-1=0$ (so $\phi+\psi=1$, $\phi\psi=-1$), $1-x-x^2=(1-\phi x)(1-\psi x)$ (expand and match coefficients). Partial fractions: $\dfrac{x}{(1-\phi x)(1-\psi x)}=\dfrac1{\phi-\psi}\left[\dfrac1{1-\phi x}-\dfrac1{1-\psi x}\right]$ (solve for the two numerators directly, or verify by clearing denominators). Since $\phi-\psi=\sqrt5$, and $\frac1{1-cx}=\sum_{n\geq0}c^nx^n$ (geometric series) for each factor: $G(x)=\dfrac1{\sqrt5}\sum_{n\geq0}(\phi^n-\psi^n)x^n$. Comparing coefficients of $x^n$ on both sides gives $F_n=\dfrac{\phi^n-\psi^n}{\sqrt5}$. ∎

This is generating functions doing genuine work, not merely restating a formula: the recurrence became an algebraic equation for $G(x)$, solving that equation and expanding the (rational) result back into a power series read off the closed form directly, term by term. The same method solves any linear recurrence with constant coefficients, with the recurrence's characteristic-equation roots playing $\phi,\psi$'s role in general.

5. Catalan numbers via the reflection principle

Definition

$C_n$ counts Dyck paths: sequences of $n$ up-steps ($+1$) and $n$ down-steps ($-1)$, from height $0$ to height $0$, that never go below $0$.

Theorem

$C_n=\dfrac1{n+1}\dbinom{2n}n$.

Proof (reflection principle). There are $\binom{2n}n$ unrestricted paths with $n$ up- and $n$ down-steps from $(0,0)$ to $(2n,0)$ (choose which $n$ of the $2n$ steps are "up"). Call a path bad if it touches height $-1$ at some point. Given a bad path, reflect every step after its first touch of $-1$ (flip up$\leftrightarrow$down from that point on); since the path is at height $-1$ at the reflection point and the remaining $2n$ minus (steps so far) steps get flipped, the reflected path ends at height $-1-((-1)-0)=-2$ instead of $0$. This reflection is a bijection between bad paths ending at $(2n,0)$ and all paths ending at $(2n,-2)$ (any such path can be un-reflected the same way, since it must cross height $-1$ to get from $0$ to $-2$). A path to $(2n,-2)$ has $n-1$ up-steps and $n+1$ down-steps, so there are $\binom{2n}{n-1}$ of them — exactly the number of bad paths. So $C_n=\binom{2n}n-\binom{2n}{n-1}$. Since $\binom{2n}{n-1}=\binom{2n}n\cdot\frac n{n+1}$ (direct factorial simplification), $C_n=\binom{2n}n\left(1-\frac n{n+1}\right)=\frac1{n+1}\binom{2n}n$. ∎

Figure 1 draws the bijection directly: a path dipping below the axis, and its mirror image past the first touch of $-1$, landing two steps lower — exactly the map the proof constructs, checked against the closed form for $n=1,\ldots,9$.

Left panel: a lattice path that dips below the x-axis, with the portion after its first touch of y=-1 reflected to show it lands at height -2 at the end. Right panel: the Catalan number formula and the reflection-principle count agreeing exactly for n from 1 to 9 on a log scale.
Figure — The reflection principle, made concrete. Left: a random "bad" path for $n=5$ (touching $y=-1$) and its reflection past the first touch, landing at $(10,-2)$ instead of $(10,0)$ — the exact bijection Section 5's proof constructs. Right: the closed form $\frac1{n+1}\binom{2n}n$ and the reflection-principle count $\binom{2n}n-\binom{2n}{n-1}$ agree exactly at every $n$ tested, from $C_1=1$ to $C_9=4862$.

6. Pigeonhole and the Erdős–Szekeres theorem

Theorem (Pigeonhole, generalized)

If $n$ objects are placed into $m$ containers, some container holds at least $\lceil n/m\rceil$ objects.

Proof. If every container held at most $k-1$ objects, where $k=\lceil n/m\rceil$, the total would be at most $m(k-1)$. Since $k$ is the smallest integer $\geq n/m$, $k-1<n/m$, so $m(k-1)<n$ — but the total is exactly $n$, a contradiction. ∎
Theorem (Erdős–Szekeres, 1935)

Any sequence of $n^2+1$ distinct real numbers contains a monotonically increasing or monotonically decreasing subsequence of length $n+1$.

Proof. For each position $i$, let $\mathrm{inc}(i)$ (resp. $\mathrm{dec}(i)$) be the length of the longest increasing (resp. decreasing) subsequence ending at position $i$. For $i<j$: if the value at $i$ is less than at $j$, that increasing subsequence extends to $j$, so $\mathrm{inc}(j)>\mathrm{inc}(i)$; if greater, similarly $\mathrm{dec}(j)>\mathrm{dec}(i)$. Either way, $(\mathrm{inc}(i),\mathrm{dec}(i))\neq(\mathrm{inc}(j),\mathrm{dec}(j))$ — the map $i\mapsto(\mathrm{inc}(i),\mathrm{dec}(i))$ is injective. If no monotone subsequence of length $n+1$ existed, every $\mathrm{inc}(i),\mathrm{dec}(i)\in\{1,\ldots,n\}$, giving only $n^2$ possible pairs for the $n^2+1$ positions — by Pigeonhole, two positions would share a pair, contradicting injectivity. ∎

Figure 2 computes $(\mathrm{inc}(i),\mathrm{dec}(i))$ for an actual random sequence and exhibits the guaranteed subsequence directly — the proof is constructive in exactly this sense: it doesn't just assert a long monotone run exists, it hands over the injective-map argument that finds one.

A sequence of 10 distinct numbers plotted against position, with a length-5 increasing subsequence highlighted, exceeding the guaranteed minimum length of 4 for a sequence of this size.
Figure — Erdős–Szekeres, exhibited. A random arrangement of the $10=3^2+1$ numbers $0,\ldots,9$ is guaranteed (Section 6, $n=3$) a monotone subsequence of length $\geq4$; the actual longest increasing subsequence found by the $(\mathrm{inc},\mathrm{dec})$ construction has length $5$, comfortably meeting the bound.

7. Ramsey's theorem: $R(3,3)=6$

Definition

$R(3,3)$ is the smallest $N$ such that every red/blue coloring of the edges of $K_N$ contains a monochromatic triangle.

Proof that $R(3,3)\leq6$. Fix any vertex $v$ of $K_6$; it has $5$ colored edges to the other vertices. By Pigeonhole, at least $\lceil5/2\rceil=3$ share a color, say red, to vertices $a,b,c$. If any of $ab,bc,ac$ is red, that edge together with $v$'s two red edges to its endpoints forms a red triangle. Otherwise all three are blue, forming a blue triangle. Either way, a monochromatic triangle exists. ∎
Proof that $R(3,3)>5$. Color $K_5$'s edges by two disjoint $5$-cycles: red $=1$-$2$-$3$-$4$-$5$-$1$, blue $=1$-$3$-$5$-$2$-$4$-$1$ (every edge of $K_5$ lies in exactly one of these two cycles). Neither $5$-cycle contains a triangle (its shortest cycle has length $5$), so this coloring has no monochromatic triangle. ∎

Together: $R(3,3)=6$ exactly, both directions fully proved — existence for $N=6$, and an explicit witness showing $N=5$ is not enough. Ramsey numbers grow explosively past this case: $R(4,4)=18$ is known, but $R(5,5)$ remains unknown to this day, with only the bounds $43\leq R(5,5)\leq48$ established (as of this writing) — Paul Erdős's famous remark was that humanity should commit all its resources to computing $R(5,5)$ before an alien invasion demanding it on pain of destruction, but might reasonably negotiate on $R(6,6)$.

8. Burnside's Lemma

Theorem (Burnside's Lemma)

For a finite group $G$ acting on a finite set $X$: the number of orbits $|X/G|=\dfrac1{|G|}\displaystyle\sum_{g\in G}|X^g|$, where $X^g=\{x\in X:gx=x\}$.

Proof. Count pairs $(g,x)$ with $gx=x$ two ways. Summing over $g$ first: $\sum_{g\in G}|X^g|=|\{(g,x):gx=x\}|$. Summing over $x$ first: this equals $\sum_{x\in X}|\mathrm{Stab}(x)|$, where $\mathrm{Stab}(x)=\{g:gx=x\}$. By the orbit-stabilizer theorem (a standard group-theory fact, not re-derived here), $|\mathrm{Stab}(x)|=|G|/|\mathrm{Orb}(x)|$. So $\sum_{x\in X}|\mathrm{Stab}(x)|=|G|\sum_{x\in X}\frac1{|\mathrm{Orb}(x)|}$. Group this last sum by orbit: every $x$ in a given orbit $O$ contributes $1/|O|$, and there are $|O|$ such $x$, so each orbit contributes exactly $1$ to the sum — total $=$ number of orbits. Equating the two ways of counting: $\sum_{g\in G}|X^g|=|G|\cdot|X/G|$. ∎

Application: counting necklaces of $n$ beads in $k$ colors up to rotation, with $G=\mathbb Z_n$ acting by rotation. A rotation by $d$ positions fixes exactly the colorings constant on each cycle of that rotation; rotation by $d$ has $\gcd(n,d)$ cycles, so it fixes $k^{\gcd(n,d)}$ colorings. Burnside's Lemma gives the number of distinct necklaces as $\frac1n\sum_{d=0}^{n-1}k^{\gcd(n,d)}$ — a formula that, regrouped by the value of $\gcd(n,d)$, is exactly the standard necklace-counting formula $\frac1n\sum_{e\mid n}\varphi(n/e)k^e$ (Euler's totient function counting how many $d$ give each gcd value).

9. Computation

The figures above are generated by combinatorics/generate_figures.py. The snippet below checks Binet's formula and the derangement formula against their defining recurrences.

import math

def fib_recurrence(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def fib_binet(n):
    phi, psi = (1 + math.sqrt(5)) / 2, (1 - math.sqrt(5)) / 2
    return round((phi**n - psi**n) / math.sqrt(5))

for n in [10, 20, 30, 40, 50]:
    print(n, fib_recurrence(n), fib_binet(n), fib_recurrence(n) == fib_binet(n))

def derangements_recurrence(n):
    if n == 0: return 1
    if n == 1: return 0
    dp = [1, 0]
    for i in range(2, n + 1):
        dp.append((i - 1) * (dp[-1] + dp[-2]))
    return dp[n]

def derangements_formula(n):
    return round(math.factorial(n) * sum((-1)**i / math.factorial(i) for i in range(n + 1)))

for n in [5, 8, 10]:
    print(n, derangements_recurrence(n), derangements_formula(n))

Actual output:

10 55 55 True
20 6765 6765 True
30 832040 832040 True
40 102334155 102334155 True
50 12586269025 12586269025 True

5 44 44
8 14833 14833
10 1334961 1334961

Binet's closed form (Section 4, involving irrational $\phi,\psi$ and division by $\sqrt5$) reproduces the purely integer recurrence exactly, with simple rounding, up to $F_{50}$ — the irrational parts cancel precisely, not approximately. The derangement recurrence and the Inclusion-Exclusion formula (Section 3) agree exactly too, at every $n$ tested.

10. Common pitfalls

Pitfall — the addition principle needs disjointness

$|A\cup B|=|A|+|B|$ only when $A\cap B=\varnothing$; otherwise Section 3's Inclusion-Exclusion is the correct (and more general) tool — $|A\cup B|=|A|+|B|-|A\cap B|$, with the addition principle as the special case $|A\cap B|=0$. Forgetting the correction term is the single most common combinatorics error.

Pitfall — a Pigeonhole existence proof does not identify which container is crowded

Section 6's proof shows a monotone subsequence of length $\geq n+1$ exists, and the injective-map argument even shows how to find one algorithmically (Figure 2) — but the basic Pigeonhole principle in its bare form (Section 6's first theorem) is a pure counting argument: it certifies existence without saying which container is the crowded one, only that at least one must be.

Pitfall — Ramsey's theorem guarantees existence, at a specific threshold, not "often" or "usually"

$R(3,3)=6$ is exact: every single 2-coloring of $K_6$ has a monochromatic triangle (Section 7), and there is a specific coloring of $K_5$ with none. Ramsey numbers for larger cliques grow so explosively (the best known bounds for $R(5,5)$ still leave a gap of several units) that "the exact value is known" is the exception, not the rule, past the smallest cases.

Pitfall — Burnside's Lemma counts orbits, not fixed points, and needs a genuine group action

$|X^g|$ for a single $g$ (say the identity) is $|X|$ itself, wildly overcounting orbits if used alone — the whole point of Section 8's theorem is the average over all of $G$, not any single group element's fixed-point count. The formula also presupposes $G$ genuinely acts on $X$ (respecting the group operation); applying it to an arbitrary collection of permutations that isn't closed under composition gives a meaningless number.

11. Connections

12. References