Permutation & Combination - Abhishek Singhania, IIM Lucknow
Abhishek Singhania is the principal trainer and CEO of ABS Classes. He completed his MBA from IIM Lucknow and has a rich experience of 12+ years in mentoring students for competitive exams like CAT and GMAT. This article is derived from an event by ABS classes on the topic Permutation & Combination. ABS Classes offers free materials on CAT preparation which includes questions, theory notes, video lessons and mock tests.
Arrangement of Identical objects:
Arrange letters T W O to form 3 letter words
We all know the answer is 3! = 6
What if there were 2 Os. we know the answer will be 3!/2!= 3 but why ?
Look at the list above
If instead of W there was another O, then how many distinct letters will be there?
So what goes away is the internal arrangement of identical letters, there is a constraint only on it. Earlier there was 2! Arrangement between W and O, now there is only one..so out of all cases i.e. 3! The proportion required by us 3! X 1/2!
so its not about identical objects its more about constraints or conditions placed in arrangement of specific objects here, in this case W and O.
For example 4 persons in a line A always ahead of B, so 4! X 1/2!
5 persons in a line A ahead of B who is ahead of C, so 5! X 1/3!
5 persons in a line A and B ahead of C, so 5! X 2/3!, because it can be ABC or BAC
10 persons, A, B, C and D must sit in this order: 10! X 1/4!
10 persons including a family of 4, father mother son and daughter, parents ahead of the children: 10 x 4/4! because for the family there are 4 possible father/mother – mother/father – son/daughter – daughter/son..only 4 out of 4! Is acceptable to us
2 families of 4 each, father mother son and daughter, parents ahead of the children: 8! X 4/4! X 4/4!
hope the previous examples helped you understand a certain approach which is take care of constraints then apply the formulae..even in very basic questions we do that.
for example, 7 persons in a line. A and B always seperated by 2 seats..Now A and B can sit in following ways in chairs numbers 1-4, 2-5, 3-6, 4-7..and in each of these cases they can sit in 2 ways (A-B ) or (B-A)..this was our constraint..we have taken care of it..how many cases do we have now ? 4 cases each with 2 arrangements = 4 x 2 = 8...for the rest there is no constraint so we straight away use the formulae 5 persons 5 chairs = 5! = 120..so the answer is 8 x 12= 960
Why n-1 !
First we must understand why do we need to consider circular arrangement differently and why not take it same as linear or straight line arrangement
The only difference in circular arrangement is that there is no sense of direction in a circle, there are no starting or ending points as it is a closed loop, there are no looses ends.
In a linear arrangement even if the chairs are identical, exact replica of each other in terms of shape, design, colour etc., they can be considered distinct by virtue of their position. But in circular we cant...there is no sense of position. To solve this problem, we differentiate one chair by making any one person sit in a chair. It does not matter who sits as ultimately all of them will occupy different chairs. Once a person is seated in a chair, the arrangement is as good as a straight line. So if there is any way to identify the chairs we dont need to use (n-1)! of say different colours or different size etc..
Now what if only one chair is distinct..say there is a throne and rest all are normal chairs in a circle..try to imagine will u be able to diffrentiate between chairs..1st chair to the right of the throne, 3rd chair to the left of the throne and so on.. So the idea is 1 chair different all chairs diferent...since we dont have colour of tags (unlike FB ) how do we diffrentiate then, make them different.
only resource at our disposal is people..
so we make 1 person sit..that chair now is distinct
and as we learnt one chair is different, all chairs are different
for rest of the people it is as good as a straight line an open loop and n! will work now
There are 9 persons standing in 2 circles of 6 and 4 persons and one person is common in both the circles. Find the number of possible ways
answer is 9!, it does not matter that the arrangement is circular..because one position in both the circles is distinct, visually identifiable..the common chair...one distinct all distinct..so as good as straight line arrangement. so 9 chairs, 9 persons..9!
1) 6 men and 2 women, women dont sit together
2) 6 men and 3 women, no two women sit together
We can make men sit..and then filled the gaps with wome..so men in circle will sit in 5!..and there will be 6 gaps..now 2 women can sit 6 positions in 6P2..because nPr and rPn is one and the same..so the answer for first question is 5! x 6P2= 3600 and second ques 5! x 6P3= 14400
In case of objects which can be turned upside down, like garlands, necklaces, or a giant wheel in a fair, the number of arrangements will be (n-1)!/2 ways
This is because the clock wise and anti clock wise arrangements there are same, as you can turn thing upside down, which we cant do with say a group a of person sitting in a circular arrangement (neither should we try!!!)
this has nothing to do with distinct or identical objects.
1) A garland from 8 identical rose flowers?
2) A garland from 7 identical rose flowers and 1 jasmine flower
3) A garland from 8 different flowers?
4) A garland from 5 rose flowers of diferent sizes and 5 jasmine flowers of different sizes?
Answers: 1, 1, 7!/2, 9!/2
DIVISION OF IDENTICAL ITEMS INTO DISTINCT GROUPS
Say you go to party and there is a plate with 6 sweets on it. Its decision making time. What do you do now?
You may pick none, or 1 or 2 or 3 or 4 or 5 or 6 ( if no one’s looking)
So you have 7 choices
Now the number of sweets you pick and the number of sweets left on the tray will always equal 6 as there were 6.
So if A represents the number of sweets left on the tray and B represents the number of sweets you picked, then we can construct and equation:
A + B = 6
And we know that this equation will have 7 solutions
So if m identical items are to be divided in 2 distinct groups it can be done in m+1 ways
Now if extend this problem to 3 groups. Say a friend comes along and let the number of sweets picked by him be C
So now equation will be
A + B + C = 6
So possible solutions can be
A= 0, B= 1, C=5
A=1, B=2, C=3
And there will many more solutions which makes the task of enumeration very difficult
In such cases we can use the following formulae
1. The number of ways of dividing n identical things among r persons (or groups), each of whom, can receive zero or more things is n + r – 1Cr – 1 where 0 ≤ r ≤ n.
2. The number of ways of dividing n identical things among r persons, each one of whom receives at least one item is n – 1Cr – 1 where 1 ≤ r ≤ n.
So using the first formulae
A + B + C=6
So the n = 6 and r = 3, so 6 + 3 – 1C3 – 1 = 8C2 = 28
Say the person carrying the tray insist that both of you pick at least 1 sweet and both of you are also mindful of the fact that you should leave at least 1 sweet on the tray, then in the equation
A+B+C=6, each of A, B and C will have minimum value of 1
So we can use the 2nd formulae: n – 1Cr – 1 = 6 – 1C3 – 1 = 5C2 = 10
The 2nd formulae is derived from the 1st formulae. For example in the 2nd case, what is each of you pick at least 1 sweet, and also leave one on the tray, then there are 3 sweets to be distributed amongst you, your friend and the tray.
So the equation will be A+ B+ C = 3
We can use the first formulae here as each of the groups have the minimum requirement of 1 sweet and therefore can afford to have no more
So the answer will be 3+ 3 – 1C3 – 1 = 5C2 = 10
The number of ways of dividing n identical things among r persons, with each having different minimum requirement of (p, q, r…) items is n –(p+q+r..) + r - 1Cr – 1 where 1 ≤ r ≤ n.
The concept we are just discussing is a little complicated..but its one those things that if you understand then you can solve practically every question related to it..so we can spend some time over this and make sure that each one us understand it with complete clarity,..some of you who already know this may have to be a little patient as we come with questions...please shoot doubts in concept..
best way to learn is summarize:
1) identical objects, distinct groups
2) no constraints
3) no fixed number to be allocated to any group or you account for the same
exceptions: maximum value of any group may not be acceptable, for example sum of 4 dice is 8...now thw formula does not understand that dice cannot be more than 6..so formulae will talke all cases including the case where once dice is 8 and rest are 0 and so on..so for such cases we will ahve to manually adjust which we will learn in some time
1) how many 7 digits numbers whose sum of the digits is 8
2) In how many ways 10 identical rings be worn in the 5 fingers of the hand?
3) 20 foxes hunted by 4 hunters. In how many ways?
1) How many 7 digit numbers have sum of digits as 10
2) How many numbers less than 10^10 have sum of digits as 9
3) Sum of the faces of 4 cube = 7, how many ways
The examples that we are posting now and which every student craves are of very little relevance. This is not IIT JEE or NASA entrance exam. its a simple management entrance. You will become business man not scientists..people who like PnC, enjoy doing these questions but it is of low priority for CAT prep..if you are the unluckiest person on Earth, u MAY get one such question in the whole paper..alas! unless such mind numbing questions are served, most students dont feel fulfilled..our schools have inculcated a strong sadistic streak in all of us. in the above questions 1 and 3, the complication is that maximum value possible is less than the total..i.e. cube cannot exceed 6, no digit in a number can be more 9..but formual is immune to all this..it takes all possibel cases..u will have to manually adjust that. the above questions are more tricky than tough..some of u who are not feeling that confident just need to identify the trick..in first question, give one to the first digit, so sum of digits is 9..and there is only one case which is not possible...in the 3nd ques...give one each to each die as a die cannt be 0..
ques 1: let the 7 digit number abcdefg, so a cannot be 0 (1st digit) also as given a+b+c+d+e+f+g = 10, this is same as giving 10 chocolates to 7 kids and one kid must be givne at least 1 chocolate in this case the first kid..so give him 1 chocolate..so now 9 chocolates and 7 kids and complete flexibility, any number of chocolates to any kid..so u can staright use the formula.. n+r-1Cr-1 i.e. 15C6..however there is a small problem here, these are digits and maximum value of a digit is 9..so first digit has already been given at least 1, so we can give maximum of 8 more..however formula will not understadn that it will also onclude a case where the first kid is given 9 and rest all are given 0..so we need to subtract that one case
ques 2: Numbers less than 10^10 will have 1 to 10 digits...lets take 10 digit number abcdefghij...so that a+b+c+d+e+f+g+h+i+j = 10......now u will say that wht about 9 digit numbers..remember our formula is completely unprejudiced..no bias at all..so formula may give 0 to a,, the first digit the moment u make the first digit 0, the number becomes a 9 digit number...so we can still use the formula!!!...if it gives 0 to first two digits, its a 8 digit number and so on..so all will be covered..answer will be simply (10+9-1)C(10-1)=18C9
ques 3: give 1 to each cube..so c1+c2+c3+c4 = 3..u can still 5 more to any cube as the maximum value of a cube is 6...so there is no problem with the upper limit that we can give to any cube..so the answer is 6C3
1) 100 chairs, 4 person. No two sit together?
Hint: take the gaps between the 4 persons, there will be 5 such gaps, them as a, b, c, d, e and the total of these gaps will be 96
2) 4 dice: sum is 12
Hint: subtract cases, if one dice is 7, then the sum of other 3 is 5 in 7C2 ways, if one dice is 8, sum of other 3 is 4 in 6C2 ways and so on
ques 1: as explained, take the gaps as a, b, c, d and e..now the first gap (a) is basically the chairs to the left of the first person seated..so there may not be any chairs i.e. a can be 0...1st person may be seated in 1st.....similarly e is the number of chairs to the right of the last person..again there may not be any chairs there..4th person may be seated in the very last chair..so e can be 0..however b,c and d indicate the number of chairs between any two successive person seated and there has to be a gap of at least 1 chair between any two successive persons, so b, c and d have a minimum value of 1..so lets give 1 to each one of the,,so the new equation is a+b+c+d+e = 100 - 4 (4 persons seated) - 3 = 93. Now we have the flexibility to give any amount of the 5 groups so we can straight away use the formula..(93+5-1)C(5-1) = 97C4..this is basically allocation of 4 sets to 4 persosn or 96 seats to 5 gaps..but 4 persons can arrange themselves in 4! ways so the final answer is ..97C4 x 4!
ques 2: c1+c2+c3+c4 = 12,,,give 1 to each cube..so c1+c2+c3+c4 = 8..now the prob is we can give maximum of 5 to any cube now..but the formula will include cases like 8+0+0+0 and so on..this we will have to take care on a case by case basis..let c1= 6 (which shudnt be allowed) so c2+c3+c4 = 2 which is possible in 4C2 ways...same will be true when we take c2 =6...now lets take c1 = 7 so c2+c3+c4 = 1 i.e. 3C2 ways, again same true when c2 or c3 or c4 is 7... now lets take c1 = 8 so c2+c3+c4 = 0 i.e. 2C2 =1way, again same true when c2 or c3 or c4 is 7..so the number of cases we dont want is 4(4C2 + 3C2 + 2C2) = 4*(5C3). So total favourable cases = 11C4 (8 given to 4 cubes) - 4*(5C3)
1) An exam with 2 sections with 4 and 5 questions in each section. All questions in section with 4 questions have 3 options and all questions in section with 5 questions are True False questions..in how many ways can one more than 7 questions in the paper
ans: 8 questions : 5+3 or 4+4 so (5C5*2^5) * (4C3*3^3) + (5C4*2^4) * (4C4*3^4).
9 questions = 3^4 * 2^5.. all the questions to be asnwered so no selecion of questions