Permutations and Combinations

Syllabus coverage

Understand the terms permutation and combination, and solve simple problems involving selections
Solve problems about arrangements of objects in a line, including those involving repetition, for example the number of ways of arranging the letters of a word in which some letters are repeated
Solve problems about arrangements of objects in a line including those involving restriction, for example the number of ways several people can stand in a line if two particular people must, or must not, stand next to each other
Solve problems in which the objects are arranged in two or more rows

Part of the AS & A Level Maths syllabus 9709.

Counting with restrictions. Left: two people who must sit together become one block, so six objects become five and the block is arranged internally in 2 ways, giving

5! \times 2 = 240

. Right: a pair in separate rows is counted row by row,

2 \times 12 = 24

pairs of seats, then

6! = 720

ways for the rest.

Counting in stages: the multiplication principle

Every question in this topic is a counting problem, and almost every one is solved by breaking it into stages. If a first choice can be made in $m$ ways and, for each of those, a second choice can be made in $n$ ways, then the two choices together can be made in $m \times n$ ways. Three stages multiply three numbers, and so on.

Two habits make the principle reliable. Decide what the stages are before you write any numbers down, and check that the stages cover each outcome exactly once. If two different sequences of choices can lead to the same outcome, you are counting that outcome twice and the answer is too big.

A cafe offers 4 starters and 6 main courses, so a two-course meal can be chosen in $4 \times 6 = 24$ ways. Add 3 desserts and the three-course meal can be chosen in $4 \times 6 \times 3 = 72$ ways. Multiplying is right when the choices are made one after another; adding is right when the cases are alternatives, so 'a starter or a main course' would be $4 + 6 = 10$ .

Stages made one after another: multiply, $4 \times 6 \times 3 = 72$
Alternative cases that cannot both happen: add, $4 + 6 = 10$
Check that no outcome has been counted twice: if it has, divide it out or change the stages

Multiply for stages, add for alternatives. Most wrong answers in this topic come from multiplying two things that should have been added, or from adding two things that should have been multiplied.

Permutations: order matters

A permutation is an arrangement in which order matters: 1234 and 4321 are different permutations of the same four digits. The number of ways of arranging $n$ different objects in a line is $n!$ (read as 'n factorial'), where $n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1$ So 5 different books can be arranged on a shelf in $5! = 120$ ways, and 8 people can stand in a line in $8! = 40320$ ways.

If only $r$ of the $n$ objects are used, the number of arrangements is the product of the first $r$ descending numbers from $n$ , written $^{n} P_{r} = \frac{n!}{(n - r)!} = n (n - 1) (n - 2) \dots (n - r + 1)$ For example $^{10} P_{3} = 10 \times 9 \times 8 = 720$ : ten choices for the first place, nine for the second and eight for the third.

Two special cases are worth knowing by sight. When $r = n$ the formula gives $^{n} P_{n} = n!$ , which is the arrangement of everything. And $0! = 1$ by definition, which is what makes the formula work when nothing is chosen - there is exactly one way to choose nothing.

A permutation question often hides its stages. 'How many different three-letter codes can be made from the letters A to J, with no letter used twice?' is $^{10} P_{3} = 720$ , because the code is a line of three positions and order matters: ABC is not CBA.

The factorials get large quickly:

10! = 3628800

. Write the product in factorised form and cancel before multiplying out, or the arithmetic will cost you more than the question is worth.

Combinations: order does not matter

A combination is a selection in which order does not matter: choosing Ali, Bea and Chen for a committee is the same committee as choosing Chen, Ali and Bea. The number of ways of choosing $r$ objects from $n$ is $^{n} C_{r} = (\binom{n}{r}) = \frac{n!}{r! (n - r)!}$ and it is read as 'n choose r'. The $r!$ on the bottom is exactly the correction for the over-counting: every selection of $r$ objects can be written down in $r!$ different orders, and all of those orders are the same selection.

That argument also gives the link between the two formulas: $^{n} P_{r} =^{n} C_{r} \times r!$ Choose the $r$ objects first, then arrange them. Use it in both directions: $^{8} P_{3} =^{8} C_{3} \times 3! = 56 \times 6 = 336$ , and a question that says 'choose a team and then arrange them' is asking for the two stages multiplied together.

The formula is symmetric: $^{n} C_{r} =^{n} C_{n - r}$ , because choosing which $r$ objects to take is the same as choosing which $n - r$ to leave. That saves arithmetic: $^{12} C_{10}$ is $^{12} C_{2} = 66$ , which is far less work than the definition.

Selection	Value	What it counts
$^{5} C_{2}$	10	choosing 2 books from a shelf of 5
$^{6} C_{3}$	20	choosing a committee of 3 from 6 people
$^{8} C_{3}$	56	choosing 3 players from a squad of 8
$^{10} C_{3}$	120	choosing 3 questions from 10
$^{12} C_{4}$	495	choosing 4 cards from 12
$^{n} C_{0} =^{n} C_{n}$	1	one way to choose none of them, and one way to choose all of them

A permutation answer divided by the factorial of the number chosen gives the combination answer, and a combination answer multiplied by it gives the permutation answer. If your two answers differ by a factor of 6, you probably chose 3 objects and used the wrong one.

Which one does the question want?

The first mark in most questions is for the decision, so make the decision deliberately. Ask whether swapping two of the chosen items would give a different outcome. If it would, order matters and you need a permutation; if it would not, you need a combination.

'Arrange', 'in a line', 'seated', 'in order', 'first, second and third' all point to order mattering. 'Choose', 'select', 'committee', 'team' and 'group' all point to order not mattering. The words 'at least', 'at most' and 'exactly' tell you to split the problem into cases; 'must be together' tells you to use a block; 'must not be together' tells you to subtract from the total.

Once the type is settled, look for the structure: are there repeated objects, is there a restriction, are the objects in more than one row, and is there a choice followed by an arrangement? Nearly every 9709 question is one of those patterns or a combination of two of them.

The words in the question	What to do
arrange, in a line, seated, in order	order matters: use $^{n} P_{r}$ or $n!$
choose, select, committee, team, group	order does not matter: use $^{n} C_{r}$
with repetition, repeated letters, identical objects	divide $n!$ by the factorial of each repeat
must be together, next to each other, adjacent	form one block, then multiply by the arrangements inside it
must not be together, apart, separated	subtract the 'together' arrangements from the total
at least, at most, exactly, no more than	split into mutually exclusive cases and add them
in two rows, front row, back row	treat each row as a line of positions, then multiply

Order matters if a swapped pair is a different answer. A password of 3 digits is a permutation; a hand of 3 cards is a combination.

Arrangements when some objects are identical

When some of the objects are identical, dividing by their factorials removes the arrangements that only swap identical items. For $n$ objects in which one item appears $a$ times, another $b$ times and so on, the number of distinct arrangements is $\frac{n!}{a! b! \dots}$

The letters of BALLOON give 7 letters with L twice and O twice, so the number of arrangements is $\frac{7!}{2! 2!} = \frac{5040}{4} = 1260$ . Writing $7! = 5040$ on its own would count each word four times, because the two Ls can be swapped with each other and the two Os can be swapped with each other, giving $2 \times 2 = 4$ identical versions of every word.

The same formula counts arrangements of identical objects that are not letters: 3 red counters and 2 blue counters can be placed in a row in $\frac{5!}{3! 2!} = 10$ ways, because only the pattern of colours matters, not which red counter is which.

Only divide by the factorial of an item that really is repeated. A letter appearing once contributes $1! = 1$ and can be ignored, so the answer stays the same whether you write it or not.

BALLOON: 7 letters, L twice and O twice, so $\frac{7!}{2! 2!} = 1260$
SUCCESS: 7 letters, S three times and C twice, so $\frac{7!}{3! 2!} = 420$
3 red and 2 blue counters in a row: $\frac{5!}{3! 2!} = 10$
If all the objects are different, the formula gives $\frac{n!}{1!} = n!$ , as it should

Check the denominator by counting the letters. If a word has 9 letters and you have divided by 2! twice, you have only accounted for 4 of them, and a third repeated letter is missing.

Restriction: objects that must stay together

If two particular objects must be next to each other, glue them into a single block. The block counts as one object, so $n$ objects become $n - 1$ and those are arranged in $(n - 1)!$ ways. The two objects inside the block can then be arranged in $2! = 2$ ways, so the total is $(n - 1)! \times 2$ .

With 7 people in a line and two particular people who must stand next to each other, the block gives 6 objects, so there are $6! = 720$ ways to arrange the six objects and $720 \times 2 = 1440$ ways in all.

If three particular objects must stay together, the block is arranged internally in $3! = 6$ ways, so the count is $(n - 2)! \times 3!$ : for 8 objects with three that must stay together, that is $6! \times 6 = 4320$ .

If two separate pairs must each stay together, make two blocks and multiply by 2! for each pair: with 8 objects in two pairs, the count is $(8 - 2)! \times 2! \times 2! = 720 \times 4 = 2880$ .

7 objects, 2 together: $6! \times 2 = 1440$
8 objects, 3 together: $6! \times 3! = 4320$
8 objects, two pairs each together: $6! \times 2! \times 2! = 2880$

The block is one object for the purpose of arranging, and it is not one object when you arrange what is inside it. Both steps are needed, and the second one is the step students forget.

Restriction: objects that must not be together

Count the arrangements that break the restriction instead: the answer is the total minus the arrangements with the two particular objects together. With $n$ objects in a line the total is $n!$ , and the number with two particular objects together is $(n - 1)! \times 2$ , so the number with them apart is $n! - (n - 1)! \times 2$

With 7 people, that is $7! - 6! \times 2 = 5040 - 1440 = 3600$ . Notice that the together count is exactly the answer to the previous question, so the two patterns are two halves of the same piece of work.

There is a second method that works when three or more objects must all be apart: place the other objects first, count the gaps between them, and choose positions for the restricted objects in those gaps. With 7 people and two who must not be adjacent, the 5 other people can be arranged in $5! = 120$ ways and there are 6 gaps to place the pair in, in order, so $120 \times 6 \times 5 = 3600$ - the same answer, which is a good check.

Use the complement when the restricted objects are few, because subtracting one case is quicker than listing many. Use the gap method when you are told that none of three or more objects may be adjacent, because the complement then has several overlapping cases to untangle.

Total arrangements of 7 people: $7! = 5040$
Arrangements with two particular people together: $6! \times 2 = 1440$
Arrangements with them apart: $5040 - 1440 = 3600$
Gap check: $5! \times 6 \times 5 = 3600$

Read the question twice. 'Must stand next to each other' and 'must not stand next to each other' differ by one word and the answers are 1440 and 3600.

People in two or more rows

A row of seats is a line of positions, so the counting is the same as for a single line; the extra work is in deciding how the people are shared between the rows. If the number of people in each row is fixed, choose who goes in each row first and then arrange each row.

Six students seated in two rows of three can be arranged in $6! = 720$ ways. The long way round shows why: choose the three for the front row in $^{6} C_{3} = 20$ ways, arrange the front row in $3! = 6$ ways and the back row in $3! = 6$ ways, and $20 \times 6 \times 6 = 720$ . The short way is to see that the six seats are six distinct positions, so $6!$ covers it.

With a restriction the seat positions matter, and it helps to count the ordered pairs of seats that satisfy the condition. Six students in two rows of three, with two particular students who must sit in the same row: there are $3 \times 2 = 6$ ordered pairs of seats in one row, so $2 \times 6 = 12$ ordered pairs in the same row altogether. The remaining 4 students fill the remaining 4 seats in $4! = 24$ ways, giving $12 \times 24 = 288$ .

The same reasoning handles a front row of 4 and a back row of 3: the seats are 7 distinct positions, so with no restriction there are $7! = 5040$ arrangements, and a restriction on particular seats is counted by the number of ordered seat pairs that satisfy it.

6 students in two rows of 3, no restriction: $6! = 720$
6 students in two rows of 3, two particular students in the same row: $12 \times 4! = 288$
8 students in two rows of 4, no restriction: $8! = 40320$
Two rows of 4, two particular students in the same row: $24 \times 6! = 17280$

Circular arrangements are not in this syllabus. Cambridge states that questions about objects arranged in a circle will not be included, so if a textbook asks one, you can leave it.

Selections with conditions: at least, at most, exactly

'At least' and 'at most' mean cases, and the cases are added because they cannot happen together. 'Exactly' means one case. 'Not both' is usually the total minus the case you have to exclude. Write the cases down before you calculate, and the question almost answers itself.

A committee of 3 is to be chosen from 4 men and 3 women, with at least one woman. The long way is three cases: 1 woman and 2 men is $^{3} C_{1} \times^{4} C_{2} = 3 \times 6 = 18$ , 2 women and 1 man is $^{3} C_{2} \times^{4} C_{1} = 3 \times 4 = 12$ , and 3 women is $^{3} C_{3} = 1$ . That gives $18 + 12 + 1 = 31$ . The short way is the complement: all the committees are $^{7} C_{3} = 35$ , the all-men committees are $^{4} C_{3} = 4$ , and $35 - 4 = 31$ .

Choose from each group separately and multiply, because the two choices are independent stages. From 5 women and 4 men, a committee of 3 with exactly 2 women is $^{5} C_{2} \times^{4} C_{1} = 10 \times 4 = 40$ . The multiplication is the multiplication principle again: 10 ways to pick the women, and for each of them 4 ways to pick the man.

When the two groups are described as 'the rest', do not forget that the leftover people are still available. A committee of 4 chosen from 6 people with two particular people who must not both be included is $^{6} C_{4} -^{4} C_{2} = 15 - 6 = 9$ : take the case where both are included, which needs 2 more people from the other 4.

At least one woman from 4 men and 3 women, committee of 3: $18 + 12 + 1 = 31$ , or $35 - 4 = 31$
Exactly 2 women from 5 women and 4 men, committee of 3: $^{5} C_{2} \times^{4} C_{1} = 40$
Not both of two particular people, committee of 4 from 6: $^{6} C_{4} -^{4} C_{2} = 9$
Choose then arrange: $^{8} C_{3} \times 3! = 56 \times 6 = 336$

The complement is usually the shorter route when the condition contains the word 'at least', because the cases you exclude are the small ones: none, or one.

Key terms you must be able to define

Permutation: An arrangement in which order matters. 1234 and 4321 are different permutations of the same four digits.

Combination: A selection in which order does not matter. Choosing Ali, Bea and Chen is the same committee as choosing Chen, Ali and Bea.

Factorial: $n! = n \times (n - 1) \times \dots \times 2 \times 1$ , the number of ways of arranging $n$ different objects in a line. By definition $0! = 1$ .

Multiplication principle: If one stage can be done in $m$ ways and the next in $n$ ways, the two together can be done in $m \times n$ ways.

$^{n} P_{r}$: The number of arrangements of $r$ objects chosen from $n$ different objects, order mattering: $^{n} P_{r} = \frac{n!}{(n - r)!}$ .

$^{n} C_{r}$: The number of selections of $r$ objects from $n$ , order not mattering: $^{n} C_{r} = (\binom{n}{r}) = \frac{n!}{r! (n - r)!}$ , read as 'n choose r'.

Identical objects: Objects that cannot be told apart, such as the repeated letters of a word. Arrange the $n$ objects and divide by the factorial of each repeat.

Block method: Treating a group of objects that must stay together as one object, arranging the blocks, then multiplying by the arrangements inside each block.

Complement (in counting): Counting what you do not want and subtracting it from the total. The standard method for 'must not be together' and for 'at least one'.

Mutually exclusive cases: Cases that cannot happen at the same time, such as 'exactly 2 women' and 'exactly 3 women'. Count each case and add them.

Restriction: A condition in the question that some objects must be together, or apart, or included, or excluded. Deal with it first, before arranging anything else.

Two-stage problem: A question that first selects some objects and then arranges them. Multiply the number of selections by the number of arrangements.

Arrangement in a line: A permutation of objects in a row of positions. Each position can hold one object, and different objects in the same positions count as different arrangements.

Row of positions: A way of thinking about seating: each seat is a distinct position, so two rows of four are eight distinct positions, not one row.

At least: One or more, including the upper limit. 'At least 2 women' means 2, 3, 4 or 5 women, and each case is counted separately and added.

At most: No more than, including zero. 'At most 1 man' means 0 men or 1 man.

Applied

At AS & A Level the marks sit in the setup: choosing the model, stating the variable and writing the equation before any working. These show the shape of a full-mark answer, then you do the algebra yourself.

Letters with repeats

The word BALLOON has 7 letters with L repeated twice and O repeated twice, so the number of arrangements is $\frac{7!}{2! 2!} = \frac{5040}{4} = 1260$ . Dividing by 2! twice removes the arrangements that differ only by swapping the two Ls or the two Os.

Two particular people together

Seven people stand in a line, and two particular people must stand next to each other. Treat the pair as one block, giving 6 objects, so there are $6! = 720$ ways to arrange the objects, and the pair can be ordered in 2 ways. The answer is $720 \times 2 = 1440$ .

Two particular people apart

Six people stand in a line, and two particular people must not stand next to each other. The total is $6! = 720$ ; the arrangements with them together are $5! \times 2 = 240$ . The answer is $720 - 240 = 480$ .

A committee with a condition

A committee of 3 is chosen from 5 men and 4 women, with exactly 1 woman. Choose the woman in $^{4} C_{1} = 4$ ways and the two men in $^{5} C_{2} = 10$ ways, so the number of committees is $4 \times 10 = 40$ .

Choose first, then arrange

Four students are chosen from 9 and then seated in a row of four chairs. The choice can be made in $^{9} C_{4} = 126$ ways and the seating in $4! = 24$ ways, so there are $126 \times 24 = 3024$ possibilities. That is $^{9} P_{4}$ , since $^{9} C_{4} \times 4! =^{9} P_{4}$ .

Flashcards

Click a card to flip it. Mark honestly — the tracker uses this.

Q1What is the difference between a permutation and a combination?

In a permutation order matters, so 1234 and 4321 are different. In a combination order does not matter, so the same three people form the same committee however they are listed.

Q2State the formula for

^{n} P_{r}

^{n} P_{r} = \frac{n!}{(n - r)!} = n (n - 1) \dots (n - r + 1)

. It counts arrangements of

r

objects chosen from

n

, with order mattering.

Q3State the formula for

^{n} C_{r}

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

. It counts selections of

r

objects from

n

, with order not mattering.

Q4What is the value of

0!

1, by definition. That is what makes

^{n} P_{n} = n!

and

^{n} C_{0} = 1

work out.

Q5How many ways can

n

different objects be arranged in a line?

n!

ways. Five different books can go on a shelf in

5! = 120

orders.

Q6How do you arrange objects when some are identical?

Divide

n!

by the factorial of each repeated item:

\frac{n!}{a! b! \dots}

. BALLOON gives

\frac{7!}{2! 2!} = 1260

Q7What is the block method for?

Objects that must stay together. Glue them into one object, arrange the objects, then multiply by the arrangements inside the block.

Q8How do you count arrangements where two particular objects must not be together?

Total minus together:

n! - (n - 1)! \times 2

. For 7 people that is

5040 - 1440 = 3600

Q9What does 'at least' tell you to do?

Split the problem into cases and add them, or subtract the excluded cases from the total. 'At least 2 women' means 2, 3, 4 or 5 women.

Q10How do you count a selection from two separate groups?

Choose from each group separately and multiply the results, because the choices are independent stages:

^{5} C_{2} \times^{4} C_{1} = 40

Q11Why is

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

Choosing which

r

objects to take is the same as choosing which

n - r

to leave behind, so both counts must be equal.

Q12What is the link between

^{n} P_{r}

and

^{n} C_{r}

^{n} P_{r} =^{n} C_{r} \times r!

: choose the

r

objects, then arrange them. For 8 choose 3:

56 \times 6 = 336

Q13What does 'exactly' tell you to do?

Count one case only. 'Exactly 2 women' means 2 women and no more, so the other members of the committee must all be men.

Q14How do you count people seated in two rows?

Treat every seat as a distinct position, so two rows of four are eight positions. With a restriction, count the ordered pairs of seats that satisfy it, then arrange the rest.

Q15Are circular arrangements in the 9709 syllabus?

No. The syllabus states that questions about objects arranged in a circle will not be included.

Q16When do you multiply and when do you add?

Multiply for stages that happen one after another; add for mutually exclusive cases. 'Four starters and six mains' multiplies; 'a starter or a main' adds.

0 of 16 marked as known

Exam technique for this topic

Decide first whether order matters, and write the decision down. If swapping two chosen items gives a different outcome it is a permutation; if it gives the same outcome it is a combination. That sentence is often worth a mark on its own.
For 'at least' or 'at most', write the cases before calculating and show the working for each. If the excluded cases are few, subtract them from the total instead - and say which total you are subtracting from.
For 'must be together', form a block and multiply by the arrangements inside it. For 'must not be together', subtract the together arrangements from the total. The second is the complement of the first.
Show the expression before the number, for example $\frac{7!}{3! 2!}$ or $^{8} C_{3} \times 3!$ . A mark is usually available for the correct expression even when the arithmetic slips.
Check the size of the answer against the problem. Arranging 8 different people gives 40320 ways, so an answer in the millions for eight people means something has been multiplied twice.

Why students lose marks here

A student wroteThe number of ways of choosing a committee of 3 from 7 people is

7 \times 6 \times 5 = 210

Why it loses marksThat is the number of ordered selections. A committee does not have an order, and every committee has been counted 3! = 6 times, once for each order of its three members.

The answer that scores

^{7} C_{3} = \frac{7!}{3! 4!} = \frac{210}{6} = 35

committees.

A student wroteFor two particular people who must not stand next to each other in a line of 6, I answered

5! \times 2 = 240

Why it loses marks240 is the number of arrangements in which they ARE next to each other. The question asks for the arrangements in which they are apart, which is the complement of that.

The answer that scores

6! - 5! \times 2 = 720 - 240 = 480

arrangements.

A student wroteThe letters of BALLOON can be arranged in

7! = 5040

ways.

Why it loses marksSwapping the two Ls, or the two Os, produces the same word, so 5040 counts every word four times over.

The answer that scores

\frac{7!}{2! 2!} = \frac{5040}{4} = 1260

different arrangements.

A student wroteA committee of 3 from 5 men and 4 women, with at least one woman, is

^{4} C_{1} \times^{5} C_{2} = 40

Why it loses marksThat counts only the committees with exactly one woman. The committees with 2 women and with 3 women also satisfy 'at least one', and they have been left out.

The answer that scores

40 +^{4} C_{2} \times^{5} C_{1} +^{4} C_{3} = 40 + 30 + 4 = 74

. The complement gives the same answer:

^{9} C_{3} -^{5} C_{3} = 84 - 10 = 74

A student wroteThe number of ways of arranging 5 people in a line, with two particular people together, is

5! = 120

Why it loses marksOnce the pair is glued together there are only 4 objects to arrange, not 5, and the pair itself has 2 orders. Both corrections are needed.

The answer that scores

4! \times 2! = 24 \times 2 = 48

arrangements.

Syllabus coverage

Counting in stages: the multiplication principle

Permutations: order matters

Combinations: order does not matter

Which one does the question want?

Arrangements when some objects are identical

Restriction: objects that must stay together

Restriction: objects that must not be together

People in two or more rows

Selections with conditions: at least, at most, exactly

Key terms you must be able to define

Applied

Flashcards

Exam-style questions

Mark scheme — tick each point you actually made

Mark scheme — tick each point you actually made

Mark scheme — tick each point you actually made

Mark scheme — tick each point you actually made

Mark scheme — tick each point you actually made

Mark scheme — tick each point you actually made

Mark scheme — tick each point you actually made

Mark scheme — tick each point you actually made

Exam technique for this topic

Why students lose marks here