Counting Methods

Permutations and combinations: how many ways can it happen?

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$ :

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

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

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

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:

\binom{n}{k_1, k_2, \dots, k_r} = \frac{n!}{k_1!\, k_2! \cdots k_r!}

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