It is currently 10 Sep 2026, 13:38
Home
Messages
Tests
Schools
Events
Close
GMAT Club Daily Prep
Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track
Your Progress

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History
Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.
Go to My Error Log Learn more
Close
Request Expert Reply
Confirm Cancel
User avatar
D4kshGargas
User avatar
Joined: 01 Apr 2020
Last visit: 28 Feb 2021
Posts: 80
Location: India
GMAT 1: 650 Q46 V34 (Online)
GMAT 2: 680 Q48 V35 (Online)
GMAT 2: 680 Q48 V35 (Online)
Posts: 80
Combinatorics Made Easy!
Post URL
25 Jun 2020, 23:05
Bunuel
Unfair Distributions in Combinatorics - Part 1
BY KARISHMA, VERITAS PREP

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.
Show more


Hi, why is question 1 different from Question 3?
I mean, why does it REALLY matter whether fruits are different or the same? I mean I know we usually divide by the x! whenever we see repetition.
But, even if all apples are the same, still, each apple can be distributed in 4 respective ways.
Why was there any need to list down all the cases?

Am I missing something?
Kudos
Add Kudos
1
Bookmarks
Bookmark this Post
avatar
darkknight016
avatar
Joined: 02 Jun 2019
Last visit: 23 Mar 2025
Posts: 12
Posts: 12
Combinatorics Made Easy!
Post URL
15 Jul 2020, 23:28
Bunuel
The Dreaded Combinatorics
BY KARISHMA, VERITAS PREP

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?
Show more
Hi VeritasKarishma ma'am, plz clarify my doubt
In example 3, why is it not 10C5 x 5! (10C5 for selecting 5 alphabets out of 10 and 5! for arranging them)?
Is it because while using 10C5 I am selecting any 5 non repeating ones while the letters can get repeated too?
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
KarishmaB
User avatar
Joined: 16 Oct 2010
Last visit: 10 Sep 2026
Posts: 16,648
Location: Pune, India
Expert
Expert reply
Active GMAT Club Expert! Tag them with @ followed by their username for a faster response.
Posts: 16,648
Combinatorics Made Easy!
Post URL
20 Jul 2020, 02:16
darkknight016
Bunuel
The Dreaded Combinatorics
BY KARISHMA, VERITAS PREP

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?
Hi VeritasKarishma ma'am, plz clarify my doubt
In example 3, why is it not 10C5 x 5! (10C5 for selecting 5 alphabets out of 10 and 5! for arranging them)?
Is it because while using 10C5 I am selecting any 5 non repeating ones while the letters can get repeated too?
Show more

Yes, the question stem does not say that no letter should be repeated in the password. Any of the 10 letters can be repeated any number of times (upto 5) to make a valid password. A valid password is 'aaaaa'. But in your case, you are not considering this as a possible password.

_________________
-
Start FREE with selected GMAT/EA Content upon registration at anaprep.com

YouTube Channel: karishma.anaprep
Signature Read More
Kudos
Add Kudos
1
Bookmarks
Bookmark this Post
avatar
fertooos
avatar
Joined: 29 Jun 2020
Last visit: 10 May 2021
Posts: 4
Posts: 4
Combinatorics Made Easy!
Post URL
28 Jul 2020, 11:38
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.
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
Harsh9676
User avatar
Joined: 18 Sep 2018
Last visit: 27 Feb 2023
Posts: 234
Location: India
Concentration: Finance, International Business
GMAT 1: 690 Q49 V36
GPA: 3.72
WE:Investment Banking (Finance: Investment Banking)
Products:
My Reviews
GMAT 1: 690 Q49 V36
Posts: 234
Combinatorics Made Easy!
Post URL
08 Aug 2020, 03:08
Bunuel
Linear Arrangement Constraints - Part I
BY KARISHMA, VERITAS PREP

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?

Show Spoiler
Attachment:
Ques31.jpg
Show more


Hi I have a small question in Q3.

I am not able to arrive at the same solution using the combinotrics approach.

Total ways = 8C7 * 7! >> Selecting Seven Seats out of 8 and arranging 7 people in 7 seats.
Unfavourable outcomes - A&F Together = 8C7 * 6! * 2! >>> Selecting 7 seats again, arranging 6 people (A+F) together and A&F can interchange so 2! again.

So Favourable Outcomes are = 8! - 8*6!*2!.

Bunuel, chetan2u, VeritasKarishma, Please help where I am going wrong with this approach.
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
chetan2u
User avatar
GMAT Expert
Joined: 02 Aug 2009
Last visit: 10 Sep 2026
Posts: 11,291
Status:Math and DI Expert
Location: India
Concentration: Human Resources, General Management
GMAT Focus 1: 735 Q90 V89 DI81
Products:
My Reviews
Expert
Expert reply
GMAT Focus 1: 735 Q90 V89 DI81
Posts: 11,291
Combinatorics Made Easy!
Post URL
08 Aug 2020, 08:07
Harsh9676


Hi I have a small question in Q3.

I am not able to arrive at the same solution using the combinotrics approach.

Total ways = 8C7 * 7! >> Selecting Seven Seats out of 8 and arranging 7 people in 7 seats.
Unfavourable outcomes - A&F Together = 8C7 * 6! * 2! >>> Selecting 7 seats again, arranging 6 people (A+F) together and A&F can interchange so 2! again.

So Favourable Outcomes are = 8! - 8*6!*2!.

Bunuel, chetan2u, VeritasKarishma, Please help where I am going wrong with this approach.
Show more


Hi,

When you have taken A and F together, you don’t have 8 seats but 7 seats as you are taking two adjoining seats for A and F as one, so 7 seats out of which you have to choose 6 and then arrange these in 6! ways.
Now A and F can be arranged between themselves in 2! ways. Hence 7*6!*2!=7!*2

Final answer - 8!-7!*2

_________________
Chetan Sharma,
1. Absolute modulus 2. Fractions 3. Percentage increase 4. Combinations
Signature Read More
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
Harsh9676
User avatar
Joined: 18 Sep 2018
Last visit: 27 Feb 2023
Posts: 234
Location: India
Concentration: Finance, International Business
GMAT 1: 690 Q49 V36
GPA: 3.72
WE:Investment Banking (Finance: Investment Banking)
Products:
My Reviews
GMAT 1: 690 Q49 V36
Posts: 234
Combinatorics Made Easy!
Post URL
08 Aug 2020, 10:33
Ah!!!!

Understood. Thanks chetan2u
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
Shrey08
User avatar
Joined: 04 Mar 2020
Last visit: 04 Mar 2026
Posts: 169
Location: India
GMAT 1: 640 Q47 V30
GMAT 1: 640 Q47 V30
Posts: 169
Combinatorics Made Easy!
Post URL
31 Aug 2020, 00:01
Quote:

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?
https://gmatclub.com/forum/combinatorics-made-easy-206266.html#p1579485
Show more

Great write up VeritasKarishma!

Can you please help me understand why am I wrong if I solve the question the following way:

There are total 5! ways to sit around the table w/o any restrictions.

Andy and Bob can sit diametrically opposite to each other in 2*3*4! ways (2 because they can swap places at diametrically opposite ends, 3 because there are six seats and in pair they can sit on 3 pair of seats, and 4! for other four people)

5!-6*4! is negative number. :roll:

_________________
In sterquiliniis invenitur- Carl Jung
That which you most want to find will be found where you least want to look
Signature Read More
Kudos
Add Kudos
Bookmarks
Bookmark this Post
avatar
marialst
avatar
Joined: 30 Sep 2018
Last visit: 10 Aug 2026
Posts: 1
Posts: 1
Combinatorics Made Easy!
Post URL
01 Sep 2020, 07:13
Thank you so much! I've learned a lot from VeritasKarishma posts.

Could you provide the answers to this questions?

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?


Thanks a lot!!
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
KarishmaB
User avatar
Joined: 16 Oct 2010
Last visit: 10 Sep 2026
Posts: 16,648
Location: Pune, India
Expert
Expert reply
Active GMAT Club Expert! Tag them with @ followed by their username for a faster response.
Posts: 16,648
Combinatorics Made Easy!
Post URL
03 Sep 2020, 21:43
ShreyKapil08
Quote:

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?
https://gmatclub.com/forum/combinatorics-made-easy-206266.html#p1579485

Great write up VeritasKarishma!

Can you please help me understand why am I wrong if I solve the question the following way:

There are total 5! ways to sit around the table w/o any restrictions.

Andy and Bob can sit diametrically opposite to each other in 2*3*4! ways (2 because they can swap places at diametrically opposite ends, 3 because there are six seats and in pair they can sit on 3 pair of seats, and 4! for other four people)

5!-6*4! is negative number. :roll:
Show more

When you say that Andy and Bob can sit opposite to each other in 2*3 = 6 ways, you are forgetting that it is a circular arrangement, which means the seats are not distinct. If the seats were numbered 1, 2,3 ,4 5, 6, then you can select one pair (1-4) and switch Andy and Bob on those.
Here, Andy sits on any seat and it is all the same. Now Bob can sit at only one place (opposite to Andy) if Andy and Bob are to sit opposite to each other.
Hence Bob and Andy can sit opposite to each other in 4! total ways.
You get 5! - 4! = 4*4!

_________________
-
Start FREE with selected GMAT/EA Content upon registration at anaprep.com

YouTube Channel: karishma.anaprep
Signature Read More
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
KarishmaB
User avatar
Joined: 16 Oct 2010
Last visit: 10 Sep 2026
Posts: 16,648
Location: Pune, India
Expert
Expert reply
Active GMAT Club Expert! Tag them with @ followed by their username for a faster response.
Posts: 16,648
Combinatorics Made Easy!
Post URL
03 Sep 2020, 21:44
marialst
Thank you so much! I've learned a lot from VeritasKarishma posts.

Could you provide the answers to this questions?

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?


Thanks a lot!!
Show more

Please give the individual links of each of these questions. If they are not yet up on the forum, please put them in a new post as per the forum guidelines.

_________________
-
Start FREE with selected GMAT/EA Content upon registration at anaprep.com

YouTube Channel: karishma.anaprep
Signature Read More
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
akshitab2912
User avatar
Joined: 24 Jan 2020
Last visit: 29 Jul 2026
Posts: 21
Posts: 21
Combinatorics Made Easy!
Post URL
24 Sep 2020, 03:36
Bunuel
Combinations with Constraints
BY KARISHMA, VERITAS PREP

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
Show more

Hi,

In this question:If a committee of 3 people is to be selected from among 6 married couples such that the committee does not include two people who are married to each other, how many such committees are possible?
Why can't the solution be 12C1 X 10C1 X8C1? We are selecting in this case and not arranging anyway. Please advise.
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
chetan2u
User avatar
GMAT Expert
Joined: 02 Aug 2009
Last visit: 10 Sep 2026
Posts: 11,291
Status:Math and DI Expert
Location: India
Concentration: Human Resources, General Management
GMAT Focus 1: 735 Q90 V89 DI81
Products:
My Reviews
Expert
Expert reply
GMAT Focus 1: 735 Q90 V89 DI81
Posts: 11,291
Combinatorics Made Easy!
Post URL
24 Sep 2020, 03:51
akshitab2912

Hi,

In this question:If a committee of 3 people is to be selected from among 6 married couples such that the committee does not include two people who are married to each other, how many such committees are possible?
Why can't the solution be 12C1 X 10C1 X8C1? We are selecting in this case and not arranging anyway. Please advise.
Show more


12C1*10C1*8C1 is arrangement that is the order matters.
For example let there be A1, B1, and C1
Now 12C1*10C1*8C1 would mean A1,B1,C1 and B1,A1,C1 and so on
That is why we divide by 3!

_________________
Chetan Sharma,
1. Absolute modulus 2. Fractions 3. Percentage increase 4. Combinations
Signature Read More
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
akshitab2912
User avatar
Joined: 24 Jan 2020
Last visit: 29 Jul 2026
Posts: 21
Posts: 21
Combinatorics Made Easy!
Post URL
24 Sep 2020, 09:47
chetan2u
akshitab2912

Hi,

In this question:If a committee of 3 people is to be selected from among 6 married couples such that the committee does not include two people who are married to each other, how many such committees are possible?
Why can't the solution be 12C1 X 10C1 X8C1? We are selecting in this case and not arranging anyway. Please advise.


12C1*10C1*8C1 is arrangement that is the order matters.
For example let there be A1, B1, and C1
Now 12C1*10C1*8C1 would mean A1,B1,C1 and B1,A1,C1 and so on
That is why we divide by 3!
Show more

Thanks, I got your point. But help me with this piece:

Let's say there are 2 group of colors:
Group_1:Blue, Black, Brown, Pink .
Group_2: Red, Green, Magenta

I need to select any one color from Group_1 and any one from Group_2.
I can do it by applying 4C1 X 3C1=12.

Now the combinations are Blue-Red, Blue-Green,Blue-Magenta, Black-Red, Black-Green,Black-Magenta,Brown-Red, Brown-Green,Brown-Magenta, Pink-Red, Pink-Green,Pink-Magenta.

These are the 12 combinations. Nowhere I come across Pink-Magenta or Magenta-Pink. I dont see why I need to divide it any further by 2!. Can you please help me in filling the gap here?

Also when you say Combination I am assuming order doesn't matter unlike in arrangement/enumeration where order matters.
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
chetan2u
User avatar
GMAT Expert
Joined: 02 Aug 2009
Last visit: 10 Sep 2026
Posts: 11,291
Status:Math and DI Expert
Location: India
Concentration: Human Resources, General Management
GMAT Focus 1: 735 Q90 V89 DI81
Products:
My Reviews
Expert
Expert reply
GMAT Focus 1: 735 Q90 V89 DI81
Posts: 11,291
Combinatorics Made Easy!
Post URL
24 Sep 2020, 19:17
akshitab2912
chetan2u
akshitab2912

Hi,

In this question:If a committee of 3 people is to be selected from among 6 married couples such that the committee does not include two people who are married to each other, how many such committees are possible?
Why can't the solution be 12C1 X 10C1 X8C1? We are selecting in this case and not arranging anyway. Please advise.


12C1*10C1*8C1 is arrangement that is the order matters.
For example let there be A1, B1, and C1
Now 12C1*10C1*8C1 would mean A1,B1,C1 and B1,A1,C1 and so on
That is why we divide by 3!

Thanks, I got your point. But help me with this piece:

Let's say there are 2 group of colors:
Group_1:Blue, Black, Brown, Pink .
Group_2: Red, Green, Magenta

I need to select any one color from Group_1 and any one from Group_2.
I can do it by applying 4C1 X 3C1=12.

Now the combinations are Blue-Red, Blue-Green,Blue-Magenta, Black-Red, Black-Green,Black-Magenta,Brown-Red, Brown-Green,Brown-Magenta, Pink-Red, Pink-Green,Pink-Magenta.

These are the 12 combinations. Nowhere I come across Pink-Magenta or Magenta-Pink. I dont see why I need to divide it any further by 2!. Can you please help me in filling the gap here?

Also when you say Combination I am assuming order doesn't matter unlike in arrangement/enumeration where order matters.
Show more

Hi,

The above example deals with two different groups. You cannot pick up the same in 4C1 and then again in 3C1.

But 12C1, 8C1 and 10C1 deal with the same group, so A1 could be picked as 12C1, and if not picked in first go, then it could be 10C1 and so on. Thus, here A1 picked as 12C1 or 10C1 or 8C1 are treated as different way in 12C1*10C1*8C1

_________________
Chetan Sharma,
1. Absolute modulus 2. Fractions 3. Percentage increase 4. Combinations
Signature Read More
1
Kudos
Add Kudos
Bookmarks
Bookmark this Post
avatar
hkkat
avatar
Joined: 07 Oct 2020
Last visit: 16 Jan 2021
Posts: 31
Posts: 31
Combinatorics Made Easy!
Post URL
19 Oct 2020, 20:58
Bunuel
Circular Arrangement Constraints - Part I
BY KARISHMA, VERITAS PREP

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.
Show more

I'm a bit lost here, why do i have to muntiply by 2 "But Andy and Bob can swap places so we need to multiply 5! by 2." ?
Kudos
Add Kudos
Bookmarks
Bookmark this Post
User avatar
chetan2u
User avatar
GMAT Expert
Joined: 02 Aug 2009
Last visit: 10 Sep 2026
Posts: 11,291
Status:Math and DI Expert
Location: India
Concentration: Human Resources, General Management
GMAT Focus 1: 735 Q90 V89 DI81
Products:
My Reviews
Expert
Expert reply
GMAT Focus 1: 735 Q90 V89 DI81
Posts: 11,291
Combinatorics Made Easy!
Post URL
19 Oct 2020, 21:29
hkkat




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.

I'm a bit lost here, why do i have to muntiply by 2 "But Andy and Bob can swap places so we need to multiply 5! by 2." ?
Show more

Let the 7 person be 1, 2, 3, 4, 5, A and B..
Since we have taken AB as one unit, we have 6 people...1, 2, 3, 4, 5 and (AB).....On a circular table, they can be arranged in 5! ways, but each of these has AB in the given order.
One such way would be 12(AB)345, but 12(BA)345 is a different way, and to account for that, we multiply total ways by 2.

_________________
Chetan Sharma,
1. Absolute modulus 2. Fractions 3. Percentage increase 4. Combinations
Signature Read More
1
Kudos
Add Kudos
Bookmarks
Bookmark this Post
avatar
hkkat
avatar
Joined: 07 Oct 2020
Last visit: 16 Jan 2021
Posts: 31
Posts: 31
Combinatorics Made Easy!
Post URL
21 Oct 2020, 00:48
Bunuel
Using Combinations to Make Groups
BY KARISHMA, VERITAS PREP

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

Show more

I don't get it, what makes it distinctive?
Kudos
Add Kudos
Bookmarks
Bookmark this Post
avatar
hkkat
avatar
Joined: 07 Oct 2020
Last visit: 16 Jan 2021
Posts: 31
Posts: 31
Combinatorics Made Easy!
Post URL
21 Oct 2020, 05:39
Bunuel
Tackling the Beasts Together
BY KARISHMA, VERITAS PREP



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
Show more
i don't quit get the pink part, can someone explain it in another way
Kudos
Add Kudos
Bookmarks
Bookmark this Post
avatar
sr12345
avatar
Joined: 22 Dec 2016
Last visit: 20 Jun 2021
Posts: 1
Posts: 1
Combinatorics Made Easy!
Post URL
07 Nov 2020, 08:14
Bunuel
Combinations with Constraints
BY KARISHMA, VERITAS PREP

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
Show more

In question 1, could you please validate the below solution if we use the formula
Selecting 3 couples - 6C3 and then selecting 3 people among those 3 couples - 2*2*2. -where am I going wrong?

Posted from my mobile device
Kudos
Add Kudos
Bookmarks
Bookmark this Post
   1   2   3   4   
NEW TOPIC
POST REPLY
Downloads
My Bookmarks
Reviews
Moderator:
Bunuel
Math Expert
113419 posts