Concepts related to Permutation
In this article, we will have a look at the various problems that are formulated on the concept on Permutation.
Compare this with the previous article on Combination, to further enhance your knowledge regarding the differences between these two closely related concepts.
n distinct items
Arranging all items
Number of ways to arrange all n distinct items = $P^n_n$ = n!
Q. In how many ways can 9 persons be arranged in a row?
Explanation:
So, Number of possible ways = $P^9_9$ = 9!
Q. In how many ways can we arrange the letters of the word ‘BHUTAN’?
Explanation:
Number of possible ways to arrange these 6 distinct letters = 6! = 720 ways
Cases of Subgroups
In some cases n distinct items are provided, but there are subgroups within the larger group.
Let’s see some examples:
Q. In how many ways can we arrange the letters of the word ‘BHUTAN’, in such a way that the vowels always come together?
Explanation:
As vowels are always together, we will consider the two vowels UA as one letter.
So, we basically have to arrange these 5 letters – B, H, T, N, (UA)
Number of possible ways to arrange these 5 distinct letters = 5! = 120 ways
Moreover, the number of ways in which the vowels (UA) may be arranged = 2! = 2
So, total possible ways = 120 × 2 = 240 ways
Arranging r items out of n (without repetition)
Number of ways to select and arrange r items from n distinct items (Repetition is not allowed) = $P^n_r$
Solutions are of the type: n × (n - 1) × (n - 2) … × (n - m)
Here we make use of boxes to visualize the situation.
The first box can be filled up in n ways.
The second box can be filled up again in n-1 ways (because repetition is not allowed)
The third box can be filled in n-2 ways and so on.
So, the $r^{th}$ box can be filled in n-(r-1) or n-r+1 ways.
So, number of ways of filling all the r boxes (i.e. 1st box AND 2nd box AND …. AND rth box) = n × (n-1) × (n-2) × (n-3) … (n-r+1) times = $\frac{n!}{(n-r)!}$ = $P^n_r$
Q. How many three digit numbers can be made using the digits 1, 2, 3, 4 and 5, without repeating any digit?
Explanations :
All the 5 digits are distinct.
Number of ways to select and arrange r items from n distinct items (Repetition is not allowed) = $P^n_r$ = $P^5_3$ = 5 × 4 × 3 = 60
The problem can also be visualized as follows:
- Do Selection of 3 digits out of 5: $C^5_3$
- Then Arrange those 3 digits: 3!
So, Required answer = $C^5_3$ × 3! = 5!/2! = 60 ways
All the 5 digits are distinct.
The 1st digit of the number can be any of the given 5 digits. So, number of ways = 5
The 2nd digit of the number can be any of the remaining 4 digits (as repetition of digits is not allowed). So, number of ways = 4
Similarly, 3rd digit of the number can be any of the remaining 3 digits (as repetition of digits is not allowed). So, number of ways = 3
| Digit 1 | Digit 2 | Digit 3 |
|---|---|---|
| 5 possible ways | 4 possible ways | 3 possible ways |
Hence, number of ways of formulating such a number (i.e. ways to choose 1st digit AND 2nd digit AND 3rd digit) = 5 × 4 × 3 = 60
(Remember with ‘AND’ we use multiplication)
Q. How many three letter words can be made using the letters of the word ‘BRAHMIN’, if repetition of letters is not allowed?
Explanations :
All the 7 letters are distinct.
Number of ways to select and arrange r items from n distinct items (Repetition is not allowed) = $P^n_r$ = $P^7_3$ = 7 × 6 × 5 = 210
The problem can also be visualized as follows:
- Do Selection of 3 letters out of 7: $C^7_3$
- Then Arrange those 3 letters: 3!
So, Required answer = $C^7_3$ × 3! = 7!/4! = 210 ways
All the 7 letters are distinct.
The 1st letter of the word can be any of the given 7 letters. So, number of ways = 7
The 2nd letter of the word can be any of the remaining 6 letters (as repetition of letters is not allowed). So, number of ways = 6
Similarly, 3rd letter of the word can be any of the remaining 5 letters (as repetition of letters is not allowed). So, number of ways = 5
| Letter 1 | Letter 2 | Letter 3 |
|---|---|---|
| 7 possible ways | 6 possible ways | 5 possible ways |
Hence, number of ways of formulating such a word (i.e. ways to choose 1st letter AND 2nd letter AND 3rd letter) = 7 × 6 × 5 = 210
(Remember with ‘AND’ we use multiplication)
Arranging r items out of n (repetition allowed)
The number of permutations (i.e. ways of arranging) of n things, taking r at a time (wherein each item may be repeated once, twice, …. up to r times) = $n^r$
Here also we make use of boxes to visualize the situation.
The first box can be filled up in n ways.
The second box can also be filled up again in n ways (because repetition is allowed)
The third box can also be filled in n ways and so on.
So, the $r^{th}$ box can be filled in n ways too.
So, number of ways of filling all the r boxes (i.e. 1st box AND 2nd box AND …. AND rth box) = n × n × n × n … r times = $n^r$
Q. In how many ways can 3 different balls be distributed among 4 different boxes, wherein any box can have any number of balls?
Explanations :
The number of permutations (i.e. ways of arranging) of n things, taking r at a time (wherein each item may be repeated once, twice, .... up to r times) = $n^r$ = $4^3$ = 64
All the balls and boxes are distinct.
The 1st ball can be placed in any of the given 4 boxes. So, number of ways = 4
The 2nd ball can also be placed in any of the given 4 boxes (as repetition is allowed). So, number of ways = 4
Similarly, 3rd ball can also be placed in any of the given 4 boxes. So, number of ways = 4
| Box 1 | Box 2 | Box 3 | Box 4 |
|---|
Hence, number of ways of putting all the balls in boxes (i.e. possible placement options for 1st ball AND 2nd ball AND 3rd ball) = 4 × 4 × 4 = $4^3$ = 64
(Remember with ‘AND’ we use multiplication)
A Caveat:
The number of permutations (i.e. ways of arranging) of 3 balls in 4 boxes = $4^3$ and not $3^4$
Correct way of thinking: Each ball can be placed in how many boxes.
Incorrect way of thinking: Each box can have how many balls.
Let’s see why this is incorrect.
1st box can contain any of the 3 balls.
2nd box can contain any of the 3 balls.
3rd box can contain any of the 3 balls.
4th box can contain any of the 3 balls.
So, number of ways = $3^4$ = 81 (But correct answer is $4^3$ = 64)
Here we have counted some impossible cases too. E.g. if the first box has all the 3 balls, then the other boxes cannot have any ball.
n items - some or all identical
Now, let us study the Permutation of n items, wherein some or all are identical.
All items identical
Number of ways to arrange all n identical items = 1
(If all the items are identical, then there can be only one way in which all these items can be arranged. That is, no matter how you arrange them, the pattern will look the same.)
Some items identical
Number of ways to arrange all n items, wherein p are of one kind and q are of other kind (and rest all are distinct) = $\frac{n!}{(p! q!)}$
Here, ‘of one kind’ implies identical items
(same pattern will continue if there are more groups of identical items)
Q. In how many ways can we arrange the letters of the word ‘INDIA’?
Explanation:
Number of ways to arrange all n items, wherein p are of one kind and q are of other kind (and rest all are distinct) = $\frac{n!}{(p! q!)}$ = $\frac{5!}{(2!)}$ = $\frac{120}{2}$ = 60