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!