Combinations: counting unordered selections with $\binom{n}{r}$

What this dot point is asking

NESA wants you to count unordered selections (combinations) of $r$ objects from $n$ distinct objects, apply the formula $\binom{n}{r}$, use the key identities (symmetry, Pascal's rule, the sum to $2^n$), and handle the standard restriction types: "at least", "at most", "must include / must exclude a particular object", and splitting a set into groups. The single idea that unlocks the whole topic is that a combination is a permutation with the ordering thrown away, which is why the formula has an extra division by $r!$.

The answer

The combination formula

The number of ways to choose $r$ unordered objects from $n$ distinct objects is

The notation $\binom{n}{r}$ is read "$n$ choose $r$" and is also written ${}^n C_r$. It is defined for integers $0 \le r \le n$.

Why you divide by $r!$ (the link to permutations)

A combination is what you get from a permutation when order stops mattering. To choose and arrange $r$ from $n$ there are ${}^{n}P_r = \frac{n!}{(n-r)!}$ ordered lists. But every unordered selection of $r$ objects can be written as $r!$ different ordered lists (the $r!$ ways of arranging those same $r$ objects). So the ordered count over-counts the unordered count by exactly $r!$, and

The picture below makes the "divide by $r!$" concrete for $r = 3$: a single chosen set $\{A, B, C\}$ corresponds to $3! = 6$ ordered arrangements.

Key identities

Symmetry.

Choosing $r$ objects to include is the same act as choosing $n - r$ objects to exclude. This is also a labour-saver: compute whichever of the two has the smaller bottom number.

Pascal's rule.

Focus on one particular object. Either it is in the chosen subset (then choose the remaining $r - 1$ from the other $n - 1$) or it is not (then choose all $r$ from the other $n - 1$). These two cases are exclusive and exhaustive, so they add. This identity is exactly what builds Pascal's triangle row by row.

Sum identity.

The left side counts subsets of every size; the right side counts subsets by deciding "in or out" independently for each of the $n$ elements. Both count all subsets of an $n$-element set.

Boundary values.

$\binom{n}{0} = \binom{n}{n} = 1$ (one way to choose nothing, one way to choose everything), and $\binom{n}{1} = n$.

Complementary counting

For "at least $k$" or "at most $k$" problems it is usually far quicker to count the complement than to add up every allowed case:

The signal to reach for the complement is the phrase "at least one", because its opposite ("none") is a single, easy combination, whereas the direct count is a sum of several cases.

Splitting into groups

To split $n$ distinct objects into groups of sizes $r_1, r_2, \dots, r_k$ (with $r_1 + \dots + r_k = n$):

This is the multinomial coefficient, and equivalently it is the chain $\binom{n}{r_1} \cdot \binom{n - r_1}{r_2} \cdots \binom{r_k}{r_k}$ (choose the first group, then the second from what is left, and so on). A crucial wrinkle: this counts labelled groups (team A, team B, team C). If the groups are the same size and unlabelled, divide by the number of equal-sized groups factorial, because any relabelling of them gives the same division.

Counting with constraints

"Must include object $A$": $A$ is already in, so choose the remaining $r - 1$ from the other $n - 1$: $\binom{n - 1}{r - 1}$.

"Must exclude object $A$": $A$ is out, so choose all $r$ from the other $n - 1$: $\binom{n - 1}{r}$.

"Includes $A$ or $B$ but not both": add (includes $A$, excludes $B$) and (includes $B$, excludes $A$).

"At least one of $A, B, C$": use complementary counting (total minus the selections containing none of them).

How exam questions ask about combinations

• "How many [committees / teams / hands / subsets] of size $r$ ...?" with no mention of order: a plain $\binom{n}{r}$.
• "... containing at least one [type]?": complementary counting, total minus none.
• "... containing exactly $k$ [type]?": choose the $k$ from that type and the rest from the others, then multiply: $\binom{a}{k}\binom{b}{r-k}$.
• "... that must include [a named person/object]?": fix it in, then $\binom{n-1}{r-1}$.
• "... that must not include [a named person/object]?": $\binom{n-1}{r}$.
• "Split / divide [people] into groups of ...": multinomial $\dfrac{n!}{r_1!\cdots r_k!}$; divide by the symmetry factor if equal-sized groups are unlabelled.
• "In how many ways can a [defence] and a [forward line] be chosen?" (two pools): choose from each pool and multiply.
• "Show that $\binom{n}{r} = \binom{n}{n-r}$" or a Pascal's-rule identity: argue by the in/out or include/exclude meaning, not just algebra.
• Watch for the order cue. "Arranged", "in a row", "ranked", "first, second, third" means a permutation, not a combination.