MTH5P1: Permutations and combinations

This unit explains Permutations and combinations

The other day, I wanted to travel from Bangalore to Allahabad by train. There is no direct train from Bangalore to Allahabad, but there are trains from Bangalore to Itarsi and from Itarsi to Allahabad. From the railway timetable I found that there are two trains from Bangalore to Itarsi and three trains from Itarsi to Allahabad. Now, in how many
ways can I travel from Bangalore to Allahabad?

There are counting problems which come under the branch of Mathematics called combinatorics.
Suppose you have five jars of spices that you want to arrange on a shelf in your kitchen.

You would like to arrange the jars, say three of them, that you will be using often in a more accessible position and the remaining two jars in a less accessible position. In how many ways can you do it?

In another situation suppose you are painting your house. If a particular shade or colour is not available, you may be able to create it by mixing different colours and shades.

While creating new colours this way, the order of mixing is not important. It is the combination or choice of colours that determine the new colours; but not the order of mixing.

To give another similar example, when you go for a journey, you may not take all your dresses with you. You may have 4 sets of shirts and trousers, but you may take only 2 sets.

In such a case you are choosing 2 out of 4 sets and the order of choosing the sets doesn’t matter. In these examples, we need to find out the number of choices in which it can be done.
In this lesson we shall consider simple counting methods and use them in solving such simple counting problems.

COUNTING PRINCIPLE

Let us now solve the problem mentioned in the introduction. We will write to denote trains from Bangalore to Itarsi and for the trains from Itarsi to Allahabad. Suppose I take to travel from Bangalore to Itarsi. Then from Itarsi I can take So the possibilities are denotes travel from Bangalore to Itarsi by and travel from Itarsi to Allahabad by Similarly, if I take to travel from Bangalore to Itarsi, then the
possibilities are Thus, in all there are 6(2´3) possible ways of travelling from Bangalore to Allahabad.

Here we had a small number of trains and thus could list all possibilities. Had there been 10 trains from Bangalore to Itarsi and 15 trains from Itarsi to Allahabad, the task would have been very tedious. Here the Fundamental Principle of Counting or simply the Counting Principle comes in use :

If any event can occur in m ways and after it happens in any one of these ways, a second event can occur in n ways, then both the events together can occur in mxn ways.

Example 7.1 How many multiples of 5 are there from 10 to 95 ?
Solution : As you know, multiples of 5 are integers having 0 or 5 in the digit to the extreme right (i.e. the unit’s place).
The first digit from the right can be chosen in 2 ways.
The second digit can be any one of 1,2,3,4,5,6,7,8,9.
i.e. There are 9 choices for the second digit.
Thus, there are 2 x 9 =18 multiples of 5 from 10 to 95.

Example 7.2 In a city, the bus route numbers consist of a natural number less than 100,
followed by one of the letters A,B,C,D,E and F. How many different bus routes are possible?
Solution : The number can be any one of the natural numbers from 1 to 99.
There are 99 choices for the number.
The letter can be chosen in 6 ways.

Therefore: Number of possible bus routes are 99 x 6 = 594.

Example 7.3 There are 3 questions in a question paper. If the questions have 4,3 and 2
solutionsvely, find the total number of solutions.
Solution : Here question 1 has 4 solutions,
question 2 has 3 solutions
and question 3 has 2 solutions.
Therefore; By the multiplication (counting) rule,
total number of solutions = 4x3x2
= 24

Example 7.4. Consider the word ROTOR. Whichever way you read it, from left to right or
from right to left, you get the same word. Such a word is known as palindrome. Find the maximum possible number of 5-letter palindromes.
Solution : The first letter from the right can be chosen in 26 ways because there are 26 alphabets

Having chosen this, the second letter can be chosen in 26 ways
Therefore; The first two letters can chosen in 26×26 = 676 ways
Having chosen the first two letters, the third letter can be chosen in 26 ways.
Therefore; All the three letters can be chosen in 676×26 =17576 ways.
It implies that the maximum possible number of five letter palindromes is 17576 because the
fourth letter is the same as the second letter and the fifth letter is the same as the first letter.

Note : In Example 7.4 we found the maximum possible number of five letter palindromes. There cannot be more than 17576. But this does not mean that there are 17576 palindromes. Because some of the choices like CCCCC may not be meaningful words in the English language.

Example 7.5 How many 3-digit numbers can be formed with the digits 1,4,7,8 and 9 if the
digits are not repeated.
Solution : Three digit number will have unit’s, ten’s and hundred’s place.
Out of 5 given digits any one can take the unit’s place.
This can be done in 5 ways. … (i)
After filling the unit’s place, any of the four remaining digits can take the ten’s place.
This can be done in 4 ways. … (ii)
After filling in ten’s place, hundred’s place can be filled from any of the three remaining digits.

This can be done in 3 ways. … (iii)
Therefore; By counting principle, the number of 3 digit numbers = 5x4x3 = 60
Let us now state the General Counting Principle

If there are n events and if the first event can occur in ways, the second event can occur in ways after the first event has occurred, the third event can occur in ways after the second event has occurred, and so on, then all the n events can occur in

Example 7.6 Suppose you can travel from a place A to a place B by 3 buses, from place B to place C by 4 buses, from place C to place D by 2 buses and from placeD to place E by 3 buses. In how many ways can you travel from A to E?
Solution : The bus from A to B can be selected in 3 ways.
The bus from B to C can be selected in 4 ways.
The bus from C toD can be selected in 2 ways.
The bus from D to E can be selected in 3 ways.
So, by the General Counting Principle, one can travel from A to E in 3x4x2x3 ways = 72 ways.

PERMUTATIONS

Suppose you want to arrange your books on a shelf. If you have only one book, there is only one way of arranging it. Suppose you have two books, one of History and one of Geography.
You can arrange the Geography and History books in two ways. Geography book first and the History book next,GH or History book first and Geography book next;HG. In other words, there are two arrangements of the two books.
Now, suppose you want to add a Mathematics book also to the shelf. After arranging History and Geography books in one of the two ways, say GH, you can put Mathematics book in one of the following ways:MGH,GMH orGHM. Similarly, corresponding toHG, you have three other ways of arranging the books. So, by the Counting Principle, you can arrange Mathematics, Geography and History books in 3×2 ways = 6 ways.

By permutation we mean an arrangement of objects in a particular order. In the above example, we were discussing the number of permutations of one book or two books.
In general, if you want to find the number of permutations of n objects how can you do it? Let us see if we can find an answer to this.

Similar to what we saw in the case of books, there is one permutation of 1 object, 2×1
permutations of two objects and 3x2x1 permutations of 3 objects. It may be that, there are
n x (n -1)x (n – 2)x…x 2 x 1 permutations of n objects. In fact, it is so, as you will see when we prove the following result.

Theorem 7.1 The total number of permutations of n objects is n (n – 1) ….2.1.
Proof : We have to find the number of possible arrangements of n different objects.
The first place in an arrangement can be filled in n different ways. Once it has been done, the second place can be filled by any of the remaining (n–1) objects and so this can be done in (n–1) ways. Similarly, once the first two places have been filled, the third can be filled in (n–2) ways and so on.

The last place in the arrangement can be filled only in one way, because in this case we are left with only one object.
Using the counting principle, the total number of arrangements of n different objects is

n(n -1)(n – 2) …….. 2.1. …..(7.1)

The product n (n – 1) … 2.1 occurs so often in Mathematics that it deserves a name and notation. It is usually denoted by n! (or by

n! = n (n – 1) … 3.2.1

Here is an example to help you familiarise yourself with this notation.

Example 7.7 Evaluate (a) 3! (b) 2! + 4! (c) 2!x3!
Solution : (a) 3!= 3x2x1= 6
(b) 2! = 2×1 = 2
4! = 4x3x2x1 = 24

Of course, the above relation is valid only for because 0! has not been defined so far. Let us see if we can define 0! to be consistent with the relation. In fact, if we define 0! = 1 … (7.3) then the relation 7.2 holds for n = 1 also.

Example 7.8 Suppose you want to arrange your English, Hindi, Mathematics, History,
Geography and Science books on a shelf. In how many ways can you do it?
Solution : We have to arrange 6 books.
The number of permutations of n objects is n! = n. (n – 1) . (n – 2) … 2.1
Here n = 6 and therefore, number of permutations is 6.5.4.3.2.1 = 720

PERMUTATION OF r OBJECTS OUT OF n OBJECTS

Suppose you have five story books and you want to distribute one each to Asha, Akhtar and Jasvinder. In how many ways can you do it? You can give any one of the five books to Asha and after that you can give any one of the remaining four books to Akhtar. After that, you can give one of the remaining three books to Jasvinder. So, by the Counting Principle, you can distribute the books in 5x4x3 ie.60 ways.
More generally, suppose you have to arranger objects out of n objects. In how many ways can you do it? Let us view this in the following way. Suppose you haven objects and you have to arrange r of these in r boxes, one object in each box.

Suppose there is one box. r = 1. You can put any of the n objects in it and this can be done in n ways. Suppose there are two boxes. r = 2. You can put any of the objects in the first box and after that the second box can be filled with any of the remaining n – 1 objects. So, by the counting principle, the two boxes can be filled inn (n – 1) ways. Similarly, 3 boxes can be filled in n (n – 1) (n – 2) ways.

In general, we have the following theorem.

Theorem 7.2 The number of permutations of r objects out of n objects is
n (n–1)…..(n – r + 1).
The number of permutations of r objects out of n objects is usually denoted by

Proof : Suppose we have to arrange r objects out of n different objects. In fact it is equivalent to filling r places, each with one of the objects out of the given n objects.

The first place can be filled in n different ways. Once this has been done, the second place can be filled by any one of the remaining (n–1) objects, in (n–1) ways. Similarly, the third place can be filled in (n – 2) ways and so on. The last place, the rth place can be filled in [n–(r–1)] i.e.
(n–r+1) different ways. You may easily see, as to why this is so.
Using the Counting Principle, we get the required number of arrangements of r out of n objects
is n (n -1) (n – 2)…………(n – r +1)

Example 7.10 If you have 6 New Year greeting cards and you want to send them to 4 of your friends, in how many ways can this be done?
Solution : We have to find number of permutations of 4 objects out of 6 objects.

This number is

Consider the formula for This can be obtained by removing the terms n – r, n – r – 1,…,2, 1 from the product for n!. The product of these terms is (n – r) (n – r – 1) …2.1, i.e., (n – r)!.

So, using the factorial notation, this formula can be written as follows :

PERMUTATIONS UNDER SOME CONDITIONS

We will now see examples involving permutations with some extra conditions.
Example 7.13 Suppose 7 students are staying in a hall in a hostel and they are allotted 7 beds. Among them, Parvin does not want a bed next to Anju because Anju snores. Then, in how many ways can you allot the beds?
Solution : Let the beds be numbered 1 to 7.
Case 1 : Suppose Anju is allotted bed number 1.
Then, Parvin cannot be allotted bed number 2.
So Parvin can be allotted a bed in 5 ways.
After allotting a bed to Parvin, the remaining 5 students can be allotted beds in 5! ways.
So, in this case the beds can be allotted in 5×5!ways = 600 ways.
Case 2 : Anju is allotted bed number 7.
Then, Parvin cannot be allotted bed number 6
As in Case 1, the beds can be allotted in 600 ways.

Case 3 : Anju is allotted one of the beds numbered 2,3,4,5 or 6.
Parvin cannot be allotted the beds on the right hand side and left hand side of Anju’s bed. For example, if Anju is allotted bed number 2, beds numbered 1 or 3 cannot be allotted to Parvin.
Therefore, Parvin can be allotted a bed in 4 ways in all these cases.
After allotting a bed to Parvin, the other 5 can be allotted a bed in 5! ways.
Therefore, in each of these cases, the beds can be allotted in 4×5! = 480 ways.
Therefore;  The beds can be allotted in
(2×600 + 5×480)ways = (1200 + 2400)ways = 3600 ways.

Example 7.14 In how many ways can an animal trainer arrange 5 lions and 4 tigers in a row so that no two lions are together?
Solution : They have to be arranged in the following way :

The 5 lions should be arranged in the 5 places marked ‘L’.
This can be done in 5! ways.
The 4 tigers should be in the 4 places marked ‘T’.
This can be done in 4! ways.
Therefore, the lions and the tigers can be arranged in 5!x4! ways = 2880 ways.

Example 7.15 There are 4 books on fairy tales, 5 novels and 3 plays. In how many ways can
you arrange these so that books on fairy tales are together, novels are together and plays are
together and in the order, books on fairy tales, novels and plays.
Solution : There are 4 books on fairy tales and they have to be put together.
They can be arranged in 4! ways.
Similarly, there are 5 novels.
They can be arranged in 5! ways.
And there are 3 plays.
They can be arranged in 3! ways.
So, by the counting principle all of them together can be arranged in 4!x5!x3! ways = 17280
ways.

Example 7.16 Suppose there are 4 books on fairy tales, 5 novels and 3 plays as in Example 7.15. They have to be arranged so that the books on fairy tales are together, novels are together and plays are together, but we no longer require that they should be in a specific order. In how many ways can this be done?

Solution : First, we consider the books on fairy tales, novels and plays as single objects.
These three objects can be arranged in 3!ways = 6 ways.
Let us fix one of these 6 arrangements.
This may give us a specific order, say, novels ® fairy tales ® plays.
Given this order, the books on the same subject can be arranged as follows.
The 4 books on fairy tales can be arranged among themselves in 4! = 24 ways.
The 5 novels can be arranged in 5! = 120 ways.
The 3 plays can be arranged in 3! = 6 ways.
For a given order, the books can be arranged in 24 x 120 x 6 =17280 ways.
Therefore, for all the 6 possible orders the books can be arranged in 6×17280 =103680 ways.

Example 7.17 In how many ways can 4 girls and 5 boys be arranged in a row so that all the four girls are together?
Solution : Let 4 girls be one unit and now there are 6 units in all.
They can be arranged in 6! ways.
In each of these arrangements 4 girls can be arranged in 4! ways.
Therefore; Total number of arrangements in which girls are always together

Example 7.18 How many arrangements of the letters of the word ‘BENGALI’ can be made
(i) if the vowels are never together.
(ii) if the vowels are to occupy only odd places.
Solution : There are 7 letters in the word ‘Bengali; of these 3 are vowels and 4 consonants.
(i) Considering vowels a, e, i as one letter, we can arrange 4+1 letters in 5! ways in each of which vowels are together. These 3 vowels can be arranged among themselves in 3! ways.

(ii) There are 4 odd places and 3 even places. 3 vowels can occupy 4 odd places in ways and 4 constants can be arranged in ways.

COMBINATIONS
Let us consider the example of shirts and trousers as stated in the introduction. There you have 4 sets of shirts and trousers and you want to take 2 sets with you while going on a trip. In how many ways can you do it?

Let us denote the sets by Then you can choose two pairs in the following ways :

[Observe that is the same as So, there are 6 ways of choosing the two sets that you want to take with you. Of course, if you had 10 pairs and you wanted to take 7 pairs, it will be much more difficult to work out the number of pairs in this way.

Now as you may want to know the number of ways of wearing 2 out of 4 sets for two days, say Monday and Tuesday, and the order of wearing is also important to you. We know from section 7.3, that it can be done in ways. But note that each choice of 2 sets gives us two ways of wearing 2 sets out of 4 sets as shown below :

Thus, there are 12 ways of wearing 2 out of 4 pairs.
This argument holds good in general as we can see from the following theorem.

Theorem 7.3 Let be an integer and Let us denote the number of ways of
choosing r objects out of n objects by

Proof : We can choose r objects out of n objects in ways. Each of the r objects chosen can be arranged in r! ways. The number of ways of arranging r objects is r!. Thus, by the counting principle, the number of ways of choosing r objects and arranging the r objects chosen can be done in ways. But, this is precisely In other words, we have

Dividing both sides byr!, we get the result in the theorem.
Here is an example to help you to familiarise yourself with

Example 7.19 Evaluate each of the following :

Example 7.20 Find the number of subsets of the set {1,2,3,4,5,6,7,8,9,10,11} having 4 elements.
Solution : Here the order of choosing the elements doesn’t matter and this is a problem in combinations.
We have to find the number of ways of choosing 4 elements of this set which has 11 elements.
By relation (7.6), this can be done in

Example 7.21 12 points lie on a circle. How many cyclic quadrilaterals can be drawn by
using these points?
Solution : For any set of 4 points we get a cyclic quadrilateral. Number of ways of choosing 4
points out of 12 points is Therefore, we can draw 495 quadrilaterals.
Example 7.22 In a box, there are 5 black pens, 3 white pens and 4 red pens. In how many
ways can 2 black pens, 2 white pens and 2 red pens can be chosen?
Solution : Number of ways of choosing 2 black pens from 5 black pens

Number of ways of choosing 2 white pens from 3 white pens

Number of ways of choosing 2 red pens from 4 red pens

Therefore; By the Counting Principle, 2 black pens, 2 white pens, and 2 red pens can be chosen in
10´3´6 =180 ways.
Example 7.23 A question paper consists of 10 questions divided into two parts A and B.
Each part contains five questions. A candidate is required to attempt six questions in all of which at least 2 should be from part A and at least 2 from part B. In how many ways can the candidate select the questions if he can answer all questions equally well?
Solution : The candidate has to select six questions in all of which at least two should be from
Part A and two should be from Part B. He can select questions in any of the following ways :

If the candidate follows choice (i), the number of ways in which he can do so is

If the candidate follows choice (ii), the number of ways in which he can do so is

Similarly, if the candidate follows choice (iii), then the number of ways in which he can do so is

Therefore, the candidate can select the question in 50 + 100 + 50 = 200 ways.
Example 7.24 A committee of 5 persons is to be formed from 6 men and 4 women. In how
many ways can this be done when
(i ) at least 2 women are included?
(ii ) at most 2 women are included?
Solution : (i) When at least 2 women are included.
The committee may consist of

Example 7.25 The Indian Cricket team consists of 16 players. It includes 2 wicket keepers and 5 bowlers. In how many ways can a cricket eleven be selected if we have to select 1 wicket keeper and at least 4 bowlers?
Solution : We are to choose 11 players including 1 wicket keeper and 4 bowlers or, 1 wicket keeper and 5 bowlers.
Number of ways of selecting 1 wicket keeper, 4 bowlers and 6 other players

Number of ways of selecting 1 wicket keeper, 5 bowlers and 5 other players

SOME SIMPLE PROPERTIES OF

In this section we will prove some simple properties of which will make the computations of these coefficients simpler. Let us go back again to Theorem 7.3. Using relation 7.7 we can rewrite the formula for as follows :

since we have defined 0! = 1.
The formula given in Theorem 7.3 was used in the previous section. As we will see shortly, the formula given in Equation 7.8 will be useful for proving certain properties of

This means just that the number of ways of choosing r objects out of n objects is the same as the number of ways of not choosing(n – r) objects out of n objects. In the example described in the introduction, it just means that the number of ways of selecting 2 sets of dresses is the same as the number of ways of rejecting 4 – 2 = 2 dresses. In Example 7.20, this means that the number of ways of choosing subsets with 4 elements is the same as the number of ways of rejecting 8 elements since choosing a particular subset of 4 elements is equivalent to rejecting its complement, which has 8 elements.
Let us now prove this relation using Equation 7.8. The denominator of the right hand side of this equation is r! (n – r)!. This does not change when we replace r by n – r.

The numerator is independent of r. Therefore, replacing r by n – r in Equation 7.8 we get result.

How is the relation 7.9 useful? Using this formula, we get, for example, s the same as The second value is much more easier to calculate than the first one.

Example 7.27 Evaluate :

Solution : (a) From relation 7.9, we have

There is another relation satisfied by which is also useful. We have the following relation:

Example 7.28 Evaluate :

To understand the relation 7.10 better, let us go back to Example 7.20 In this example let us calculate the number of subsets of the set, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. We can subdivide them into two kinds, those that contain a particular element, say 1, and those that do not contain 1.

The number of subsets of the set having 4 elements and containing 1 is the same as the number of subsets of {2, 3, 4, 5, 6, 7, 8, 9, 10, 11} having 3 elements. There are such subsets.

The number of subsets of the set having 4 elements and not containing 1 is the same as the number of subsets of the set {2,3,4,5,6,7,8,9,10,11,} having 4 elements. This is So, the number of subsets of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} having four elements is But, this is as we have seen in the example. So The same argument works for the number of r–element subsets of a set with n elements.
This relation was noticed by the French Mathematician Blaise Pascal and was used in the so called Pascal Triangle, given below.

The first row consists of single element The second row consists of and

From the third row onwards, the rule for writing the entries is as follows. Add consecutive elements in the previous row and write the answer between the two entries. After exhausting all possible pairs, put the number 1 at the beginning and the end of the row. For example, the third row is got as follows. Second row contains only two elements and they add up to 2. Now, put 1 before and after 2. For the fourth row, we have 1 + 2 = 3, 2 + 1 = 3. Then, we put 1 + 2 = 3, 2 + 1 = 3. Then we put 1 at the beginning and the end. Here, we are able to calculate, for example,

by using the relation 7.10. The important thing is we are able to do it using addition alone.

The numbers occur as coefficients in the binomial expansions, and therefore, they are also called binomial coefficients as we will see in lesson 8. In particular, the property 7.10 will be used in the proof of the binomial theorem.

PROBLEMS INVOLVING BOTH PERMUTATIONS AND COMBINATIONS
So far, we have studied problems that involve either permutation alone or combination alone.
In this section, we will consider some examples that need both of these concepts.

Example 7.30 There are 5 novels and 4 biographies. In how many ways can 4 novels and 2 biographies can be arranged on a shelf ?
Solution : 4 novels can be selected out of 5 in ways. 2 biographies can be selected out of

Number of ways of arranging novels and biographies

After selecting any 6 books (4 novels and 2 biographies) in one of the 30 ways, they can be arranged on the shelf in 6! = 720 ways.

By the Counting Principle, the total number of arrangements = 30´720 = 21600
Example 7.31 From 5 consonants and 4 vowels, how many words can be formed using 3 consonants and 2 vowels ?

Solution : From 5 consonants, 3 consonants can be selected in ways.

From 4 vowels, 2 vowels can be selected in ways.

Now with every selection, number of ways of arranging 5 letters is

Fundamental principle of counting states.
If there are n events and if the first event can occur in ways, the second event can occur in  ways after the first event has occurred, the third event can occur in ways after the second event has occurred and so on, then all then events can occur in

The number of permutations of n objects taken all at a time is n!

ASSIGNMENT : Permutations and combinations Assignment MARKS : 30  DURATION : 2 hours

 

Welcome to FAWE

STEM Elearning

We at FAWE have built this platform to aid learners, trainers and mentors get practical help with content, an interactive platform and tools to power their teaching and learning of STEM subjects, more

How to find your voice as a woman in Africa

top
© FAWE, Powered by: Yaaka DN.
X