Combinations

A combination is a selection of objects where order doesn’t matter. Choosing $3$ friends to invite to a movie, picking pizza toppings, or being dealt a hand of cards are all combinations: the same items in a different order are the same selection. Combinations are closely related to permutations, and they’re the numbers in Pascal’s triangle.

Key ideas

What is a combination?

A combination of $r$ objects chosen from $n$ different objects is a selection where order doesn’t matter. Choosing two letters from A, B, C gives just three combinations:

$$\text{AB, AC, BC}$$

Compare this with the six permutations AB, BA, AC, CA, BC, CB. Each combination shows up $2! = 2$ times as a permutation.

The formula

The number of combinations of $r$ objects chosen from $n$ different objects is

$$\binom{n}{r} = \frac{n!}{r!\,(n - r)!}$$

Read $\dbinom{n}{r}$ as ”$n$ choose $r$”. It’s also written $C(n, r)$ or ${}_nC_r$, and most calculators have an nCr key: for $\dbinom{8}{3}$, type $8$, then nCr, then $3$.

How combinations relate to permutations

Every combination of $r$ objects can be put in order in $r!$ ways. So each combination is counted $r!$ times among the permutations:

$$P(n, r) = \binom{n}{r} \times r! \qquad\text{so}\qquad \binom{n}{r} = \frac{P(n, r)}{r!}$$

For example, $\dbinom{8}{3} = \dfrac{P(8, 3)}{3!} = \dfrac{336}{6} = 56$.

Useful facts

• $\dbinom{n}{0} = 1$ and $\dbinom{n}{n} = 1$: there’s one way to choose nothing, and one way to choose everything.
• Symmetry: $\dbinom{n}{r} = \dbinom{n}{n - r}$. Choosing $3$ people to go is the same as choosing the $n - 3$ who stay.
• Pascal’s triangle: $\dbinom{n}{r}$ is the entry $t_{n, r}$ in row $n$, position $r$. See Pascal’s triangle for the patterns.

Permutation or combination?

Ask the swap question: if I swap two of the chosen items, is it a different result?

Order matters: permutation	Order doesn’t matter: combination
president, VP, and treasurer	a committee of $3$
first, second, third place	the top $3$ finishers, unranked
arranging books on a shelf	choosing books to take on a trip
a lock code	a hand of cards

“At least” and “at most”

Some committee problems have conditions, like “at least $2$ teachers”. There are two ways to count them:

• Cases: split into separate cases (exactly $2$, exactly $3$, …), count each with the multiplicative principle, then add the cases.
• Complement: count everything, then subtract the cases you don’t want. For “at least one”, the complement is “none”, which is usually one quick calculation.

Worked examples

Example 1: Pizza toppings

A pizza place has $8$ toppings. How many different $3$-topping pizzas can you order (all toppings different)?

Solution. Pepperoni-mushroom-olive is the same pizza as olive-pepperoni-mushroom, so order doesn’t matter:

$$\binom{8}{3} = \frac{8!}{3!\,5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$$

Example 2: Permutation or combination?

A coach has $6$ swimmers.

• (a) How many ways can she pick a $4$-person relay team and the order they swim in?
• (b) How many ways can she pick $4$ swimmers to go to a training camp?

Solution. (a) Swimming first is different from swimming last, so order matters:

$$P(6, 4) = 6 \times 5 \times 4 \times 3 = 360$$

(b) The camp group is just a group, so order doesn’t matter:

$$\binom{6}{4} = \frac{6!}{4!\,2!} = 15$$

Check: $15 \times 4! = 15 \times 24 = 360$. ✓

Example 3: A committee with two groups

A committee of $5$ is chosen from $6$ teachers and $8$ students. How many committees have exactly $2$ teachers?

Solution. Exactly $2$ teachers means exactly $3$ students. Choose the teachers and the students, and multiply:

$$\binom{6}{2} \times \binom{8}{3} = 15 \times 56 = 840$$

Example 4: At least one

Using the same $6$ teachers and $8$ students, how many committees of $5$ have at least one teacher?

Solution. Use the complement. With no restriction, choose $5$ from all $14$ people:

$$\binom{14}{5} = 2002$$

“At least one teacher” is the opposite of “no teachers”, which means all $5$ are students: $\dbinom{8}{5} = 56$.

$$2002 - 56 = 1946$$

You could also add the cases $1, 2, 3, 4, 5$ teachers, but that’s five calculations instead of two.

Common mistakes

Using a combination when order matters. If the chosen items get different roles or positions, it’s a permutation. A committee with a chair and a secretary is not just a committee.

Adding when you should multiply. ”$2$ teachers and $3$ students” means multiply. Add only between separate cases (exactly $2$ teachers or exactly $3$ teachers).

Counting “at least one” as one choice times the rest. It’s tempting to pick one teacher ($6$ ways), then any $4$ others ($\dbinom{13}{4}$ ways). This counts many committees more than once (a committee with two teachers gets counted twice). Use cases or the complement instead.

Forgetting a case. For “at least $2$ of $4$”, the cases are exactly $2$, $3$, and $4$. List them before calculating.

Mixing up the formula. $\dbinom{n}{r}$ has two factorials on the bottom, $r!$ and $(n - r)!$. If your answer isn’t a whole number, check the formula.

Practice

1. (Warm-up) Evaluate $\dbinom{7}{2}$, $\dbinom{10}{10}$, $\dbinom{9}{0}$, and $\dbinom{12}{3}$.

Solution

$\dbinom{7}{2} = \dfrac{7 \times 6}{2} = 21$, $\dbinom{10}{10} = 1$, $\dbinom{9}{0} = 1$, and $\dbinom{12}{3} = \dfrac{12 \times 11 \times 10}{6} = 220$.

2. (Warm-up) Permutation or combination?

• (a) being dealt $5$ cards
• (b) choosing a captain and an assistant captain
• (c) picking $6$ numbers for a lottery ticket
• (d) the top $3$ finishers in a race, in order

Solution

(a) Combination. (b) Permutation (different roles). (c) Combination. (d) Permutation.

3. (Warm-up) At a meeting, each of $10$ people shakes hands once with every other person. How many handshakes are there?

Solution

Each handshake is a pair of people, and the order doesn’t matter:

$$\binom{10}{2} = \frac{10 \times 9}{2} = 45$$

4. (Core) Show that $\dbinom{9}{4} = \dbinom{9}{5}$, and explain why this makes sense.

Solution

$$\binom{9}{4} = \frac{9!}{4!\,5!} = 126, \qquad \binom{9}{5} = \frac{9!}{5!\,4!} = 126$$

Choosing $4$ items from $9$ automatically leaves $5$ behind, so every choice of $4$ matches exactly one choice of $5$.

5. (Core) A class of $25$ students chooses student council representatives.

• (a) How many ways can it choose $3$ representatives?
• (b) How many ways can it choose a president, a vice-president, and a secretary?

Solution

(a) Order doesn’t matter: $\dbinom{25}{3} = 2300$.

(b) The roles are different: $P(25, 3) = 25 \times 24 \times 23 = 13\,800$.

Check: $2300 \times 3! = 13\,800$. ✓

6. (Core) A pizza place has $10$ toppings. How many different pizzas can you order with at most $3$ toppings (a plain cheese pizza counts)?

Solution

Add the cases $0, 1, 2, 3$ toppings:

$$\binom{10}{0} + \binom{10}{1} + \binom{10}{2} + \binom{10}{3} = 1 + 10 + 45 + 120 = 176$$

7. (Core) A committee of $4$ is chosen from $5$ Grade 11 students and $7$ Grade 12 students. How many committees have at least $2$ Grade 11 students?

Solution

Add the cases $2$, $3$, and $4$ Grade 11 students:

$$\begin{aligned} &\binom{5}{2}\binom{7}{2} + \binom{5}{3}\binom{7}{1} + \binom{5}{4}\binom{7}{0} \\ &= 10 \times 21 + 10 \times 7 + 5 \times 1 \\ &= 210 + 70 + 5 = 285 \end{aligned}$$

Check with the complement: the total is $\dbinom{12}{4} = 495$, and committees with $0$ or $1$ Grade 11 student number $\dbinom{7}{4} + \dbinom{5}{1}\dbinom{7}{3} = 35 + 175 = 210$. $495 - 210 = 285$. ✓

8. (Challenge) A diagonal of a polygon joins two vertices that aren’t next to each other. How many diagonals does a $10$-sided polygon (decagon) have?

Solution

Any pair of the $10$ vertices gives a line segment: $\dbinom{10}{2} = 45$. Of these, $10$ are sides, not diagonals:

$$45 - 10 = 35$$

9. (Challenge) A committee of $5$ is chosen from $12$ people. Ravi and Mei refuse to serve together. How many committees are possible?

Solution

Use the complement. All committees: $\dbinom{12}{5} = 792$. Committees with both Ravi and Mei: they’re in, so choose the other $3$ from the remaining $10$: $\dbinom{10}{3} = 120$.

$$792 - 120 = 672$$