Permutations & Combinations: Introduction

Home»Permutations & Combinations: Introduction

In Permutations & Combinations, we are only concerned about the number of ways to accomplish a task which may be itself composed of several sub-tasks.

The entire subject is based on the Fundamental Principle of Counting(FPC).

The basics of Permutations and combinations are counting, it is not concerned in particular ways to accomplish a task.


Independent events: Two events are independent if ocuurence of one cannot affect the occurence of other or the outcome of the event A has no effect on the outcome of event B.


We often get confuse between product rule and sum rule while solving the problems of permutation and combination. Below, i will make it easy for you:



Product rule: If a process can be completed by a few sub sequancial independent processes, number of ways of doing the process will be equal to product of number of ways of doing the sub-processes.

e.g.  We need to go from a station A to station C and we have to find the number of ways to do this task. Firstly, we observe from the figure that there are 3 ways to go to B from A.

If we follow any one path from A to B it will not affect our decision to choose the path from B to C. So these two events i.e. to choose the path from A to B and from B to C are independent events. 

Further, for every path from A to B there are 4 choices from B to C. We have 3 choices from A to B and for every choice there are 4 choices from B to C

Therefore, total number of ways to reach C from A = no. of paths from A to B * no. of paths from B to C
                                                                             = 3 * 4 
                                                                             = 12

The working of product rule is based on above example. 
If there are several sub-tasks and suppose a sub-task can be done in n1 ways and second sub-task can be done in n2 ways and for every choice of completing a sub task you find n2 number of ways to do other sub-task then you need to put multiplication sign between the number of ways of these two tasks i.e. 


Product: Remeber for every choice of a path for a sub task you have  equal number of choices of paths for second sub task.

e.g. Find the number of 4-digit words form by the letters 'PALM' ?

first we can pick any one of 4 letters i.e. we have 4 choices, after choosing one letter now  3 letters left so 3 choices , then 2 and finally only 1 choice left.

so, for four letter words , choices for every blanks are:

4   3     1

now for every letter choose in first place we have 3 choices in 2nd place and for every letter of second place we have 2 choices in 3rd place. So these are independent events and we need to take product to get required number of ways:

4*3*2*1
= 24


Mutually Exclusive Events: Occurence of one event prevents the occurence of others or If event A happens, B cannot and vice-versa.


Sum Rule: The process can be completed by parallel mutually exclusive sub-processes, number of doing the process will be the sum of number of ways of doing the sub process.

In the above figure there are two more different ways directly from A to C. So, if you choose one parallel path you cannot choose another path of A to B to C. So, these are mutually exclusive events so we will apply sum rule.

So, total number of ways to reach C from A = 3*4 + 1 + 1 = 14


PROBLEMS:

Now, in this topic problems are based on 

*Order Important ( Arrangement )
*Order Unimportant (Selection)


*No Repetition
*Repetition


So, there are basically four types of problems:

1. Arrangement without Repetition 

2. Selection without Repetition

3. Arrangement with infinite Repetition, 

4. Selection with infinite Repetition,  or 

 

Permutation: Arrangement without repetition


Permutation: Permutations enables us to find the numer of ways of arranging a set of objects, some of which may be identical. Any particular arrangement of the set of objects will be one permutation out of all the possible permutations. In permutation order is important as it is basically the number of ways of arrangement of a set of objects.


1. Arrangement without Repetition:

a. Order is important


Sometimes we have to arrange objects where order is important 
e.g. 1,2,3
if we place these three numbers in different orders we get different results as 123 and 321. Therefore, here order is important.

b. Without Repetition ( Objects are distinct )

i.e. without repetition means in a particular arrangement all objects are different

e.g. here some objects are repeated 112 , 222, 333, 121 


Now take an example, suppose there are five letters a, b , c , d , e and we have to make five letters words from these 5 letters. So, the question is what are the number of words we can form having distinct letters or what are the number of ways to arrange 5 letters without repetition.

There are five places and we have to put these five distinct letters to these five places

First place can be filled by 5 ways ( i.e. a or b or c or d or e )

when we choose a letter for first place, since repetition is not allowed we have left with only 4 letters now and 2nd place can be filled by 4 ways. Similarly 3rd place can be filled by 3 ways , 4th place by 2 ways and 5th place only by 1 way.


Remember product rule, for every choice of 1st place we have 4 ways to choose the letter for 2nd place and so on 

Therefore, total number of arrangements =    = 120

5! called as 5 factorial 

and , 5! = 5*4*3*2*1

7! = 7*6*5*4*3*2*1

So if we generalise the above example i.e. we have 
to arrange n distinct objects, the number of ways = n!

Now if we have to make three letter words out of five letters a,b,c,d and e

So we have three places, first place can be filled by 5 ways, 2nd by 4 ways and 3rd or last by 4 ways,

Therefore, total number of ways or total number of three letter words having different letters formed by the given 5 letters = 5 * 4 * 3 = 60





  - Number of ways of Arranging 'n' things, taken 'r' at a time

So, there are r places and n objects,

1st place can be filled by n ways, 2nd by (n - 1), 3rd by (n - 2) and so on. And rth place can be filled by (n - r + 1) ways,

therefore,

 

or, 

or, 
 



Ques: How many words can be made of letters COURTESY which began with C and end with Y ?


Sol: Since first letter C and last letter Y are fixed. Therefore we have to permutate only six letters between C and Y,

C O U R T E S Y

Therefore, total number of words =  = 6! = 720 



Ques: Of 8 balls how many arrangement can be made in which 3 given balls are not all together ?



Sol: First we have to find the number of ways in which 3 given balls are together and then we subtract it by the total number of ways of arrangind these 8 balls, so we will get the number of ways in which 3 given balls are not all together.

Number of ways in which 3 given balls are not all together = Total Number of ways - Number of ways in which 3 given balls are together


for total number of ways i.e. arranging 8 balls in 8 places

Total number of ways =  = 8! 

for number of ways in which 3 given balls are together, we tie the given balls and treat them as ONE ball, now we have 6 balls and total number of ways to arrange them is  , 

But we can also arrange these 3 given balls in  ways ,

Therefore, 
Number of ways in which 3 given balls are together =  = 6!.3!


Therefore,
Number of ways in which 3 given balls are not all together = 8! - 6!.3!


Ques: A self conains 20 books 4 are single volume and others forms sets of 8, 5 and 3 volumes respectively. Find how many ways the books can arrange in the self so that the volume of these sets are together and will be in order ?


Sol: There are 20 books and there are also three sets of books having 8, 5 and 3 volumes.

Since we have to place the volumes of these sets together, therefore we have to treat the bundle of the same volumes of sets as one book.

Therefore, now we have to place 7 books in 7 places

Therefore, number of ways to place these books in self =  = 7!

but these volumes should be in order and can place in two ways i.e. in descending order or ascending order

e.g. vol. 1  vol. 2  vol. 3
or vol. 3 vol. 2 vol. 1

and there are three sets having volumes,

So, total number of ways these books in shelf having the volumes are together and in order = 7!*2*2*2 

Posted by: Abhijat Srivastava. in Maths | Date: 17/03/2016

Share this article

Other articles

Back to article listing

Find a Great Teacher

Tell us your learning needs in detail and get immediate response from qualified tutors

Terms & conditions agreed
Ask a Question
Top