Counting Methods

Counting is the bedrock of discrete probability. When all outcomes are equally likely, $P(A) = |A|/|\Omega|$ — and the hard part is just counting the numerator and denominator.

A permutation is an ordered arrangement. The number of ways to arrange $k$ distinct items chosen from $n$:

A combination is an unordered selection. The number of $k$-element subsets of an $n$-set:

The difference matters: there are $5! = 120$ ways to arrange 5 books on a shelf, but only $\binom{5}{2} = 10$ ways to pick 2 of them to take on vacation.

For splitting $n$ items into groups of sizes $k_1, \dots, k_r$ (with $\sum k_i = n$), the multinomial coefficient generalizes the binomial:

The hardest counting question is usually "ordered or unordered?" — get that right and the formula is mechanical.