Progress Log in Get Started

Combinatorics Cheat Sheet

Permutations, combinations, stars and bars, inclusion–exclusion and derangements.

Counting

Permutations

P (n, k) = \frac{n !}{( n - k )!}

Combinations

(k n) = \frac{n !}{k ! ( n - k )!}

Multinomial

\frac{n !}{k _{1} ! k _{2} ! \dots k _{m} !}

Stars and bars

(k - 1 n + k - 1)

Ways to put $n$ identical balls into $k$ labelled boxes.

Advanced

Inclusion–exclusion

i ⋃ A_{i} = \sum ∣ A_{i} ∣ - \sum ∣ A_{i} \cap A_{j} ∣ + \dots

Derangements

! n = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !} \approx \frac{n !}{e}

Catalan numbers

C_{n} = \frac{1}{n + 1} (n 2 n)

Learn this topic Browse problems