Combinations: Counting Selections

Tell selections from arrangements, count selections with nCr, handle must-include, at-least and group conditions, and solve equations with nCr.

In the exam for IGCSE Additional Maths 0606 · 13 real past-paper questions below

اقرأ هذا الدرس مشروحاً بالعربي ←

Choosing, not arranging

You pick 3 friends from 5 to come to the cinema. Picking Ali, Badr and Celine is the same group as picking Celine, Ali and Badr. The order does not matter.

Permutation: order matters

Arranging in a line, codes, passwords, numbers, 1st, 2nd and 3rd prizes.

Combination: order does not matter

Choosing a team, a committee, a group, a hand of cards.

Count the groups using what you already know. Arranging 3 of the 5 friends in order gives $^{5} P_{3} = 60$ . But each group of 3 appears in that list $3! = 6$ times, once for each order.

Worked example

1
How many different groups of 3 can be chosen from 5 friends?
2
$^{5} P_{3} = 5 \times 4 \times 3 = 60$ — Ordered lists of 3 friends.
3
$3! = 6$ — Each group appears in 6 different orders.
4
$60 \div 6 = 10$ — So there are 10 different groups.

Rule

Ask: if I swap two of the chosen items, is it a different answer? Yes: permutation. No: combination.

Key idea

A lottery where you choose 6 numbers from 49 has 13 983 816 possible tickets. The order you pick the numbers in does not matter, so it is a combination.

Key idea

A combination is a permutation with the order removed. Divide by the number of ways to order the chosen items.

The nCr formula

Dividing by $r!$ every time gives the formula for combinations. The number of ways to choose r items from n is written $^{n} C_{r}$ or $(r n)$ .

Formula

^{n} C_{r} = \frac{n !}{r ! ( n - r )!}

$n$ — how many different items there are to choose from.
$r$ — how many you choose.
$r!$ — removes the orders of the chosen items, because order does not matter.

Rule

0606 and 4037 print this formula on the paper, inside the Binomial Theorem, written as $(r n)$ . Your calculator has an nCr key for Paper 2.

Worked example

1
A committee of 4 is chosen from 10 people. How many committees are possible?
2
$^{10} C_{4} = \frac{10 !}{4 ! 6 !}$ — n = 10, r = 4, so n − r = 6.
3
$= \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1}$ — The 6! cancels. Without a calculator, cancel before you multiply.
4
$= 210$ — 5040 ÷ 24 = 210.

Two facts save time. Choosing which r to take is the same as choosing which $n - r$ to leave behind.

Formula

^{n} C_{r} =^{n} C_{n - r}

$n - r$ — the number left out. For example, $^{10} C_{8} =^{10} C_{2} = 45$ .

Formula

^{n} C_{0} =^{n} C_{n} = 1

$0 or n$ — there is one way to choose nothing, and one way to choose everything.

Common mistake

Using $^{n} P_{r}$ for a team or committee. A team has no order, so use $^{n} C_{r}$ .

Key idea

$^{n} C_{r}$ counts groups. Use it whenever swapping two chosen items gives the same answer.

Must include, must not include

Conditions change how many you still need to choose, and from how many.

Steps

1
1. Must include someone: put them in. Choose the rest from the others.
2. Must not include someone: take them out of the pool.
3. Choose from two groups: choose from each group, then multiply.

Worked example

1
A team of 5 is chosen from 12 players. The captain must be in the team, and one injured player cannot be chosen. How many teams are possible?
2
$5 - 1 = 4 places left$ — The captain fills one place.
3
$12 - 2 = 10 players left$ — Remove the captain and the injured player from the pool.
4
$^{10} C_{4} = 210$ — Choose the other 4 from the 10.

Worked example

1
Choose 2 boys from 6 and 3 girls from 5. How many groups are possible?
2
$^{6} C_{2} = 15$ — Ways to choose the boys.
3
$^{5} C_{3} = 10$ — Ways to choose the girls.
4
$15 \times 10 = 150$ — Boys AND girls, so multiply.

Some people must stay together: both in, or both out. Count each case, then add.

Worked example

1
A team of 6 is chosen from 14 people. Two twins must be chosen together or not at all. How many teams are possible?
2
$Both in:^{12} C_{4} = 495$ — The twins take 2 places. Choose 4 more from the other 12.
3
$Both out:^{12} C_{6} = 924$ — Choose all 6 from the other 12.
4
$495 + 924 = 1419$ — One case OR the other, so add.

Memory trick

AND means multiply. OR means add.

Key idea

Change the numbers first: places left to fill, and people left to choose from. Then use $^{n} C_{r}$ .

At least: cases or the opposite

“At least 2 women” means 2 women, or 3, or 4, and so on. List every case, count each one, then add.

Worked example

1
A group of 5 is chosen from 7 men and 4 women. How many groups have at least 2 women?
2
$2 women, 3 men:^{4} C_{2} \times^{7} C_{3}$ $= 6 \times 35 = 210$ — Choose the women AND the men, so multiply.
3
$3 women, 2 men:^{4} C_{3} \times^{7} C_{2}$ $= 4 \times 21 = 84$ — Same idea for the next case.
4
$4 women, 1 man:^{4} C_{4} \times^{7} C_{1}$ $= 1 \times 7 = 7$ — The last case: every woman is chosen.
5
$210 + 84 + 7 = 301$ — Add the cases.

When there are many cases, count the opposite instead. The opposite of “at least one woman” is “no women at all”.

Formula

at least one = total - none

$total$ — all selections, with no condition.
$none$ — the selections that break the rule.

Worked example

1
Same group of 7 men and 4 women. How many groups of 5 have at least one woman?
2
$^{11} C_{5} = 462$ — All groups of 5 from 11 people.
3
$^{7} C_{5} = 21$ — Groups with no women: all 5 are men.
4
$462 - 21 = 441$ — Total minus none.

The mark scheme gives a mark for each correct case product, or for total minus the opposite. Write each case clearly.

Common mistake

Choosing 1 woman first and then any 4 others: $4 \times^{10} C_{4} = 840$ . This counts the same group many times. A group with two women is counted once for each of them.

Common mistake

Missing a case. Check that the numbers in each case add up to the group size, and that you have every case up to the limit.

Key idea

At least: add the cases. At least one: total minus none.

Equations with nCr

Some questions use $^{n} C_{r}$ in algebra, often on the non-calculator paper. Write each one with factorials, then cancel.

Rule

Two cancelling facts: $(n + 1)! = (n + 1) \times n!$ , and $\frac{n !}{( n - 2 )!} = n (n - 1)$ .

Worked example

1
Find n, given that $^{n + 1} C_{3} = 4 \times^{n} C_{2}$ .
2
$\frac{( n + 1 )!}{3 ! ( n - 2 )!} = 4 \times \frac{n !}{2 ! ( n - 2 )!}$ — Write both sides with the formula.
3
$\frac{( n + 1 ) n ( n - 1 )}{6} = \frac{4 n ( n - 1 )}{2}$ — Cancel (n − 2)! on each side.
4
$\frac{n + 1}{6} = 2$ — Divide both sides by n(n − 1), and 4 ÷ 2 = 2.
5
$n = 11$ — n + 1 = 12.

A “show that” question asks you to prove a result for every n. Work on the left side only until it becomes the right side.

Worked example

1
Show that $^{n + 1} C_{2} -^{n} C_{2} = n$ .
2
$^{n + 1} C_{2} = \frac{( n + 1 ) n}{2}$ — Cancel (n − 1)! from the factorials.
3
$^{n} C_{2} = \frac{n ( n - 1 )}{2}$ — Cancel (n − 2)!.
4
$\frac{n ^{2} + n - n ^{2} + n}{2}$ — Subtract. Expand both tops.
5
$= \frac{2 n}{2} = n$ — As required.

The marks go for the factorial form, then the simplified algebra, then the answer. Show the factorial line before you cancel.

Common mistake

Writing $\frac{n !}{( n - 2 )!} = \frac{n}{n - 2}$ . Factorials do not cancel like that. Write out the top until you reach $(n - 2)!$ : $\frac{n ( n - 1 ) ( n - 2 )!}{( n - 2 )!} = n (n - 1)$ .

Key idea

Write each $^{n} C_{r}$ with factorials, cancel the common part, and solve the ordinary equation that is left.

Which method? Read the question

The words decide whether you arrange or choose, and how.

You see	You do
“Arrange”, “in a line”, a code or a number	Permutation: $^{n} P_{r}$
“Choose”, “select”, a team or a committee	Combination: $^{n} C_{r}$
“Must include” someone	Put them in, choose the rest
“Must not include” someone	Remove them from the pool
From two groups	Choose from each, then multiply
“Together or not at all”	Both-in case + both-out case
“At least two”	List the cases, then add
“At least one”	Total minus none
An equation with $^{n} C_{r}$	Factorials, cancel, solve

Common mistake

Mixing the two: using $^{n} P_{r}$ for a selection, or $^{n} C_{r}$ for an arrangement. Ask the swap question every time.

Key idea

If swapping two chosen items makes no difference, it is a combination. Then AND multiplies and OR adds.

Practise combinations: counting selections now

Interactive visual aids, then real past-paper questions marked on your working like the exam. Free to start.

Practise free on Lemmara

Real past-paper questions on combinations: counting selections

Each with a full worked solution.

All 13 questions on this topic →

Lemmara is an independent study tool, not affiliated with or endorsed by Cambridge International Education or Pearson Edexcel. The lessons and worked examples are Lemmara’s own.