Quarter Wit, Quarter Wisdom: Considering Combinations

Quarter Wit, Quarter WisdomWe will start with Combinations today. The moment we start talking about Permutations and Combinations, the first question many people ask is: “How do I know whether the given problem is a combinations problem or a permutations problem?”

My answer is: “Focus on what you have to do. Do you have to just SELECT some friends/toys/candies/candidates etc or do you have to ARRANGE them in distinct seats/among some children/in distinct positions etc too. If you have to only select, it is a combinations problem; if you have to only arrange, it is a permutations problem; if you have to first select and then arrange, it is a combinations and permutations problem. But if you are not using the formulas (nPr and nCr), you don’t have to think in terms of permutations and combinations. Just think in terms of selecting and arranging.” In the discussion below, I will start with an explanation of how we can make selections and how we can work on combinations without using the formula. We will also take a quick look at the formula and why it is what it is. Then we will move on to some examples.

I hope you remember the basic counting principle that we looked at some weeks back. We can use the same to understand combinations too. Let’s see how.

Say, there are 5 friends but only 3 seats in a row. In how many ways can you make 3 of the 5 friends sit in the 3 seats?

We start by using the basic counting principle.

We have 3 seats ____  ____  ____

In how many ways can we make someone sit on the leftmost seat? In 5 ways. In how many ways can we make someone sit on the middle seat? In 4 ways. In how many ways can we make someone sit on the rightmost seat? In 3 ways. Then in how many ways can we fill all the 3 seats? In 5*4*3 = 60 ways.

Here, we have effectively selected 3 people out of 5 and arranged them in 3 seats. What if we had to only select and not arrange?

Say you have 5 friends and you have to invite any 3 of them to go with you on a vacation. In how many ways can you do that?

Will  the answer still be 60? No because 60 includes the different arrangements too. In this case, we only need to select 3 friends. We don’t have to arrange them in 3 positions. What do you do if you want to un-arrange 3 people? You arrange 3 people by multiplying by 3!. Therefore, you can un-arrange 3 people by dividing by 3!.

Number of ways of selecting 3 people out of 5 = 60/3! = 10 ways

This is equivalent to using the formula:

Number of ways of selecting r people out of a total of n people = nCr = n!/(r! * (n-r)!)

Number of ways of selecting 3 people out of a total of 5 people = 5C3 = 5!/(3! * (5-3)!) = 10

I hope you understand the logic behind the formula. If you don’t want to use the formula, don’t. You can just think in terms of basic counting principle and un-arranging. Let’s look at a couple of examples now.

Question 1: A company consists of 5 senior and 3 junior staff officers. If a committee is created with 3 senior and 1 junior staff officers, in how many ways can the committee be formed?

(A) 12
(B) 30
(C) 45
(D) 80
(E) 200

Solution:

You have to select 3 senior and 1 junior officers. Note here that you don’t have to arrange them in any way. You just have to select.

There are a total of 5 senior officers. You can select 3 of them in 5*4*3/3! ways. Note that we divide by 3! to un-arrange.

There are 3 junior officers and you have to select one of them. You can do that in 3 different ways. Note here that you don’t need to do any calculations when you have to select just one person. Out of 3 people (say A, B and C), you can select one in 3 ways (you can select A or B or C).

So you can select 3 senior and 1 junior officers in 5*4*3/3! * 3 = 30 ways

Answer (B)

Question 2: A class is divided into four groups of four students each. If a project is to be assigned to a team of three students, none of which can be from the same group, what is the greatest number of distinct teams to which the project could be assigned?

(A) 4^3
(B) 4^4
(C) 4^5
(D) 6(4^4)
(E) 4(3^6)

Solution: We need to make a team here. There is no arrangement involved so it is a combinations problem. First we will select 3 groups and then we will select one student from each of those 3 groups.

In how many ways can we select 3 groups out of a total of 4? From the theory discussed above, I hope you agree that we can select 3 groups out of 4 in 4*3*2/3! = 4 ways. The interesting thing to note here is that selecting 3 groups out of 4 is the same as selecting 1 group out of 4. Why? Because we can think of making the selection in two ways – we can select 3 groups from which we will pick a student each or we can select 1 group from which we will not select a student. This will automatically give us a selection of 3 groups. We know that we can select 1 out of 4 in 4 ways (hence the calculation done above was actually not needed).

Now from each of the 3 selected groups, we have to pick one student. In how many ways can we select one student out of 4? In 4 ways. This is true for each of the three groups. We can select 3 groups and one student from each one of the three groups in 4*4*4*4 = 4^4 ways.

Answer (B)

Now that we have discussed the basic theory of combinations, next week we will discuss some combinations questions with constraints.

Karishma, a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches GMAT prep for Veritas Prep and regularly participates in content development projects such as this blog!

4 Responses

  1. Himanshu says:

    Hi Karishma,
    In question 2 of above article, can’t we solve the question other way round. i.e selecting students first and then selecting the groups.

    Total students = 16; So first slot will be filled in 16 ways
    Second slot will be filled in 16-4 = 12 ways
    Third Slot will be filled in 12-4= 8 ways
    So, total number of ways to select students such that none is from the same group =

    16*12*8/3!

    Now, selecting 3 groups out of 4 can be done in 4C3 ways

    So, total ways = 4^5 (I am getting additional 4).

    Why this is wrong. The same approach is being used in the below question.

    If a committee of 3 people is to be selected from among 6 married couples such that the committee does not include two people who are married to each other, how many such committees are possible?

    Please explain.

    Thanks
    H

    • Karishma says:

      You are perfectly correct till here:
      So, total number of ways to select students such that none is from the same group =
      16*12*8/3! = 4^4

      You need to stop now since this is the answer. We have already considered all 4 groups and we don’t need to select 3 groups out of 4 anymore.

  2. Vaishno says:

    Hi Karishma,

    In the second question, I am not able to understand why do we select 3 groups and then pick 1 student from each group?

    Why can’t we just select a team from 4 groups?

    Well I used permutation and then ungrouped the result, but I know that’s not the way I should get used to solving this type of problems.

    • Karishma says:

      You need 3 people and there are 4 groups. Also, you can select only one person from one group. So it’s a 2 step process.
      Select 3 groups out of the 4 because we need only 3 people. We need to consider the different ways in each the 3 people can be from three different groups. You can have (A1, B3, C4) or (B1, C2, D4) etc
      Then select 1 person from each group. You can have (A1, B2, C4) or (A2, B1, C2) etc

Leave a Reply

Spam protection by WP Captcha-Free