Demystifying Permutation & Combination  Rajesh Balasubramanian  CAT 100th Percentile  CAT 2011, 2012 and 2014 (Part 1/7)

rajesh_balasubramanian
Director, 2IIM Online CAT Preparation  IIT Madras  IIM Bangalore  CAT 100th percentile  CAT 2011, 2012 and 2014.
Permutation and Combination is a wonderful topic to learn. This topic is all about counting. In all other topics, we need to get to an answer, be it average, or speed, or angle, or LCM. In this topic, we will mostly concern ourselves with the idea of counting the number of ways of doing something. In most scenarios we will be enumerating possibilities rather than solving to get an answer. Before we go further, let us define a few ground rules.
 This topic is based on the simple idea of counting. So, from now on, we will avoid the terms ‘permutation’ and ‘combination’.
 We will build the theory for this topic mostly with examples.
 Wherever possible, we will list and count. Especially, if the answer is less than 10 we will shoot to list out all possibilities.
 nCr, nPr, n! will be resorted to only if absolutely necessary. Counting errors happen when we look to force–fit an idea on to a question. We will use nPr, nCr etc, when we hit the framework. We will not use these as starting points.
Now let us move to first set of questions.
Ram wants to travel from Chennai to Kolkatta (to join IIM Kolkatta). He wants to take only 1 piece of baggage with him. He has 3 types of suitcases and 4 types of back packs. In how many ways can he select his luggage?
This is straightforward. Out of the seven pieces available, he has to select exactly one. If he has suitcases S1, S2, S3 and bags B1, B2, B3 and B4, he can pick one of these 7. So, there are 7 options.
After trying to fit in his luggage, Ram realizes that he needs to carry two pieces of baggage. He plans to carry one suitcase and one backpack. In how many ways can he select his baggage now?
He can select S1 or S2 or S3 and B1, B2, B3 or B4. Totally he has 12 options now.
S1B1, S1B2, S1B3, S1B4
S2B1, S2B2, S2B3, S2B4
S3B1, S3B2, S3B3, S3B4Fundamental Rule of Counting
If there are ‘m’ ways of doing a task and ‘n’ ways of doing another task, then there are m × n ways of doing both.
If a process can be broken into multiple steps and you have to do each of the many steps, then the total number of ways of doing the process = product of number of ways of doing each step.AND => ×
Rule of Sum
If there are m ways of doing a task and n ways of doing another task, then the number of ways of doing either of these two (but not both) = m + n. In other words, if we have to do one thing OR another thing, the number of ways = sum of the number of ways of doing each step
OR => +
Number of ways Ram can choose 1 suitcase = 3
Number of ways Ram can choose 1 bag = 4
Number of ways he can choose 1 suitcase OR 1
bag = 3 + 4 = 7
Number of ways he can choose 1 suitcase AND 1 bag = 3 × 4 = 12Let us take one more example and build counting ideas.
John, who is in charge of creating number plates for cars, has three colors at his disposal – black, white and yellow. He has to paint the number plate with one color and the letters and numbers in another color. In how many ways can he create a number plate?
Again, let us list and count.
 Black plate, white letters
 Black plate, yellow letters
 White plate, yellow letters
 White plate, black letters
 Yellow plate, white letters
 Yellow plate, black letters
There are totally six ways.
Mike has three types of flowers with him – roses, lilies and violets. Mike decides he has to create a bouquet that has two distinct flowers. In how many ways can he create this?
 Rose and Lily
 Lily and Violet
 Rose and Violet
What is the difference?
In the number plate example, we select 2 colors out of 3, in the bouquet example we select 2 flowers out of 3. There are 6 ways of doing the former, but only 3 ways for the latter. What is the difference?
The Idea of Order
The difference is characterised by this term called ‘order’. In the number plate example, ‘black plate–white letters’ is different from ‘white plate–black letters’; whereas in the bouquet example, ‘rose–lily is the same as lily–rose’.
If in a type of selection ‘AB’ is different from ‘BA’, then order is important. If ‘AB’ is same as ‘BA’ then order is not important. Essentially, if the reason for which the selections are made is the same, then order does not matter. In the bouquet example, the flowers are chosen for the ‘same’ bouquet. But in the number plate example, one color is for the background and the other color is for the letters and numbers. Here the reasons are different.
Mike has three types of flowers with him – roses, lilies and violets. Mike decides he has to create a bouquet that has two flowers. In how many ways can he create this?
RL, LV, RV, RR, LL, VVWhat is the difference between selecting two distinct flowers and two flowers?
The Idea of Repetition
This difference is based on the idea of repetition. If the same element can be selected again, then we allow ‘repetition’. If we are selecting two flowers, then we can select rose and rose. However, if we are looking for two distinct flowers, then rose–rose is not to be counted.
If in a type of selection ‘AA’ is permitted and should be counted, then repetition is allowed. If ‘AA’ cannot be a legitimate selection, repetition is not allowed.
Understanding the idea of Repetition
A teacher has a chocolate, a biscuit and a cold–drink with her. She says that whoever gets a question correct would get one of the three as award.
Ram gets the first question right. How many options does he have of choosing his award? 3
Krish gets the second question right. How many options does he have of choosing his award? 2
John gets the third question right. He has only one option for choosing the award.Next day, the teacher follows a new awards scheme. She gives Star rating, Circle rating and Square rating to students who get questions right.
Ram gets the first question right. How many options does he have of choosing his award? 3
Krish gets the second question right. How many options does he have of choosing his award? 3
John gets the third question right. How many options does he have of choosing his award? 3In the first instance, selection is made without repetition. In the second instance, repetition is allowed. If repetition is not allowed, the choice–set shrinks with every selection that is made. If repetition is allowed, then the choice–set remains the same. At every stage, there are the same n objects to choose from.
Rearrangements
Ram, Krishna and John decide to take part in a race. If there is to be no tie, in how many ways can the three positions on the race be determined?
1st Position Ram John John Krishna Krishna 2nd Position John Ram Krishna John Ram 3rd Position Krishna Krishna Ram Ram John For the first slot, there are 3 options, for the second one there are two options, for the third there is only one option. Totally, there are 3 × 2 × 1 = 6 = 3! options.
The number of ways of rearranging r objects is given by r!A school plans to paint the three floors of its building. The painter can choose from the colour red, blue, yellow, and orange for each floor in the building. In how many ways can he choose the colours to paint the building?
The painter can choose from four colors for the first floor.
The painter can choose from four colors for the second floor.
The painter can choose from four colors for the third floor.
Total number of options = 4 × 4 × 4 = 64A school plans to paint the three floors in its building. The painter can choose from red, blue, yellow, and orange for each floor in the building. Further he decides that each floor should have a different colour. In how many ways can he choose the colours to paint the building?
The painter can choose from four colors for the first floor.
The painter can choose from three colors for the second floor.
Total number of options = 4 × 3 × 2 = 24The principal of a school, who is an eccentric person, decides that all three floors should have a color that is a mixture of three colours that the painter has selected. In how many ways can the school be painted?
Now, this is different from the previous question in one key aspect. In the previous question, we select a color for the first floor, one for the second floor and one for the third floor. Here we are going to select 3 colours out of 4 and mix them. Here, a selection of red, blue and green results in an identical outcome as that of a selection of blue, green and red. In other words, order does not matter. The number of ways would be red–blue–yellow, red–blue–orange, red–yellow–orange, and blue–yellow–orange. There are only 4 options totally.
Now, let us see if there is a method to arrive at this answer. Let us look at this by enumerating some options. Look at the following six sequences. These are options that one could have chosen if one were painting each floor with a different colour (as outlined in the previous question).
First Red Red Blue Blue Yellow Yellow Second Blue Yellow Red Yellow Red Blue Third Yellow Blue Yellow Red Blue Red In the case of selecting some set of three colours to get an overall blend, all the 6 options outlined above result in only one end outcome. So, the 4 × 3 × 2 options of the previous question result in (4 x 3 x 2)/6 options for this one. In other words, the number of ways of selecting 3 paints for a blend is (4 x 3 x 2) / ( 3 x 2 x 1) . Why is it 3 × 2 × 1 in the denominator? For every 3 × 2 ×1 outcomes for Question 2, there is only one end outcome when we consider the scenario outlined in Question 3.
What matters in this question is the combination of the colors and not the order. Hence considering the different possible arrangements of a selection is redundant here. And, we know that 3 distinct things can be rearranged in 3! ways; so we need to divide (4 × 3 × 2) by 3! to get the correct answer.
We are going to redefine the questions differently and create a general framework.
A school has to paint the ‘r’ floors in its building. The painter can choose from n different colours for each floor in the building. In how many ways can he choose the colours to paint the building?
From n colours, select one for each floor, ‘r’ number of times. This can be done in
$n^r$ ways.
From n options, select ‘r’ such that order is important and repetition is allowed. This can be done in$n^r$ ways.A school has to paint the ‘r’ floors in its building. The painter can choose from ‘n’ different colours for each floor in the building. Further he decides that each floor should have a different colour. In how many ways can he choose the colours to paint the building?
From n colours, select one distinct one for each of ‘r’ different floors.
From n options, select ‘r’ three such that order is important and repetition is not allowed. This can be done in n (n – 1) (n – 2) n – 3)….up to r terms. This can be re–written as n! / (n  r)! This term is called nPr.The principal of the school, who is an eccentric, decides that all ‘r’ floors should have the same colour and that colour should be a mixture of some ‘r’ of the ‘n’ colours available. In how many ways can the school be painted?
From n colours, select r and then mix them together to get one blend to be used across the entire school
From n options, select ‘r’ such that order is not important and repetition is not allowed. This can be done in n (n – 1) (n – 2) (n – 3)….up to r terms / (1 × 2 × 3 × …r). This can be re–written as$n! / (n  r)!r!$ . This term is called as nCr.Also, the number of permutations can be seen as the number of combinations multiplied by the different arrangements possible for each combination. That is, nPr = nCr × r!
Selecting in order = Selecting without order AND Rearranging themA football team plays a 5–a–side tournament. In all these tournaments, there should be 1 forward, 1 defender, 2–midfielders, and 1 goal keeper. 1 of the 5 should also be the captain of the team. Ram is the coach of team ‘Samba’ which has a squad of only 5 people. Let us say the 5 people are A, B, C, D and E.
In how many ways can Ram select a forward and a defender from this five?
Number of ways of selecting forward = 5.
Number of ways of selecting defender = 4.
Total number of outcomes = 5 × 4 = 20
The selections are as follows:BA CA DA EA AB CB DB EB AC BC DC EC AD BD CD ED AE BE CE DE In how many ways can Ram select a goal keeper and captain from this 5?
Number of ways of selecting goal keeper = 5.
Number of ways of selecting captain = 5.
Total number of outcomes = 5 × 5 = 25
The sections are as follows:AA BA CA DA EA AB BB CB DB EB AC BC CC DC EC AD BD CD DD ED AE BE CE DE EE In how many ways can Ram select 2 midfielders from this 5?
Number of ways of selecting two players out of
5 = 5C2 = (5 x 4)/2 = 10.
The selections are as followsAB AC BC AD BD CD AE BE CE DE Technically speaking, the three answers are 5P2,
$5^2$ and 5C2 respectively. The key difference between selecting forward and defender vis–a–vis two midfielders is that in the former order is important, in the latter order is not important.