Added the PDF of the article at the end of the post! 3 Deadly mistakes you must avoid in Permutation and Combination
This is the 3rd and the final article in the series of Permutation and Combination.
If you did not read our previous article, we recommend that you read them. The first 2 article will help you to get your basic in place.
Article-1: Learn when to “Add” and “Multiply” in Permutation & Combination questionsArticle-2: Fool-proof method to Differentiate between Permutation & Combination QuestionsA brief summary of the previous articles• The logical way to apply addition or multiplication with the help of keywords
• Frequently used keywords to identify a combination-selection question
o Such as AND, OR, SELECT, CHOOSE, PICK, ARRANGE, ORDER etc
• How to approach a PnC question when keywords are not given.
In this article, we will explain 3 most common mistakes that a student makes in PnC questions and along with that we will also explain how to avoid these mistakes.
Multiple Counting: Common Error Type 1Let us look at a very simple example to understand a common mistake.
There are 10 books on a shelf, of which 4 are paperbacks and 6 are hardbacks. How many possible selections of 5 books from the shelf contain at least one paperback and at least one hardback? (OG question) A) 75
B) 120
C) 210
D) 246
E) 252
Common Approach Used By Students:We need to select 5 books such that there is at least one paperback book and at least one hardback book.
Hmm…so let us select 1 paperback and 1 hardback first. That will help us ensure that I have one book of each type. Then I will worry about selecting the extra 1 book from the remaining 8 books.
• Hence, the answer should be \(^4C_1\)*\(^6C_1\)*\(^8C_2\).
This is how usually a lot of student approach this question and then wonder if this is the correct way to solve the question or not.
So, think, is this the right way to solve this question?
NO!!!!!!!! It is not.
The answer is incorrect, and it is incorrect because we double counted some cases.What is Double Counting or Multiple Counting?Let us take a small example to understand what double counting is.
• We have 4 books of which 2 are paperbacks, A and B, and 2 are hardbacks, C and D. We have to find in how many ways we can select 3 books such that we have at least 1 paperback book and at least 1 hardback book.
Let us list down the various combination when we solve the above example by \(^2C_1\)*\(^2C_1\)*\(^2C_1\)=8
Notice that same color-coded cells in the 4th column.
• The selection books ACB and BCA are same.
• The selection books ACD and ADC are same.
• The selection books ADB and BDA are same.
• The selection books BCD and BDC are same.
Thus, we repeated 4 cases and that is why we were getting the wrong answer to the actual question.
We call this counting of some extra cases as
double or multiple counting.How to avoid Double Counting in such cases?In questions like these, we have two categories: Hardback and Paperback.
And we need a “mix” of both the types.
In scenarios like these where there are multiple categories and we need a mix of all the types, in such situations, we will first jot down all the possible cases in which all the types can be mixed or collected together.
• Thus, in this case we will write down all the possible ways of having paperback and hardback books (keeping in mind the constraint: we need at least one book of each type)
• 2 Paperback and 1 Hardback
• 1 Paperback and 2 Hardback
o Thus, Total possible ways of collecting 3 books =
(2 paperback AND 1 hardback) OR (1 paperback AND 2 hardback)
• Possible way= \(^2c_2\)*\(^2c_1\)+ \(^2c_1\)* \(^2c_2\)= 1*2 + 2*1= 4
Wow!!! We now know the correct approach to solve this type of question.
Now here is a small exercise for you:1. Let’s say you need to select 3 vehicles from 5 cars and 4 bicycles, in which we need at least 1 car and 1 bicycle. In how many ways can you do it?
Will you write it as:
a. \(^5C_1\) * \(^4C_1\) * \(^7C_1\) OR
Will you write is as:
b. Cases Possible: 2 Cars & 1 Bicycle OR 1 Car & 2 Bicycles = \(^5C_2\) * \(^4C_1\) + \(^5C_1\) * \(^4C_2\)
If you have chosen Option B. Then Congrats you have successfully learned how to avoid double counting in such cases!
Let us now solve our actual question again.There are 10 books on a shelf, of which 4 are paperbacks and 6 are hardbacks. How many possible selections of 5 books from the shelf contain at least one paperback and at least one hardback? (OG question)A) 75
B) 120
C) 210
D) 246
E) 252
SolutionWe need to select 5 books such that there is at least one paperback book and at least one hardback book.
We can select 5 books in various ways:
• 1 Paperback book and 4 hardback books Or,
• 2 Paperback books and 3 hardback books Or,
• 3 Paperback books and 2 hardback books Or,
• 4 Paperback books and 1 hardback book.
Key Takeaways1. This simple example elaborates the most common mistake by a majority of students i.e. Double counting.
2. In scenarios like these where there are multiple categories and we need a mix of all the types, in such situations, we will first jot down all the possible cases in which all the types can be mixed or collected together.
Let us see another case where most of the students apply double counting: The case when certain objects are identical.
The Curious Case of Identical Objects – Common Error Type 2While solving PnC questions, we may come across a few questions where we might be asked to select and arrange a few objects which are identical in nature.
For example, you might be asked to arrange 5 identical books, or you might be asked to arrange the word “MISSISSIPPI”, in which there are few letters which are identical (the letters I, S and P are present in this word multiple times).
Students have the tendency to make mistake whenever they come across such cases. And thus, we should learn the best and full-proof way to solve such questions!
Let us understand how to tackle these situations with the help of an example.
Assume a scenario where we have 3 different letters- A, B, C and we need to form 3 letter words.
• Total 3 different letter words = 3! = 6 words
• And these are the following cases:
o ABC
o ACB
o BAC
o BCA
o CAB
o CBA
Now, let’s play with these words!
Tell, me how many unique words will we get if we replace C by A??If we replace C with A in the above example, we will get:
• Total words=ABA+AAB+BAA+BAA+AAB+ABA= 2(AAB+ABA+BAA) = 2! (AAB+ABA+BAA) = 2! * 3
Now, notice that there are only 3 unique words possible: AAB, ABA, and BAA. However, we have 2! multiplied with it in above equation.
Now, what should we do to get the actual answer which is 3??
• We are getting multiple case, because we wrote AAB twice, ABA twice and BBA twice.
• And we wrote the twice, because while jotting the cases, we arrange AA in AAB, ABA and BBA twice or 2! times.
• Thus, to get the actual answer, we need to divide 2! *3 by 2!.
• AAB+ABA+BAA= \(6/2!\) = Total ways when all the letters were different/ repetitive counting of the identical letters.
Now, let us extend this idea further to find the number of different words by using three A’s, two B’s.
Since we know that we will again get repetitive cases because of three identical A’s and two identical B’s.
• Total words= (Total ways when all the 5 letters are different) / (multiple counting of the identical letters)
• Total ways= 5! / (Repetitive counting of three A’s and repetitive counting of Two B’s)
o Three A give only 1 word, but we counted extra cases by assuming all three A’s to be different. Hence, we will divide by 3!
o Similarly, we counted extra cases by assuming the two B’s to be different. Hence, we will divide by 2!
• Total ways= \(5! /{3! *2!}\)
Extending the idea further, we can generalize that:The number of arrangements of n objects with p1 identical objects of one kind, p2 identical objects of second kind, p3 identical objects of third kind and so on is equal to:
\(\frac{n!}{{(p1! * p2! * p3!*…..)}}\).
e-GMAT Example 1Q--
In how many different ways can the letters of the word SINISTER be arranged such that two S are never together?
SolutionSINISTER is an 8-letter word with S and I repeated two times.
We want the cases in which two S are never together and how can we do that??
We can solve the question in two ways:
• By adding all the cases when two S are separated has at least 1 letter between them.
o Ways when (Two S separated by 1 letter+ Two S separated by 2 letter+…..+Two S separated by 6 letters)
• By removing all the cases in which Two S are together from the total cases.
o Total cases- Number of cases in which both the S are together.
It is very clear that 2nd method is easy. Thus, we only need to find:
• Total cases in which SINISTER can be arranged and,
• Number of cases in which both the S are together.
Total cases:SINISTER can be arranged in \(8! / {2! * 2!}\) = 10080 ways
Number of cases in which both the S are together:Two S always has to be together, so we can group together as SS.
We can assume SS to be one letter as they will only be arranged like a letter with the other 6 letters.
• Thus, total words = 6 letters other than S+ 1 group of two S
However, SS is actually a 2-letter word which can arrange in itself.
Thus, Total ways when both the S are together= arrangement of 7 letters * arrangements in the group SS
• Total ways= 7!/2! * 1(SS can be arranged in only 1 way)
• Total ways when both the S are together= 7!/2! = 2520 ways [we are dividing by 2! because there are 2 Is which will give us repetitive cases]
Thus, total cases in which two S are never together= 10080- 2520= 7560 ways.
e-GMAT Example 2Q--
If we have 9 different points in a plane out of which 4 are collinear. How many different straight lines we can draw.SolutionTo make a straight line we need to select 2 points among 9 points.
However, only 1 straight line can pass through from the 4 collinear points.
• Can you visualize that this is similar to the case of identical objects??
• In case of similar object, we only have 1 arrangement and in case of collinear points we only have 1 line.
In this case, all the lines are not repeating, only the lines whose both the points lies on 4 collinear points are repeating.
Thus, we can get the line in 3 different ways:
• Select any two points from 5 non-collinear points Or,
• Select one point from 5 non-collinear points and another from 4 collinear points Or,
• 1 line from the 4 collinear points
Total ways= \(^5c_2\)+\(^5c_1\)*\(^4c_1\)+1 = 10+20+1= 31
Thus, we will get 31 different straight lines.
Key Takeaways• Identical objects can be arranged in 1 way.
• To find the arrangement of n different things of which some are identical then we divide by the arrangement of identical things assuming the identical thigs to be different.
• The number of arrangements of n objects with p1 identical objects of one kind, p2 identical objects of second kind, p3 identical objects of third kind and so on is equal to:
\(\frac{n!}{{(p1! * p2! * p3!*…..)}}\).
• From n collinear points, only 1 line can be drawn.
Let us now move to the 3rd and one of most common type of mistake.
Confusion of Powers: Common Error Type 3To understand the third type of mistake, let us try to find the answer to one simple question.
e-GMAT Example 2Q--
In how many ways, 3 different prizes can be distributed to 2 students where each is eligible for all the 3 prizes?Can you find the answer to this interesting question???
• Is the answer \(2^3\) or \(3^2\)???
SolutionIf your answer is \(3^2\) then You just did a very common mistake.
So, we should figure out why \(3^2\) is wrong.
Let us delve into the details of the question find this.
Let us suppose the two students are: X and Y, and three prizes are A, B, and C.
Now, when we say that total ways to distribute the prizes=3*3, we mean that:
• X can get either 1 prize or two prizes or all the three prizes.
• Similarly, Y can get either 1 prize or two prizes or all the three prizes.
This can be shown in the tabular form as:
Observe Case 1: • If, say, X gets prize A and Y gets prize B, then none of them got prize C.
• • There is also a possibility that both X and Y might be given the same price A
o Did we take any precaution that both get different prizes, while writing the first case? No, we did not. ☹
Observe Case 3, 5, 6, 7, 8:We are distributing more than 3 prizes to both of them, is it possible?
No, right!!!!This implies that there is a mistake when we are distributing 3 prizes in 3*3 ways.
This is common mistake that students make. This is known as
counting invalid cases!Now, let us come to the correct approach to distribute 3 prizes in 2 students.
Correct approachWe need to distribute all the three prizes, right?
Thus, let us take Prize A and decide in how many ways can this be given to X and Y.
• Prize A can be given to either X OR Y = 2 cases
• Similarly, Prize B can be given to either X OR Y = 2 cases and
• Prize C can be given to either X OR Y = 2 cases.
Also, think, we need to distribute all the prizes, right?
• Thus, total ways to distribute prize = Give Prize A AND Give Prize B AND Give Prize C = 2 x 2 x 2 = 8 ways.
All the possible 8 cases can be shown as:
Thus, there are \(2^3\)=8 possible ways.
Key Takeaways from the exampleSolving the question in this way ensure 2 things:
1. All the prizes are distributed: A, B and C was considered one by one and distributed.
2. Eliminates the chances of double or invalid counting, since A will go to either X or Y, similarly B and C goes to either X or Y and not both!
3. If we replace 3 by ‘n’ and 2 by ‘r’ in the above example, then we can infer that:
• The total number of ways to distribute ‘n- different object’ in to ‘r- different things’ = r^n
Let us solve another example to get 100% clarity over the concept.
e-GMAT Example 2Q--
There are 10 different envelopes and 3 post boxes. In how many ways can we post 4 envelopes in 3 post boxes such that each post box can send any number of envelopes.SolutionWe have 10 envelopes and we need to send any 4 envelopes from 3 post-boxes.
• Thus, we first need to find select the 4 envelopes from the 10 envelopes then we can put the letter into post boxes.
o Thus, total ways= Ways to select 4 envelopes from 10 envelopes * ways to post 4 envelopes in 4 post boxes.
Ways to select 4 envelopes• 4 envelopes can be selected from 10 envelopes in \(^{10}C_4\)= 210 ways.
Now, we have 4 selected envelopes and we need to put the selected envelopes in to 3 post boxes.
Way to post 4 envelopes in 3 post boxes• Method-1)
o Since each envelope can go in to any of the post boxes thus each envelope can be posted into 3 ways.
o For example, envelope one can go in PB1 or PB2 or PB3 = 3 ways.
o And the same will be done for all the other envelopes.
o Hence, total ways to post 4 envelopes in to 3 boxes= 3*3*3*3= 3^4=81
• Method-2) – Use of Direct Formula:
o Here Objects are envelopes and we have 4 envelopes. Thus n = 4
o Since the three post boxes are the different things, in which they will be posted, r = 3.
o Hence, by the application of r^n, total ways to post 4 envelopes in to 3 boxes= 3^4= 81 ways.
Thus, total ways= 210*81=17010
Key Takeaways from the article1. In scenarios where there are multiple categories and we need a mix of all the types, in such situations, we will first jot down all the possible cases in which all the types can be mixed or collected together.
2. The number of arrangements of n objects with p1 identical objects of one kind, p2 identical objects of second kind, p3 identical objects of third kind and so on is equal to:
\(\frac{n!}{{(p1! * p2! * p3!*…..)}}\).
3. If r objects out of n objects are identical then we divide the total number of different cases by the number of repetitive case.
4. The number of ways to distribute n different objects to r different things is \(r^n\).
_________________