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

rajesh_balasubramanian
Director, 2IIM Online CAT Preparation  IIT Madras  IIM Bangalore  CAT 100th percentile  CAT 2011, 2012 and 2014.
PROBLEMS BASED ON DIGITS OF A NUMBER
How many three digit numbers exist? How many of these three–digit numbers comprise only even digits? In how many 3–digit numbers is the hundreds digit greater than the ten’s place digit, which is greater than the units’ place digit?
Three digit numbers range from 100 to 999. There are totally 900 such numbers. There is a simple framework for handling digits questions.
Let three digit number be ‘abc’.
‘a’ can take values 1 to 9 {as the leading digit cannot be zero}.
‘b’ can take values 0 to 9.
‘c’ can take values 0 to 9.
Totally, there are 9 × 10 × 10= 900 possibilities.
Now, three digit number with even digits
Let the three–digit number be ‘abc’.
‘a’ can take values 2, 4, 6 or 8 {as the leading digit cannot be zero}.
‘b’ can take values 0, 2, 4, 6 or 8.
‘c’ can take values 0, 2, 4, 6 or 8.
4 × 5 × 5 = 100 numbersIn how many 3–digit numbers is the hundreds digit greater than the ten’s place digit, which is greater than the units’ place digit?
The digits have to be from 0 to 9. Of these some three distinct digits can be selected in 10C3 ways. For each such selection, exactly one order of the digits will have the digits arranged in the descending order.
So, number of possibilities = 10C3 = 120.
We do not have to worry about the leading digit not being zero, as that possibility is anyway ruled out as a > b > c.How many 4–digit numbers exist where all the digits are distinct?
Let 4–digit number be ‘abcd’.
‘a’ can take values from 1 to 9. 9 possibilities
‘b’ can take values from 0 to 9 except ‘a’. 9 possibilities
‘c’ can take values from 0 to 9 except ‘a’ and ‘b’. 8 possibilities
‘d’ can take values from 0 to 9 except ‘a’, ‘b’ and ‘c’. 7 possibilities
Total number of outcomes = 9 × 9 × 8 × 7PROBLEMS BASED ON REARRANGEMENT OF LETTERS OF A WORD
In how many ways can we rearrange the letters of the word ‘MALE’?
In how many ways can we rearrange the letters of the word ‘ALPHA’?
In how many ways can we rearrange the letters of the word ‘LETTERS’?Number of ways of arranging letters of the word MALE = 4! = 24. (Think about the number of ways of arranging r distinct things).
Now, ‘ALPHA’ is tricky. If we had 5 distinct letters, the number of rearrangements would be 5!, but here we have two ‘A’s.
For a second, let us create new English alphabet with A1 and A2. Now the word A1LPHA2 can be rearranged in 5! ways. Now, in this 5! listings we would count A1LPHA2 and A2LPHA1, both of which are just ALPHA in regular English. Or, we are effectively double–counting when we count 5!. So, the total number of possibilities = 5!/2.
The formula is actually 5!/2!. . Whenever we have letters repeating we need to make this adjustment.In how many ways can we rearrange the letters of the word ‘LETTERS’? – 7!/2!2!
In how many ways can we rearrange letters of the word ‘POTATO’ such that the two O’s appear together?
In how many ways can we rearrange letters of the word ‘POTATO’ such that the vowels appear together?The two O’s appear together
Let us put these two O’s in a box and call it X.
Now, we are effectively rearranging the letters of the word PTATX. This can be done in 5!/2! ways.Now, we need to count the ways when the vowels appear together.
Let us put the three vowels together into a box and call it Y.
We are effectively rearranging PTTY. This can be done in 4!/2! ways.
However, in these 4!/2! ways, Y itself can take many forms.
For instance, a word PTTY can be PTTAOO or PTTOAO or PTTOOA.
How many forms can Y take?
Y can take 3!/2! = 3 forms.
So, total number of ways = 4!/2! × 3!/2! = = 12 × 3 = 36 waysPROBLEMS BASED ON DICE
Dice questions have a similar framework to digits question. When a die is thrown thrice, we can take the outcomes to be ‘a’, ‘b’, ‘c’. There are two simple differences visavis digits questions.
 a, b, c can take only values from 1 to 6. In digits we have to worry about 0, 7, 8 and 9 as well
 There are no constraints regarding the leading die. All throws have the same number of options.
So, in many ways, dice questions are simpler versions of digits questions.
In how many ways can we roll a die thrice such that all three throws show different numbers?
Let the throws be ‘a’, ‘b’, ‘c’.
‘a’ can take 6 options – 1 to 6
‘b’ can take 5 options – 1 to 6 except ‘a’
‘c’ can take 4 options – 1 to 6 except ‘a’ and ‘b’
Total number of outcomes = 6 × 5 × 4 = 120In how many ways can we roll a die thrice such that at least two throws show the same number?
We can have either two throws same or all three same.
There are 6 ways in which all three can be same — (1, 1, 1), (2, 2, 2), (3, 3, 3), (4, 4, 4), (5, 5, 5), (6, 6, 6).
Now, two throws can be same in three different forms a = b, b = c or c = a
a = b –> Number of outcomes = 6 × 1 × 5. ‘a’ can take values from 1 to 6. b should be equal to ‘a’ and c can take 5 values – 1 to 6 except ‘a’
b = c there are 30 possibilities,
and c = a there are 30 possibilities
Total number of options = 6 + 30 + 30 + 30 = 96In how many ways can we roll a die twice such that the sum of the numbers on the two throws is an even number less than 8?
Sum can be 2, 4 or 6
2 can happen in one way: 1 + 1
4 can happen in 3 ways: 1 + 3, 2 + 2, 3 + 1
6 can happen in 5 ways: 1 + 5, 2 + 4, 3 + 3, 4 + 2,5 + 1
Totally, there are 1 + 3 + 5 = 9 ways.PROBLEMS BASED ON COIN TOSSES
When a coin is tossed three times, how many ways can exactly one head show up?
When a coin is tossed coin 5 times, in how many ways can exactly 3 heads show up?
When a coin is tossed 5 times, in how many ways can do utmost 3 heads show up?Three coins are tossed, options with one head are HTT, THT and TTH. 3 ways
5 coins are tossed, three heads can be obtained as HHHTT, HTHTH, TTHHH, …etc. Obviously this
is far tougher to enumerate.
We can think of this differently. All the versions are nothing but rearrangements of HHHTT. This can be
done in 5!/3!2! ways.Coins questions are common, so it helps to look at them from another framework also.
Let us assume the outcomes of the 5 coin tosses are written down in 5 slots.
Now, suppose, we select the slots that are heads and list them down.
So, a HHHTT would correspond to 123.
HTHTH would be 135.
TTHHH would be 345.
The list of all possible selections is nothing but the number of ways of selecting 3 slots out of 5. This
can be done in 5C3 ways, or, 10 ways.Number of ways of getting exactly r heads when n coins are tossed = nCr
In how many ways can we toss a coin 5 times such that there are utmost 3 heads?
Utmost 3 heads => Maximum of three heads
Number of ways of having 3 heads = 5C3 = 10
Number of ways of having 2 heads = 5C2 = 10
Number of ways of having 1 head = 5C1 = 5
Number of ways of having 0 heads = 5C0 = 1
Utmost 3 heads = 10 + 10 + 5 + 1 = 26 ways.When a coin is tossed 6 times, in how many ways do exactly 4 heads show up? Exactly 2 tails?
When a coin is tossed 6 times, what is the total number of outcomes possible?Coin tossed 6 times, number of ways of getting 4 heads = 6C4 = 15
Exactly two tails = 6C2 = 15
Every outcome where there are 4 heads corresponds to an outcome where there are 2 tails. So, we are
effectively counting the same set of outcomes in both scenarios.
In other words nCr = nC(n–r)
Total number of outcomes = 6C0 + 6C1 + 6C2 + 6C3 + 6C4 + 6C5 + 6C6 = 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64.
This 64 is also$2^6$ .
When a coin is tossed once, there are 2 possible outcomes.
When it is tossed 6 times there will be 2 × 2 × 2 × 2 × 2 × 2 =$2^6$ = 64 outcomes.
Therefore, nC0 + nC1 + nC2 + ……….. + nCn =$2^n$ {This is also seen in the topic ‘Binomial Theorem’. But never hurts to reiterate!}
PROBLEMS BASED ON CARD PACKS
Questions based on card pack are very straightforward. We need to know exactly what lies inside a card pack. Once we know this, everything else falls in place.
A card pack has 52 cards  26 in red and 26 in black.
There are 4 suits totally, 2 of each colour. Each suit comprises 13 cards  an Ace, numbers 2 to 10, and Jack, Queen and King.The cards with numbers 2 to 10 are called numbered cards.
Cards with J, Q, K are called Face cards as there is a face printed on them.In how many ways can we select 4 cards from a card pack such that all are face cards?
There are 12 face cards in a pack. Number of ways of selecting 4 out of these = 12C4
In how many ways can we select 3 cards from a card pack such that none are black numbered cards?
There are 18 black numbered cards. If we select 3 cards and none of these are black numbered cards, then all of these must be from the remaining 34. Number of ways of selecting 3 cards from 34 is 34C3
In how many ways can we select 5 cards from a card pack such that we select at least 1 card from each suit?
We should select 1 card each from 3 of the suits and 2 from the fourth.
The suit that contributes the additional card can be selected in 4C1 ways.
So, total number of outcomes = 4C1 × 13C1 × 13C1 × 13C1 × 13C2CIRCULAR ARRANGEMENT
Let us say there are n people to be seated around a circular table. In how many ways can this happen? If we think about this as n slots, where n things are to fit in, the answer would be n!. But, what we miss out here is the fact that if every object moves one step to the right/left then this would not be a different arrangement. In fact any rotation of one arrangement is not giving us another arrangement. So, how do we think about this?
Let us fix one person’s position. Then, we have the remaining (n–1) persons who can be arranged in (n–1)! ways.
In how many ways can 6 people be arranged around a circle?
In how many ways can 6 people be arranged around a circle if A and B should never sit together?Number of ways of arranging n people around a circle = (n –1)!.
So, the number of ways of arranging 6 people around a table = (6 –1)! = 5! = 120.Now, A and B should never sit together. Let us calculate all the possibilities where A and B do sit together.
Now, A and B can be together called X.
Number of ways of arranging 5 around a circle = 4!.
Now, AB can be sitting such that A is to the left of B or B is to the left of A.
So, total number of options = 4! × 2.
Number of options where A and B do not sit adjacent to each other = 5! – 2 × 4! = 120 – 48 = 72.SELECTING ONE OR MORE FROM A SET
If there are 4 books and 3 CDs on a table, in how many ways can we select at least one item from the table?
Each article has 2 options, either you can select it or you can skip it.
Total no of option =$2^7$ . Within this$2^7$ possibilities, there is one possibility that we skip ALL the items.
Since we need to select at least least one item, we need to subtract this possibility.
Total number of ways =$2^7$ – 1 = 127.If there are 4 identical copies of a book and 3 identical copies of a CD on a table, in how many ways can we select at least one item from the table?
We can select either 0, 1, 2, 3 or 4 books. Similarly, we can select 0, 1, 2 or 3 CDs.
So, total number of options = 5 × 4 = 20 ways.
Of these one will include the option of not selecting any of the things.
So, total number of possible outcomes = 4 × 5 – 1 = 19.Note that here we do not worry about WHICH CD or book we are selecting. Since the CDs and books
are identical, only the number of CDs/books matters