A permutation counts arrangements, where first, second and third are different outcomes. A combination counts selections, where only WHO is chosen matters. Dividing out the \(r!\) orders of each selection turns \({}^{n}P_{r}\) into \({}^{n}C_{r}\), and that one number handles committees, teams and hands of cards.
If the order of the chosen items matters, count permutations, \({}^{n}P_{r} = \dfrac{n!}{(n - r)!}\); if it does not, count combinations, \({}^{n}C_{r} = \dbinom{n}{r} = \dfrac{n!}{r!\,(n - r)!} = \dfrac{{}^{n}P_{r}}{r!}\). Choosing \(r\) to take is the same as choosing \(n - r\) to leave, so \({}^{n}C_{r} = {}^{n}C_{n-r}\). For selections from separate groups, multiply the counts for each group; for 'at least one', use the total minus the selections with none.
Fig. 1: Pascal's triangle, rows n = 0 to 6. The entry in position r of row n (counting from r = 0) is nCr. Each entry is the sum of the two above it, as 5C1 + 5C2 = 6C2 = 15, and each row reads the same from both ends, as 6C2 = 6C4. You will meet these rows again in the binomial expansion (Topic 12)
Section 01
Arrange or select?
In the last lesson you counted arrangements: \({}^{n}P_{r}\) ways to fill \(r\) ordered places from \(n\) different items. Many questions only ask which items are chosen. Picking Ana, Ben and Chen for a team is the same team as picking Chen, Ana and Ben, so the \(3! = 6\) orders of one group must be counted once. In general every selection of \(r\) items can be ordered in \(r!\) ways, which gives the link \({}^{n}P_{r} = r! \times {}^{n}C_{r}\).
Order matters: permutation
Order does not matter: combination
arrange, line up, in a row, a code or a number
choose, select, a committee, a team, a group
first, second and third prizes; different named roles
a hand of cards, a sample, books to take on holiday
\({}^{n}P_{r} = \dfrac{n!}{(n - r)!}\)
\({}^{n}C_{r} = \dfrac{n!}{r!\,(n - r)!}\)
Worked example Same club, two questions
A club has 7 members. In how many ways can (a) 3 members be chosen to go to a conference (b) a chair, a secretary and a treasurer be chosen?
(b) The three roles are different, so order matters: \({}^{7}P_{3} = 7 \times 6 \times 5 = 210\).
(a) Only the group of three matters. Each group of three can be given the three roles in \(3! = 6\) ways, so every group was counted 6 times in (b).
\({}^{7}C_{3} = \dfrac{210}{6} = 35\).
Answer: (a) \(35\) (b) \(210\)
Worked example Decide, then count
Decide whether each is a permutation or a combination, then evaluate it. (a) A 4-letter arrangement using 4 different letters of the word PLANET. (b) A pizza with 4 different toppings chosen from 6.
(a) PLAN and NALP are different arrangements, so order matters: \({}^{6}P_{4} = 6 \times 5 \times 4 \times 3 = 360\).
(b) Ham, olive, pepper and onion is the same pizza in any order, so this is a combination.
From 8 runners, in how many ways can a relay squad of 4 be selected (the running order is decided later)?
Only the squad matters, so \({}^{8}C_{4} = \dfrac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70\).
Examiner trap
A committee is a combination ONLY if its members are all equal. 'A committee with a captain and a vice-captain' gives two members named roles, so swapping them is a different outcome. Read for named positions, prizes or places in a line before you choose \(C\) or \(P\).
Section 02
The formula and its shortcuts.
Divide the permutation formula by the \(r!\) orders of each selection:
Ends: \({}^{n}C_{0} = {}^{n}C_{n} = 1\) (one way to choose nothing, one way to choose everything) and \({}^{n}C_{1} = n\).
Symmetry: \({}^{n}C_{r} = {}^{n}C_{n-r}\), because choosing \(r\) to take is the same as choosing \(n - r\) to leave behind. Use the smaller of \(r\) and \(n - r\).
Choose two: \({}^{n}C_{2} = \dfrac{n(n - 1)}{2}\), the form that turns up in equations.
Check with Pascal's triangle (Fig. 1): row \(n\) lists \({}^{n}C_{0}, {}^{n}C_{1}, \dots, {}^{n}C_{n}\), and each entry is the sum of the two above it.
Worked example Cancel before you multiply
Evaluate \({}^{10}C_{3}\) without a calculator, and hence write down \({}^{10}C_{7}\).
\({}^{10}C_{3} = \dfrac{10!}{3!\,7!}\). Cancel the \(7!\) into the \(10!\): \(\dfrac{10 \times 9 \times 8}{3 \times 2 \times 1}\).
\(\dfrac{720}{6} = 120\).
Choosing 7 of the 10 to take is the same as choosing the 3 to leave, so \({}^{10}C_{7} = {}^{10}C_{3}\).
\(\dfrac{n!}{r!}\) is NOT \({}^{n}C_{r}\): you must divide by \((n - r)!\) as well. \(\dfrac{10!}{3!}\) is over half a million, while \({}^{10}C_{3} = 120\). And when you solve for \(n\), always reject the negative root, since you cannot choose from \(-9\) people.
Stage 1 · Learn
Check your understanding
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
Which of these is counted by a combination?
Quick check+10 XP
Evaluate \({}^{7}C_{3}\).
Quick check+10 XP
Which of these is equal to \({}^{12}C_{5}\)?
Quick check+10 XP
In how many ways can 2 men and 2 women be chosen from 6 men and 4 women?
Section 03
Committees, teams and at least one.
Selection problems in the exam are built from a few moves. When the items come from separate groups, choose from each group and MULTIPLY, because every choice from one group can go with every choice from the other. When a question says 'at least one', count the opposite (none at all) and subtract it from the total, or add up the separate cases. When a person must be included, put them in and choose the rest from the others; when they must be left out, remove them first.
From groups: \(r\) from the men and \(s\) from the women gives \({}^{m}C_{r} \times {}^{w}C_{s}\).
At least one: total \(-\) none, or the sum of the cases 'exactly 1', 'exactly 2', and so on.
Must be included: choose the other \(r - 1\) from the remaining \(n - 1\): \({}^{n-1}C_{r-1}\).
Must not be included: choose all \(r\) from the remaining \(n - 1\): \({}^{n-1}C_{r}\).
Two people not both: total \(-\) (selections with both): \({}^{n}C_{r} - {}^{n-2}C_{r-2}\).
Worked example Men and women on a committee
A committee of 5 is chosen from 6 men and 4 women. How many committees contain (a) exactly 3 men (b) at least one woman?
(a) Exactly 3 men means 3 men AND 2 women: \({}^{6}C_{3} \times {}^{4}C_{2} = 20 \times 6 = 120\).
(b) Total committees from 10 people: \({}^{10}C_{5} = 252\). Committees with no woman are all men: \({}^{6}C_{5} = 6\).
A group of 4 is chosen from 5 men and 3 women. How many groups contain at least one woman?
Total \({}^{8}C_{4} = 70\); all men \({}^{5}C_{4} = 5\); so \(70 - 5 = 65\).
Examiner trap
Do not count 'at least one woman' as 'pick one woman, then any 4 of the other 9': \(4 \times {}^{9}C_{4} = 504\) is far more than the 252 committees that exist, because a committee with two women is counted once for each of them. Use total minus none, or separate cases. And between groups MULTIPLY: \({}^{6}C_{3} + {}^{4}C_{2}\) is wrong.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to IGCSE Additional Mathematics Paper 1 and Paper 2 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
Given that \({}^{n}C_{2} = 66\), find the value of \(n\).
Exam style+20 XP
A team of 4 is chosen from 5 boys and 7 girls. How many teams contain at least one boy?
Exam style+20 XP
A squad of 6 is chosen from 10 players. Two of the players, Ravi and Sam, refuse to be in the squad together. How many squads are possible?
Exam style+20 XP
A committee of 5 is chosen from 6 men and 5 women. How many committees contain at least 3 women?
Skill unlocked
Selections counted, order ignored.
This skill is now recorded on your profile. Keep the chain going.