Combinatorics Made Easy!

The first thing I want to discuss is something we call “Basic Counting Principle” because it is useful in almost all 600-700 level questions of Combinatorics (Note here that I will avoid using the terms “Permutation” and “Combination” and the formulas associated with them since they are not necessary and make people uncomfortable). Also, many of the 700+ level questions use basic counting principle as the starting point so it’s not possible to start a discussion on combinatorics without discussing this principle first. Let’s try to understand it using an example.

Example 1: There are 3 boys and 2 girls. We want to select a pair of one boy and one girl for a dance. In how many ways can we do it?

Solution: Let’s discuss the solution in detail. This is a very basic and very important concept.

Say the 3 boys are B1, B2 and B3. Say the 2 girls are G1 and G2.

In how many ways can you make a pair?

B1 – G1

B1 – G2

B2 – G1

B2 – G2

B3 – G1

B3 – G2

A total of 6 ways. We see that we can select a boy in 3 ways (since there are 3 boys) and we can select a girl in 2 ways (since there are 2 girls). So we can make a pair in 3*2 = 6 ways.

The basic counting principle deals with problems having ‘distinct spots’ and ‘available contenders’. Here we have 1 spot for a boy and 1 spot for a girl i.e. 2 distinct spots. There are 3 contenders for the empty ‘boy spot’ and 2 contenders for the empty ‘girl spot’. These spots can be filled in 3*2 = 6 ways. The word ‘distinct’ is important here as we will see in the next few weeks.

Also notice here that it is not 3+2 = 5 ways. This is so because we have to choose a boy AND a girl simultaneously. For every boy, we could choose a girl in 2 ways and there are 3 boys so we can choose a pair in 3*2 ways. If we had to choose one boy OR one girl (i.e. just one person), we could have done it in 3+2 = 5 ways because there are 5 people and we have to choose one of them. The distinction between ‘AND’ and ‘OR’ is quite important since it defines whether you will multiply or add.

Let’s look at some more examples of basic counting principle.

Example 2: A restaurant serves 6 varieties of appetizers, 10 different entrees and 4 different desserts. In how many ways can one make a meal if one chooses one appetizer, one entree and one dessert?

Solution: In how many ways can you choose an appetizer? 6 ways

In how many ways can you choose your entree? 10 ways

In how many ways can you choose your dessert? 4 ways

In how many different ways can you make your meal? To make your meal, you need one appetizer AND one entree AND one dessert. There are 3 distinct spots and you have to fill each one of them. You can do it in 6*10*4 = 240 ways.

Example 3: In how many ways can you make a five letter password using the first ten letters of the English alphabet? (You can use only capital letters.)

Solution: In how many ways can you choose the first letter of the password? 10 ways. You can put in any letter from A to J.

What about the second letter? Again, you can choose it in 10 ways. The question doesn’t say that you cannot repeat a letter once you use it.

Similarly, each digit can be chosen in 10 ways.

Since you have to choose the first letter AND the second letter AND the third letter etc, the total number of ways of selecting a five letter password is 10*10*10*10*10 = 10^5 ways. You have 5 distinct spots and you can fill each one of them in 10 ways.

You can make the 5 letter password in 10^5 ways.

Example 4: Five friends go to watch a movie. They are supposed to occupy seat numbers 51 to 55. In how many different ways can they do it?

Solution: Let’s look at the first seat i.e. seat number 51. In how many ways can you make someone sit there? Of course 5 ways since you have 5 people. Say, you make one of them sit on seat number 51. Now in how many ways can you make someone sit on seat number 52? Remember that you have only 4 contenders left now since one of them is already sitting on seat number 51. Therefore, you can make someone sit there in 4 ways only. Next, for seat number 53, you only have 3 contenders left. For seat number 54, you have only 2 contenders left and then for seat number 55, only the last person is remaining i.e. just one option.

The total number of ways of arranging 5 people on 5 distinct seats is 5*4*3*2*1 = 120

These are some of the most basic examples of basic counting principle. Below, I am giving more questions which are just twists on these questions. Try them and get back if you have any doubts. We will take some higher level concepts from next post on.

Question 1: A restaurant serves 6 varieties of appetizers, 10 different entrees and 4 different desserts. In how many ways can one make a meal if one chooses an appetizer, at least one and at most two different entrees and one dessert?

Question 2: In how many ways can you make a five digit password using the first ten letters of the English alphabet if each letter can be used at most once? (You can use only capital letters.)

Question 3: In how many ways can BRIAN make a five digit password using the first ten letters of the English alphabet if each letter can be used at most once and one is not allowed to use any letter which appears in one’s name? (You can use only capital letters.)

Question 4: Six friends go to watch a movie. They are supposed to occupy seat numbers 51 to 56. However one of them falls sick and returns home. In how many different ways can the 5 people sit?

Question 5: Eight friends go to watch a movie but only 5 tickets were available. In how many different ways can 5 people sit and watch the movie?

Where are the answers to the last 5 questions?

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

Hi VeritasKarishma ma'am, chetan2u

In Q 1 - If the question had not mentioned equally, the answer would have been 4^12? - Same as Q1 in topic: Unfair Distributions in Combinatorics - Part 1

Also When do we Use the below formula:

a. if r >= 0 n+r-1 C r-1
b. If r > 1 , n-1 C r-1


Thanks
Harsh

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.

Let me first give you the solution to the question I gave you in my last post:

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

Solution: What happens when the first friend enters the room? Are all the seats same for him?



Are the seat numbers 5 and 6 the same for him? (The seats are not actually numbered. We have numbered them for easy reference.)

No, they are not! Seat no. 5 has a corner (of the table) on the right hand side and an empty chair on the left hand side while seat no. 6 has a corner on the left hand side and an empty chair on the right hand side. So then, are all the seats distinct for him? I am sure you agree that they are not. It is similar to a circle situation but not quite. Seat no. 6 and seat no. 4 are alike since they both have a corner on the left hand side and an empty chair on the right hand side.

Isn’t the case the same for seat numbers 2 and 8 as well? Can I say that the seat numbers 2, 4, 6 and 8 are the same? It doesn’t matter on which seat he sits out of these 4; the arrangement stays the same. Similarly, notice that seat numbers 1, 3, 5 and 7 are also the same. Therefore, there are 2 ways in which the first person can sit. He can either sit on one of 1, 3, 5 and 7 or on one of 2, 4, 6 and 8. After he sits, all the remaining 7 seats are distinct. 7 people can sit on 7 distinct seats in 7! ways.

Total number of arrangements = 2*7!

Hope it makes sense to you, especially for GMAT prep purposes. You can try any number of variations now. You can also try putting in constraints. I will focus on constraints in linear arrangements today. Perhaps, in another post, we can look at constraints in circular arrangements. In the first post on combinatorics, we learned the basic counting principle. Using that we can solve many simple questions for example:

Question 1: In how many ways can 3 people sit on 3 adjacent seats of the front row of the theatre?

Solution: We know that it is a straight forward basic counting principle application. On the leftmost seat, a person can sit in 3 ways (choose any one of the 3 people). On the middle seat, a person can sit in 2 ways (since 1 person has already been seated). There is only 1 person left for the rightmost seat so he can sit there in 1 way. Total number of arrangements = 3*2*1 = 3! = 6

Now, let’s try to add some constraints here. I will start will some very simple constraints and go on to some fairly advanced constraints.

Question 2: In how many ways can 6 people sit on 6 adjacent seats of the front row of the theatre if two of them, A and B, cannot sit together?

Solution: This is a very simple constraint question. First tell me, what if there was no constraint i.e. what is the total number of arrangements in which 6 people can sit in a row? You should know by now that it is 6! (using Basic Counting Principle). Now, rather than counting the number of ways in which they will not sit next to each other, we can count the number of ways in which they will sit next to each other and subtract that from the total number of arrangements. Why? Because it is easier to group them together (think that we have handcuffed them together) and treat them as a single person to get the arrangements where they will sit together.

So let’s deal with a different question first: In how many ways can 6 people sit on 6 consecutive seats of the front row of the theatre if two of them, A and B, must sit together?

There are 5 individuals/groups: AB C D E F

These 5 can be arranged in a line in 5! ways. But the group AB itself can be arranged in 2 ways AB or BA i.e. B could be to the right of A or to the left of A.

Total number of arrangements = 2*5! (Notice the multiplication sign here. We have to arrange the 5 individuals/groups AND A and B.)

This is the number of arrangements in which A and B will sit together.

Therefore, the number of arrangements in which they will not sit together = 6! – 2*5!

Now let’s discuss some trickier variations of this question.

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

Solution: Here, there is an additional vacant spot since there are only 7 people but 8 seats. You might think that it is a little confusing since you will need to deal with the vacant spot separately. Actually, this be done in a very straight forward way.

7 people including A and F have to be seated such that A and F are not next to each other. So an arrangement where A and F have the vacant spot between them is acceptable. I will just imagine that there is an invisible person called Mr. V. He takes the vacant spot. If A and F have V between them, that arrangement is acceptable to us. Now this question is exactly like the question above. We have 8 people sitting in 8 distinct seats. 8 people (including our imaginary Mr. V) can sit in 8 seats in 8! arrangements.

A and F can sit together in 2*7! arrangements (similar to question no. 2)

Hence, the number of arrangements in which A and F will not sit together = 8! – 2*7!

Question 4: 7 people, A, B, C, D, E, F and H, go to a movie and sit next to each other in 8 adjacent seats in the front row of the theatre. In how many different arrangements will there be at least one person between A and F?

Solution: This variant wants you to put at least one person between A and F. This means that all those cases where A and F are together are not acceptable and all those cases where A and F have Mr. V (the vacant spot) between them are also not acceptable.
8 people (including our imaginary Mr. V) can sit in 8 seats in 8! ways.

A and F can sit together in 2*7! arrangements (similar to question no. 2). Number of arrangements in which A and F have Mr. V between them = 2*6!

How? Now we group AVF together and consider this group one person. So there are 6 distinct individuals/groups which can be arranged in 6! ways. But we have 2 arrangements in this group: AVF and FVA. So total number of arrangements here = 2*6!

These cases are not acceptable.

Hence, the number of arrangements in which A and F will have a person between them = 8! – 2*7! – 2*6! = 8! – 16*6!

Compare question no. 3 with question no. 4: one where you don’t want them to be together, the other where you don’t want them to be together and you don’t want the vacant spot between them.

Obviously, in the second case, the number of cases you do not want are higher. So you subtract a higher number out of the total number of cases.

Let me leave you with a question now. Make sure you answer exactly what is asked.

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

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.

Hi Bunuel KarishmaB can you please give a more direct/analytical approach for Ques 3 & Ques 4 above, instead of solving them by listing the scenarios?

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.

In the quesiton "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?" - Should we not devide the final answer by 3! to unnarrange the final answer?

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?