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.

After studying this lesson, you will be able to :

· find out the number of ways in which a given number of objects can be arranged;

· state the Fundamental Principle of Counting;

· define n! and evaluate it for defferent values of n;

· state that permutation is an arrangement and write the meaning of n P

COUNTING PRINCIPLE :

Let us now solve the problem mentioned in the introduction. We will writet1, t2 to denote trains from Bangalore to Itarsi and T1, T2, T3, for the trains from Itarsi to Allahabad. Suppose I take t1 to travel from Bangalore to Itarsi. Then from Itarsi Ican take T1 or T2 or T3. So the possibilities are t1T1, t2T2 and t3T3 where t1T1 denotes travel from Bangalore to Itarsi by t1 and travel from Itarsi to Allahabad by T1. Similarly, if I take t2 to travel from Bangalore to Itarsi, then the possibilities are t2T1, t2T2 and t2T3. Thus, in all there are 6 (2 x 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 verytedious. 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 m x n ways.

EX. 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 9  18 multiples of 5 from 10 to 95.

EX. 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.

 Number of possible bus routes are 99 6  594.

Let us now state the General Counting Principle

If there are n events and if the first event can occur in m1 ways, the second event can occur in m2 ways after the first event has occured, the third event can occur in m3 ways after the second event has ocurred, and so on, then all the n events can occur in m1 x m2   mn 1  mn ways.

EX. 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 place D 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 to D 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 3 4 23 ways = 72 ways.

PERMUTATION :

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. Geographybook 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 or GHM. Similarly, corresponding to HG, you have three other ways ofarrangingthe books. So, bythe Counting Principle, youcan arrange Mathematics, Geography and History books in 3 2 ways = 6 ways.

By permutation we meanan 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 n 1, 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 3 21 permutations of 3 objects. It may be that, there are n  (n 1)  (n  2) ... 2 1 permutations of n objects. In fact, it is so, as you will see when we prove the following result.

Evaluate (a) 3! (b) 2! + 4! (c) 2! 3!

EX. 7) 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 OBJECT OUT OF N OBJECT

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 anyone 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 5 4  3 ie.60 ways.

More generally, suppose you have to arrange r objects out of n objects. In how manyways can you do it? Let us view this in the following way. Suppose you have n objects and you have to arrange r of these in r boxes, one object in each box.

EX. 8) 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 alloting 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.

 The beds can be allotted in........

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 S1, S2, S3, S4. Then you can choose 2 pairs in the following ways :

Now as you maywant 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 4P  12 ways. But note that each choice of 2 sets gives us

two ways of wearing 2 sets out of 4 sets as shown below :