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. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
PermutationsCombinationsBinomial Theorem and Pascal's TriangleStars and BarsInclusion-Exclusion PrincipleCatalan NumbersMultinomial CoefficientsGenerating FunctionsPigeonhole PrincipleStirling Numbers and Bell NumbersInteger PartitionsBurnside's Lemma and Symmetry CountingTwelvefold Way SummaryKey Combinatorial Identities
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!} |