Combinations

A combination is a selection of objects without regard to order. Choosing $\{A, B, C\}$ from a pool is the same combination as choosing $\{B, A, C\}$ or $\{C, B, A\}$. Combinations are used for committees, hands of cards, subsets , anywhere "who is in" matters but "in what order" does not.

Definitions

The number of ways to choose $r$ objects from $n$ distinct objects (without regard to order) is $\boxed{\binom{n}{r} = {^nC_r} = \dfrac{n!}{r!\,(n - r)!},}$ read "$n$ choose $r$". Some textbooks write $C(n, r)$.

Defined for $0 \le r \le n$. By convention $\binom{n}{r} = 0$ if $r < 0$ or $r > n$.

Why $r!$ in the denominator?

Compared to permutations: choosing $r$ from $n$ and also arranging them gives $P(n, r) = \dfrac{n!}{(n - r)!}$. But every unordered selection of $r$ objects corresponds to $r!$ different orderings. So $P(n, r) = r! \cdot \binom{n}{r} \implies \binom{n}{r} = \dfrac{P(n, r)}{r!} = \dfrac{n!}{r!(n - r)!}.$

Important identities

1. Symmetry: $\binom{n}{r} = \binom{n}{n - r}$. Choosing $r$ to include is the same as choosing $n - r$ to exclude.

2. Boundary: $\binom{n}{0} = \binom{n}{n} = 1$. $\binom{n}{1} = n$.

3. Pascal's identity: $\binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r}$. (Used to build Pascal's triangle.)

4. Sum of a row: $\sum_{r = 0}^{n} \binom{n}{r} = 2^n$. (Total number of subsets of an $n$-set.)

Proof of Pascal's identity

We count subsets of size $r$ from $\{1, 2, \dots, n\}$. Either the element $n$ is in the subset or not.

• If $n$ is in: we still need to choose $r - 1$ more from $\{1, 2, \dots, n - 1\}$, in $\binom{n-1}{r-1}$ ways.
• If $n$ is out: choose all $r$ from $\{1, 2, \dots, n-1\}$, in $\binom{n-1}{r}$ ways.

Total: $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$. $\qed$

When to use combinations

• Committees. Select a group; order doesn't matter.
• Card hands. Hand of $5$ cards from $52$: $\binom{52}{5}$.
• Subsets of a set. Choose any subset of size $r$.
• Lottery, sampling. Pick $r$ tickets/balls.

Pascal's triangle

Build it row by row using Pascal's identity:

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1

Row $n$ contains $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$.

Worked examples

Example 1. Compute $\binom{10}{3}$.

$\dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \dfrac{720}{6} = 120$.

Example 2. From a group of $5$ men and $4$ women, how many committees of $3$ men and $2$ women can be formed?

$\binom{5}{3} \cdot \binom{4}{2} = 10 \cdot 6 = 60$.

Example 3. How many ways can $5$ cards be chosen from a standard $52$-card deck?

$\binom{52}{5} = 2{,}598{,}960$.

Example 4. How many lines can be drawn through any two of $10$ points, no three of which are collinear?

A line is determined by two points (since no three are collinear). Number of pairs: $\binom{10}{2} = 45$.

Example 5 (harder). From $4$ red, $5$ blue and $3$ green balls, in how many ways can we select $4$ balls so that at least one is red?

Total selections of $4$ from $12$: $\binom{12}{4} = 495$.

Selections with no red ball (all from $8$ blue+green): $\binom{8}{4} = 70$.

Selections with at least one red: $495 - 70 = 425$.

Try it yourself

1. Compute $\binom{8}{3}$, $\binom{9}{4}$, $\binom{15}{5}$.
2. Verify $\binom{n}{r} = \binom{n}{n - r}$ for $n = 7, r = 3$.
3. Use Pascal's identity to find $\binom{6}{2}$.
4. In how many ways can $11$ players be chosen from a squad of $15$?
5. From a group of $7$ men and $5$ women, how many committees of $5$ contain at least $3$ women?
6. How many diagonals does a convex polygon with $n$ vertices have?
7. From $52$ cards: how many $5$-card hands contain exactly $2$ aces?
8. Find $n$: $\binom{n}{2} = 21$.
9. How many $3$-element subsets of $\{1, 2, 3, \dots, 10\}$ have all elements odd?
10. How many ways can $5$ jobs be assigned to $5$ workers, one job each? (This is a permutation, not combination , practice distinguishing.)
11. Show $\binom{n}{r} \cdot r = \binom{n - 1}{r - 1} \cdot n$.
12. In a class of $10$ students, in how many ways can a sub-committee of $3$ be chosen (no roles)?

Pitfalls / Tricks

• Order matters? If yes, permutation. If no, combination.
• "How many subsets of size $r$" $= \binom{n}{r}$. "How many sequences of length $r$" $= P(n, r)$.
• "At least" and "at most" problems often use complement: total minus the easier case.
• Insight. Whenever a problem says "choose", "select", "committee", "team", "group" , it's a combination. Whenever it says "arrange", "order", "sequence", "queue", "line up" , it's a permutation.