Permutations and Combinations
Permutations and Combinations is a topic which involves basic counting techniques. We would learn how to calculate number of ways of arranging and selecting a group of objects without listing down all the possibilities.
Example problem:
Find the total number of possible outcomes when 3 coins are tossed at the same time?
What else you can do inside qs leap ?
Listing down all the possibilities: {H, H, H}, {H, H, T}, {H, T, H}, {H, T, T}, {T, H, H}, {T, H, T}, {T, T, H}, {T, T, T}
Where each set represents a possible outcome.
{T, H, T} means 1st coin has Tails, 2nd coin has Heads and 3rd coin has Tails and so on.
Total number of possibilities is 8
Knowledge of Permutations and Combinations allows us to come to the conclusion without making the list. Most of the numbers we work in this chapter are large so it becomes impractical to list down all the possibilities.
This technique is widely used in statistics where we have to deal with data. So it is used everywhere is science and technology.
Fundamental Principle of Counting
Principle of Multiplication (the rule of AND)
Let’s assume a situation in which Luffy the pirate wants to attack Marines headquarters. He has 3 ships AND 2 robots. In how many ways he can choose 1 ship and 1 robot to make the attack.
There are 3 ways in which a ship can be chosen because there are 3 ships. For every choice of ship Luffy has 2 robots.
So total number of ways he can choose 1 ship and 1 robot is 3 x 2 = 6
Let’s call ships as S¬1, S2 and S3 and robots R1 and R2. Our choices are
S1 R1
S1 R2
S2 R1
S2 R2
S3 R1
S3 R2
Total 6 ways to select.
In fundamentals of counting this is called the multiplication principle.
It states that “If there are two events, one of them can occur in p ways while the other can occur in q ways, the total number of ways both 1st and 2nd event can occur is p x q.”
In general
“If n events, x1, x2, x3, . . . xn can occur in a1, a2, a3 . . . an ways. The total number of ways x1 and x2 and x3 . . . and xn can happen is a1 x a2 x a3 . . . x an .”
Principle of addition (the rule of OR):
Namrata is going to draw one card from a deck of cards. In how many ways she can draw a king or a queen.
There are 4 kings and 4 queens in a deck. Namrata has to choose either king OR queen she can’t choose both (unlike the previous case where Luffy had to choose one ship AND one robot).
So number of ways of choosing = 4 + 4 = 8
Situation 2:
Namrata has to choose either a Queen or a hearts
We know that there are 4 queens, 13 hearts and there is 1 queen of hearts. So total number of choices would be 4 + 13 – 1 = 16
“In general, if n events x1, x2, x3, . . . xn can occur in a1, a2, a3 . . . an ways respectively and there is no way of two events happening at once the number of ways x1 or x2 or x3 . . . or xn can occur is a1 + a2 + a3 + . . . + an .”
[Similarly, "If there are two events x1 and x2 and they can occur in a1 and a2 ways and there are n ways in which they can occur together. Total number of ways x1 or x2 can occur is a1 + a2 – n.” Warning this second rule of addition should not be extrapolated for n objects!]What else you can do inside qs leap ?
Permutations:
Permutations simply mean the number of ways of arranging a certain number of objects.
To understand permutations let’s see what are the different types of problems we can encounter.
Problem type 1. n distinct objects arranged in n different places in a row
How many 7 letter words can be formed by using the letters of the word PRODUCT where repetition is not allowed.
Solution:
We have 7 empty spots to fill with 7 letters.
1^{st} spot can have 7 different letters
2^{nd} spot cannot have the letter we placed on the first spot because repetition is not allowed. So 2^{nd} spot has 6 choices of letters.
Similarly, 3^{rd} spot has 5 choices, 4^{th} spot 4 choices, 5^{th} spot 3 choices, 6^{th} spot 2 choices and 7^{th} spot is left with 1 choice.
Since we have to fill 1^{st} spot AND 2^{nd} spot AND 3^{rd} spot and so on
Multiplication rule will apply (the rule of AND).
Total number of words that can be made using the letters of the word product = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 7!
This solution can be generalised for arrangement of n-objects.
N! is the product of all the integers from 1 through N.
N! = 1 x 2 x 3 x . . . x (N-1) x N
In general number of ways of arranging n DISTINCT objects in n distinct places in a row is n!
Important to remember 0! = 1
Reason why 0! =1? Because 0! Is number of ways of arranging 0 objects. And number of ways of arranging 0 objects is 1; i.e. you don’t arrange them. (this is a crude explanation. Actual proof involves use of what we call a gamma function in statistics. It is one of fundamentals in statistics but is not in the syllabus. Gamma function defines factorials for non-whole numbers i.e. it is generalisation of factorial. If you have any inquiries related to the gamma function you can discuss on official quant group on LEAP. I would be happy to reply.)
Problem type 2: n distinct objects arranged in r distinct places in a row.
How many ways are there to make 4 letter word with or without meaning from the letters of the word PRODUCE without repetition? (i.e. each letter can appear only once in the word)
We have 4 spots to create a 4 letter word __ __ __ __
Word PRODUCE has 7 distinct characters.
1^{st} spot has 7 choices
2^{nd} spot has 6 choices
3^{rd} spot has 5 choices
4^{th} spot has 4 choices
So total number of words that can be made using 4 letters of the word PRODUCE is = 7 x 6 x 5 x 4
Multiplying and dividing this number by 3 x 2 x 1
= (7 x 6 x 5 x 4 x 3 x 2 x 1) / 3 x 2 x 1
= 7! / 3! = 7! / (7 – 4)!
The term 7! / (7 – 4)! Is called ^{7}P_{4}
In general, ^{n}P_{r} is the number of ways of arranging n different objects in r different places in a row where ^{n}P_{r} = n! / (n-r)!
Problem type 3: How many 4 letter words can be formed by letters of the word PRODUCT with Repetition allowed?
We have four spots to create a 4 letter word __. __. __. __.
1^{st} place has 7 options
Since repetition is allowed second place also has 7 options
Similarly, 3^{rd} and 4^{th} place have 7 options.
So total number of permutations (arrangement of letters or words) =
7 x 7 x 7 x 7 = 7^{4}
Problem type 4 (very important):
We have noticed that in all the above problems the objects we have to arrange are distinct. But what would happen if we have arranged a set of objects in which there are identical sets of objects?
We took the word PRODUCT for arrangements. Notice that each and every letter of the word PRODUCT is different. What would happen if rather than choosing the word PRODUCT we chose the word CAREERS? Both have 7 letters the only difference is in the word CAREERS the letters ‘R’ and ‘E’ are repeated twice.
Let’s compare the two situations with a very basic example:
Situation 1: number of ways of arranging letters of the word AB;
We know that there are 2. AB and BA.
Situation 2: number of ways of arranging letters of the word AA;
There is only 1 way because even if we switch the letters we will get the same word AA.
So if we have non-distinct objects, number of arrangements is reduced because we have to remove similar arrangements.
The problem statement:
Find the number of ways of arranging the letters of the word TREE.
To solve this let’s begin with assuming the word has all distinct letters.
Total number of ways of arranging a 4 letter word is 4! (problem type 1)
But there are two E’s (let’s call them E_{1} and E_{2})
The permutation TRE_{1}E_{2} will be same as TRE_{2}E_{1} and should be counted as 1
So from 4! We have remove all the possible arrangements of E_{1} and E_{2} that are counted more than once.
Number of ways of arranging E_{1} and E_{2} = 2!
Therefore, total number of permutations = 4! / 2!
Alternate Clarification
If E_{1} and E_{2} were distinct | If E_{1} and E_{2} are same |
TRE_{1}E_{2 } | TREE |
TRE_{2}E_{1} | |
TE_{1}RE_{2} | TERE |
TE_{2}RE_{1} | |
E_{1}TRE_{2} | ETRE |
E_{2}TRE_{1} | |
And so on . . .
We can see that for every 2 arrangements there is only one UNIQUE arrangement that should be counted. Hence actual number of unique permutations = total number of permutations / number of ways E_{1} and E_{2} can be arranged among themselves = 4! / 2!
Example 2: Same problem type
Find number of ways to arrange letters of the word CHEESE?
Solution:
Here we see E appears thrice.
Let’s call the three E’s E_{1}, E_{2} and E_{3}
Total number of ways of arranging the words of letter CHEESE considering E_{1}, E_{2} and E_{3 }to be different = 6! (problem type 1)
Total number of ways of arranging E_{1}, E_{2} and E_{3} = 3!
So number of unique arrangements for the word CHEESE = 6! / 3!
Visualisation:
CHE_{1}E_{2}SE_{3}, CHE_{1}E_{3}SE_{2}, CHE_{2}E_{1}SE_{3}, CHE_{2}E_{3}SE_{1}, CHE_{3}E_{1}SE_{2}, CHE_{3}E_{2}SE_{1}
Are all considered same as CHEESE. We have kept C, H and S at the same spot and arranged E_{1}, E_{2} and E_{3}. And number of ways of arranging 3 different objects is 3! (just like in the case of previous TREE example every 3! Objects have to be considered as 1)
Generalisation:
Problem: Number of ways of arranging n objects where r_{1} objects are of 1 kind, r_{2} objects are of second kind, r_{3} objects are of 3^{rd} kind and so on . . . then
Total number of unique arrangements possible = n! / (r_{1}! r_{2}! r_{3}! . . .)
Example:
How many ways are there to arrange the letters of the word MISSISSIPPI?
In the word MISSISSIPPI
Total number of letters = 11
“M” occurs 1 time, “I” occurs 4 times, “S” occurs 4 times, “P” occurs 2 times
So total number of unique arrangements = 11! / (1! X 4! X 4! X 2!)
We usually don’t write 1! Because it is equal to 1.
Important Example:
A binary number x contains a total of n digits and r 1’s. What is the number of ways of arranging the digits of x?
Solution:
A binary number consists of 0s and 1s
Total number of digits in x = n
Total number of 1s in x = r
Hence total number of 0s in x = n – r
So x has r 1s and (n – r) 0s
From previous example we can say that Number of ways of arranging digits in x = n! / r! x (n – r)!
I will be referring back to this example in the article relating to Combinations.
Coming up next week Circular Permutations.
Will post the link once it is up.