Combinatorics Made Easy!

Let’s continue our discussion on combinations here. From the previous posts, we understand that combination is nothing but “selection.” Today we will discuss a concept that confuses a lot of people. It is similar to making committees (that we saw last week), but with a difference. Read the two questions given below:

Question 1: In how many ways can one divide 12 different chocolate bars equally among four boys?

Question 2: In how many ways can one divide 12 different chocolate bars into four stacks of 3 bars each?

Do you think the 2 questions are the same and the answer would be the same in both cases? After all, once you divide the chocolates into four stacks, it doesn’t matter who you give them to! Actually, it does! The two questions are different. Since the chocolates are different, the four stacks will be different. So how you distribute the stacks among the 4 boys is material.

Let us take a simple case first.

Say, there are just 4 chocolate bars: A, B, C, D
We want to split them in 2 groups containing 2 chocolate bars each. There are two ways of doing this:

Method I
In group 1, we can put any 2 chocolate bars and we will put the remaining 2 chocolate bars in group 2.

We could put them in two distinct groups in the following 6 ways:

1. Group1: A and B, Group2: C and D
2. Group1: C and D, Group2: A and B (If you notice, this is the same as above. The only difference is that A and B is group 2 and C and D is group 1 here)
3. Group1: A and C, Group2: B and D
4. Group1: B and D, Group2: A and C (This is the same as above. The only difference is that A and C is group 2 and B and D is group 1 here)
5. Group1: A and D, Group2: B and C
6. Group1: B and C, Group2: A and D (Again, this is the same as above. Here, B and C is group 2 and A and D is group 1)

We have to put the four chocolates in two different groups, group 1 and group 2. It is similar to distributing 4 chocolates between 2 boys equally. Boy 1 could get (A and B) or (C and D) or (A and C) or (B and D) or (A and D) or (B and C). Boy 2 gets the other 2 chocolates in each case.

Method II
The two groups can be made in the following three ways:

A and B, C and D

A and C, B and D

A and D, B and C

In this case, the groups are not named/distinct. You have 4 chocolates in front of you and you just split them in 2 groups. (A and B, C and D) is the same as (C and D, A and B). There are a total of 3 ways of doing this i.e. half of the number of ways we saw in method 1. It is logical, isn’t it? You divide the answer you get above by 2! because the two groups are not distinct in this case.

Let’s look at the original two questions now:

Question 1: In how many ways can one divide twelve different chocolate bars equally among four boys?

You need to divide 12 chocolate bars among four boys i.e. you have to make four distinct groups. To boy 1, you can give the first chocolate in 12 ways, the second chocolate in 11 ways and the third chocolate in 10 ways. But we don’t want to arrange the chocolates so you can select 3 chocolates for boy 1 in 12*11*10/3! ways (this is equivalent to 12C3 if you follow the formula). Similarly, you can select 3 chocolates for the second boy in 9*8*7/3! ways (i.e. 9C3), for the third boy in 6*5*4/3! ways (i.e. 6C3) and for the fourth boy in 3*2*1/3! ways (i.e. 3C3)

Therefore, you can distribute 12 chocolates among 4 boys equally in (12*11*10/3!) * (9*8*7/3!) * (6*5*4/3!) * (3*2*1/3!) = 12!/(3!*3!*3!*3!) ways

Alternatively, you can visualize putting the 12 chocolates in a row in 12! ways and drawing a line after every three chocolates to demarcate the groups.

OOO l OOO l OOO l OOO

Since the chocolates within the groups are not arranged, we divide 12! by 3! for every group. Since there are 4 groups, number of ways of making 4 distinct groups = 12!/(3!*3!*3!*3!)

Question 2: In how many ways can one divide 12 different chocolate bars into four stacks of 3 bars each?

What do you think will the answer be here? Will it be the same as above? No. Here the 4 stacks are not distinct. You need to divide the answer you obtained above by 4! (similar to the simple example with just 4 chocolates we saw above).

In this case, the required number of ways = 12!/(3!*3!*3!*3!*4!)

Since the groups are not distinct here, your answer changes. When the question says that you need to make n groups/bundles/teams that are not distinct, you need to divide by (n!). If the groups/bundles/teams are distinct then you do not divide by (n!).

Let’s look at another question that uses the same concept.

Question 3: 8 friends want to play doubles tennis. In how many different ways can the group be divided to make 4 teams of 2 people each?

(A) 420
(B) 2520
(C) 168
(D) 90
(E) 105

Solution: It is quite clear here that the teams are not distinct i.e. we don’t have team 1, team 2 etc. But let’s solve this question by first making team 1, team 2, team 3 and team 4. Later we will adjust the answer.

Out of 8 people, in how many ways can we make team 1? In 8*7/2! ways (i.e. 8C2).
Out of 6 people, in how many ways can we make team 2? In 6*5/2! ways (i.e. 6C2).
Out of 4 people, in how many ways can we make team 3? In 4*3/2! ways (i.e. 4C2).
Out of 2 people, in how many ways can we make team 4? In 2*1/2! ways (i.e. 2C2).

In how many ways can we make the 4 teams? In 8*7*6*5*4*3*2*1/(2!*2!*2!*2!) = 8!/(2!*2!*2!*2!) ways. But here, we have considered the 4 teams to be distinct. Since the teams are not distinct, we will just divide by 4!

We get 8!/(2!*2!*2!*2!*4!) = 105

Answer (E) This question is discussed HERE.

I hope the explanation makes sense. We will continue with Combinatorics in the next post. I told you that once we get into it, it takes a long time to get out of it

In this post, I want to discuss the symmetry principle of linear arrangements with you. If you do not understand the symmetry principle, then it is possible that the following has happened with you:

You see a hard question and start working on it. You know that there are going to be three-four different cases. You find the number of arrangements in each case. Then, very carefully, you add them all up and get your answer. You check the answer key and behold, your answer is correct. Just for the fun of it, you turn your page to the solutions section and see that there are just two lines there which go something like this: “You can arrange 6 people in 6! ways. In half of these 6! ways, A will be ahead of B so answer is 6!/2.” and you end up feeling pretty unhappy even though you got the correct answer!

To ensure that this doesn’t happen again, let’s try and understand the symmetry principle.

Let’s work on a simple example first:

Question: There are 3 contestants, A, B and C. In how many different ways can they complete a race if the race doesn’t end in a dead heat?

Solution: Since the race doesn’t end in a dead heat, there is no tie. The following arrangements are possible:

A B C
A C B
B A C
B C A
C A B
C B A

A total of 3! = 6 arrangements. The first position is occupied by the contestant whose name is written first i.e. A B C implies A stands first, B stands second and C stands third in the race.

In how many of these arrangements is A ahead of B? We count and get 3 (A B C, A C B and C A B)

In how many of these arrangements is B ahead of A? We count and get 3 again (B A C, B C A, C B A)

The question is that out of 6 arrangements, why is it that in half A is ahead and in the other half, B is ahead? This is so because the arrangements are symmetrical. Each element has the same status. Since we are taking into account all arrangements, if half of them are partial toward A, other half have to be partial toward B. There is no difference between A and B. They are considered equal elements. Now if I ask you the number of arrangements in which B is ahead of C, you should jump up and say 3 immediately.

Let’s now look at the question I left you with in the last post.

Question 6: 6 people go to a movie and sit next to each other in 6 adjacent seats in the front row of the theatre. If A cannot sit to the right of F, how many different arrangements are possible?

Solution: ‘to the right of F’ means anywhere on the right of F, not necessarily on the adjacent seat. Here we see symmetry because there are only 2 ways in which A can sit. In every arrangement, A is either to the left of F (any seat on the left) or to the right of F (any seat on the right). There is nothing else possible. The number of cases in which A will sit to the left of F will be the same as the number of cases in which he will sit to the right of F. That is why the answer here will be 6!/2 = 360.

I hope you understand this principle now.

Let’s quickly look at a couple of variants now.

Question 7: 7 people (A, B, C, D, E, F and G) go to a movie and sit next to each other in 7 adjacent seats in the front row of the theatre. A will not sit to the left of F and B will not sit to the left of E. How many different arrangements are possible?

Solution: Number of ways of arranging 7 people in 7 seats is 7! (using Basic Counting Principle)

Of these 7! arrangements, we want those arrangements in which A is sitting to the right of F and B is sitting to the right of E. A will sit to the right of F in half of the 7! arrangements. Of these 7!/2 arrangements, half will have B to the right of E and other half will have B to the left of E. So the number of arrangements in which A is to the right of F and B is to the right of E is (7!/2)/2 = 7!/4

Question 8: 7 people (A, B, C, D, E, F and G) go to a movie and sit next to each other in 8 adjacent seats in the front row of the theatre. A will not sit to the left of F in how many different arrangements?

Solution: We have a vacant spot here. Recall the way we deal with vacant spots (discussed in the last post) — we use Mr V.

8 people (including our imaginary Mr V) can be arranged in 8 seats in 8! ways.

We want only those arrangements in which A is sitting to the right of F. In half of the 8! arrangements, A must be to the right of F (same as before) so required number of arrangements = 8!/2

There are many more variations possible but I will stop here. Try some on your own and get back if you have a doubt. I will discuss some other little concept of Combinatorics with you in the next post.

using some examples, let’s look at different ways of distributing identical/distinct objects among people or in groups. There are some formulas which can be used in some of these cases but I will only discuss how to use the concepts we have learned so far to deal with these questions. I am not a fan of unintuitive formulas since the probability (we will come to this topic soon) that we will get to use even one of them in GMAT is quite low while the effort involved in cramming all of them is humongous. Therefore, I only want to focus on our core concepts which we can apply in various situations. Let’s start with our first example.

Question 1: In how many ways can 5 different fruits be distributed among four children? (Some children may get more than one fruit and some may get no fruits.)

(A) 4^5
(B) 5^4
(C) 5!
(D) 4!
(E) 4!*5!

Solution 1: This is the simplest case – 5 different things are to be distributed among 4 different people. Say, the five different fruits are: an apple, a banana, a strawberry, an orange and a blueberry. In how many ways can you give an apple to someone? In 4 ways. You can give the apple to any one of the 4 children. Similarly, in how many ways can you give a banana to someone? Again in 4 ways. It is acceptable to give more than one fruit to the same child so you again have 4 possibilities for the banana. Similarly, all the remaining fruits can also be distributed in 4 ways each.

Total number of ways of distributing 5 different fruits among 4 children = 4*4*4*4*4 = 4^5 ways.

Answer (A) This question is discussed HERE.

Another popular variation on this type of question is this:

Question 1a: In how many ways can 5 different rings be worn in four particular fingers? (Some fingers may get more than one ring and some may get no rings.)

Here, the answer will be a little different. Think why.

Question 2: In how many ways can 5 apples (identical) be distributed among 4 children? (Some children may get no apples.)

(A) 56
(B) 144
(C) 200
(D) 256
(E) 312

Solution: We have 5 identical apples and 4 children. We want to find the number of ways in which these apples can be distributed among the children.

Method I

5 apples can be distributed in various ways: {5, 0, 0, 0}, {4, 1, 0, 0}, {3, 2, 0, 0}, {3, 1, 1, 0}, {2, 2, 1, 0}, {2, 1, 1, 1}.

{5, 0, 0, 0} means that one child gets all 5 apples and all others get none. Similarly, {4, 1, 0, 0} means that one child gets 4 apples and another child gets 1 apple. No one else gets any apples and so on…

In each one of these cases, various arrangements are possible e.g. take the case of {5, 0, 0, 0}. The first child could get all 5 apples OR the second child could get all 5 apples OR the third child could get all 5 apples OR the fourth child could get all 5 apples. Basically, the number of ways in which these 4 objects – 5, 0, 0 and 0 can be distributed in 4 different spots (i.e. 4 children) is 4!/3! = 4 arrangements (we divide by 3! because three of the objects – 0, 0 and 0 – are identical). This is just our beloved basic counting principle in action.

Similarly, in the case of {4, 1, 0, 0}, we will get 4!/2! = 12 arrangements (since 2 objects are identical) i.e. 5 apples can be distributed among 4 children by giving 4 apples to one child and 1 apple to another child in 12 ways. The first child could get 4 apples and the second child could get 1 apple OR the third child could get 4 apples and the first child could get 1 apple etc.

In the same way, we will get 12 arrangements in each one of these cases: {3, 2, 0, 0}, {3, 1, 1, 0} and {2, 2, 1, 0}. In the case of {2, 1, 1, 1}, we will get 4!/3! = 4 arrangements.

In all, 5 identical apples can be distributed among 4 children in 4 + 12 + 12 + 12 + 12 + 4 = 56 ways

Here, we have just counted out the ways in which 5 things can be distributed in 4 groups. If we miss even one of these cases, all our effort would go waste. Therefore, let’s look at a more analytical method of solving this question.

Method II

Let’s put the 5 apples in a row: A A A A A

We have to split them in 4 groups. The 4 groups will have a one-to-one relation with the 4 children – Apples in the first group will be given to the first child, those in the second group will be given to the second child and so on…

Say we split the apples in 4 groups in the following way: A A l A l A l A

The vertical lines separate one group from the other. The first group has 2 apples and the rest of the three groups have 1 apple each. This means, the first child gets 2 apples and each of the other 3 children get 1 apple each.

The split can also be made in the following way: A l A A l A l A

Here, the second group has 2 apples and the rest of the three groups have 1 apple each. So the second child gets 2 apples and the rest of the 3 children get 1 apple each.

The split can also be made in the following way: l A A A l A l A

Here, the first group has no apples, the second group has 3 apples and the third and the fourth groups have one apple each. The first child gets no apples, the second child gets 3 apples and the other 2 children get 1 apple each.

What I am trying to show here is that arranging these 5 identical As and the 3 identical vertical lines in as many different ways as possible will give us all the ways in which we can distribute 5 identical apples among 4 different children.

In how many different ways can we arrange these 8 objects i.e. 5 identical As and 3 identical vertical lines? In 8!/(5! * 3!) = 56 ways

Answer (A). This question is discussed HERE.

We have seen how to solve this question in two different ways. A point to note here is that method II cannot be used in question 1 above. Think why.

Now try to solve these two questions:

Question 3: In how many ways can 5 different fruits be distributed among 4 identical baskets?

Question 4: In how many ways can 5 apples (identical) be distributed among 4 identical baskets?

We will look at their solutions and the solution of the variation question in the next post.

Let’s start this post with a question: In how many different ways (relative to each other) can 5 friends sit around a round table if all the seats are identical?

I guess that most of you will be able to answer it –> \(4! = 24\) ways

After all, you know the formula of circular arrangement which is \((n-1)!\). But, many of you probably do not understand exactly why the formula is (n-1)! Today’s post is focused on explaining the concept of circular arrangement. If you are wondering why you need to know the theory behind the formula when all you need to do in a question is apply the formula and get the answer, here is why — you will be able to solve a straight forward 500-600 level question knowing just the formula but you will not get the 700+ level GMAT question correct. You need to understand the basics behind the formula so that you can apply it with modifications in more inventive situations. I will give you a couple of questions after discussing the theory and you will see what I mean. Right now, let’s focus on the question posed above.

Question 6: In how many different ways (relative to each other) can 5 friends sit around a round table if all the seats are identical?

Now there are two ways to explain the formula used here. I will give both. See what makes more sense to you.

Method 1:

When we pose questions on circular arrangement, the different arrangements we are looking for are those in which people are sitting differently relative to each other. So ignore any other point of reference. Say there is a monochromatic circular room with a circular door right in the middle of the roof and people enter the room Mission-Impossible style. There is a circular table with 5 chairs around it all placed at equal distances. When the first person, Mr. T, drops in, which chair should he sit on? Can we say that it is immaterial which chair he sits on since all the seating spaces are exactly the same?



Since there is no one else sitting as yet, for him every seat is the same. In how many ways can he choose a seat then? In only one way (since every way in which he chooses a seat is the same). No matter which chair he sits on, the arrangement remains exactly the same.

Now when the second person, Mr. B, drops in, in how many different ways can he occupy a seat? Mr. B has four choices. Each one of the seats is different relative to where Mr. T. sits. Mr. B can choose to sit on the left of Mr. T, next to him — i.e., on seat number 1. Or he can choose to sit on the left of Mr. T but with a seat between them i.e. seat number 2. Or he can sit on the right of Mr. T, next to him i.e. seat number 4. Or he can sit on the right of Mr. T but with a seat between them i.e. seat number 3. Each one of the 4 seats are different relative to Mr. T.



So Mr. B can choose a seat in 4 ways.

Next, when Mr. M drops in, he can choose a seat in 3 ways and so on till the last person has 1 seat left for him. The total number of arrangements then are 4*3*2*1 = 24 (think of your basic counting principle here). For the first person, all seats are the same so he can choose in 1 way. He creates a frame of reference and thereafter, every seat is distinct (relative to him). So the rest of the (n-1) people can sit in (n-1) seats in (n-1)! ways (using Basic Counting Principle).

This is how we arrive at the formula (n-1)!

Method 2:

Let’s say we have arranged the 5 people on the 5 seats. Would you say that the following 5 combinations are exactly the same (relative to people)?



Mr. B is next to Mr. T on the left and Mr. N is next to Mr. T on the right. Mr. M is to the left of Mr. B and Mr. C is to the right of Mr. N.

Similarly, these 5 arrangements are exactly the same too (but different from the arrangements above).



Mr. C is next to Mr. T on the left and Mr. M is next to Mr. T on the right. Mr. B is to the left of Mr. C and Mr. N is to the right of Mr. M.

Every group of 5 arrangements is actually a single arrangement since relative to one another, people are arranged in the same way. So we divide 5! by 5 to count only the actual distinct arrangements.

Hence we get the formula \(\frac{n!}{n} = (n-1)!\)

I like to think in terms of method 1 since it helps me take care of a lot of variations on simple circular arrangement questions. Let’s look at one of these variations.

Question 7: There are 5 people – A, B, C, D and E. They have to sit around a circular table with 5 chairs such that A can sit neither next to D nor next to E. How many such distinct arrangements are possible?

Solution: A can sit neither next to D nor next to E. So A has to sit next to B and C. Let’s say we first make A sit on any one chair. In how many ways can A choose his chair? In only 1 way because all the chairs are the same for him (he is the first person being seated). Now B and C have to sit next to him. B can sit on the right of A and C can sit on the left of A OR B can sit on the left of A and C can sit on the right of A. There are two ways in which you can arrange B and C around A. Now there are 2 chairs left and two people D and E. D can choose his chair in 2 ways since the two seats are distinct (relative to A, B and C) and the last chair will be left for E.

Total number of arrangements = 1*2*2*1 = 4 ways

Note: In case nothing is mentioned, in a circular arrangement, two seating arrangements are considered different only when the positions of the people are different relative to each other. If it is given that the seats are distinct (say they are different colored), then the number of arrangements is n! (same as in the case of linear arrangements)

Now, let me leave you with a question which is based on the concept of circular arrangement and can be easily solved if you understand the theory above. I will discuss its solution in the next post.

Question 8: In how many different ways (relative to each other) can 8 friends sit around a square table with 2 seats on each side of the table?

In the post above, we discussed the basics of combinations. Until and unless you have worked a decent bit with combinatorics in high school, the formula of combinations will not be very intuitive. We have already discussed how you can easily think of “selection” in terms of basic counting principle and un-arranging instead of the formula, if you so desire. Today, I would like to discuss some combination questions with constraints. A very common type of such questions asks you to make a committee of r people out of n people under some constraints. Let me show you what I mean with the help of some examples.

Question 1: 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?

(A) 20
(B) 40
(C) 80
(D) 120
(E) 160

Solution: We have 6 married couples i.e. we have 12 people. Out of these 12 people, we have to choose 3. If there were no constraints on the choice and we could choose any 3 out of these 12, in how many ways could we do that?

12 people and 3 available positions – We use basic counting principle to arrive at 12*11*10. But, recall that we have arranged the 3 people here. To un-arrange, we divide this by 3! to get 12*11*10/3! arrangements. This is what we discussed last week.

Moving forward, this question has a constraint – no two people married to each other should be selected i.e. at most one of any two married people could be selected. Say, if we select Mr. X, we cannot select Ms. X and vice versa.

Let’s try to use our basic counting principle and un-arranging method here:

You have 12 people and 3 positions. In the first position, you can put any one of the 12 people. In the second position, you can put any one of 10 people (not 11 because the spouse of the person put in 1st position cannot be put in the second position). In the third position you can put any one of 8 people. (We have already selected 2 people for the previous two places and their spouses cannot be selected for the third position so 4 of the 12 people are out.)

Total number of arrangements = 12*10*8

But mind you, these are arrangements. We just need a group of 3 people. They don’t need to be arranged in the group. So we divide these arrangements by 3! to just ‘select’ the people.

Number of committees possible = 12*10*8/3! = 160

I think this was easy, right? Let’s look at a little more complex problem now.

Question 2: A group of 10 people consists of 2 married couples and 6 bachelors. A committee of 4 is to be selected from the 10 people. How many different committees can be formed if the committee can consist of at most one married couple?

Solution: We have to select 4 people out of: 6 bachelors and 2 married couples.

The number of ways of selecting any 4 people out of 10 is 10*9*8*7/4! = 210 (Note here that we are just selecting 4 people. We are not arranging them so we divide by 4!)

The people will get selected in various ways:

1. Four bachelors
2. One from a couple and three bachelors
3. Two from two different couples and two bachelors
4. One couple and two bachelors
5. One couple, one person from a couple, one bachelor
6. Two couples

If we add the number of committees possible in each of these cases, we will get 210. Out of all these cases, only the last one (two couples) has more than one married couple. Instead of calculating the number of different committees that can be formed in each of the first five cases, we can calculate the number of committees in the last case and subtract it from 210.

How many different committees can be formed such that there are 2 couples? Only one since we have only 2 couples. We will have to select both the couples and we will get 4 people.

Number of different committees of 4 people such that there is at most one married couple = 210 – 1 = 209.

Just for practice, let’s see how we can calculate the different number of committees that can be formed in each of the first five cases. The sum of all these cases should give us 209.

1. Select 4 bachelors from 6 bachelors in 6*5*4*3/4! = 15 different committees
2. Select 1 person out of the two couples (4 people) in 4 ways and 3 bachelors from 6 bachelors in 6*5*4/3! = 20 ways. So you select the 4 people in 4*20 = 80 different committees
3. Select 2 people from 2 different couples in 4*2/2! = 4 ways and 2 bachelors from 6 bachelors in 6*5/2! = 15 ways. So you select the 4 people in 4*15 = 60 different committees
4. Select 1 couple in 2 ways and 2 bachelors from 6 bachelors in 6*5/2! = 15 ways. So you select the 4 people in 2*15 = 30 different committees
5. Select 1 couple in 2 ways, 1 person from the remaining couple in 2 ways and 1 bachelor from 6 bachelors in 6 ways. So you can select the 4 people in 2*2*6 = 24 different committees

The sum of all these five cases = 15 + 80 + 60 + 30 + 24 = 209 different committees (as expected)

Let me add here that combinatorics is a huge topic. We can put up a 100 posts on it and still not exhaust all the content. If there is a particular concept that you would like me to discuss, let me know. Else, I will follow my own train of thought and discuss the most frequently occurring topics

In the last two posts, we discussed how to easily handle constraints in linear arrangements. Today we will discuss how to handle constraints in circular arrangements, which are actually even simpler to sort out. Let’s look at some examples.

Question 1: Seven people are to be seated at a round table. Andy and Bob don’t want to sit next to each other. How many seating arrangements are possible?

Solution: There are 7 people who need to be seated around a circular table. Number of arrangements in which 7 people can be seated around a circular table = (7-1)! = 6!

(If you are not sure how we got this, check out this post.)

We need to find the number of arrangements in which two of them do not sit together. Let us instead find the number of arrangements in which they will sit together. We will then subtract these arrangements from the total 6! arrangements. Consider Andy and Bob to be one unit. Now we need to arrange 6 units around a round table. We can do this in 5! ways. But Andy and Bob can swap places so we need to multiply 5! by 2.

Number of arrangements in which Andy and Bob do sit next to each other = 2*5!

So, number of arrangements in which Andy and Bob don’t sit next to each other = 6! – 2*5!

This is very similar to the way we handled such constraints in linear arrangements.

Question 2: There are 6 people, A, B, C, D, E and F. They have to sit around a circular table such that A cannot sit next to D and F at the same time. How many such arrangements are possible?

Solution: Total number of ways of arranging 6 people in a circle = 5! = 120

Now, A cannot sit next to D and F simultaneously.

Let’s first find the number of arrangements in which A sits between D and F. In how many of these 120 ways will A be between D and F? Let’s consider that D, A and F form a single unit. We make DAF sit on any three consecutive seats in 1 way and make other 3 people sit in 3! ways (since the rest of the 3 seats are distinct). But D and F can swap places so the number of arrangements will actually be 2*3! = 12

In all, we can make A sit next to D and F simultaneously in 12 ways.

The number of arrangements in which A is not next to D and F simultaneously is 120 – 12 = 108.

A slight variation of this question that would change the answer markedly is the following:

Question 3: There are 6 people, A, B, C, D, E and F. They have to sit around a circular table such that A can sit neither next to D nor next to F. How many such arrangements are possible?

Solution: In the previous question, A could sit next to D and F; the only problem was that A could not sit next to both of them at the same time. Here, A can sit next to neither D nor F. Generally, it is difficult to wrap your head around what someone cannot do. It is easier to consider what someone can do and go from there. A cannot sit next to D and F so he will sit next to two of B, C and E.

Let’s choose two out of B, C and E. In other words, let’s drop one of B, C and E. We can drop one of B, C and E in 3 ways (we can drop B or C or E). This means, we can choose two out of B, C and E in 3 ways (We will come back to choosing 2 people out of 3 when we work on combinations). Now, we can arrange the two selected people around A in 2 ways (say we choose B and C. We could have BAC or CAB). We make these three sit on any three consecutive seats in 1 way.

Number of ways of choosing two of B, C and E and arranging the chosen two with A = 3*2 = 6

The rest of the three people can sit in three distinct seats in 3! = 6 ways

Total number of ways in which A will sit next to only B, C or E (which means A will sit neither next to D nor next to F) = 6*6 = 36 ways

Now we will look at one last example.

Question 4: Six people are to be seated at a round table with seats arranged at equal distances. Andy and Bob don’t want to sit directly opposite to each other. How many seating arrangements are possible?

Solution: Directly opposite means that Andy and Bob cannot sit at the endpoints of the diameter of the circular table.

Total number of arrangements around the circular table will be (6-1)! = 5!

But some of these are not acceptable since Andy sits opposite Bob in these. Let us see in how many cases Andy doesn’t sit opposite Bob. Let’s say we make Andy sit first. He can sit at the table in 1 way since all the seats are exactly identical for him. Now there are 5 seats left but Bob can take a seat in only 4 ways since he cannot occupy the seat directly opposite Andy. Now there are 4 people left and 4 distinct seats left so they can be occupied in 4! ways.

Total number of ways of arranging the 6 people such that Andy does not sit directly opposite Bob = 1*4*4! = 96 arrangements.

Make sure you understand the logic used in this question. We will build up on it in the next post.

With today’s post, let’s wrap up arrangements for the time being. We will discuss some complex circular arrangement constraints (which we will easily work through) today and start with combinations (i.e. picking “r” units out of “n” units) next week. Thereafter we will look at questions involving both, picking and arranging (yeah, that will be fun!).

Question 1: A group of 8 friends sit together in a circle. If A refuses to sit beside B unless C sits on the other side of A as well, how many possible seating arrangements are possible?

Solution: Let’s start with what we know. We know that the total number of ways in which 8 people can be arranged around a circular table is \((8-1)! = 7!\)

Since we do not want A to sit next to B, let’s try and make them sit together. This will give us the number of arrangements that are unacceptable to us. Let’s say that A and B are a single unit. So now there are 7 units which need to be arranged in a circle. This can be done in \((7-1)! = 6!\) ways. Since there are two arrangements possible, AB and BA, within the unit, we need to multiply 6! by 2.

Number of arrangements in which A and B sit together \(= 2*6!\)

We can subtract these ‘unacceptable arrangements’ from total arrangements to get the number of ‘acceptable arrangements’. But this number of ‘unacceptable arrangements’ includes those arrangements where C is sitting on the other side of A. But those arrangements are acceptable to us so we should not subtract them out. How many such arrangements are there in which A and B are sitting together and C is sitting beside A too?

Now C, A and B form a single unit leaving us with 6 units to be arranged in a circle. 6 units can be arranged in \((6-1)! = 5!\) ways

CAB can also be arranged as BAC, hence the 5! needs to be multiplied by 2. (Mind you, we will not consider ABC, ACB etc here since A should be in the middle)

Number of arrangements in which A and B sit together and C sits beside A = \(2*5!\)

Therefore, number of unacceptable arrangements \(= 2*6! – 2*5!\)

We subtract these out of the total number of arrangements and we get the total number of acceptable arrangements.

Possible number of seating arrangements = \(7! – (2*6! – 2*5!) = 3840\)

If you are wondering about the ‘painful’ calculation involved in the step above, don’t worry. Calculations with factorials are generally quite straight forward.

\(7! – (2*6! – 2*5!) = 7! – 2*6! + 2*5!\)

\(= 2*5! (21 – 6 + 1)\) (Take 2*5! common out of the three terms)

\(= 2*120*16 = 32*120 = 3840\)

I hope the solution makes sense to you. Let’s look at another tricky circular arrangement problem.

Question 2: Seven men and seven women have to sit around a circular table so that no two women are together. In how many different ways can this be done?

Solution:
There are 7 men: Mr. A, Mr. B, Mr. C, Mr. D …
and 7 women: Ms. A, Ms. B, Ms. C, Ms. D …

Let’s say we have 14 identical chairs around the round table.

We need to seat the 7 women such that no two of them are together i.e. there should be a man on either side of every woman. Since there are exactly 7 men, the women and men should sit alternately. Let’s make the women sit first. For the first woman who sits, each seat is identical so she sits in one way (say Ms.C takes a seat). Now each seat is distinct relative to this woman (Ms. C). There are 7 seats identified for men (e.g. seats right next to Ms. C and every alternate seat) and 6 for the remaining 6 women. The 7 men can occupy the 7 distinct seats in 7! ways and the 6 women can occupy the 6 distinct seats in 6! ways.

Total number of arrangements = \(6!*7!\)

Something to ponder upon: The total number of arrangements is not 13!. Why?

Question 3: Find the number of ways in which four men, two women and a child can sit at a circular table if the child is seated between the two women.

Solution:

We have 7 people and 7 seats around a circular table.

First let’s make the child sit anywhere in one way since all the places are identical. The two women can sit around the child in 2! ways. Now we have 4 distinct seats (relative to the people sitting) left for the 4 men and they can occupy the seats in 4! ways.

Total number of arrangements \(= 1*2!*4! = 48\)

Things to ponder upon:

Case 1: Same question as above but the chairs are numbered i.e. all the seats are distinct. Find the number of ways in which four men, two women and a child can sit around a circular table with numbered seats if the child is seated between the two women.

Case 2: Same question as above but they need to stand in a row instead. Find the number of ways in which four men, two women and a child can stand in a row if the child is standing between the two women.

Are the two cases above equivalent?

We 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 = \frac{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 = \frac{n!}{(r! * (n-r)!)}\)

Number of ways of selecting 3 people out of a total of 5 people \(= 5C3 = \frac{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 \(\frac{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 \(\frac{5*4*3}{3!}* 3 = 30\) ways

Answer (B) This question is discussed HERE.

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 \(\frac{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) This question is discussed HERE.

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

Now that we have discussed both permutations and combinations independently, it’s time to look at questions that involve both. Mind you, these questions are not difficult -– they just involve both concepts. The first one is a circular arrangement question with a tiny twist. The second one requires us to make some cases. It takes a fair bit of patience to work out one case at a time and I doubt that GMAT will give you such a question since it is a little bit of a bore. (Actual GMAT questions have more entertainment value for the test maker and the test taker. They make you think and are FUN to solve) That said, it is a great question to bind together everything that we have learned till now and strengthen your understanding. Let’s start.

Question 1: Seven women and four men have to sit around a circular table so that no two men are together. In how many different ways can this be done?

Solution: Try and think about it for a while. We did a very similar question while working on circular arrangements. In that question, number of women and number of men were equal so we just had to place them in alternate positions. Here, we have fewer men. What do we do now?

Two men cannot sit together but some women will sit together since there aren’t enough men. So, let’s make the 7 women sit around the round table in (7-1)! = 6! ways (We covered the (n-1)! concept in the post on circular arrangements)

Now, how many places do we have for the men? A man can sit between any two women sitting next to each other. How many such pairs of women are there? Since there are 7 women, we have 7 such pairs and hence 7 possible spaces for men. There are two different approaches you can take from here:

Approach 1:

We have 4 men but 7 possible spaces for them. For the first man, we can select a space in 7 ways. For the second man, we can select a space in 6 ways. For the third one, in 5 ways and for the fourth one in 4 ways. So we can arrange the men in 7*6*5*4 ways. This is just our basic counting principle in action.

Approach 2:

Some people like to split up the task into two steps – make the selection, then arrange. Out of 7 spaces, we need to select any 4 for the 4 men. How do you select 4 out of 7? Using basic counting principle and un-arranging concept, we can do it in 7*6*5*4/4! ways (or we can use the formula 7C4). We have selected 4 spaces so now we just want to arrange the 4 men in the 4 spaces. We can do this in 4! ways.

It doesn’t matter which approach you use. The first one uses just the basic counting principle. The second one is used more often by people who are very comfortable with the combinations formula.

The total number of arrangements we get = 6! * 7*6*5*4 or we can write this as 6!*7!/3! to make it a little compact.

Let’s look at the second question now.

Question 2: How many words of 4 letters can be formed from the word “INFINITY”? (They may or may not be actual words in the English language.)

The word INFINITY has 5 distinct letters – I, N, F, T, Y

Repetitions – I, I, I, N, N

The question doesn’t say that all letters of the words have to be distinct. So, you can make a word using all three Is and another letter or two Ns and two Is etc. So you cannot just select any four letters and arrange them. The number of arrangements will vary depending on whether the letters are all distinct or have some repetitions. Let’s look at all possible cases:

Case 1: All letters are distinct (Form: abcd)

From the 5 distinct letters, we can select any 4 (or drop any 1 letter) in 5 ways (you can also use 5C4 or 5*4*3*2/4! to arrive at the figure of 5)

We can arrange these 4 selected letters in 4! ways.

Number of ways in which you can make a 4 letter word with all distinct letters = 5*4! = 120 ways

Case 2: Two letters same, others different (Form: aabc)

Only I and N are repeated so we have to select one of them and we have to select 2 of the other 4 (F, T, Y and whatever is not selected out of N and I) letters.

Select one of N and I in 2 ways. Then to choose 2 other letters, pick two from the other 4 letters in 4*3/2 ways (or 4C2) = 6 ways.

Now we have 3 letters and one of them is repeated so in all we have 4 letters. We can arrange 4 letters (with a repetition) in 4!/2! ways (we divide by 2! because one letter is repeated).

Number of ways in which you can make a 4 letter word with one repetition = 2 * 6 * 4!/2! = 144 ways

Case 3: 2 letters, both repeated (Form: aabb)

We have only two letters that are repeated, N and I. We will need to select both of them so the selection can be done in only 1 way.

Since both the letters are repeated, the 4 letter word can be formed in 4!/(2!*2!) = 6 ways

Case 4: 3 letters same, fourth different (Form: aaab)

Only I appears 3 times so it must be selected. We have to select one letter from the other four. We can choose the fourth letter in 4 ways.

Since I is repeated 3 times, the four letters can be arranged in 4!/3! = 4 ways.

Number of ways in which you can make a 4 letter word 4 * 4 = 16 ways

All four letters cannot be the same since no letter appears four times.

Total number of 4 letter words that can be formed using the letters of the word ‘INFINITY’ are 120 + 144 + 6 + 16 = 286 words

The solution is long but very methodical. If you go one step at a time, it is not complicated at all. I will see you in the next post with some tricky questions. Till then, keep practicing.

Today’s post is a continuation of last week’s post and heavily refers back to it. I would suggest you to take a quick look at last week’s post again to make sense of this post. Let’s start with the variation question 1a we saw in the last post.

Question 1a: In how many ways can 5 different rings be worn in four particular fingers? (Some fingers may get more than one ring and some may get no rings.)

Solution: The first ring can be worn in 4 ways i.e. in any one of the four fingers. The second ring can be worn in 5 ways (it can go on any one of the four fingers and it can also go below the first ring so there are 5 distinct places for the second ring). The third ring can be worn in 6 ways (any one of the four fingers or below the second ring or below the first ring). The fourth ring can be worn in 7 ways (any one of the four fingers or below the third ring or below the second ring or below the first ring). The fifth ring can be worn in 8 ways (any one of the four fingers or below the fourth ring or below the third ring or below the second ring or below the first ring).

Total number of ways in which 5 different rings can be worn in 4 particular fingers = 4*5*6*7*8.

Compare this with question 1 of last post: In how many ways can 5 different fruits be distributed among four children?

The answer in this case was \(4^5 = 4*4*4*4*4\).

Why are these two questions different? After all, we are distributing 5 different things among 4 children/fingers in both the cases. The difference lies in the fact that when a child gets 2 fruits, the fruits are not arranged but when a finger gets two rings, it gives us 2 different arrangements since the rings can be arranged in 2 ways. You can wear 2 rings on your fingers in 2 different ways (A on top, B at the bottom or B on top and A at the bottom). When you get 2 fruits, there is no arrangement involved. Whether you got fruit A first or fruit B first doesn’t matter. At the end of it, you have 2 fruits A and B and that’s all that matters. In fact this is the reason we cannot solve question 1 using method 2 of question 2 (discussed in the last post). Let’s still try to use it and see why it doesn’t work.

Say, we have 5 different things in a row: A B C D E and 3 identical vertical lines to split these 5 objects into 4 groups. We can arrange these 8 objects, 3 of which are identical, in 8!/3! ways. Notice that 8!/3! = 8*7*6*5*4 i.e. the numbers of ways in which 5 different rings can be worn in 4 fingers. It is not the same as the number of ways in which 5 different fruits can be distributed among 4 children.

We see that:

AB l C l DE
and
BA l C l DE

are two different arrangements. Since how you wear the rings gives you different arrangements, the vertical lines split method can be used to get the answer in the rings question (question 1a). Since these two should not be two different arrangements in case we are talking about distributing fruits among children, this method is not suitable for question 1.I hope I haven’t already confused you. We still have a long way to go!

We should now pay attention to question numbers 3 and 4 from the previous post.

Question 3: In how many ways can 5 different fruits be distributed among 4 identical baskets?

Solution: Let’s use the same format as that used in the previous post. 5 fruits can be split into 4 groups in the following ways: {5, 0, 0, 0}, {4, 1, 0, 0}, {3, 2, 0, 0}, {3, 1, 1, 0}, {2, 2, 1, 0}, {2, 1, 1, 1}

Does it concern us that the baskets are identical? It does. Let’s see how.

{5, 0, 0, 0} means that one basket has all 5 fruits and the rest of the 3 baskets are empty. It doesn’t matter which basket has the fruits because all the baskets are identical. So, this gives us 1 way of distributing the fruits.

{4, 1, 0, 0} means that one basket has 4 fruits, another has the leftover 1 fruit and the other 2 baskets have no fruit. The lone fruit can be chosen in 5 ways. The rest of the 4 fruits will be together in another basket and 2 baskets will be empty. This gives us 5 different ways of distributing the fruits.

{3, 2, 0, 0} means that one basket has 3 fruits, another has the leftover 2 fruits and the other 2 baskets have no fruit. The 3 fruits can be chosen in 5*4*3/3! = 10 ways (= 5C3). The rest of the 2 fruits will be together in another basket in one way and 2 baskets will be empty. This gives us 10 different ways of distributing the fruits.

{3, 1, 1, 0} means that one basket has 3 fruits, another two have a fruit each and the leftover basket has no fruit. The 3 fruits can be chosen in 5*4*3/3! = 10 ways (= 5C3). The rest of the 2 fruits will be in two baskets in one way (since the baskets are all identical) and the last basket will be empty. This gives us 10 different ways of distributing the fruits.

{2, 2, 1, 0} means that 2 baskets have 2 fruits each, one basket has one fruit and the last basket is empty. We can select 1 fruit out of 5 in 5 ways. Now we are left with 4 fruits which have to be split into 2 groups of 2 each. This can be done in 4!/2!*2!*2! = 3 ways (We have already discussed this concept in the post on Groups. Check out the initial theory and question no. 2) This gives us 5*3 = 15 different ways of distributing the fruits.

{2, 1, 1, 1} means that one basket has 2 fruits and the rest of the 3 baskets have a fruit each. We can select 2 fruits out of 5 in 5*4/2! = 10 ways (= 5C2). This gives us 10 different ways of distributing the fruits.

Total number of different ways of distributing the fruits = 1 + 5 + 10 + 10 + 15 + 10 = 51 ways

Something for you to think about: We used the brute force method here. Can we use some more analytical and direct method to solve this question?

Meanwhile, let’s look at question number 4 now.

Question 4: In how many ways can 5 apples (identical) be distributed among 4 identical baskets?

Solution: As we have seen previously, 5 fruits can be split into 4 groups in the following ways: {5, 0, 0, 0}, {4, 1, 0, 0}, {3, 2, 0, 0}, {3, 1, 1, 0}, {2, 2, 1, 0}, {2, 1, 1, 1}

Here, {5, 0, 0, 0} means that one basket has all 5 apples and the rest of the baskets are empty. Since the baskets are all identical, there is only 1 way of doing this.
{4, 1, 0, 0} means that one basket has 4 apples, another one has 1 apple and the rest of the baskets are empty. Since the fruits and the baskets are all identical, there is again only 1 way of doing this.

You have to select neither the fruits nor the baskets since they are all identical. You only have to decide how to distribute the apples in 4 groups. Therefore, each one of these cases will give us only one different way of distributing the fruits. Since there are 6 such cases, there are only 6 different ways of distributing the fruits.

I wouldn’t be surprised if you are a little confused at this point since the different variations change the thought process completely. That is the whole fun of combinatorics. You change one word and we have to start thinking from the scratch. You miss one word and you either don’t realize at all that your answer is wrong (if the options are cunning) or you realize after you have solved the entire question. Thankfully, GMAT has only one to two questions based on this topic.

Of all the topics on the GMAT quant section, few get students as confused as the concept of combinatorics. The concept of going to the store and picking up one of four possible gifts for a niece is pretty straightforward (she generally likes Barbies© or My Little Pony© toys), but picking up two toys out of four for your twin nieces and then deciding which one gets which often deteriorates into an exercise of brute force combinatorics.

Most people suspect that there’s a simple way to calculate the possible combinations, but they don’t bother to learn it because you can always figure it out with a pen and paper (or an abacus) and copious amounts of spare time.

But what happens when the exam asks you a combinatorics question that will take too long to solve via brute force? Well, figuring out what the question is asking is the first step towards success. The two first issues you should always address are: Does order matter, and is repetition allowed? If the order of the elements matters, you’re looking for permutations, not combinations. The difference is that you can get Barbie for Erin and a pony for Anne or Barbie for Anne and Barbie for Erin in this scenario, whereas if you’re buying two gifts for the same child then order is moot. Repetition is not allowed in this scenario because you won’t get her the same gift twice (or if you do you’re likely headed to the nursing home).

The general rule for permutations is that, if you’re looking for k toys out of n possible options, your options are defined by n!/(n-k)! (“!” Denotes factorial, which is taking the product of that integer and all integers smaller than it). In the example above, you have n=4 and k=2, so (4*3*2*1) / 2*1 options. It becomes quickly obvious that writing down the *1 at the end of every permutation adds nothing, so really this is (4*3*2)/2, which we can simplify to 4*3 or 12. If the order mattered you would have had fewer options, so determining the importance of order is paramount to getting the right answer.

Now that we’ve jogged our memories about combinatorics, let’s review a problem where understanding is as important (no, more important… ok, as important) as knowing the formula.

Question: How many 5 digit numbers can be formed which are divisible by 3 using the numerals 0, 1, 2, 3, 4, 5 without repetition.

A) 120
B) 216
C) 240
D) 720
E) 3152

Blindly applying the formula we just discussed would yield n=6 and k = 5, so 6!/(6-5)! which is just 6! and therefore 720. Answer choice D is waiting for us if we go down this route, and it seems like a safe guess if you have no idea how to proceed, so a fair number of students may be tempted by this option. However, the formula gives you all possible permutations of these numbers, including, for example, 01234, which does not meet the second criterion of the question: That the numbers be divisible by 3. This restriction will eliminate many of the possibilities, so 720 possibilities (and 3152 even more so) is overshooting the target.

So what do we do? Go through all 720 possibilities and whittle the list down for every possibility that isn’t divisible by 3? That’s a good way to spend an unproductive afternoon! Why don’t we try and limit the number of possibilities by seeing which combinations of digits give us something divisible by 3 and then going through the permutations for those digits only? The rule for divisibility by 3 is that the sum of the digits must be divisible by 3. The fact that each digit must be unique means we only have six possibilities of digits, each possibility ignoring one of the six digits provided.

Digits 0,1,2,3,4 only: sum 10. Does not work.
Digits 0,1,2,3,5 only: sum 11. Does not work.
Digits 0,1,2,4,5 only: sum 12. Works!
Digits 0,1,3,4,5 only: sum 13. Does not work.
Digits 0,2,3,4,5 only: sum 14. Does not work.
Digits 1,2,3,4,5 only: sum 15. Works!

So we only really need to calculate the permutations of {1,2,3,4,5} and {0,1,2,4,5}. The first one is easier, as we can just take 5!/0! (0! Is 1 by definition) which gives us 120 possibilities. The second one contains a famous GMAT trick, which is that it cannot begin by 0 and still be a 5-digit number. Just like 7 is a one-digit number and not a five-digit number by adding an arbitrary number of 0’s at the beginning of it (James Bond’s understudy 00007). This logic dictates that the second set has only four possible numbers in the first position, and then 4 again for the second (any of the four that wasn’t put in the first spot) and then three, two, one as normal. Instead of the standard 5! we get 4 * 4! which is 96. As such, the correct answer is 120 + 96 = 216.

Answer choice B. This question is discussed HERE.

As we can see from the answer choices provided, the GMAT test makers know the mistakes you’re likely to make and prepare answer choices to trap you in case you make a simple mistake or absent-minded omission. Answer choices A (5!), C (2*5!) and D (6!) are all traps designed to make you feel like you got the right answer even though you made a mistake. Be particularly wary of answer choice C, most people who pick this answer feel confident that they got the question right. If you recognize that understanding the parameters of the question is the first step to getting the correct answer, you’ll be ready for any permutation of questions the GMAT throws at you

While discussing Permutations and Combinations many months back, we worked through several examples of arranging people in seats. Today we bring you an interesting question based on those concepts. It brings to the fore the tricky nature of both Data Sufficiency and Combinatorics – so much so that when the two get together, it is unlimited fun!

In some circumstances, we suggest you to travel the whole nine yards – i.e. solve for the answer in Data Sufficiency questions too even if you feel that sufficiency has already been established. This is especially true for quadratic equations which we assume will give us two values of x but might actually give just a single unique value (such that both roots are the same). In Combinatorics too, sometimes what may look like two distinct cases could actually give the same answer. Let’s jump on to the question.

Question 1: There are x children and y chairs in a room where x and y are prime numbers. In how many ways can the x children be seated in the y chairs (assuming that each chair can seat exactly one child)?

Statement 1: x + y = 12
Statement 2: There are more chairs than children.

Solution:

There are x children and y chairs.

x and y are prime numbers.

Statement 1: x + y = 12

Since x and y are prime numbers, a quick run on 2, 3, 5 shows that there are two possible cases:

Case 1: x=5 and y=7

There are 5 children and 7 chairs.

Case 2: x=7 and y=5

There are 7 children and 5 chairs

At first glance, they might look like two different cases and you might feel that statement 1 is not sufficient alone. But note that the question doesn’t ask you for number of children or number of chairs. It asks you about the number of arrangements.

Case 1: x=5 and y=7

If there are 5 children and 7 chairs, we select 5 chairs out of the 7 in 7C5 ways. We can now arrange 5 children in 5 seats in 5! ways.

Total number of arrangements would be 7C5 * 5!

Case 2: x = 7 and y = 5

If there are 7 children and 5 chairs, we select 5 children out of the 7 in 7C5 ways. We can now arrange 5 children in 5 seats in 5! ways.

Total number of arrangements would be 7C5 * 5!

Note that in both cases the number of arrangements is 7C5*5!. Combinatorics does not distinguish between people and things. 7 children on 5 seats is the same as 5 children on 7 seats because in each case you have to select 5 out of 7 (either seats or children) and then arrange 5 children in 5! ways.

So actually this statement alone is sufficient! Most people would not have seen that coming!

Statement 2: There are more chairs than people.

We don’t know how many children or chairs there are. This statement alone is not sufficient.

Answer: A This question is discussed HERE.

We were tempted to answer the question as (C) but it was way too easy. Statement 1 gave 2 cases and statement 2 narrowed it down to 1. Be aware that if it looks too easy, you are probably missing something!

Now, what if we alter the question slightly and make it:

Question 2: There are x children and y chairs arranged in a circle in a room where x and y are prime numbers. In how many ways can the x children be seated in the y chairs (assuming that each chair can seat exactly one child)?

Statement 1: x + y = 12
Statement 2: There are more chairs than children

21. Combinatorics/Counting Methods

• Theory
  Math: Combinatorics
  Combinatorics Made Easy!
  1 hour Combinatorics Video Lesson
  Combinations while dealing with similar and dissimilar things
  When Permutations & Combinations and Data Sufficiency Come Together
  
  • Questions
    Advanced Topic: Probability and Combinations Questions With Solutions
    Letter Arrangements in Words
    Seating Arrangements in a Row and around a Table
    Constructing Numbers, Codes and Passwords
    DS Questions
    PS Questions
  
  

  22. Probability

  
  
  • Theory
    Math: Probability
    Probability Made Easy!
    GMAT Tip of the Week: 99 Problems But Probability Ain't One
    
    • Questions
      Probability and Geometry Problems
      Advanced Topic: Probability and Combinations Questions With Solutions
      DS Questions
      PS Questions

For more:
ALL YOU NEED FOR QUANT ! ! !
Ultimate GMAT Quantitative Megathread


Hope it helps.

A recurring question from many students who are preparing for GMAT is this: When should one use the permutation formula and when should one use the combination formula?

People have tried to answer this question in various ways, but some students still remain unsure. So we will give you a rule of thumb to follow in all permutation/combination questions:

You never NEED to use the permutation formula! You can always use the combination formula quite conveniently. First let’s look at what these formulas do:

Permutation: \(nPr = \frac{n!}{(n-r)!}\)
Out of n items, select r and arrange them in r! ways.

Combination: \(nCr = \frac{n!}{[(n-r)!*r!]}\)
Out of n items, select r.

So the only difference between the two formulas is that nCr has an additional r! in the denominator (that is the number of ways in which you can arrange r elements in a row). So you can very well use the combinations formula in place of the permutation formula like this:

\(nPr = nCr * r!\)

The nCr formula is far more versatile than nPr, so if the two formulas confuse you, just forget about nPr.

Whenever you need to “select,” “pick,” or “choose” r things/people/letters… out of n, it’s straightaway nCr. What you do next depends on what the question asks of you. Do you need to arrange the r people in a row? Multiply by r!. Do you need to arrange them in a circle? Multiply by (r-1)!. Do you need to distribute them among m groups? Do that! You don’t need to think about whether it is a permutation problem or a combination problem at all. Let’s look at this concept more in depth with the use of a few examples.

There are 8 teachers in a school of which 3 need to give a presentation each. In how many ways can the presenters be chosen?

In this question, you simply have to choose 3 of the 8 teachers, and you know that you can do that in 8C3 ways. That is all that is required.

\(8C3 = \frac{8*7*6}{3*2*1} = 56\) ways

Not too bad, right? Let’s look at another question:

There are 8 teachers in a school of which 3 need to give a presentation each. In how many ways can all three presentations be done?

This question is a little different. You need to find the ways in which the presentations can be done. Here the presentations will be different if the same three teachers give presentations in different order. Say Teacher 1 presents, then Teacher 2 and finally Teacher 3 — this will be different from Teacher 2 presenting first, then Teacher 3 and finally Teacher 1. So, not only do we need to select the three teachers, but we also need to arrange them in an order. Select 3 teachers out of 8 in 8C3 ways and then arrange them in 3! ways:

We get \(8C3 * 3! = 56 * 6 = 336\) ways

Let’s try another one:

Alex took a trip with his three best friends and there he clicked 7 photographs. He wants to put 3 of the 7 photographs on Facebook. How many groups of photographs are possible?

For this problem, out of 7 photographs, we just have to select 3 to make a group. This can be done in 7C3 ways:

\(7C3 = \frac{7*6*5}{3*2*1} = 35\) ways

Here’s another variation:

Alex took a trip with his three best friends and there he clicked 7 photographs. He wants to put 3 of the 7 photographs on Facebook, 1 each on the walls of his three best friends. In how many ways can he do that?

Here, out of 7 photographs, we have to first select 3 photographs. This can be done in 7C3 ways. Thereafter, we need to put the photographs on the walls of his three chosen friends. In how many ways can he do that? Now there are three distinct spots in which he will put up the photographs, so basically, he needs to arrange the 3 photographs in 3 distinct spots, which that can be done in 3! ways:

Total number of ways \(= 7C3 * 3! = (\frac{7*6*5}{3*2*1}) * 6= 35 * 6 = 210\) ways

Finally, our last problem:

12 athletes will run in a race. In how many ways can the gold, silver and bronze medals be awarded at the end of the race?

We will start with selecting 3 of the 12 athletes who will win some position in the race. This can be done in 12C3 ways. But just selecting 3 athletes is not enough — they will be awarded 3 distinct medals of gold, silver, and bronze. Athlete 1 getting gold, Athlete 2 getting silver, and Athlete 3 getting bronze is not the same as Athlete 1 getting silver, Athlete 2 getting gold and Athlete 3 getting bronze. So, the three athletes need to be arranged in 3 distinct spots (first, second and third) in 3! ways:

Total number of ways = \(12C3 * 3!\) ways

Note that some of the questions above were permutation questions and some were combination questions, but remember, we don’t need to worry about which is which. All we need to think about is how to solve the question, which is usually by starting with nCr and then doing any other required steps. Break the question down — select people and then arrange if required. This will help you get rid of the “permutation or combination” puzzle once and for all.

We have seen in previous posts how to deal with permutation and combination questions on the GMAT. There is a certain variety of questions that involve getting a bunch of numbers using permutation, and then doing some operations on the numbers we get. The questions can get a little overwhelming considering the sheer magnitude of the number of numbers involved! Let’s take a look at that concept today. We will explain it using an example and then take a question as an exercise:

What is the sum of all four digit integers formed using the digits 1, 2, 3 and 4 such that each digit is used exactly once in each integer?

First of all, we will use our basic counting principle to find the number of integers that are possible.

The first digit can be chosen in 4 ways. The next one in 3 ways since each digit can be used only once. The next one in 2 ways and there will be only one digit left for the last place.

This gives us a total of 4*3*2*1 = 24 ways of writing such a four digit number. This is what some of the numbers will look like:

1234

1243

1324

1342

…

2143

…

4321

Now we need to add these 24 integers to get their sum. Note that since each digit has an equal probability of occupying every place, out of the 24 integers, six integers will have 1 in the units place, six will have 2 in the units place, another six will have 3 in the units place and the rest of the six will have 4 in the units place. The same is true for all places – tens, hundreds and thousands.

Imagine every number written in expanded form such as:

\(1234 = 1000 + 200 + 30 + 4\)

\(2134 = 2000 + 100 + 30 + 4\)

…etc.

For the 24 numbers, we will get six 1000’s, six 2000’s, six 3000’s and six 4000’s.

In addition, we will get six 100’s, six 200’s, six 300’s and six 400’s.

For the tens place, will get six 10’s, six 20’s, six 30’s and six 40’s.

And finally, in the ones place we will get six 1’s, six 2’s, six 3’s and six 4’s.

Therefore, the total sum will be:

\(6*1000 + 6*2000 + 6*3000 + 6*4000 + 6*100 + 6*200 + … + 6*3 + 6*4\)

\(= 6*1000*(1 + 2 + 3 + 4) + 6*100*(1 + 2 + 3 + 4) + 6*10*(1 + 2 + 3 + 4) + 6*1*(1 + 2 + 3 + 4)\)

\(= 6*1000*10 + 6*100*10 + 6*10*10 + 6*10\)

\(= 6*10*(1000 + 100 + 10 + 1)\)

\(= 1111*6*10\)

\(= 66660\)

Note that finally, there aren’t too many actual calculations, but there is some manipulation involved. Let’s look at a GMAT question using this concept now:

What is the sum of all four digit integers formed using the digits 1, 2, 3 and 4 (repetition is allowed)
A) 444440
B) 610000
C) 666640
D) 711040
E) 880000

Conceptually, this problem isn’t much different from the previous one.

Using the same basic counting principle to get the number of integers possible, the first digit can be chosen in 4 ways, the next one in 4 ways, the next one in again 4 ways and finally the last digit in 4 ways. This is what some of the numbers will look like:

1111

1112

1121

…

and so on till 4444.

As such, we will get a total of \(4*4*4*4 = 256\) different integers.

Now we need to add these 256 integers to get their sum. Since each digit has an equal probability of occupying every place, out of the 256 integers, 64 integers will have 1 in the units place, 64 will have 2 in the units place, another 64 integers will have 3 in the units place and the rest of the 64 integers will have 4 in the units place. The same is true for all places – tens, hundreds and thousands.

Therefore, the total sum will be:

\(64*1000 + 64*2000 + 64*3000 + 64*4000 + 64*100 + 64*200 + … + 64*3 + 64*4\)

\(= 1000*(64*1 + 64*2 + 64*3 + 64*4) + 100*(64*1 + 64*2 + 64*3 + 64*4) +\)
\(+10*(64*1 + 64*2 + 64*3 + 64*4) + 1*(64*1 + 64*2 + 64*3 + 64*4)\)

\(= (64*1 + 64*2 + 64*3 + 64*4) * (1000 + 100 + 10 + 1)\)

\(= 64*10*1111\)

\(= 711040\)

So our answer is D. This question is discussed HERE.

Sometimes, you come across some seriously interesting questions in Combinatorics. For example, this question I came across seemed like any other Combinatorics question, though it was a little cumbersome. But when I saw the answer, it got me thinking – it couldn’t have been a coincidence. There had to be a simpler logic to it and there was! I just wish I had thought of it before going the long route. So I must share it with you; you never know what might come in handy on test day!

But before I tell you what that question was, let’s solve a couple of questions which are similar to some questions you might have seen before  (for the sake of brevity,  let’s ignore the options):

Question 1: In how many ways can 10 different paintings be distributed between two collectors – Dave and Mona – if Dave should get either three paintings or five paintings? (All paintings should be given away).

Solution 1:

There are two ways of distributing the paintings in this case:

Dave gets 3 paintings and Mona gets the rest: You select 3 of the 10 paintings and give them to Dave. This can be done in 10C3 = 120 ways

Dave gets 5 paintings and Mona gets the rest: You select 5 of the 10 paintings and give them to Dave. This can be done in 10C5 = 252 ways

Total number of ways in which you can distribute the paintings = 120 + 252 = 372 ways

Simple enough, right? Let’s take a  look at another simple similar question.

Question 2: In how many ways can 10 different paintings be distributed between two collectors – Dave and Mona – if Dave should get at least two paintings? (All paintings should be given away.)

Solution 2:

Dave should get at least two paintings so it means he can get 2 or 3 or 4 or more up to 10 paintings. Calculating all those cases would be tedious so this is a perfect opportunity to use ‘Total – Opposite’ method.

Total ways in which you can distribute 10 paintings between two people without any constraints: Each painting can be given away in two ways – either to Dave or to Mona. So the paintings can be distributed in 2*2*2*…*2 = 2^10 = 1024 ways

Number of ways in which Dave gets 0 paintings or 1 painting: 1 + 10C1 = 11 ways

So number of ways in which Dave gets 2 or 3 or 4 … upto 10 (i.e. at least 2 paintings) = 1024 – 11 = 1013 ways

Another ‘seen before, know how to solve it’ kind of question. Now let’s come to the question of the day which doesn’t look much different but actually is.

Question 3: In how many ways can 10 different paintings be distributed between two collectors – Dave and Mona – if both collectors should get an even number of paintings? (All paintings should be given away.)

Solution 3:

Paintings can be distributed in the following ways:

0, 10 – One person gets 0 paintings and the other gets 10

2, 8 – One person gets 2 paintings and the other gets 8

4, 6 – One person gets 4 paintings and the other gets 6

You will need to calculate each one of these ways and then add them. Note that the ‘Total – Opposite’ method does not work here because finding the number of ways in which each person gets odd number of paintings is equally daunting.

Case 1: 0, 10

One person gets 0 paintings and the other gets 10. This can be done in 2 ways – either Dave gets all the paintings or Mona gets them.

Case 2: 2, 8

One person gets 2 paintings and the other gets 8. Select 2 paintings out of 10 for Dave in 10C2 = 45 ways. Mona could also get the 2 selected paintings so total number of ways = 45*2 = 90 ways

Case 3: 4, 6

One person gets 4 paintings and the other gets 6. Select 4 paintings out of 10 for Dave in 10C4 = 210 ways. Mona could also get the 4 selected paintings so total number of ways = 210*2 = 420

Total number of ways such that each person gets even number of paintings = 2 + 90 + 420 = 512 ways

But 512 is 2^9 – in form, suspiciously close to 2^10 we used in question 2 above. Is there some logic which leads to the answer 2^(n-1)? There is!

You have 10 different paintings. Each painting can be given to one of the 2 people in 2 ways. You do that with 9 paintings in 2*2*2…  = 2^9 ways. When you distribute 9 paintings, one person will have odd number of paintings and one will have even number of paintings (0 + 9 or 1 + 8 or 2 + 7 or 3 + 6 or 4 + 5).

The tenth painting needs to be given to the person who has the odd number of paintings so you give the tenth painting in only one way. This accounts for all cases in which both get even number of paintings.

Total ways = 2^9 * 1 = 512

On the same lines, now think about this:

Question 4: In how many ways can 10 different paintings be distributed between two collectors – Dave and Mona – if both collectors should get an odd number of paintings? (All paintings should be given away.)

we said V cannot be considered as a person, how can we count in total no. of ways. Please clarify