5

Permutations and S1 

combinations 5

Permutations and combinations

An estate had seven houses;
Each house had seven cats;
Each cat ate seven mice;
Each mouse ate seven grains of wheat.
Wheat grains, mice, cats and houses,
How many were there on the estate?
Ancient Egyptian problem

ProudMum
My son is a genius!
I gave Oscar five bricks and straightaway he did this!
Is it too early to enrol him with MENSA?

What is the probability that Oscar chose the bricks at random and just happened
by chance to get them in the right order?

There are two ways of looking at the situation. You can think of Oscar selecting
the five bricks as five events, one after another. Alternatively, you can think of
1, 2, 3, 4, 5 as one outcome out of several possible outcomes and work out the
probability that way.

Five events

Look at the diagram.

1 2 3 4 5

Figure 5.1 

If Oscar had actually chosen them at random:

the probability of first selecting 1 is 51

1 correct choice from
the probability of next selecting 2 is 14 4 remaining bricks.
123
S1  the probability of next selecting 3 is 13

the probability of next selecting 4 is 12

5
then only 5 remains so the probability of selecting it is 1.
Permutations and combinations

So the probability of getting the correct numerical sequence at random is

1
5
× 14 × 13 × 12 × 1 = 120
1
.

Outcomes

How many ways are there of putting five bricks in a line?

To start with there are five bricks to choose from, so there are five ways of
choosing brick 1. Then there are four bricks left and so there are four ways of
choosing brick 2. And so on.

The total number of ways is

5 × 4 × 3 × 2 × 1 = 120.
Brick 1 Brick 2 Brick 3 Brick 4 Brick 5

Only one of these is the order 1, 2, 3, 4, 5, so the probability of Oscar selecting it

1
at random is 120 .
Number of possible
outcomes.

●
? Do you agree with Oscar’s mother that he is a child prodigy, or do you think it
was just by chance that he put the bricks down in the right order?

What further information would you want to be convinced that he is a budding

genius?

Factorials
In the last example you saw that the number of ways of placing five different
bricks in a line is 5 × 4 × 3 × 2 × 1. This number is called 5 factorial and is written
5!. You will often meet expressions of this form.

In general the number of ways of placing n different objects in a line is n!, where
n! = n × (n − 1) × (n − 2) × ... × 3 × 2 × 1.

n must be a
positive integer.

124
 S1 
EXAMPLE 5.1 Calculate 7!

SOLUTION
5
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040

Factorials
Some typical relationships between factorial numbers are illustrated below:

10! = 10 × 9!         or in general   n! = n × [(n − 1)!]

10! = 10 × 9 × 8 × 7!   or in general   n! = n × (n − 1) × (n − 2) × [(n − 3)!]

These are useful when simplifying expressions involving factorials.

EXAMPLE 5.2 Calculate  5!

3!

SOLUTION

5! = 5 × 4 × 3! = 5 × 4 = 20
3! 3!

7 ! × 5!
EXAMPLE 5.3 Calculate 
3! × 4!

SOLUTION

7! × 5! = 7 × 6 × 5 × 4 × 3! × 5 × 4 !
3! × 4 ! 3! × 4 !
= 7 × 6 × 5 × 4 × 5 = 4200

EXAMPLE 5.4 Write 37 × 36 × 35 in terms of factorials only.

SOLUTION

37 × 36 × 35 = 37 × 36 × 35 × 34 !
34 !
= 37 !
34 !

EXAMPLE 5.5 (i) Find the number of ways in which all five letters in the word GREAT can be
arranged.
(ii) In how many of these arrangements are the letters A and E next to each
other?

SOLUTION

(i) There are five choices for the first letter (G, R, E, A or T). Then there are four
choices for the next letter, then three for the third letter and so on. So the
number of arrangements of the letters is

5 × 4 × 3 × 2 × 1 = 5! = 120

125
S1 
(ii) The E and the A are to be together, so you can treat them as a single letter.

So there are four choices for the first letter (G, R, EA or T), three choices for
5 the next letter and so on.

So the number of arrangements of these four ‘letters’ is

Permutations and combinations

4 × 3 × 2 × 1 = 4! = 24

However EA   G   R   T

is different from AE   G   R   T

So each of the 24 arrangements can be arranged into two different orders.

The total number of arrangements with the E and A next to each other is

      2 × 4! = 48

Note
The total number of ways of arranging the letters with the A and the E apart is

120 – 48 = 72

Sometimes a question will ask you to deal with repeated letters.

EXAMPLE 5.6 Find the number of ways in which all five letters in the word GREET can be
arranged.

SOLUTION

There are 5! = 120 arrangements of five letters.

However, GREET has two repeated letters and so some of these arrangements are
really the same.
For example, E   E   G   R   T

is the same as E  E  G  R  T

The two Es can be arranged in 2! = 2 ways, so the total number of arrangements is

5!
= 60.
2!

EXAMPLE 5.7 How many different arrangements of the letters in the word MATHEMATICAL
are there?

SOLUTION

There are 12 letters, so there are 12! = 479 001 600 arrangements.

126
 S1 
However, there are repeated letters and so some of these arrangements are the same.

For example, M  A   T   H  E   M  A   T   I   C   A   L

M  A   T   H  E   M  A   T   I   C   A   L 5

Exercise 5A
and M  A   T   H  E   M  A   T   I   C   A   L

are the same.

In fact, there are 3! = 6 ways of arranging the As.

So the total number of arrangements of

M   A   T   H   E   M   A   T   I   C   A   L is

12 letters

12!
–––––––––   = 19 958 400
2! × 2! × 3! Three As repeated

Two Ms repeated Two Ts repeated

Example 5.7 illustrates how to deal with repeated objects. You can generalise
from this example to obtain the following:

●● The number of distinct arrangements of n objects in a line, of which p are

identical to each other, q others are identical to each other, r of a third type are
identical, and so on is n ! .
p !q !r !…
8! 5! × 6!
EXERCISE 5A 1 Calculate (i) 8! (ii) (iii)
6! 7! × 4 !
(n − 1)! (n − 1)!
2 Simplify (i) (ii)
n! (n − 2)!
(n + 3)! n!
3 Simplify (i) (ii)
(n + 1)! (n − 2)!

4 Write in factorial notation.

8×7×6 15 × 16 (n + 1)n(n − 1)
(i) (ii) (iii)
5×4×3 4×3×2 4×3×2
5 Factorise (i) 7! + 8! (ii) n! + (n + 1)!
6 How many different four letter words can be formed from the letters A, B, C and
D if letters cannot be repeated? (The words do not need to mean anything.)

7 How many different ways can eight books be arranged in a row on a shelf?
8 I n a greyhound race there are six runners. How many different ways are there
for the six dogs to finish?

127
S1 
9 In a 60-metre hurdles race there are five runners, one from each of the
nations Austria, Belgium, Canada, Denmark and England.

5 (i) How many different finishing orders are there?

(ii) What is the probability of predicting the finishing order by choosing
Permutations and combinations

first, second, third, fourth and fifth at random?

10 J ohn has an MP3 player which can play tracks in ‘shuffle’ mode. If an album
is played in ‘shuffle’ mode the tracks are selected in a random order with a
different track selected each time until all the tracks have been played.
John plays a 14-track album in ‘shuffle’ mode.
(i) In how many different orders could the tracks be played?
(ii) What is the probability that ‘shuffle’ mode will play the tracks in the
normal set order listed on the album?
11 In a ‘Goal of the season’ competition, participants are asked to rank ten goals
in order of quality.
The organisers select their ‘correct’ order at random. Anybody who matches
their order will be invited to join the television commentary team for the
next international match.
(i) What is the probability of a participant’s order being the same as that of
the organisers?
(ii) Five million people enter the competition. How many people would be
expected to join the commentary team?

12 The letters O, P, S and T are placed in a line at random. What is the

probability that they form a word in the English language?
13 Find how many arrangements there are of the letters in each of these words.
(i) EXAM (ii) MATHS (iii) CAMBRIDGE
(iv) PASS (v) SUCCESS (vi) STATISTICS

14 How many arrangements of the word ACHIEVE are there if

(i) there are no restrictions on the order the letters are to be in
(ii) the first letter is an A
(iii) the letters A and I are to be together.
(iv) the letters C and H are to be apart.

128
Investigations

1 Solve the inequality n!  10m for each of the cases m = 3, 4, 5.

S1 
2 In how many ways can you write 42 using factorials only? 5
3 (i) There are 4! ways of placing the four letters S, T, A, R in a line, if each of

Permutations
them must appear exactly once. How many ways are there if each letter
may appear any number of times (i.e. between 0 and 4)? Formulate a
general rule.
(ii) There are 4! ways of placing the letters S, T, A, R in line. How many ways
are there of placing in line the letters
(a) S, T, A, A (b) S, T, T, T?
Formulate a general rule for dealing with repeated letters.

Permutations

I should be one of the judges! When I heard the 16 songs in the competition, I knew
which ones I thought were the best three. Last night they announced the results and I
had picked the same three songs in the same order as the judges!
Joyetta

What is the probability of Joyeeta’s result?

The winner can be chosen in 16 ways.
The second song can be chosen in 15 ways.
The third song can be chosen in 14 ways.
Thus the total number of ways of placing three songs in the first three positions is
1
16 × 15 × 14 = 3360. So the probability that Joyeeta’s selection is correct is 3360 .
In this example attention is given to the order in which the songs are placed. The
solution required a permutation of three objects from sixteen.
In general the number of permutations, nPr , of r objects from n is given by
nP
r = n × (n − 1) × (n − 2) × ... × (n − r + 1).

This can be written more compactly as

nP = n!
●● r (n − r)!

129
S1 
EXAMPLE 5.8 Six people go to the cinema. They sit in a row with ten seats. Find how many
ways can this be done if
(i) they can sit anywhere
5 (ii) all the empty seats are next to each other.
Permutations and combinations

SOLUTION

(i) The first person to sit down has a choice of ten seats.
The second person to sit down has a choice of nine seats.
The third person to sit down has a choice of eight seats.
...
The sixth person to sit down has a choice of five seats.
So the total number of arrangements is 10 × 9 × 8 × 7 × 6 × 5 = 151 200.
This is a permutation of six objects from ten, so a quicker way to work this
out is
number of arrangements = 10P6 = 151 200

(ii) Since all four empty seats are to be together you can consider them to be a
single ‘empty seat’, albeit a large one!
So there are seven seats to seat six people.
So the number of arrangements is 7P6 = 5040

Combinations
It is often the case that you are not concerned with the order in which items are
chosen, only with which ones are picked.

To take part in the UK National Lottery you fill in a ticket by selecting six
numbers out of a possible 49 (numbers 1, 2, . . . , 49). When the draw is made a
machine selects six numbers at random. If they are the same as the six on your
ticket, you win the jackpot.

●
? You have the six winning numbers. Does it matter in which order the machine
picked them?

The probability of a single ticket winning the jackpot is often said to be 1 in

14 million. How can you work out this figure?

The key question is, how many ways are there of choosing six numbers out of 49?

If the order mattered, the answer would be 49P6, or 49 × 48 × 47 × 46 × 45 × 44.

However, the order does not matter. The selection 1, 3, 15, 19, 31 and 48 is the
same as 15, 48, 31, 1, 19, 3 and as 3, 19, 48, 1, 15, 31, and lots more. For each set
130 of six numbers there are 6! arrangements that all count as being the same.
 S1 
So, the number of ways of selecting six balls, given that the order does not
matter, is
49 × 48 × 47 × 46 × 45 × 44 .
5
49P
This is –––6
6! 6!

Combinations
This is called the number of combinations of 6 objects from 49 and is denoted
by 49C6.

49!
●
? Show that 49C6 can be written as
6! × 43!
.

Returning to the UK National Lottery, it follows that the probability of your one
ticket winning the jackpot is 491 .
C6

●
? Check that this is about 1 in 14 million.

This example shows a general result, that the number of ways of selecting r
objects from n, when the order does not matter, is given by
n
n n! P
Cr = = r
r!(n − r)! r !

●
? How can you prove this general result?

Another common notation for nCr is   . Both notations are used in this book to
n
r 
help you become familiar with both of them.

 n
! The notation   looks exactly like a column vector and so there is the possibility
r 
of confusing the two. However, the context should usually make the meaning clear.

EXAMPLE 5.9 A School Governors’ committee of five people is to be chosen from eight
applicants. How many different selections are possible?

SOLUTION
 8 8! = 8 × 7 × 6 = 56
Number of selections =   =
 5  5! × 3! 3 × 2 × 1 131
S1 
EXAMPLE 5.10 In how many ways can a committee of four people be selected from four applicants?

SOLUTION
5
Common sense tells us that there is only one way to make the committee, that is
Permutations and combinations

by appointing all applicants. So 4C4 = 1. However, if we work from the formula

4C = 4! = 1
4 4! × 0! 0!
For this to equal 1 requires the convention that 0! is taken to be 1.

●
? Use the convention 0! = 1 to show that nC0 = nCn = 1 for all values of n.

The binomial coefficients

 n
In the last section you met numbers of the form nCr or   . These are called the
r 
binomial coefficients; the reason for this is explained in Appendix 3 (which you
can find on the CD) and in the next chapter.

 n n !  and the results  n  =  n  = 1 to check that

ACTIVITY 5.1 Use the formula   =  0   n 
 r  r !(n − r)!
the entries in this table, for n = 6 and 7, are correct.

r 0 1 2 3 4 5 6 7
n=6 1 6 15 20 15 6 1 –
n=7 1 7 21 35 35 21 7 1

It is very common to present values of nCr in a table shaped like an isosceles

triangle, known as Pascal’s triangle.
This completes
1 the triangle.
1 1
1 2 1
This is 4C0. This is 5C3.
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
… … … … … … … …

The numbers in this row are the same as

those in the first row of the table above.

Pascal’s triangle makes it easy to see two important properties of binomial

132
coefficients.
 1 Symmetry: nCr = nCn–r

If you are choosing 11 players from a pool of 15 possible players you can either
S1 
name the 11 you have selected or name the 4 you have rejected. Similarly, every 5
choice of r objects included in a selection from n distinct objects corresponds to a
choice of (n − r) objects which are excluded. Therefore nCr = nCn–r.

Using binomial coefficients to calculate probabilities

This provides a short cut in calculations when r is large. For example
100C = 100C4 = 100 × 99 × 98 × 97 = 3 921 225.
96 1× 2× 3× 4
It also shows that the list of values of nCr for any particular value of n is
unchanged by being reversed. For example, when n = 6 the list is the seven
numbers 1, 6, 15, 20, 15, 6, 1.

2 Addition: n+1C = nCr + nCr+1

r+1

Look at the entry 15 in the bottom row of Pascal’s triangle, towards the right.
The two entries above and either side of it are 10 and 5,

… 10 5 …
5C
3
… 15 … 5C
4

6C
4

and 15 = 10 + 5. In this case 6C4 = 5C3 + 5C4. This is an example of the general
result that n+1Cr+1 = n Cr + n Cr+1. Check that all the entries in Pascal’s triangle
(except the 1s) are found in this way.
This can be used to build up a table of values of n Cr without much calculation. If
you know all the values of n Cr for any particular value of n you can add pairs of
values to obtain all the values of n+1Cr , i.e. the next row, except the first and last,
which always equal 1.

Using binomial coefficients to calculate probabilities

EXAMPLE 5.11 A committee of 5 is to be chosen from a list of 14 people, 6 of whom are men
and 8 women. Their names are to be put in a hat and then 5 drawn out.

What is the probability that this procedure produces a committee with no

women?

SOLUTION

The probability of an all-male committee of 5 people is given by

There are 6 men.

the number of ways of choosing 5 people out of 6 6C

6
–––––––––––––––––––––––––––––––––––––––––––– = 14 5 = ≈ 0.003
the number of ways of choosing 5 people out of 14 C 5 2002
133
There are 14 people.
S1  b GoByBus.com b
5 Help decide our new bus routes
The exact route for our new bus
Permutations and combinations

service is to be announced in April.

Rest assured our service will run
from Amli to Chatra via Bawal and
will be extended to include Dhar
once our new fleet of buses arrives
in September. As local people know,
there are several roads connecting
these towns and we are keen to hear the views as to the most useful
routes from our future passengers. Please post your views below!

This consultation is a farce. The chance of

getting a route that suits me is less than one
RChowdhry in a hundred :(

Is RChowdhry right? How many routes are there from Amli to Dhar? Start by
looking at the first two legs, Amli to Bawal and Bawal to Chatra.

There are three roads from Amli to Bawal and two roads from Bawal to Chatra.
How many routes are there from Amli to Chatra passing through Bawal on
the way?

Look at figure 5.2.

x
Amli Bawal u Chatra
y
v
z

Figure 5.2

The answer is 3 × 2 = 6 because there are three ways of doing the first leg,
followed by two for the second leg. The six routes are

x − u     y − u     z − u
x − v     y − v     z − v.

134
 S1 
There are also four roads from Chatra to Dhar. So each of the six routes from
Amli to Chatral has four possible ways of going on to Dhar. There are now
6 × 4 = 24 routes. See figure 5.3.
5
x p
Amli Bawal u Chatra Dhar

Using binomial coefficients to calculate probabilities

y
q
v
z r
s

Figure 5.3

They can be listed systematically as follows:

x − u − p y − u − p z − u − p x − v − p y − v − p z −v−p
x − u − q ................ ................ ................ ................ ................
x − u − r ................ ................ ................ ................ ................
x − u − s ................ ................ ................ ................ z−v−s

In general, if there are a outcomes from experiment A, b outcomes from

experiment B and c outcomes from experiment C then there are a × b × c different
possible combined outcomes from the three experiments.

●
? 1 If GoByBus chooses its route at random, what is the probability that it will be
the one RChowdhry wants? Is the comment justified?

2 In this example the probability was worked out by finding the number of
possible routes. How else could it have been worked out?

EXAMPLE 5.12 A cricket team consisting of 6 batsmen, 4 bowlers and 1 wicket-keeper is to be

selected from a group of 18 cricketers comprising 9 batsmen, 7 bowlers and 2
wicket-keepers. How many different teams can be selected?

SOLUTION

The batsmen can be selected in 9C6 ways.

The bowlers can be selected in 7C4 ways.
The wicket-keepers can be selected in 2C1 ways.
Therefore total number of teams = 9C6 × 7C4 × 2C1

= 9! × 7 ! × 2!
3! × 6! 3! × 4 ! 1! × 1!
=9×8×7×7×6×5×2
3× 2×1 3× 2×1
= 5880
135
S1 
EXAMPLE 5.13 In a dance competition, the panel of ten judges sit on the same side of a long
table. There are three female judges.

5 (i) How many different arrangements are there for seating the ten judges?
(ii)  ow many different arrangements are there if the three female judges all
H
Permutations and combinations

decide to sit together?

(iii) Ifthe seating is at random, find the probability that the three female judges
will not all sit together.

(iv)  our of the judges are selected at random to judge the final round of the
F
competition. Find the probability that this final judging panel consists of two
men and two women.

SOLUTION

(i) There are 10! = 3 628 800 ways of arranging the judges in a line.
(ii) I f the three female judges sit together then you can treat them as a single
judge.

So there are eight judges and there are 8! = 40 320 ways of arranging the
judges in a line.

However, there are 3! = 6 ways of arranging the female judges.

So there are 3! × 8! = 241 920 ways of arranging the judges so that all the
female judges are together.

(iii) There are 3 628 800 − 241 920 = 3 386 880 ways of arranging the judges so that
the female judges do not all sit together.

So the probability that the female judges do not all sit together is
3 386 880
= 0.933 (to 3 s.f.).
3 628 800
(iv) The probability of selecting two men and two women on the panel of four is
2×
3C 7C
2
= 3! × 7 ! ÷ 10!
10C
4
1! × 2! 5! × 2! 6! × 4 !
= 3 × 21 ÷ 210
= 0.3

136
 Find the values of (a) 6P2 (b) 8P4 (c) 10P4.
S1 
EXERCISE 5B 1 (i)

(ii) Findthe values of (a) 6C2 (b) 8C4 (c) 10C4.

(iii) Show that, for the values of n and r in parts (i) and (ii),
nP
5
nC = r.

Exercise 5B
r r!
2 There are 15 runners in a camel race. What is the probability of correctly
guessing the first three finishers in their finishing order?

3 To win the jackpot in a lottery a contestant must correctly select six numbers
from the numbers 1 to 30 inclusive. What is the probability that a contestant
wins the jackpot with one selection of six numbers?

4 A group of 5 computer programmers is to be chosen to form the night shift

from a set of 14 programmers. In how many ways can the programmers be
chosen if the 5 chosen must include the shift-leader who is one of the 14?

5 My brother Mark decides to put together a rock band from amongst his year at
school. He wants a lead singer, a guitarist, a keyboard player and a drummer.
He invites applications and gets 7 singers, 5 guitarists, 4 keyboard players and
2 drummers. Assuming each person applies only once, in how many ways can
Mark put the group together?

6 A touring party of cricket players is made up of 5 players from each of India,

Pakistan and Sri Lanka and 3 from Bangladesh.

(i) How many different selections of 11 players can be made for a team?
(ii) In one match, it is decided to have 3 players from each of India, Pakistan
and Sri Lanka and 2 from Bangladesh. How many different team selections
can now be made?

7 A committee of four is to be selected from ten candidates, six men and four
women.

(i) In how many distinct ways can the committee be chosen?

(ii) Assuming that each candidate is equally likely to be selected, determine the
probabilities that the chosen committee contains
(a) no women
(b) two men and two women.

8  committee of four is to be selected from five boys and four girls. The
A
members are selected at random.

(i) How many different selections are possible?

(ii) What is the probability that the committee will be made up of
(a) all girls?
(b) more boys than girls?

137
S1 
9 Baby Imran has a set of alphabet blocks. His mother often uses the blocks
I, M, R, A and N to spell Imran’s name.

5 (i) One day she leaves him playing with these five blocks. When she comes
back into the room Imran has placed them in the correct order to spell
Permutations and combinations

his name. What is the probability of Imran placing the blocks in this
order? (He is only 18 months old so he certainly cannot spell!)
(ii) A couple of days later she leaves Imran playing with all 26 of the alphabet
blocks. When she comes back into the room she again sees that he has
placed the five blocks I, M, R, A and N in the correct order to spell his
name. What is the probability of him choosing the five correct blocks
and placing them in this order?
10 (i) A football team consists of 3 players who play in a defence position,
3 players who play in a midfield position and 5 players who play in a
forward position. Three players are chosen to collect a gold medal for the
team. Find in how many ways this can be done
(a) if the captain, who is a midfield player, must be included, together
with one defence and one forward player.
(b) if exactly one forward player must be included, together with any two
others.
(ii) Find how many different arrangements there are of the nine letters in the
words GOLD MEDAL
(a) if there are no restrictions on the order of the letters,
(b) if the two letters D come first and the two letters L come last.
[Cambridge International AS and A Level Mathematics 9709, Paper 6 Q7 June 2005]

11 The diagram shows the seating plan for passengers in a minibus, which has
17 seats arranged in 4 rows. The back row has 5 seats and the other 3 rows
have 2 seats on each side. 11 passengers get on the minibus.

Back Front

(i) How many possible seating arrangements are there for the 11 passengers?
(ii) How many possible seating arrangements are there if 5 particular people
sit in the back row?
Of the 11 passengers, 5 are unmarried and the other 6 consist of 3 married
couples.
(iii) In how many ways can 5 of the 11 passengers on the bus be chosen if
there must be 2 married couples and 1 other person, who may or may
138 not be married?
[Cambridge International AS and A Level Mathematics 9709, Paper 6 Q4 June 2006]
 S1 
12 Issam has 11 different CDs, of which 6 are pop music, 3 are jazz and 2 are
classical.
How many different arrangements of all 11 CDs on a shelf are there if the
5
(i)
jazz CDs are all next to each other?
(ii) Issam makes a selection of 2 pop music CDs, 2 jazz CDs and 1 classical

Exercise 5B
CD. How many different possible selections can be made?
[Cambridge International AS and A Level Mathematics 9709, Paper 6 Q3 June 2008]

13 A choir consists of 13 sopranos, 12 altos, 6 tenors and 7 basses. A group

consisting of 10 sopranos, 9 altos, 4 tenors and 4 basses is to be chosen from
the choir.
(i) In how many different ways can the group be chosen?
(ii) In how many ways can the 10 chosen sopranos be arranged in a line if the
6 tallest stand next to each other?
(iii) The 4 tenors and the 4 basses in the group stand in a single line with all
the tenors next to each other and all the basses next to each other. How
many possible arrangements are there if three of the tenors refuse to
stand next to any of the basses?
[Cambridge International AS and A Level Mathematics 9709, Paper 6 Q4 June 2009]

14 A staff car park at a school has 13 parking spaces in a row. There are 9 cars to
be parked.
(i) How many different arrangements are there for parking the 9 cars and
leaving 4 empty spaces?
(ii) How many different arrangements are there if the 4 empty spaces are
next to each other?
(iii) If the parking is random, find the probability that there will not be 4
empty spaces next to each other.
[Cambridge International AS and A Level Mathematics 9709, Paper 6 Q3 November 2005]

15 A builder is planning to build 12 houses along one side of a road. He will

build 2 houses in style A, 2 houses in style B, 3 houses in style C, 4 houses in
style D and 1 house in style E.
(i) Find the number of possible arrangements of these 12 houses.
(ii)
Road

First group Second group

The 12 houses will be in two groups of 6 (see diagram). Find the number
of possible arrangements if all the houses in styles A and D are in the first
group and all the houses in styles B, C and E are in the second group.
(iii) Four of the 12 houses will be selected for a survey. Exactly one house
must be in style B and exactly one house in style C. Find the number of
ways in which these four houses can be selected.
139
[Cambridge International AS and A Level Mathematics 9709, Paper 6 Q4 November 2008]
S1 
16 (i) Find how many numbers between 5000 and 6000 can be formed from
the digits 1, 2, 3, 4, 5 and 6
(a) if no digits are repeated,
5 (b) if repeated digits are allowed.
(ii) Find the number of ways of choosing a school team of 5 pupils from
Permutations and combinations

6 boys and 8 girls

(a) if there are more girls than boys in the team,
(b) if three of the boys are cousins and are either all in the team or all not
in the team.
[Cambridge International AS and A Level Mathematics 9709, Paper 61 Q5 November 2009]

KEY POINTS
1 The number of ways of arranging n unlike objects in a line is n!
2 n! = n × (n – 1) × (n – 2) × (n – 3) × ... × 3 × 2 × 1.

3 The number of distinct arrangements of n objects in a line, of which p are

identical to each other, q others are identical to each other, r of a third type
are identical, and so on is
n!
.
p !q !r !…
4 The number of permutations of r objects from n is
nP = n! .
r (n − r)!

5 The number of combinations of r objects from n is

nC = n! .
r (n − r)!r !

6 For permutations the order matters. For combinations it does not.

7 By convention 0! = 1.

140