Combinations and the formula for nCr

Order or no order

Coach Selvi has four runners: Asha, Bilal, Chen and Dev. She needs two of them.

• For a relay, one runs first and one runs second. Asha then Bilal is different from Bilal then Asha.
• For a team photo, she just picks two. Asha and Bilal is the same pair as Bilal and Asha.

The relay needs an arrangement, a permutation. The photo needs a selection, a combination. In a combination, order does not matter.

Listing them

Write the runners as A, B, C and D. The selections of two are

• $\{A, B\}$, $\{A, C\}$ and $\{A, D\}$, the pairs with A;
• $\{B, C\}$, $\{B, D\}$ and $\{C, D\}$, the pairs without A.

That is $6$ selections. The arrangements of two number $^{4}P_{2} = 4 \times 3 = 12$. Each selection appears twice among them, once in each order.

From arrangements to selections

The number of selections of $r$ things from $n$ different things is written $^{n}C_{r}$, read "$n$ choose $r$". Books also write $C(n, r)$ or $\dbinom{n}{r}$.

To arrange $r$ things from $n$, you can work in two steps.

Step 1. Choose which $r$ things: $^{n}C_{r}$ ways.

Step 2. Arrange the chosen $r$ in a row: $r!$ ways.

By the multiplication principle,

Since $^{n}P_{r} = \dfrac{n!}{(n - r)!}$, dividing by $r!$ gives the formula:

Working it out quickly

You rarely need the full factorials. Cancel $(n - r)!$ first:

There are $r$ factors on top, counting down from $n$. For example,

The answer is always a whole number, even though it looks like a fraction.

Small values

• $^{n}C_{0} = 1$. There is one way to choose nothing. This is why $0! = 1$.
• $^{n}C_{n} = 1$. There is one way to choose everything.
• $^{n}C_{1} = n$. Choose any single one.
• $^{n}C_{2} = \dfrac{n(n - 1)}{2}$. This counts the pairs, or the handshakes in a group of $n$.

In the simulation, each bar of row $n$ is one value of $^{n}C_{k}$. Move $r$ and compare the selections with the arrangements.

Set $r = 1$. Then $r! = 1$ and the selections equal the arrangements. Set $r = 0$: there is exactly one selection, the empty one.

A worked example

Meghna's exam paper has $12$ questions. She must answer any $8$. In how many ways can she choose them?

Step 1. Order? She answers the same questions whatever order she picks them in. So this is a selection.

Step 2. The formula. $^{12}C_{8} = \dfrac{12!}{8!\,4!}$.

Step 3. Cancel. Keep the smaller factorial below: $\dfrac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = 495$.

Answer: $495$ ways. Choosing $8$ to answer is the same as choosing $4$ to leave out, so $^{12}C_{8} = {}^{12}C_{4}$.

Practise with new numbers

Try it in Python

The itertools module lists the selections and the arrangements. The math module has comb(n, r) for $^{n}C_{r}$.

Common mistakes

• Using $^{n}P_{r}$ for a selection. A committee, a team or a hand of cards has no order. Divide by $r!$.
• Using $^{n}C_{r}$ for an arrangement. Prizes of different value, posts such as captain and vice captain, or a code, all have order.
• Working out huge factorials. Cancel $(n - r)!$ first, and multiply only $r$ factors on top.
• Forgetting $^{n}C_{0} = 1$. Choosing nothing is one choice, not zero.

Remember these

• A combination is a selection; order does not matter.
• $^{n}C_{r} = \dfrac{n!}{r!\,(n - r)!}$, and $^{n}P_{r} = {}^{n}C_{r} \times r!$.
• $^{n}C_{r} = \dfrac{n(n - 1)\cdots(n - r + 1)}{r!}$, with $r$ factors on top.
• $^{n}C_{0} = {}^{n}C_{n} = 1$, $^{n}C_{1} = n$ and $^{n}C_{2} = \dfrac{n(n - 1)}{2}$.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Is choosing $5$ students to clean the lab a permutation or a combination?

2. Work out $^{9}C_{2}$ and $^{9}C_{7}$.

3. Ten guests at a party each shake hands with every other guest once. How many handshakes are there?

4. $^{n}P_{3} = 990$ and $^{n}C_{3} = 165$. Check that these fit $^{n}P_{r} = {}^{n}C_{r} \times r!$.

5. Why is $^{n}C_{0} = 1$ and not $0$?