Permutations and combinations

The base is the multiplication principle: if a task is done in \(m\) steps and the first has \(a_1\) ways, the second \(a_2\), and so on, there are \(a_1a_2\cdots a_m\) ways in total. Ordering \(n\) distinct objects gives \(n!=n(n-1)\cdots1\) permutations; ordering only \(k\) of them gives \(P(n,k)=n(n-1)\cdots(n-k+1)\).

If order does not matter, each selection of \(k\) elements is counted \(k!\) times in \(P(n,k)\), hence \(\binom{n}{k}=P(n,k)/k!\). It is read «\(n\) choose \(k\)» and satisfies \(\binom{n}{k}=\binom{n}{n-k}\): choosing what goes in is the same as choosing what stays out.

Guiding example: a 5-card hand has \(\binom{52}{5}=2{,}598{,}960\) possible hands, all equally likely; the probability of an event is the number of favorable hands over that total. This links counting with classical probability.

The key question is always: does order matter? President and secretary do; committee members do not. Another common mistake is forgetting that \(0!=1\), or applying \(P(n,k)\) when elements repeat, in which case one must divide by the repetitions.