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

rajesh_balasubramanian last edited by rajesh_balasubramanian
Director, 2IIM Online CAT Preparation  IIT Madras  IIM Bangalore  CAT 100th percentile  CAT 2011, 2012 and 2014.
DISTRIBUTION INTO GROUPS
In how many ways can we split 8 different objects into groups of 5 and 3?
In how many ways can we split this into groups of 4, 3 and 1?
In how many ways can we split this into groups of 4, 2, and 2?Number of ways of splitting 8 different objects into groups of 5 and 3 = 8C5:
Select 5 objects, the remaining 3 form the second group automatically.
You should also note that it is same as selecting 3 objects from 8, 8C3 x 8C5 = 8C3.8 different objects into groups of 4, 3 and 1:
First select 4 objects – this can be done in 8C4 ways.
Then select 3 out of the remaining 4 – this can be done in 4C3 ways.
Total number of ways = 8C4 × 4C3 = 8!/4!4! x 4!/3!1! = 8!/4!3!1!So, it follows that p + q + r objects can be split into groups of p, q and r in (p+q+r)!/p!q!r! ways as long as p, q, r are distinct.
8 different objects into groups of 4, 2 and 2:
Now, we need to treat this differently. From 8 objects, number of ways of selecting 4 is 8C4.
Post this, number of ways of selecting 2 out of 4 would be 4C2.
But 8C4 × 4C2 would overstate the number. In the final 4C2, we calculate the number of ways of selecting 2 objects from 4, with the assumption that the remaining 2 would form the other group.However, let us say we need to select two out of A, B, C, and D. For every selection of AB in the Group 1 and CD for Group 2, we could have an exact mirror selection CD in Group 1 and AB in Group 2. So, the correct answer should be (8C4 x 4C2)/2!.
Every time we split and allocate into groups of same size, we need to be careful.DISTRIBUTION INTO GROUPS – VARIANTS
In how many ways can 6 identical toys be placed in 3 identical boxes such that no box is empty?
This is simple. Since the toys and boxes are identical, we just need to deal with a ways of splitting six into three natural numbers
1 + 2 + 3 = 6
1 + 1 + 4 = 6
2 + 2 + 2 = 6
These are the three ways in which it can be done.In how many ways can 6 identical toys be placed in 3 distinct boxes such that no box is empty?
Again, we are looking to solve for a + b + c = 6. But in this case, a (1, 2, 3) will be counted as a separate from (3, 2, 1) and (2, 1, 3).
(1, 2, 3) can be rearranged in 3! = 6 ways
(1, 1, 4) can be rearranged in 3C1 ways = 3 ways.
We need to select which box has the set of 4 toys. The other two boxes will have 1 each. Alternatively, we are thinking about in how many ways we can rearrange 114. This can be done in 3!2! ways.
(2, 2, 2) can be done in only one way.
So, totally we have 6 + 3 + 1 = 10 ways.Alternative Method
a + b + c = 6. Now, let us place six sticks in a row
    
This question now becomes the equivalent of placing two ‘+’ symbols somewhere between these sticks. For instance
  +    + , This would be the equivalent of 2 + 3 + 1. or, a = 2, b = 3, c = 1.
There are 5 slots between the sticks, out of which one has to select 2 for placing the ‘+’s.
The number of ways of doing this would be 5C2 = 10.Bear in mind that this kind of calculation counts ordered triplets. (2, 3, 1) and (1, 2, 3) will both be counted as distinct possibilities. This is why we use this method for finding the number of ways of placing 6 identical objects in 3 distinct boxes. So, the above question can also be phrased like this: In how many ways can we have ordered triplets of natural numbers (a, b, c) such that a + b + c = 6. There is another version of this question with ordered triplets of whole numbers. Think about what adjustment needs to be done there.
In how many ways can 6 distinct toys be placed in 3 identical boxes such that no box is empty?
First let us think of the distributions.
The boxes can have
1, 2, 3: This can be done in 6C3 × 3C2 ways. First select 3 out of 6, and then 2 out of the remaining 3. This is nothing but distributing 6 as 3, 2, 1 which can be done in 6!/(2! × 3! ×1!)ways
1, 1, 4: This can be done in 6C4 ways. Once we select 4 out of 6, the other two go into one box each. Since the boxes are identical, we do not have to worry about selecting anything beyond the first set of 4 toys.
2, 2, 2: This looks like it could be 6C2 × 4C2 ways. But this will carry some multiple counts. The idea we are using here is simple – select 2 out of 6 and then select 2 out of 4.When we do this, a selection of AB, and then CD will get counted. This will get accounted as AB, CD, EF. However, we will also be counting a selection of CD, AB, EF, and EF, AB, CD. Since the boxes are identical, all these selections are effectively the same. So, number of ways would be 6C2 x 4C2 / 3!
So, total number of ways of doing this would be 60 + 15 + 15 = 90 ways.
In how many ways can 6 distinct toys be placed in 3 distinct boxes such that no box is empty?
Again, let us start with the distributions.
Scenario I: (1, 2, 3): This can be done in 6C3 × 3C2 × 3! ways. First select 3 out of 6, and then 2 out of the remaining 3. After we have done this, the toys can go into the three distinct boxes in 3! ways. 360 waysScenario II: 1, 1, 4: This can be done in 6C4 × 3! ways. Once we select 4 out of 6, the other two go get broken up as 1 and 1. Now, we have something akin to ABCD, E and F to be allotted into 3 distinct boxed. This can be done in 3! ways. 90 ways
Scenario III: 2, 2, 2: This should be 6C2 × 4C2 ways. The idea we are using here is simple – select 2 out of 6 for the first box and then select 2 out of 4 for the second box. 90 ways.
Total number of ways = 360 +90 + 90 = 540 ways.
Now, this question can be rephrased wonderfully like this:
How many onto functions can be defined from {a, b, c, d, e, f} to {1, 2, 3}?
You can solve the above question by thinking of all functions from the first set to the second and subtracting the non–onto functions from that. Needless to say, we would get the same answer.COUNTING AND NUMBER THEORY
How many factors of
$2^7 * 11^5 * 7^4$ are perfect squares?Any factor of
$2^7 * 11^5 * 7^4$ will be of the form$2^a * 11^b * 7^c$ a < = 7
b < = 5
c < = 4Any perfect square’s prime factorisation will have all the powers as even numbers. So, a can take values 0, 2, 4, 6; b can take values 0, 2 or 4; and c can take values 0, 2 or 4.
Number of factors that are perfect squares are 4 × 3 × 3 = 36All numbers from 1 to 250 (in decimal system) are written in base 7 and base 8 systems. How many of the numbers will have a non–zero units digit in both base 8 and base 7 notations?
A number when written in base 8, if it ends in 0, should be a multiple of 8. Likewise for base 7. So, effectively this question becomes — How many natural numbers exist less than 251 that are multiples of neither 7 nor 8.
Let us first find out numbers that are multiples of either 7 or 8.
Multiples of 7 — 7, 14, 21, 28,.......245... 35 numbers in this list.
Multiples of 8 — 8, 16, 24, 32,.......248... 31 numbers in this list.
Some numbers will be multiples of 7 and 8.
Multiples of 56 — 56, 112, 168, 224… 4 numbers in this list
Number of numbers that are multiples of 7 or 8 = 35 + 31 – 4 = 62
Number of numbers that are multiples of neither 7 nor 8 = 250 – 62 = 188How many natural numbers less than 10000 exist such that sum of their digits is 6?
We are considering all numbers up to 9999.
All numbers of the form ABCD such that a, b, c, d can take values from 0 to 9.
a + b + c + d = 6 where a, b, c, d are all whole numbers.
Now, a, b, c, d can take value 0. Let us simplify this as p = a + 1, q = b + 1, r = c + 1, s = d + 1.
Now, p + q + r + s = 10. p, q, r, s cannot be zero.
Number of solutions for the above equation is 9C3.
Bear in mind that p, q, r, s can all never be greater than 10. In this case, as the total adds up to 10, we have little to worry about. If the sum were greater than 10, it could become far more complex.How many numbers are factors of
$24^{20}$ but not of$24^{15}$ ?$24^{20}$ = ($2^3$ x 3)^20 =$2^{60}$ x$3^{20}$
Number of factors of this number = 61 × 21 = 1281$24^{15}$ =$2^{45}$ x$3^{15}$
Number of factors = 46 × 16 = 736
Factors of$24^{15}$ will be a subset of factors of$24^{20}$ .
So, the number of numbers that are factors of$24^{20}$ but not of$24^{15}$ is nothing but
61 × 21 – 46 × 16
= 1281 – 736
= 545.How many natural numbers less than
$10^4$ exist that are perfect squares but not perfect cubes?Number of perfect squares less than 10000 = 99.
10000 =$100^2$ ; so till$99^2$ will be less than 10000.
So, there are 99 perfect squares less than 10000?
From these some numbers that are also perfect cubes have to be eliminated.
So, we are looking for numbers that are perfect squares and perfect cubes. Or, we are looking for powers of 6.$1^6$ ,$2^6$ ,$3^6$ ,$4^6$ are all less than 10000, but$5^6$ is greater than 10000.
So, there are only 4 powers of 6.
So, out of 99, we need to subtract 4 possibilities. Or, there are 95 different natural numbers that will be perfect squares but not perfect cubesWill solve some problems!
In how many ways can the letters of the word ‘MALAYALAM’ be rearranged? In how many of the words would the A’s appear together? In how many of the words are the consonants together?
Rearrangements of MALAYALAM = 9!/4!2!2!
Rearrangements where the A’s appear together:
Put 4 A’s together into X and rearrange MLYLMX. This can be rearranged in 6!/2!2!
Rearrangements where the consonants appear together: Put consonants together into Z. The word will be AAAAZ. This can be rearranged in 5!/4! ways.
Now, Z is MMLLY. Z can take 5!/2!2! ways.
So, total number of arrangements =5!/4! × 5!/2!2!In Octaworld, everything is written in base 8 form. Ram’s 1050 page tome written in the real world is translated to Octa–speak and reprinted in Octa–world. In the reprint, each page number is written in base 8 form. How many times will the digit 4 be printed on the page numbers?
$(1050)_{10}$ =$(2032)_8$ .
So, we need to see how many times the digit 4 gets printed from 1 to 2032 in base 8.
Let us consider a number of the form$(abc)_8$ where a, b c take all digits from 0 to 7. Essentially, in decimal equivalent, we are considering all numbers from 1 to 511.
When c = 4, a can take all values from 0 to 7 and b can take all values from 0 to 7. So, 4 gets printed at c 64 times.
When b = 4, a can take all values from 0 to 7 and c can take all values from 0 to 7. So, 4 gets printed at b 64 times.
When a = 4, b can take all values from 0 to 7 and c can take all values from 0 to 7. So, 4 gets printed at a 64 times.
So, totally 4 gets printed 64 × 3 = 192 times from$(1)_8$ to$(777)_8$
From$(1000)_8$ to$(1777)_8$ , 4 would get printed 192 times.
So, up to$(2000)_8$ , the digit 4 gets printed 192 × 2 = 384 times.
We need to account for all base 8 numbers from$(2001)_8$ to$(2032)_8$ .
In these 26 numbers, the digit 4 gets printed thrice$(2004)_8$ ,$(2014)_8$ ,$(2024)_8$ .
So, the digit 4 gets printed 384 + 3 = 387 times.When a die is thrown twice, in how many outcomes will the product of the two throws be 12?
12 can be formed from 3 × 4 or 2 × 6 {1 × 12 is not possible with die}.
This can happen in 2 + 2 = 4 ways.How many words exist that have exactly 5 distinct consonants and 2 vowels?
Scenario I: 5 distinct consonants and 2 distinct vowels – Number of words = 21C5 × 5C2 × 7!
Scenario II: 5 distinct consonants and 1 vowel appearing twice – Number of words = 21C5 × 5C1 × 7!/2!When a coin is tossed 6 times, in how many outcomes will there be more heads than tails?
We should have more heads than tails => There should be 4 heads or 5 heads or all 6 heads.
Number of ways = 6C4 + 6C5 + 6C6
= 15 + 6 + 1
= 22In how many ways can we pick 4 cards from a card pack such that there are no Aces selected and there are more face cards than numbered cards?
Scenario I: 3 face cards and 1 numbered card: 12C3 × 36C1
Scenario II: 4 face cards and 0 numbered cards: 12C4
Therefore, total number of ways is 12C3 × 36C1 + 12C4On a table, there are 4 identical copies of a book and 3 CDs. In how many ways can we pick at least one book and at least one CD from the table?
There are 4 identical copies of a book. One can pick either 0, 1, 2, 3, or all 4 of these – 5 different options. We need to pick at least one book. So, we have only 4 options – 1, 2, 3, or 4 books being picked
There are 3 different CDs. Each CD can be either picked or not picked. So, total number of options =$2^3$ .
Of these there is one option where no CD is picked. We need to exclude that option. So, number of possibilities =$2^3$ – 1
Total number of outcomes = 4 × ($2^3$ – 1)
= 4 × 7
= 28What is sum of all 4digit numbers formed by rearranging the digits of the number 2235?
Number of rearrangements of 2235 = 4!/2! = 12.
So, we need to add these 12 numbers.
Let us consider the units’ digit of these 12 numbers.
The units digit will be the one of the digits 2, 3, or 5. If the last digit were 3, the first 3 digits should be some rearrangement of 2, 2, and 5. So, there are 3!/2! Such numbers. Or, 3 such numbers.
Similarly there are three numbers with 5 as the units digit.
If the last digit were 2, the first 3 digits should be some rearrangement of 2, 3, and 5. So, there are 3! such numbers, or, 6 such numbers.
So, the units digit will be 2 for six numbers, 3 for three numbers, and 5 for three numbers. Sum of all these unit digits will be 2 × 6 + 3 × 3 + 5 × 3 = 12 + 9 + 15 = 36.
Sum of all the tens digits will be 36. Sum of all the digits in the hundreds’ place will be 36.
Sum of all the digits in the thousands’ place is 36.
So, sum of all the 4–digit numbers will be 36 × 1111 = 39996.When a die is thrown twice, in how many ways can we have the sum of numbers to be less than 8?
Sum of the numbers seen in the two throws can be 2, 3, 4, 5, 6 or 7.
Sum of the digits = 2: This can only be 1 + 1. One way
Sum of the digits = 3: This can be 1 + 2 or 2 + 1. 2 ways
Sum of the digits = 4: 1 + 3, 3 + 1, 2 + 2. 3 ways
Sum of the digits = 5: 1 + 4, 4 + 1, 3 + 2, 2 + 3. 4 ways
Sum of the digits = 6: 1 + 5, 5 + 1, 2 + 4, 4 + 2, 3 + 3. 5 ways
Sum of the digits = 7: 1 + 6, 6 + 1, 2 + 5, 5 + 2, 3 + 4, 4 + 3. 6 ways
Sum of the numbers in the two throws can be less than 8 in 1 + 2 + 3 + 4 + 5 + 6 = 21 ways.
We notice a very simple pattern here. Try the sum of the numbers all the way to 12 and see the rest of the pattern also.Set P has elements {1, 2, 3..…10}. How many non–empty subsets of P have the product of their elements as not a multiple of 3?
Total number of subsets =
$2^{10}$
For choosing any subset, each element can either be part of the subset or not part of the subset. So, for each element, there are two options. So, with 10 elements in the set, we can create$2^{10}$ subsets. We should bear in mind that this$2^{10}$ includes the 2 improper subsets as well. The whole set P and the null set are included in this$2^{10}$ .
Subsets whose product is not a multiple of 3 = Subsets of the set {1, 2, 4, 5, 7, 8, 10} =$2^{7}$ . This includes the empty subset also. So, the correct answer should be$2^{7}$ –1A, B, C, D, E are doctors, P, Q, R, S, are engineers. In how many ways can we select a committee of 5 that has more engineers than doctors?
Two scenarios are possible.
3 engineers and 2 doctors: 4C3 × 5C2 = 4 × 10 = 40
4 engineers and 1 doctor : 4C4 × 5C1 = 1 × 5 = 5
Total number of possibilities = 40 + 5 = 45From a card pack of 52, in how many ways can we pick a sequence of 4 cards such that they are in order and from different suits? Consider Ace to be the card following King in each suit. So, Ace can be taken to precede ‘2’ and succeed ‘King’. So, JQKA would be a sequence, so would be A234. However, QKA2 is not a sequence.
4 cards in order can be A234, 2345, ….JQKA. 11 different possibilities
For a given set of four cards, say 2345, they can be from 4 different suits in 4! ways.
So, total number of possibilities = 11 × 4! = 264.