Enumerative Combinatorics

Formula sheet

Definitions and key results, unit by unit.

Drill these formulas

Jump to a unit

Unit 1: Counting principles, bijections, and the pigeonhole principle
Unit 2: Binomial and multinomial coefficients, identities, and lattice paths
Unit 3: Compositions, multisets, and distributing objects into boxes
Unit 4: Inclusion-exclusion, derangements, and surjections
Unit 5: Set partitions, Stirling numbers, and the cycle structure of permutations
Unit 6: Integer partitions and Ferrers diagrams
Unit 7: Ordinary generating functions, recurrences, and Catalan numbers
Unit 8: Exponential generating functions and labeled structures

Unit 1

Counting principles, bijections, and the pigeonhole principle

Basic rules

Sum rule

If $A$ and $B$ are disjoint finite sets, $|A \cup B| = |A| + |B|$ . More generally the size of a disjoint union is the sum of the sizes.

Product rule

If a choice is made in $r$ stages and stage $j$ always has $n_j$ options, whatever was chosen before, there are $n_1 n_2 \cdots n_r$ outcomes. In particular $|A \times B| = |A|\,|B|$ .

Bijection principle

Two finite sets have the same size exactly when there is a bijection between them. To count a set, build a bijection to a set you can already count.

Double counting

Count one set in two different ways and set the answers equal. Most binomial identities have a proof of this kind.

Subsets of an $n$ -set

2^n

Each element is either in or out: a bijection with words in $\{0,1\}^n$ .

Words, functions and arrangements

Words of length $k$ over $n$ letters

n^k

The same count as all functions $[k] \to [n]$ .

Falling factorial

\begin{gathered} n^{\underline{k}} = n(n-1)\cdots(n-k+1) \\ = \frac{n!}{(n-k)!} \end{gathered}

Words of length $k$ with no repeated letter, or injections $[k] \to [n]$ .

Permutations of $[n]$

n!

Bijections $[n] \to [n]$ . By convention $0! = 1$ .

Circular arrangements

\frac{n!}{n} = (n-1)! \quad (n \ge 1)

Seatings of $n$ people around a round table, counted up to rotation.

Pigeonhole principle

If $n+1$ objects are placed in $n$ boxes, some box holds at least two of them.

Generalized pigeonhole

\left\lceil N/k \right\rceil

If $N$ objects are placed in $k$ boxes, some box holds at least $\lceil N/k \rceil$ of them, and some box holds at most $\lfloor N/k \rfloor$ .

Erdős–Szekeres theorem

Every sequence of $rs+1$ distinct real numbers has an increasing subsequence of length $r+1$ or a decreasing subsequence of length $s+1$ . The bound $rs+1$ cannot be lowered.

Unit 2

Binomial and multinomial coefficients, identities, and lattice paths

Unit 3

Compositions, multisets, and distributing objects into boxes

Unit 4

Inclusion-exclusion, derangements, and surjections

Unit 5

Set partitions, Stirling numbers, and the cycle structure of permutations

Unit 6

Integer partitions and Ferrers diagrams

Unit 7

Ordinary generating functions, recurrences, and Catalan numbers

Unit 8

Exponential generating functions and labeled structures

This sheet was still loading. Close this and print again once every unit shows its formulas.