Combinations — Definition and Formula Derivation

A combination is a selection of $r$ objects from a larger collection of $n$ distinct objects, where — unlike a permutation — the order of selection does not matter. Choosing objects $\{A, B, C\}$ for a committee is the same combination regardless of whether $A$, $B$ or $C$ was "picked first"; only the final group matters, not how it was assembled.

The number of combinations of $r$ objects chosen from $n$ distinct objects (with $0 \le r \le n$) is denoted $^{n}C_{r}$ (also written $C(n,r)$ or $\dbinom{n}{r}$).

Deriving the formula for $^{n}C_{r}$ from $^{n}P_{r}$

Every permutation can be built in exactly two stages: first select which $r$ objects will be used (this is precisely what $^{n}C_{r}$ counts), and second, arrange those $r$ selected objects in some order (this can be done in $r!$ ways, since arranging $r$ distinct objects in a row is $^{r}P_{r} = r!$). By the Fundamental Principle of Counting, doing both stages in sequence gives the total number of ordered selections, which is exactly $^{n}P_{r}$:

Solving for $^{n}C_{r}$, and substituting the factorial form of $^{n}P_{r}$ derived in Section 3:

Key properties

• $^{n}C_{0} = \dfrac{n!}{0!\, n!} = 1$ — there is exactly one way to select no objects (the empty selection).
• $^{n}C_{n} = \dfrac{n!}{n!\, 0!} = 1$ — there is exactly one way to select all $n$ objects.
• $^{n}C_{r} = {}^{n}C_{n-r}$ — choosing $r$ objects to include in a selection automatically determines the $n - r$ objects left out, so the two counts must be equal. This is confirmed algebraically: $^{n}C_{n-r} = \dfrac{n!}{(n-r)!\,(n-(n-r))!} = \dfrac{n!}{(n-r)!\, r!} = {}^{n}C_{r}$.