Combinations

In many real situations, we care only about which objects are chosen, not the order in which they are picked — forming a committee, selecting subjects, or picking a hand of cards. These are combinations, and the way to recognise a combination problem is the mirror image of the permutation test: if reordering the same selected objects does not create a new outcome, it is a combination problem.

Definition and formula

A combination is a selection of objects where order does not matter. The number of combinations of $n$ distinct objects taken $r$ at a time (where $0 \le r \le n$) is denoted $^{n}C_{r}$ or $\binom{n}{r}$, and is given by

Relation between $^{n}P_{r}$ and $^{n}C_{r}$

Every combination of $r$ objects, once chosen, can itself be arranged in $r!$ different orders. So the number of ordered selections (permutations) is the number of unordered selections (combinations) multiplied by the number of ways to order each selection:

This relation is the fastest way to remember why combinations are "smaller" than permutations for the same $n$ and $r$ — a combination formula simply divides out the $r!$ internal orderings that a permutation counts separately.

Key properties (all provable from the formula, and all frequently tested)

1. Complement property: $^{n}C_{r} = {}^{n}C_{n-r}$ — choosing $r$ objects to include is equivalent to choosing $n-r$ objects to leave out.
2. Boundary values: $^{n}C_{0} = {}^{n}C_{n} = 1$ (there is exactly one way to choose nothing, and exactly one way to choose everything).
3. Pascal's rule: $^{n}C_{r} + {}^{n}C_{r-1} = {}^{n+1}C_{r}$ — this is the identity that generates Pascal's Triangle, and it reappears directly in the Binomial Theorem in the next section. …