Combinatorics is the branch of mathematics concerned with counting, arrangement, and combination of objects. It forms the foundation of probability theory, algorithm analysis, and discrete mathematics. This cheat sheet covers the essential techniques—from basic permutations and combinations to advanced tools like generating functions, Stirling numbers, and Burnside's lemma—with formulas and worked examples for each.
What This Cheat Sheet Covers
This topic spans 14 focused tables and 67 indexed concepts, 58 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Permutations
| Type | Example | Description | |
|---|---|---|---|
$P(5,3) = \frac{5!}{(5-3)!} = 60$ | Ordered arrangements of $r$ items from $n$ distinct items: $P(n,r) = \frac{n!}{(n-r)!}$ | ||
$3$ digits from ${0\text{–}9}$: $10^3 = 1000$ | Each position can be any of $n$ items: $n^r$ | ||
MISSISSIPPI: $\frac{11!}{1!,4!,4!,2!} = 34650$ | Arrange $n$ objects with repetitions $n_1, n_2, \ldots, n_k$: $\frac{n!}{n_1!, n_2!, \cdots, n_k!}$ | ||
$5$ people at a round table: $(5-1)! = 24$ | Arrangements around a circle: $(n-1)!$ (fixes one position to remove rotational equivalence) | ||
$5$ beads necklace: $\frac{(5-1)!}{2} = 12$ | Circular arrangement with reflection symmetry: $\frac{(n-1)!}{2}$ | ||
$D_4 = 9$; probability $\approx 1/e \approx 0.368$ | Permutations where no element appears in its original position: $D_n = n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}$ |