Chapter 5

Permutations and Combinations

5.2     Permutations

In example 3 in section 5.1, we consider the arrangements of some pictures on a wall. In that problem, there are 5 different pictures (say A, B, C, D and E) and 3 nails (say N1, N2 and N3).
fig 5.2

We have known that there are 5 ⋅ 4 ⋅ 3 ways to hang the pictures. If the pictures C, E and A are hung on the nails in that order, we can expressed it as CEA. We can notice that AEC and ACE are in different orders.

Definition.   A permutation is an arrangement of the objects in a specific order. If there are n objects, then a permutation of any such r objects, with r ≤ n, is said to be a permutation of n objects taken r at a time. The number of permutations of n distinct objects taken r at a time is usually denoted by nPr.

In the above example, the number of ways to hang the pictures is the number of permutations of 5 pictures taken 3 at a time, and so we write
$$\small{^5P_3 = \underbrace{5 \cdot 4 \cdot 3}_{3\,\, factors} }$$
  • If n and r are positive integers with r ≤ n,
    $$\small{ ^nP_r = \underbrace{n(n-1)(n-2)...(n-(r-1))}_{r\,\, \text{factors}}.}$$
  • We define nP0 to be 1, for a nonnegative integer n.

If n and r are positive integers with r ≤ n, we have
nPr = n(n - 1)(n - 2) ... (n - (r - 1))
= n(n - 1)(n - 2) ... (n - (r + 1) ⋅ (n - r)!⁄ (n - r)!
= n!⁄(n - r)!

Generally, for integers n and r with 0 ≤ r ≤ n,
nPr = n!⁄(n - r)!.

Notice that nPn = n!.

Example 8.
Evaluate   10P5 + 10P0.
Solution
10P5 + 10P0 = 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 + 1 = 30240 + 1 = 30241

Example 9.
Solve the equations for n.
(a)   nP2 = 9n
(b)   nP3 = 12 ⋅ nP2.
Solution
(a)     nP2 = 9n
n ≥ 2 and   n(n - 1) = 9n
n - 1 = 9
n = 10

(b)     nP3 = 12 ⋅ nP2.
n ≥ 3 and   n(n - 1)(n - 2) = 12 n(n - 1)
n - 2 = 12
n = 14

Example 10.
In how many ways can a president, a treasurer and a secretary for a committee be selected from a group of 15 people?
Solution
The number of ways to select people for three different positions (ranks) is the number of permutations of 15 people taken 3 at a time, and hence it is
15P3 = 15 ⋅ 14 ⋅ 13 = 2730.

Example 11.
In how many ways can all the letters of the word PENCIL be arranged, without repeating any letters?
Solution
There are 6 distinct letters. So the number of ways to arrange the letters is
6P6 = 6! = 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 720.

Example 12.
There are 2 buses, which have 5 and 4 vacant seats respectively, and 4 people at a bus stop. In how many ways can all these people be seated on either of the buses, but not both?
Solution
The first bus has 5 vacant seats, so the number of ways to be seated there is
5P4 = 5 ⋅ 4 ⋅ 3 ⋅ 2 = 120.
The second bus has 4 vacant seats, so the number of ways to be seated there is
4! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24.
Therefore the required number of ways is 120 + 24 = 144.

Example 13.
In how many ways can 6 different books be arranged along a line on a shelf if one of the books is a dictionary and it must be at one end?
Solution
The dictionary must be fixed at the 1st or the 6th position in the arrangements.
If the dictionary is in the 1st position, the number of ways to arrange all the other books in remaining positions is
5! = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 120.
If the dictionary is in the 6th position, the number of ways to arrange all the other books in remaining positions is
5! = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 120.
So, the required number of ways = (1 × 120) + (120 × 1) = 240.

Exercise 5.2

1.   Solve the equations for n.
(a)   nP2 = 42
(b)   nP3 = 9 ⋅ nP2.
Solution
(a)   nP2 = 42
n(n - 1) = 42
n2 - n - 42 = 0
(n - 7)(n + 6) = 0
n - 7 = 0   or   n + 6 = 0
n = 7   or   n = -6
∴ n = 7

(b)   nP3 = 9 ⋅ nP2
n ≥ 3 and n(n - 1)(n - 2) = 9 ⋅ n(n - 1)
n(n - 1)(n - 2)⁄n(n - 1) = 9
n - 2 = 9
n = 11

2.   A newspaper has 14 reporters available to cover 3 different stories. In how many ways can the reporters be assigned to cover the stories, if no reporter can be assigned to cover more than one story?
Solution
Number of reporters for a newspaper = 14
Number of different stories to cover = 3
If no reporter can be assigned to cover more than one story,
ways the reporters can be assigned to cover the story = 14P3
= 14(14 - 1)(14 - 2)
= 14 ⋅ 13 ⋅ 12
= 2184

3.   Suppose we have to make a signal by choosing 4 different flags out of 9 different coloured flags and arranging them in a row. How many different signals can we do?
Solution
We have to make a signal by choosing 4 different flags out of 9 different coloured flags.
The required number of ways = 9P4
= 9(9 - 1)(9 - 2)(9 - 3)
= 9 ⋅ 8 ⋅ 7 ⋅ 6
= 3024

4.   The manager of 4 movie theaters is deciding which of 12 available movies to show. The theaters have different seating capacities. How many ways can he show 4 different movies in the theaters at the same time?
Solution
The number of movies theaters = 4
The number of available movies to show = 12
Ways the manager of 4 movies can show 4 different movies in the theaters at the same time is = 12P4
= 12 (12 -1)(12 -2)(12 - 3)
= 12 ⋅ 11 ⋅ 10 ⋅ 9
= 11880

5.   A classroom has two rows of eight seats each. There are 10 students, 5 of whom want to sit in the front row, 4 want to sit in the back row and the remaining student can sit in any seat. In how many ways can the students be seated?
Solution
Number of seats in first row = 8
Number of seats in second row = 8.
If the remaining student sit in the first row with 5 of the students and 4 of the students sit in the second row,
8P6 × 8P4
= (8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3) × (8 ⋅ 7 ⋅ 6 ⋅ 5)
= 20160 × 1680
= 338 688 00
If 5 of the students sit in the first row and the remaining student sit in the second row with 4 of the students,
8P5 × 8P5
= (8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4) × (8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4)
= 6720 × 6720
= 45 158 400
Ways the students can be seated is   33,868,800 + 45,158,400
= 79,027,200