Demystifying Permutation & Combination - Rajesh Balasubramanian - CAT 100th Percentile - CAT 2011, 2012 and 2014


  • 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.

    1. This topic is based on the simple idea of counting. So, from now on, we will avoid the terms ‘permutation’ and ‘combination’.
    2. We will build the theory for this topic mostly with examples.
    3. Wherever possible, we will list and count. Especially, if the answer is less than 10 we will shoot to list out all possibilities.
    4. 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, S3B4

    Fundamental 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 = 12

    Let 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.

    1. Black plate, white letters
    2. Black plate, yellow letters
    3. White plate, yellow letters
    4. White plate, black letters
    5. Yellow plate, white letters
    6. 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?

    1. Rose and Lily
    2. Lily and Violet
    3. 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, VV

    What 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? 3

    In 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 PositionRamJohnJohnKrishnaKrishna
    2nd PositionJohnRamKrishnaJohnRam
    3rd PositionKrishnaKrishnaRamRamJohn

    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 = 64

    A 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 = 24

    The 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).

    FirstRedRedBlueBlueYellowYellow
    SecondBlueYellowRedYellowRedBlue
    ThirdYellowBlueYellowRedBlueRed

    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 nrn^r ways.
    From n options, select ‘r’ such that order is important and repetition is allowed. This can be done in nrn^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!/(nr)!r!n! / (n - r)!r!. This term is called as nCr.

    0_1484824244541_pnc_part1_1_2iim.png

    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 them

    A 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:

    BACADAEA
    ABCBDBEB
    ACBCDCEC
    ADBDCDED
    AEBECEDE

    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:

    AABACADAEA
    ABBBCBDBEB
    ACBCCCDCEC
    ADBDCDDDED
    AEBECEDEEE

    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 follows

    AB
    ACBC
    ADBDCD
    AEBECEDE

    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.

    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 numbers

    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?

    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 × 7

    PROBLEMS 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 ways

    PROBLEMS 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 vis-a-vis digits questions.

    1. 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
    2. 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 = 120

    In 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 = 96

    In 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 262^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 = 262^6 = 64 outcomes.
    Therefore, nC0 + nC1 + nC2 + ……….. + nCn = 2n2^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 × 13C2

    CIRCULAR 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 = 272^7. Within this 272^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 = 272^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

    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 ways

    Scenario 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 27115742^7 * 11^5 * 7^4 are perfect squares?

    Any factor of 27115742^7 * 11^5 * 7^4 will be of the form 2a11b7c2^a * 11^b * 7^c

    a < = 7
    b < = 5
    c < = 4

    Any 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 = 36

    All 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 = 188

    How 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 242024^{20} but not of 241524^{15} ?

    242024^{20} = (232^3 x 3)^20 = 2602^{60} x 3203^{20}
    Number of factors of this number = 61 × 21 = 1281
    241524^{15} = 2452^{45} x 3153^{15}
    Number of factors = 46 × 16 = 736
    Factors of 241524^{15} will be a subset of factors of 242024^{20} .
    So, the number of numbers that are factors of 242024^{20} but not of 241524^{15} is nothing but
    61 × 21 – 46 × 16
    = 1281 – 736
    = 545.

    How many natural numbers less than 10410^4 exist that are perfect squares but not perfect cubes?

    Number of perfect squares less than 10000 = 99.
    10000 = 1002100^2; so till 99299^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.
    161^6, 262^6, 363^6, 464^6 are all less than 10000, but 565^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 cubes

    Will 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(1050)_{10} = (2032)8(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(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(1)_8 to (777)8(777)_8
    From (1000)8(1000)_8 to (1777)8(1777)_8 , 4 would get printed 192 times.
    So, up to (2000)8(2000)_8, the digit 4 gets printed 192 × 2 = 384 times.
    We need to account for all base 8 numbers from (2001)8(2001)_8 to (2032)8(2032)_8.
    In these 26 numbers, the digit 4 gets printed thrice (2004)8(2004)_8, (2014)8(2014)_8, (2024)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
    = 22

    In 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 + 12C4

    On 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 = 232^3.
    Of these there is one option where no CD is picked. We need to exclude that option. So, number of possibilities = 232^3 – 1
    Total number of outcomes = 4 × ( 232^3 – 1)
    = 4 × 7
    = 28

    What is sum of all 4-digit 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 = 2102^{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 2102^{10} subsets. We should bear in mind that this 2102^{10} includes the 2 improper subsets as well. The whole set P and the null set are included in this 2102^{10}.
    Subsets whose product is not a multiple of 3 = Subsets of the set {1, 2, 4, 5, 7, 8, 10} = 272^{7}. This includes the empty subset also. So, the correct answer should be 272^{7} –1

    A, 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 = 45

    From 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.


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.