Permutations & Combinations

Count selections with C(n, k) and arrangements with P(n, k) — cancel the big factorial.

The idea

Permutations and combinations count the two basic ways of selecting $k$ objects from $n$: a permutation is an ordered line-up, a combination an unordered group.

To count the permutations, fill $k$ slots in turn. The first slot has $n$ candidates, the second has the $n - 1$ who remain, and so on down to $n - k + 1$ candidates for the last. Multiplying the independent choices gives $P(n, k) = n (n-1) \cdots (n - k + 1) = \frac{n!}{(n-k)!},$ where the $(n-k)!$ underneath cancels the unwanted tail of $n!$.

To count the combinations, start from the permutations and remove the order. Each group of $k$ objects appears once for every one of its $k!$ line-ups, so dividing by $k!$ counts each group exactly once: $C(n, k) = \frac{P(n, k)}{k!} = \frac{n!}{k!\,(n-k)!}.$ The figure shows this collapse for three letters $A$, $B$, $C$: all $3! = 6$ of their line-ups are the same group.

When computing either count, do not expand $n!$. Cancel the larger of $k!$ and $(n-k)!$ against it first, leaving a short descending product on top.

Ways to work on it

• Walkthrough. Compute a 'choose' count C(n, k) by cancelling the big factorial first.
• Practice. Alternates between C(n, k) ('choose') and P(n, k) ('arrange') on small n.
• Hardest. Count committees that must include a given mix of members.

Not sure where to start? Take the ten-question placement test.