Permutations & Combination : Fundamental Principles Of Counting - Ravi Handa
handakafunda last edited by
I have often seen students struggle with the topic – ‘Permutation & Combination’. As a matter of fact, I have even seen some faculties shy away from conducting those classes. This fear, for the lack of a better word, stems from the fact that the options are often very confusing. Even if you make a mistake, miss out a case, take a wrong factorial – the answer you obtain is invariably in the options. One of the most basic tips that I would like to give you is this – if you are not able to solve the question, look at the answer and then try to figure out the logic behind the answer.
I think one of the main reasons behind lot of students making mistakes in questions based on ‘Permutation & Combination’ is the fact that they start the chapter with the two formulas which are given below:
nPr = n! / (n - r)!
nCr = n! / [(n - r)! r!]
It is wrong to start off with these formulas. It is very important to understand the logic behind these formulas. And that is precisely what I wish to achieve with the help of this post by talking about ‘Fundamental Principles of Counting’.
Let us start with a very basic idea:
Rule of Product: If there are ‘m’ ways to do something and there are ‘n’ ways to do another, then the total number of ways of doing both things is ‘m x n’.
To elaborate this with an example, assume that you have 4 T-shirts and 2 Jeans. The total number of ways in which you can decide what to wear is 4 x 2 = 8.
In case you are wondering ‘Why is it 8?’, the logic is pretty simple. With every T-shirt, you have a choice between the two Jeans. This is illustrated below:
Choices of dress: T1J1, T1J2, T2J1, T2J2, T3J1, T3J2, T4J1 and T4J2
An assumption here is that you are not bothered with trivialities such as dressing-sense. Because if you are, then the decision of which jeans to wear with respect to a t-shirt will not be an independent decision. The formula of ‘m x n’ ways is valid if and only if the decisions are independent of each other.
In case the decisions are not independent, then you would have to take care of the restrictions which are applicable.
Rule of Sum: If there are ‘m’ ways to do something and there are ‘n’ ways to do another and we cannot do both at the same time, then there are ‘m +n’ ways to choose one of the actions.
To elaborate this with an example, assume that you have 5 Formal Shoes and 3 Cowboy Boots. The total number of ways in which you can decide your footwear is 5 + 3 = 8.
In case you are wondering ‘Why is it 8?’, the logic is pretty simple. You can either wear Formal Shoes or Cowboy Boots but not both. The choices are illustrated below.
Choices of footwear: FS1, FS2, FS3, FS4, FS5, CB1, CB2 and CB3
A slightly more complicated example on the same would go something like this.
Question 1: You have 4 T-shirts, 2 Jeans, 6 Sarees, 5 Formal Shoes and 3 Cowboy boots. In how many ways can you decide what to wear?
The answer for this is (4 x 2 + 6) x (5 + 3) = 14 x 8 = 112 ways.
I hope the logic behind the answer would be clear to you by now.
Continuing with the same idea, try to answer this question.
Question 2: You have 50 students in a class and you have to select three out those for the posts of President, Vice-President and General Secretary. In how many ways can you do that?
The President can be any one of the 50 students. Suppose you choose X.
The Vice-President can be any of the remaining 49 students (Not X). Suppose you choose Y.
The General Secretary can be any of the remaining 48 students (Not X or Y).
So, the total number of ways in which you can decide the students for the positions are = 50 x 49 x 48.
Question 3: In how many ways can you select and arrange ‘r’ items out of ‘n’ distinct items?
The 1st item can be selected in ‘n’ ways.
The 2nd item can be selected in ‘n – 1’ ways.
The 3rd item can be selected in ‘n – 2’ ways.
The rth item can be selected in ‘n – r + 1’ ways.
So, the total number of ways of selecting and arranging ‘r’ items out of ‘n’ distinct items is: n * (n-1) * (n-2) * ... * (n - r + 1)
As you can realize, this is a difficult formula to remember. To take care of the same, multiply (n-r)! to both the numerator and the denominator
n * (n-1) * (n-2) * ... * (n - r + 1) * (n - r)! / (n - r)!
n * (n-1) * (n-2) * ... * (n - r + 1) * (n-r) * (n - r - 1) * (n - r - 2) ... 1 * 2 * 3 / (n - r)!
= n!/(n - r)!
Does the above formula look familiar? If not, just scroll up and see what nPr is.
Question 4: In how many ways can you arrange ‘r’ items?
The 1st item can be selected in ‘r’ ways.
The 2nd item can be selected in ‘r – 1’ ways.
The 3rd item can be selected in ‘r – 2’ ways.
The rth item can be selected in ‘r – (r – 1)’ ways or simply put, 1 way.
So, the total ways of arranging ‘r’ items is:
r * (r - 1) * (r - 2) * ... * 3 * 2 * 1 = r!
Question 5: In how many ways can you select ‘r’ items out of ‘n’ distinct items?
From Question 3, I know that the number of ways of selecting and arranging is n P r.
From Question 4, I know that the number of ways of just arranging is r!
Selecting and Arranging are independent decisions, so
Selection & Arrangement = Selection * Arrangement
nPr = Selection * r!
Selection = nPr/r! = n!/(n-r)! r!
The above equation not only gives us the formula for nCr, but it also gives us a very important relationship nPr = nCr x r!
I hope with the help of this post, the logic behind nPr and nCr would have become clear to you and you would not make a mistake in the same area ever again.