COMB

Counting and combinatorics

The counting machinery behind every probability question: four standard cases, two techniques, and the arguments that prove something cannot be done.

1
Basic counting
Permutations, combinations, stars and bars, and telling the four cases apart.
- 1.1Counting: the four cases, and how to tell them apart12 min
2
Binomial coefficients
Pascal, hockey-stick, Vandermonde and the double-counting technique.
- 2.1Binomial identities, and proving them by counting twice12 min
3
Inclusion–exclusion and invariants
Derangements, the hat-check problem, pigeonhole and parity arguments.
- 3.1Inclusion–exclusion, derangements and the pigeonhole12 min
4
Advanced structures
Catalan numbers, the ballot problem, lattice paths and the reflection principle.
- 4.1Lattice paths, the reflection principle and Catalan numbers13 min

Basic counting