Maths › Further Pure 2 › Combinatorics
Combinatorics
Combinatorics counts arrangements and selections without listing them. The lesson covers the multiplication and addition principles, permutations and combinations, arrangements of repeated objects and arrangements under a restriction, and how to decide whether order matters. It goes on to the pigeonhole principle, partitions of a set, derangements, and selections restricted by a graph.
Builds on Probability and Venn diagrams and The binomial expansion.
IN THIS TOPIC
- Apply the multiplicative principle, and the addition and subtraction principles.
- Choose between permutations and combinations by asking whether order matters.
- Count subsets, and count by complement when the direct count is awkward.
- Count arrangements in a line of objects that are not all distinct, and of only some of them.
- Handle a restriction by gluing objects into a block or by subtracting the arrangements that break it.
- Use the pigeonhole principle to settle that a repeat is there.
- Count the partitions of a set into a given number of parts, and total them to the Bell numbers.
- Count derangements by an ad hoc argument, and count the selections a graph of forbidden pairs allows.
- Turn a count of arrangements into a probability.
- Count arrangements round a circle by fixing one object, so that n distinct objects sit round a table in (n − 1)! ways.
COMMON MISCONCEPTION
Permutations and combinations are two names for the same calculation.
Permutations count arrangements, where order matters, and combinations count selections, where it does not. The two differ by exactly the r! orderings of each selection, so they are never interchangeable: eleven players from a squad of 21 make 352716 selections and 11! = 39916800 times as many ordered line-ups.
Multiply the choices
If a task splits into independent stages with m options and then n options, there are mn outcomes. That is the multiplicative principle. The addition principle covers alternatives that cannot happen together, and the subtraction principle counts by complement, taking the unwanted cases from the total, when that is easier than counting directly.
A set of n elements has 2n subsets, since each element is independently in or out. That is the multiplicative principle applied n times over.
WORKED EXAMPLE
Counting by complement
How many three-digit numbers contain the digit 3 at least once?
Counting directly means splitting into cases by how many 3s appear, which is fiddly. Count the complement instead.
There are 900 three-digit numbers from 100 to 999. Those with no 3 have 8 choices for the leading digit and 9 for each of the others, giving 8 × 9 × 9 = 648.
So the answer is 900 − 648 = 252. The same trick over 1 to 999 gives 999 − 728 = 271.
More objects than boxes
One counting argument settles that something is there without counting it. The pigeonhole principle says that if n objects go into k boxes and n is bigger than k, some box holds two or more. The reason is the addition principle read backwards: if no box held more than one object, the boxes would account for at most k objects between them, and there are n of them to account for.
The general form is the same argument with a higher floor. Put n objects into k boxes and some box holds at least n/k of them, rounded up, since k boxes each holding fewer than that would not reach n. Thirty students and twelve birth months put three students in one month, because 30/12 is 2.5 and a box holds a whole number.
The work in such a question is choosing the boxes, and a question rarely supplies them. A remainder makes a good box: any five integers give two with the same remainder on division by 4, so the difference of those two is a multiple of 4. What the principle does not do is say which box is the crowded one, or which pair. It settles that a repeat is there and leaves the finding of it to somebody else.
WORKED EXAMPLE
Six numbers from ten
Six different numbers are chosen from 1 to 10. Show that two of them add to 11.
Choose the boxes so that a box holds a pair adding to 11: 1 with 10, 2 with 9, 3 with 8, 4 with 7, and 5 with 6. Those five boxes hold the ten numbers between them.
Six numbers go into five boxes, so some box receives two of them, and the two sharing a box add to 11.
Five numbers would not force it, since 1, 2, 3, 4, 5 take one box each. Six is the smallest choice that does.
GUIDED PRACTICE
Boxes of your own choosing
Show that among any 13 people two share a birth month, and that among any 25 people three of them do.
Show the working
Twelve months are the boxes. Twelve boxes holding at most one person each account for 12 people, so 13 people put two in some month.
For three, twelve boxes holding at most two people each account for 24, so 25 people put three in some month.
The general form says it in one line: 25/12 is above 2, and rounding up gives 3.
Order, or not
Permutations count arrangements, where order matters, and nPr = n!/(n − r)!. Combinations count selections, where it does not, and nCr = n!/(r!(n − r)!). The two differ by the r! ways of ordering each selection, so they are never interchangeable: confuse them and the count is out by that factor.
Describe the drawing
Two panels side by side. On the left the number of ways of choosing eleven players from twenty-one, three hundred and fifty-two thousand seven hundred and sixteen. On the right the number of ordered line-ups, about one point four times ten to the thirteen. A coral arrow between them is labelled with the factor of eleven factorial.
WORKED EXAMPLE
One squad, two questions
From a squad of 21, how many ways are there to pick a team of 11 if positions do not matter, and if they do?
Positions ignored: 21C11 = 352716.
Positions mattering: 21P11 = 352716 × 11! ≈ 1.41 × 10¹³.
The ratio is 11! = 39916800, since every selection can be lined up in that many orders.
GUIDED PRACTICE
Subsets and a symmetry
A set has 8 elements. How many subsets does it have? Also explain why 10C3 equals 10C7.
Show the working
Each element is in or out independently, so there are 2⁸ = 256 subsets, counting the empty set and the whole set.
Choosing 3 to include is the same as choosing 7 to leave out, so the two counts must agree, and both are 120.
That symmetry is why Pascal's triangle reads the same in both directions.
Splitting a set into parts
A partition of a set is a splitting of it into parts that are non-empty, share no element, and between them contain everything. Neither the parts nor the elements inside them carry an order, so {1, 2} with {3} and {3} with {2, 1} are one partition written twice. Choosing a subset leaves the rest of the set behind; a partition has to account for it.
Take the set {a, b, c}. Its partitions number five: one part, with a, b and c together; three into two parts, {a} with {b, c}, {b} with {a, c}, and {c} with {a, b}; and one into three parts, each element alone. Listing is the right method while a set is this small, and stops being one almost at once.
Write S(n, k) for the number of partitions of n objects into k parts. A recurrence reaches these without any listing. Take one object out and ask what became of it. Either it sits in a part of its own, and the other n − 1 objects are split into k − 1 parts; or it joined a part of a partition of those n − 1 objects into k parts, and there were k parts for it to join. Adding the two gives S(n, k) = S(n − 1, k − 1) + kS(n − 1, k), started off by S(n, 1) = S(n, n) = 1.
Totalling a row gives the Bell number B(n), the number of partitions of a set of n elements with no condition on how many parts there are. The entries below came from the recurrence and those two starting values, nothing else. The S(n, k) are known as the Stirling numbers of the second kind, a name worth recognising though it is not standard in A-level texts.
| n | k = 1 | k = 2 | k = 3 | k = 4 | k = 5 | B(n) |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 2 | 1 | 1 | 0 | 0 | 0 | 2 |
| 3 | 1 | 3 | 1 | 0 | 0 | 5 |
| 4 | 1 | 7 | 6 | 1 | 0 | 15 |
| 5 | 1 | 15 | 25 | 10 | 1 | 52 |
WORKED EXAMPLE
Five objects into three parts
In how many ways can five objects be split into three parts? Take the count from the recurrence and check it by the sizes of the parts.
The recurrence gives S(5, 3) = S(4, 2) + 3S(4, 3) = 7 + 3 × 6 = 25.
Now the check. Three non-empty parts holding five objects have sizes 3, 1, 1 or sizes 2, 2, 1, and no other pattern totals five.
Sizes 3, 1, 1: choose the three that go together, 5C3 = 10, and the two singletons are then settled.
Sizes 2, 2, 1: choose the object left alone, 5 ways, then pair up the four that remain, which goes 3 ways because the partner of the first of them decides the rest. That is 5 × 3 = 15.
Then 10 + 15 = 25, agreeing with the recurrence. Picking the two pairs as an ordered choice would give 4C2 = 6 and count each split twice, which is where the 3 came from.
When the objects are not all different
Both formulae above assume the objects can be told apart, and repeated objects break that assumption. Label the repeats and there are n! orders; take the labels off and each genuine arrangement has been counted once for every way of shuffling the repeats among themselves. So divide by those shuffles. With p copies of one object, q of another and so on, the number of distinct arrangements in a line is n!/(p!q!…).
A restriction is handled in one of two ways. Objects that have to stand together are tied into a single block, which is arranged with everything else and then internally; objects that have to stay apart are counted by subtracting the together case from the total, which is the complement again. A leading zero is a restriction of the same kind, so a question about numbers rather than strings wants those arrangements taken out.
Both moves are worth seeing on the digits the example below uses.
Describe the drawing
Two panels. On the left the eight digits one, two, three, three, three, two, one, nought are written with the repeats labelled, giving eight factorial, or forty thousand three hundred and twenty, orders; a coral arrow labelled divide by two factorial times two factorial times three factorial takes the labels off and leaves one thousand six hundred and eighty distinct strings. On the right the two 2s are tied into a single boxed block, so seven objects are arranged instead, giving seven factorial over two factorial three factorial, which is four hundred and twenty. The block carries no internal factor because its two digits are the same.
WORKED EXAMPLE
Eight digits, two questions
How many eight-digit numbers can be made from the digits of 12333210, and in how many of those are the two 2s apart?
Strings first. Eight digits with two 1s, two 2s and three 3s give 8!/(2!2!3!) = 1680 arrangements.
Those beginning with 0 are not eight-digit numbers. Fixing the 0 leaves 7!/(2!2!3!) = 210 of them, so the count is 1680 − 210 = 1470.
For the 2s together, tie them into one block. That is seven objects with two 1s and three 3s, giving 7!/(2!3!) = 420, less the 6!/(2!3!) = 60 that start with 0, so 360. The block needs no internal factor here, because its two digits are identical.
So the 2s are apart in 1470 − 360 = 1110 of them. Counting the adjacent case and subtracting is far shorter than placing the 2s directly.
Only some of the group
Taking r objects from n when some of them are repeats has no single formula, because how much dividing to do depends on which objects were taken. Split into cases on the pattern of repeats, count each case with the rule above, and add. Each case contributes r! divided by the factorials of the repeats it contains, multiplied by the number of ways of choosing which objects play those parts.
WORKED EXAMPLE
Four digits from those eight
How many four-digit numbers can be made from the digits of 12333210?
The pool is one 0, two 1s, two 2s and three 3s. Split on the pattern of repeats among the four digits chosen.
All four different: they have to be 0, 1, 2 and 3, in 4! = 24 orders.
One repeated pair: 3 choices of which digit is doubled, then 3 ways to choose two more values from the three left, in 4!/2! = 12 orders, giving 3 × 3 × 12 = 108.
Two pairs: 3 ways to choose which two digits are doubled, in 4!/(2!2!) = 6 orders, giving 18. A triple: it has to be the 3s, with 3 choices for the odd digit, in 4!/3! = 4 orders, giving 12.
That is 162 strings. Those starting with 0 take three digits from 1, 1, 2, 2, 3, 3, 3: all different gives 3! = 6, one pair gives 3 × 2 × 3 = 18, and three 3s gives 1, so 25 in all.
The answer is 162 − 25 = 137. Check the cases cover the ground and do not overlap before adding them.
INDEPENDENT PRACTICE
Counting, then dividing
The six letters of STRAIT are arranged in a random order. Find the probability that the arrangement spells ARTIST, and the probability that the two Ts are next to each other.
Show the working
Six letters with T twice give 6!/2! = 360 distinct arrangements, each as likely as any other.
ARTIST uses those same six letters, so it is one of the 360 and the probability is 1/360.
For the Ts together, tie them into a block. That is five objects, now all distinct, in 5! = 120 orders, so the probability is 120/360 = 1/3.
A probability question of this kind is a counting question with one division at the end, and the division needs the distinct arrangements on both top and bottom.
Round a table
Seating round a circle is an arrangement with one difference: there is no first place. Rotate everybody one seat along and it is the same arrangement, since each person still has the same neighbours. So the n! orders of a line count each circular arrangement n times over, once for each rotation, and n people sit round a table in n!/n = (n − 1)! ways. The quicker way to see it is to fix one person's seat, which removes the rotation, and arrange the other n − 1 relative to them.
A restriction is handled as before. Two people who have to sit together are tied into a block, and the block and the n − 2 others go round the table in (n − 2)! ways, doubled for the two orders inside the block. A necklace or a bracelet can also be turned over, so a reflection is the same arrangement too and the count halves again.
GUIDED PRACTICE
Seven round a table
Seven people sit round a circular table. In how many ways can they be seated, and in how many of those are two particular people, P and Q, next to each other?
Show the working
Fix one seat and arrange the other six: 6! = 720.
Tie P and Q into a block. The block and the five others go round the table in 5! = 120 ways, and P and Q can sit either way round inside it, so 2 × 120 = 240.
As a check, P has two neighbours among the six other people, so the probability that Q is one of them is 2/6 = 1/3, and 240/720 = 1/3 agrees.
Nothing in its own place
A derangement is an arrangement in which no object sits in its own place, and Dn counts the derangements of n objects. Letters going into addressed envelopes with not one of them right is the standard illustration. These counts are wanted by ad hoc argument rather than from a quoted formula, so the argument is built from the small case in hand.
Small cases go by listing. A single object has nowhere else to go, so D₁ = 0. Two objects swap, so D₂ = 1. For three, write an arrangement as the order the three places receive them: 231 and 312 leave nothing where it started and the other four orders do not, so D₃ = 2.
Four is worth an argument instead. Object 1 goes to one of the other 3 places, say place 2. Then either object 2 goes to place 1, leaving objects 3 and 4 to derange between the two places left, in D₂ ways; or object 2 does not go to place 1, and then objects 2, 3 and 4 each have one place barred to them, which is a derangement of three, in D₃ ways. So D₄ = 3(D₃ + D₂) = 9, and the same split gives Dn = (n − 1)(Dn−1 + Dn−2).
Counting by complement reaches 9 as well, and it is the inclusion and exclusion argument of the Venn diagram work carried to four sets. Arrangements leaving at least one object in place number 4C1 × 3! − 4C2 × 2! + 4C3 × 1! − 4C4 × 0! = 24 − 12 + 4 − 1 = 15, so the derangements number 24 − 15 = 9. Either route is ad hoc in the sense the board means: nothing is quoted and the count is argued.
WORKED EXAMPLE
Five letters, five envelopes
Five letters are put at random into five addressed envelopes, one to each. Find the probability that no letter reaches its own envelope.
The count wanted is D₅, and the recurrence carries it up from what is already known: D₅ = 4(D₄ + D₃) = 4(9 + 2) = 44.
The 5! = 120 arrangements are equally likely, so the probability is 44/120 = 11/30, about 0.367.
That figure hardly moves with n. The ratios Dn/n! run 0.5, 0.333, 0.375, 0.367 and settle towards 1/e = 0.368, so fifty letters give much the same answer as five.
A graph of who may not be chosen together
A selection question can carry its restrictions as a picture. Draw a node for each candidate and join two nodes when that pair may not both be chosen, and the question becomes a count of the selections containing no joined pair. Reading the picture is half the work: a node with no edges is unrestricted, and the node of highest degree is the one to split the cases on.
Handle the edges inside one group first, then let each case say which members of the other group are barred. Counting by complement serves as well, as the total less the selections that contain a joined pair, but a selection containing two joined pairs comes off twice and has to be put back, which is inclusion and exclusion again.
WORKED EXAMPLE
Three men and two women, with a graph
Three men are to be chosen from A, B, C, D and two women from P, Q, R, S. The graph of who may not be chosen together carries three edges: A with B, B with P, and Q with R. How many choices are there?
Ignoring the graph there are 4C3 × 4C2 = 4 × 6 = 24 choices, so the answer sits below that.
Take the men first, since the one edge inside a group is theirs. Of the four sets of three men, A, B, C and A, B, D carry the edge A with B, so the men are A, C, D or B, C, D.
Case A, C, D: no chosen man is joined to a woman, so any of the 6 pairs of women serves apart from Q with R, leaving 5.
Case B, C, D: B bars P, so the women come from Q, R, S. Of those 3 pairs the pair Q with R goes, leaving 2.
The two cases neither overlap nor leave a gap, so the count is 5 + 2 = 7. Listing them checks it: A, C, D with any of PQ, PR, PS, QS, RS, and B, C, D with QS or RS.
INDEPENDENT PRACTICE
A committee of three
A committee of three is chosen from six people A, B, C, D, E, F. The pairs A with B, B with C, and D with E will not serve together. How many committees are there?
Show the working
Split on B, whose degree is 2. With B on the committee, A and C are out, and the other two come from D, E, F without taking both D and E, which allows DF and EF: 2 committees.
Without B, choose 3 from A, C, D, E, F, which is 5C3 = 10, less the 3 of those that contain both D and E, leaving 7.
So 2 + 7 = 9. By complement instead: 6C3 = 20, less 4 committees for each of the three barred pairs, plus 1 put back for A, B, C, which carries two of them. That is 20 − 12 + 1 = 9.
ASSESSMENT FOCUS
- Ask whether order matters before writing any formula; that one decision fixes the whole answer.
- Reach for the complement whenever 'at least one' appears, because the direct count almost always splits into cases.
- With repeated objects, write down the repeat counts before the factorials, so that the denominator is built from a recorded list rather than from memory.
- For objects that must stay apart, count the arrangements with them together and subtract, since placing them apart directly splits into more cases.
- When only some of a group are taken and the group has repeats, list the cases by repeat pattern and check they neither overlap nor leave a gap.
- For a pigeonhole argument, name the boxes and count them before anything else; the choice of boxes is the argument, and the arithmetic that follows is one line.
- For partitions, split on the sizes of the parts and divide when two parts have the same size, since swapping them gives back the same partition.
- Given a graph of pairs that may not be chosen together, split the cases on the group whose members carry the edges, and say that the cases neither overlap nor leave a gap.
CHECK YOURSELF
In how many ways can 4 books be chosen from 9, and in how many ways can 4 be arranged in a row from 9?
Show a hint
One question ignores order and one does not.
Show the answer
Chosen: 9C4 = 126. Arranged: 9P4 = 3024, which is 126 × 4! = 126 × 24.
Multiply choices made in sequence, add alternatives, and subtract from the total when 'at least one' appears; more objects than boxes puts two of them in one box.
Permutations order the selection and combinations do not, so they differ by exactly r factorial.
Repeated objects divide the count, n! over the factorials of the repeats; partitions into k parts follow S(n, k) = S(n − 1, k − 1) + kS(n − 1, k).
Together means a block, apart means total minus together, and repeats taken some at a time or a graph of forbidden pairs mean cases; a derangement leaves nothing in its own place.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the combinatorics questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Apply the multiplicative principle, and the addition and subtraction principles.
- Choose between permutations and combinations by asking whether order matters.
- Count subsets, and count by complement when the direct count is awkward.
- Count arrangements in a line of objects that are not all distinct, and of only some of them.
- Handle a restriction by gluing objects into a block or by subtracting the arrangements that break it.
- Use the pigeonhole principle to settle that a repeat is there.
- Count the partitions of a set into a given number of parts, and total them to the Bell numbers.
- Count derangements by an ad hoc argument, and count the selections a graph of forbidden pairs allows.
- Turn a count of arrangements into a probability.
- Count arrangements round a circle by fixing one object, so that n distinct objects sit round a table in (n − 1)! ways.
Open the full revision checklist to see every objective in the course in one place.