Chapter 5
Permutations and Combinations
In this chapter, the concepts of "permutation" and "combination" are described in accordance with some counting principles. Counting techniques are indispensable to apply probability when the sample space is finite and outcomes are equally likely. They are also beneficial and applicable to many areas of Mathematics, Statistics, Science and Engineering.
5.1 Counting Principles
Suppose a coffee shop offers 2 choices of drinks (Tea and Coffee) and 3 choices of snacks (Cake, Doughnut and Sandwich). How many different choices are possible to
have a drink and a snack? We can see the complete list of all possible choices in the three diagram shown below.
In this problem, there are 2 ways to choose the type of drink. For each such choice, there are 3 ways to choose the type of snack. The number of ways to have a drink
and a snack is 6, which can be computed as 2 × 3 = 6.
Now, let us have a look at another example. Suppose a list of 5 topics is given in an essay contest. A student must select one of the topics on which to write a short
essay, and then select a different topic from the list for a long essay. How many ways can the topics be chosen for the two essays? In this example, there are 5 ways
to choose a topic for a short essay. After choosing one for the short essay, a long essay can be written on one of the remaining 4 topics. So the number of ways
to choose the topics is 5 × 4 = 20.
The two examples illustrates the following multiplication principle.
Suppose a task can be performed in m ways, and no matter how the task has been performed another task can then be performed in n ways. Then the number of ways to perform these two tasks in succession is mn.
The principle can be extended to any finite number of such successive tasks.
Example 1.
Suppose that there are 6 roads between town A and town B, and that 4 roads between town B and town C. Find the number of ways a person can drive from A to C by passing through B?
Solution
There are 6 ways to drive from A to B, and for each such way there are 4 ways to drive from B to C.
So, the number of ways to drive from A to C through B is 6 × 4 = 24.
Example 2.
There are four blood types, namely A, B, AB and O. Blood can also be RH(+ve) or RH(-ve). A blood donor can be classified as either male or female. How many different possible ways can a donor have his or her blood labeled?
Solution
There are four possibilities for the blood type, 2 possibilities for the FH factor and 2 possibilities for the gender of donor.
So, the number of ways to label is 4 × 2 × 2 = 16.
Example 3.
There are 3 pictures nails on a wall. If there are 5 different pictures and each nail can hold only one picture, in how many different ways can the pictures be hung on all the nails?
Solution
Any one of the 5 pictures can be chosen for the first nail, then any one from the remaining four for the second, and finally any one from the remaining three for the third.
The number of ways to choose the pictres for individual nails are 5, 4 and 3 respectively.
So, The number of ways to hang the pictures is 5 × 4 × 3 = 60.
Multiplication principle has been applied in solving counting problems in above examples. To introduce another counting principle, consider the following example.
Suppose a manufacturer makes shirts in 5 different sizes S, M, L, XL and XXL. Shirts having sizes S, M and L are made in 4 different designs, while those having sizes XL and XXL are in 3 different designs. If each design has 5 different color schemes, how many different types of shirts are possible to make?
We need to consider the two cases as follows:
(i) Shirts have sizes S, M or L.
(ii) Shirts have sizes XL or XXL.
For the first case, the number of types is 3 × 4 × 5 = 60.
For the second case, the number of types is 2 × 3 × 5 = 30.
So the total number of types must be 60 + 30 = 90.
Notice that the two cases we mentioned above have no arrangement falls into some of these cases. The principle we applied above generally be stated as follows:
Suppose there are k pairwise disjoint cases, into which the elements in a counting problem fall. If there are n1 elements in the first case, n2 elements in the second case, n3 elements in the third case, ..., and nk elements in the kth case, then the number of elements in the problem is
n1 + n2 + n3 + ... + nk.
Example 4.
How many different numbers can be formed using the digits 3, 5, 6, 8 and 9 in such a way that the numbers contain two or three digits without any repetition ?
Solution
The two-digit numbers can be formed in 5 × 4 = 20 ways.
The three-digit numbers can be formed in 5 × 4 × 3 = 60 ways.
So, there are 20 + 60 = 80 different numbers.
Example 5.
How many integers, having digit 5 only once, are there between 0 and 100 ?
Solution
The integers, that we want to form, must be one of the followings:
(i) One-digit integer, namely 5
(ii) Two-digit integers having 5 as tens' digit ( ones' digit may be anyone except 5)
(iii) Two-digit integers having 5 as ones' digit ( tens' digit may be anyone except 0 and 5)
For the first case, the number of integers = 1.
For the second case, the number of integers = 1 × 9 = 9.
For the third case, the number of integers = 8 × 1 = 8.
The required number of integers = 1 + 9 + 8 = 18.
Factorial Notation
The problem in example 3 can be modified as follows, to introduce a notation.
There are 7 picture nails on a wall. If there are 7 different pictures and each nail can hold only one picture, how many different ways can the pictures be hung on all the nails?
By the multiplication principle, the picture can be hung in 7 × 6 × 5 × 4 × 3 × 2 × 1 different ways. The number is the product of the first seven positive integers and can be expressed as 7!. In general, n! ( n factorial or factorial n) stands for the product of the first n positive integers n, (n - 1), (n - 2), ..., 1 if n is a positive integer. We defined 0! to be 1.
n! = n(n - 1) (n - 2) ... 1.
0! = 1.
Notice that
n! = n ⋅ (n - 1)!
n! = n ⋅ (n - 1) ⋅ (n - 2)!
and so on.
For examples, 4! = 4 ⋅ 3 ⋅ 2 ⋅ 1
$$\small{= \underbrace{4 \cdot (3 \cdot 2 \cdot 1)}_{= 4 \cdot 3!} = \underbrace{4 \cdot 3 \cdot (2 \cdot 1).}_{= 4 \cdot 3 \cdot 2!} }$$
Example 6.
Evaluate:
(a) 7!⁄4! ⋅ 3! (b) 6! + 5! - 4!⁄4!
Solution
(a) 7!⁄4! ⋅ 3! = 7 ⋅ 6 ⋅ 5 ⋅ 4!⁄4! ⋅ 3 ⋅ 2 ⋅ 1 = 35
(b) 6! + 5! - 4!⁄4! = 6 ⋅ 5 ⋅ 4! + 5 ⋅ 4! - 4!⁄4!
= (30 + 5 - 1) ⋅ 4!⁄4! = 34
Example 7.
Express 13 ⋅ 12 ⋅ 11⁄3 ⋅ 2 in factorial form.
Solution
13 ⋅ 12 ⋅ 11⁄3 ⋅ 2 = 13 ⋅ 12 ⋅ 11 ⋅ 10!⁄(3 ⋅ 2 ⋅ 1) ⋅ 10!
= 13!⁄3! ⋅ 10!
Exercise 5.1
1. A store sells men's wear. It has 6 kinds of shirts, 4 kinds of pants and 3 kinds of coats. If a man wants to buy a shirt, a pant and a coat,
in how many ways can this be done? (Assume that any choice meets his requirement.)
2. A television news director wishes to use three of the 7 news stories on an evening show. How many possible ways can the program be set up, if the
three stories are to be classified as the lead story, the second story and the closing story?
3. If a garage door opener has a 10-digit keypad, containing 0, 1, 2, ..., 9, and the code to open the door must be a 4-ditit code, how many codes are
possible to create?
4. There are 3 restaurants X, Y and Z, we can go for lunch, in a certain area. Suppose that no two restaurants have the same menu, and the numbers
of choices for appetizer, main dish and dessert available are shown in the table. Find the number of ways to have a lunch, consisting of an appetizer,
a main dish and a dessert.
| Restaurants | No. of Appetizers | No. of Main dishes | No. of Desserts |
| X | 4 | 10 | 2 |
| Y | 3 | 8 | 5 |
| Z | 5 | 12 | 3 |
5. A registeration code consists of two of the 12 different capital letters A, B, C, ..., L, followed by one of the ten digits 0, 1, 2, ..., 9, for example ID5. How many codes are possible to generate:
(a) if the repetition of the letters is allowed?
(b) if the repetition of the letter is not allowed?
(c) if two letters in the codes must be the same?
(d) if two letters are different, but must be both vowels or both consonants?
6. (a) Express 1⁄5⋅4⋅3 in factorial form.
(b) Evaluate 2 ⋅ 9! + 82⋅8!.
7. Prove that 1⁄5! + 1⁄6! + 1⁄7! = 50⁄7!.
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).
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.
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?
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?
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?
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?
5.3 Combinations
Definition. A combination is a selection, in which the order does not matter, of objects from a collection. The number of combinations of n distinct objects taken r at a time is denoted by nCr.The number of permutations of objects is related to the number of corresponding combinations. For example, the combinations of 4 objects A, B, C and D taken 3 at a time and the corresponding permutations are listed in the following table.
| Combination | Permutation | |||||
|---|---|---|---|---|---|---|
| {A, B, C} | ABC | ACB | BAC | BCA | CAB | CBA |
| {A, B, D} | ABD | ADB | BAD | BDA | DAB | DBA |
| {A, C, D} | ACD | ADC | CAD | CDA | DAC | DCA |
| {B, C, D} | BCD | BDC | CBD | CDB | DBC | DCB |
We can see from the table that each combination gives rise to 3!(= 6) permutations. Since there are 4C3 combinations, the number of permutations must be 4C3 ⋅ 3!. Thus, we have
4C3 × 3! = 4P3
Generally, for integers n and r with 0 ≤ r ≤ n,
nCr × r! = nPr
If n and r are integers with 0 ≤ r ≤ n, then
nCr = nPr ⁄ r! = n! ⁄r! (n - r)!
= n(n - 1) (n - 2) ... (n - r + 1)⁄ r (r - 1) (r - 2) ... 1.
Example 14.
In how many ways can a committee of 4 people be selected from a group of 10 people?
Solution
The number of ways is
10C4 = 10 ⋅ 9 ⋅ 8 ⋅ 7 ⁄ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 210.
Example 15.
Evaluate 21C1 , 21C21 , ⋅ 21C19 and 21C2 .
Solution
21C1 = 21
21C21 = 21! ⁄ 21! (21 - 21)!
= 21! ⁄ 21! 0!
= 21! ⁄ 21! ⋅ 1
= 1
21P19 = 21! ⁄19 (21 - 19)!
= 21! ⁄19! 2!
= 21 ⋅ 20 ⋅ 19!⁄19! ⋅ 2 ⋅ 1
= 210
21P2 = 21! ⁄2! (21 - 2)!
= 21! ⁄2! 19!
= 21 ⋅ 20 ⋅ 19!⁄2 ⋅ 1 ⋅ 19!
= 210
We notice that 21C1 = 21, 21C21 = 1 and 21C19 = 21C2 = 21C21-19.
Generally, the integers n and r with 0 ≤ r ≤ n,
nC1 = n, nCn = 1 and nCr = nCn-r
Example 16.
A music class consists of 5 piano players, 7 guitarists and 4 violinists. A band of 1 piano player, 3 guitarists and 2 violinists must be chosen to play at a school concert. In how many ways can the band be chosen?
Solution
From the music class,
1 piano player can be chosen in 5C1 ways,
3 guitarists can be chosen in 7C3 ways, and
2 violinists can be chosen in 4C2 ways.
So, the number of ways to choose a band is
5C1 ⋅ 7C3 ⋅ 4C2 = 5 ⋅ 7 ⋅ 6 ⋅ 5 ⁄3 ⋅ 2 ⋅ 1 ⋅ 4 ⋅ 3⁄2 ⋅ 1
= 1050
Example 17.
Suppose there are 4 black cars and 7 white cars. If all the cars are distinguishable, in how many ways can 3 cars of the same color be chosen?
Solution
To get the same color, the 3 cars must be all black or all white.
Out of 4 black cars, three can be chosen in 4C3 ways.
Out of 7 white cars, three can be chosen in 7C3 ways.
So, the required number of ways is
4C3 ⋅ 7C3 = 4 ⋅ 3 ⋅ 2 ⁄3 ⋅ 2 ⋅ 1 ⋅ 7 ⋅ 6 ⋅ 5⁄3 ⋅ 2 ⋅ 1
= 4 + 35
= 39 .
Example 18.
There are 6 different books. In how many ways can the books be given to 3 children, if the youngest wants to receive 3 books, the elder 1 and the eldest 2 respectively.
Solution
For the youngest child, the books can be chosen in 6C3 = 6 ⋅ 5 ⋅ 4⁄3 ⋅ 2 ⋅ 1 = 20 ways.
For the elder child, the books can be chosen in 3C1 = 3 ways.
For the eldest child, the books can be chosen in 2C2 = 1 ways.
So, the required number of ways is 20 ⋅ 3 ⋅ 1 = 60.
Example 19.
In how many ways can 4 fruits be selected out of 9 fruits, so as always to:
(a) include the largest fruit? (Assume that such a largest fruit exists.)
(b) exclude the smallest fruit? (Assume that such a smallest fruit exists.)
Solution
(a) The largest one is included in every selection. The number of ways only depends on the choice of the other three from the remaining 8 fruits, and hence it is
8C3 = 8 ⋅ 7 ⋅ 6&rasl; 3 ⋅ 2 ⋅ 1 = 56.
(b) Since the smallest one is excluded in every selection, we have to select 4 fruits from the remaining 8 fruits. So the required number ways is
8C4 = 8 ⋅ 7 ⋅ 6 ⋅ 5⁄ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 70 .
Exercise 5.3
1 Show that 12C5 ⋅ 7C4 = 12C4 ⋅ 8C5 .2. There are 10 candle holders, which are fixed in different locations along a line and each can hold only one candle. In how many ways can 7 identical candles be put in these holders?
3. There are three parts in a test. Each of the first two parts contains 5 questions, but the last part only 4. If a student must answer all from the first part, 4 and 3 questions from the second and the last part respectively, in how many ways can this be done?
4. How many games can be played in a 9-team sport league if each team plays all other teams once?
5. How many lines are determined by 8 points, if no 3 such points are collinear?
How many triangles are determined by the points?
6. In how many ways can 4 fruits be selected out of 9 fruits, having different size, so as always to include the largest fruit and exclude the smallest fruit?
5.4 Technique for Some Counting Problems
Permutations with Repetitions
We have solved example 11 about permutations of letters of the word PENCIL containing no repeated letters. Now consider the word KEENNESS. It has 8
letters consisting of one K, three E's, two N's and two S's. We want to determine the number of permutations of these letters. It can be regarded as determining
the number of ways to place these letters in 8 defferent places such that each letter occupies exactly one place.
Firstly, we need to decide which place is to be occupied by the letter K, and this can be done in 8C1 ways. Then there are 7 places left,
among them, we need to decide which places are to be occupied by 3 E's and this can be done in 7C3 ways. After that, the places of 2 N's
can be chosen in 4C2 ways. Finally, there are 2C2 ways to place 2 S's. By the multiplication principle,
the number of permutations of all the letters is
8C1 ⋅ 7C3 ⋅ 4C2 ⋅ 2C2
$$\small{= \dfrac{8!}{1! \cdot \cancel{7!}} \cdot \dfrac{\cancel{7!}}{3! \cdot \cancel{4!}} \cdot \dfrac{\cancel{4!}}{2! \cdot 2!} \cdot 1}$$
= 8!⁄1! 3! 2! 2!.
We can generallize the above result as follows.
Suppose we are given n objects, in which n1 objects are of the first kind, n2 objects are of the second kind, n3 objects are of the third kind, ..., and nr objects are of the rth kind, such that n1 + n2 + ... + nr = n. Then the number of permutations of all these n objects is
n1! ⁄ n1 ! n2! ... nr!
Example 20.
In how many ways can a permutation of all the letters of the word EXCELLENCE be formed?
Solution
In the word EXCELLENCE, there are 10 letters consisting of four E's, one X, two C's, two L's and one N. So, number of ways is
10!⁄4! 1! 2! 2! 1!.
= 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4!⁄4! ⋅ 1 ⋅(2 ⋅ 1) ⋅ (2 ⋅ 1) ⋅ 1
= 10 ⋅ 9 ⋅ 2 ⋅ 7 ⋅ 6 ⋅ 5
= 37800
The Exclusion Principle
The exclusion principle is a way to count what you are interested in by first counting what you are not interested in. This is often needed for counting where a certain property is prohibited (not allowed).Count what you are not interested in and subtract it from the total.
Consider 5-digit codes containing each of the digits 1, 2, 3, 4, 5 exactly once. We have known that the codes can be formed in 5! ways. Suppose we want to know the number of those codes, not ending in 25. On contrary, we count the number of the codes ending in 25. The number of these codes is 3!, since the last two digits is neglected. The resulting number 5! - 3! = 114 is the number of codes not ending in 25.
Example 21.
How many permutations are there of the letters of the word PROGRAM, if they do not end in:
(a) 2R's? (b) MAP?
Solution
In the word PROGRAM, there are 7 letters consisting of one P, two R's, one O, one G, one A and one M, so the number of permutations of the letter is
7! ⁄2! = 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2! ⁄2!
= 2520.
(Hereafter the factor 1! may be omitted in the denominators of such fractions.)
(a) The number of permutations ending in two R's is 5! = 120,
since the two R's are fixed at the end.
The number of permutations not ending in two R's = 2520 - 120 = 2400.
(b) The number of permutations ending in MAP is
4! ⁄2! = 4 ⋅ 3 ⋅ 2! ⁄2!
= 12,
since MAP is fixed at the end, and there are two R's in the remaining 4 letters.
The number of permutations not ending in two R's = 2520 - 12 = 2508.
Counting the Subsets of a Finite Set
Consider a set X = {a, b, c, d, e}. A subset containing r elements, with 0 ≤ r ≤ 5, can be regarded as a combination of 5 elements taking r at a time. Thus there are 5Cr subsets containing r elements. For example, there are 5C4 = 5 subsets containing 4 elements, as listed below.{a, b, c, d}, {a, b, c, e}, {a, b, d, e}, {a, c, d, e}, {b, c, d, e}
So, by the addition principle, the number of all the subsets of X is given by
5C0 + 5C1 + 5C2 + ... + 5C5.
On the other hand, to form a subset, we have to decide which elements of X should be included in that subset. There are two choices for each element of X.
By the multiplication principle, the number ways to form a subset of X is
2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 25.
This means that the set X has 25 subsets.
We have demonstrated the two different techniques for counting the subsets of the set X, and notices that
5C0 + 5C1 + 5C2 + ... + 5C5 = 25.
We can generalize the above result as follows.
nC0 + nC1 + nC2 + ... + nCn = 2n.
Example 22.
If A is a set containing 9 distinct elements, how many subsets of A contain
(a) at most 2 elements?
(b) at least 3 elements?
Solution
(a) The number of permutations containing no element, 1 element and 2 elements are 9C0, 9C1 and 9C2 respectively.
So the number of sets containing at most 2 elements is
9C0 + 9C1 + 9C2 = 1 + 9 + 9 ⋅ 8 ⁄ 2 ⋅ 1
= 1 + 9 + 36
= 46 .
(b) The number of all subsets of S is 29 = 512.
The number of subsets containing at least 3 elements = 512 - 46 = 466.
Miscellaneous Counting Problems
Example 23.How many 4-digit even numbers, greater than 4000, can be formed using the digits 1, 2, 3, 4 and 5, without repeating any digit?
Solution
Since the numbers are greater than 4000, the first digit must be 4 or 5.
Case 1. If the first digit is 4 and the last digit is 2,
The number can be formed in 1 ⋅ 3 ⋅ 2 ⋅ 1 = 6 ways.
Case 2. If the first digit is 5 and the last digit is 2 or 4,
the number can be formed in 1 ⋅ 3 ⋅ 2 ⋅ 2 = 12 ways.
So the number of 4-digit even numbers greater than 4000 is 6 + 12 = 18.
Example 24.
In how many ways can 2 different chemistry books, 4 different mathematics books and 3 different physics books be arranged in a line on a shelf if
(a) 2 chemistry books are to be placed on the left, 4 mathematics books in the middle and 3 physics books on the right?
(b) books of the same subjects are together?
Solution
(a) The number of ways to place chemistry books in the left part is 2! = 2 ⋅ 1 = 2.
The number of ways to place 3 physics books in the right part is 3! = 3 ⋅ 2 ⋅ 1 = 6.
The number of ways to place 4 mathematics books in the middle part is
4! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24.
The required number of ways = 2 ⋅ 24 ⋅ 6 = 288.
(b) The 3 subject wise groups can be placed in 3! = 6 ways, and in each such arrangement the books can be placed in 288 ways (as in part (a)).
The required number of ways to arrange books of the same subject together
= 6 ⋅ 288 = 1728.
Example 25.
How many permutations of the letters S, U, N, D, A, Y are there if the two vowels are placed together?
Solution
If the two vowels U an A unite to form a new single letter, then the number of permutations of the letters is 5! = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 120. Again, U and A can be arranged in 2 different ways as UA and AU in each such permutation.
So the required number of permutations is 120 ⋅ 2 = 240.
Example 26.
Find the number of permutations of all the letters of the word INTERNET in such a way that there are exactly 4 letters between the two T's.
Solution
The letter must be arranged in one of the three forms:
T ★ ★ ★ ★ T ★ ★ ★ T ★ ★ ★ ★ T ★ ★ ★ T ★ ★ ★ ★ T
in which the 6 letters (2 N's, 2 E's, 1 I and 1 R) other than 2 T's are to be put in star (★) positions. For each such form, the number of ways to put the six letters in star (★) positions is
6! ⁄2! ⋅ 2! = 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2! ⁄2! ⋅ 2 ⋅ 1
= 180.
So the required number of permutations is 3 ⋅ 180 = 540.
Exercise 5.4
1. Find the number of permutations of the letters of each of the following words.
(i) INFINITY (ii) PINEAPPLE (iii) ACCEPTABLE
2. Password for a mobile payment system are to consist of 6 digits from a set of digits 0, 1, 2, ... , 9 and assume that there is no other restriction.
How many such passwords have repeated digits?
3. A building has 10 windows in front. What is the number of signals that can be given, by having one or more of the windows open?
4. At a burger shop, 3 different types of buns, 7 types of cheeses and 5 types of vegetables are available. Assume that a burger may contain no cheese or no
vegetable. In how many ways can different types of burgers be ordered if a person must have a bun, and may have at most 2 types of cheeses and any number of
types vegetables.
5. How many different 4-digit codes can be formed using all the digits 0, 1, 2, 3 if
(i) There is no restriction?
(ii) repetation is not allowed?
(iii) repetation is not allowed, and 0 is either the first or the last digit?
6. Using the letters of the word EQUATION without repetations, how many 4-letter codes can be formed:
(i) Starting with T and ending with N?
(ii) starting and ending with a consonant?
(iii) with vowels only?
(iv) if it contains 3 consonants?
7. Three brothers and three sisters are lining up to be photographed. How many arrangements are there
(i) with three sisters standing together?
(ii) if brothers and sisters are in alternating positions?
8. How many permutations of the letters H, E, X, A, G, O, N are there if
(i) the 3 vowels are placed together?
(ii) the 3 vowels are not placed together?
(iii) consonants and vowels are not apear alternately?
9. Find the number of permutations of all the letters of the word PENGUIN in such a way that there are exactly 3 letters between 2 N's.
10. Find the number of permutations of all the letters of the word STRESSLESS in such a way that there are exactly 5 letters between:
(i) 2 E's. (ii) 2 S's.