Combination Question on seating

In summary, the problem asks for the number of ways to seat 11 men and 8 women in a row where no two women are seated together. The solution involves breaking up the problem into three cases - all spare seats together, 3 and 1 spare seats, and 2 and 2 spare seats - and finding the number of ways to insert them in between the 15 seats needed for the women. The final answer will be the sum of all three cases multiplied by the number of ways to arrange the 8 women and 11 men, respectively. The most challenging part of the problem is counting the number of ways to insert the individual spare seats, but with some effort, it can be solved.
  • #1
RoboNerd
410
11

Homework Statement



In how many different ways can you seat 11 men and 8 women in a row if no two women are to sit together?

Homework Equations



I have the combination and permutation equations

The Attempt at a Solution



I assume that given the context of this question if I have two, three, four, five, six or even seven consecutive women, then that is an invalid seating due to the fact that at least two women are sitting together.

Therefore I find the number of ways that I seat 11 men and 8 women with the women being alternated between men and then I subtract it from the total number of possible ways that I can seat 11 men and 8 women in a row without restrictions to get a result.

If my theoretical approach is correct, then how do I calculate the number of possibilities for 11 men and 8 women being seated together with no woman being adjacent to each other - especially since having block of three, four, five... , 8 adjacent women is invalid?

I am stuck on trying to solve this problem. Any input would be greatly appreciated. Thanks in advance!
 
Physics news on Phys.org
  • #2
You could basically consider the problem as 8 women with 19 seats, (and the 11 men just multiplies the solution by 11!). The 8 women need 15 seats, (with them always having one seat between them), and you then have 4 extra seats to put in all the possible locations. It appears it will take some effort to count the number of ways 4 spare seats can be assigned. Of course, having 8 distinguishable women multiplies the count by 8!.
 
  • #3
Charles Link said:
t appears it will take some effort to count the number of ways 4 spare seats can be assigned. Of course, having 8 distinguishable women multiplies the count by 8!.

How will I be able to count the number of ways that four spare seats are assigned then? What method should I use?
 
  • #4
RoboNerd said:
How will I be able to count the number of ways that four spare seats are assigned then? What method should I use?
It doesn't look simple. One way I see is to begin by first taking the case where these 4 seats stay together. Then there is also a case where they are separated into 3 and 1, etc. , and then 2 and 2, etc. It's a lot of counting, but I don't know how else to do it.
 
  • Like
Likes RoboNerd
  • #5
Charles Link said:
It doesn't look simple. One way I see is to begin by first taking the case where these 4 seats stay together. Then there is also a case where they are separated into 3 and 1, etc. , and then 2 and 2, etc. It's a lot of counting, but I don't know how else to do it.

Makes sense. Thanks for the recommendation. So we just treat the group of four, three, two chairs as a single "SLOT" so to say, that we insert?

So here's the plan:
8 women need 15 seats. This will be the basis for every other calculation.
I then break up the remaining chairs into three cases: all together, 3 and 1, 2 and 2. I then try to find places to insert them, and I assume that all the chairs belong to men.

I then multiply the above possibilities by 8! and 11! for the women and men respectively.

Is that it?
 
  • Like
Likes Charles Link
  • #6
That's correct. And a given state, e.g. 4+1 chairs between the second lady and the 3rd lady, must get counted only once, and then once all of these states are tallied up, you multiply by (11!)(8!)
 
  • #7
Charles Link said:
And a given state, e.g. 4+1 chairs between the second lady and the 3rd lady, must get counted only once,

I do not understand what you mean by that. Could you please explain (maybe in other words) exactly what you mean?

Thanks
 
  • #8
When you take the group of 4 spare seats that are together, you can put them to the left of the first lady, or between the first and second lady, or between the 2nd and third lady, but don't count them twice, e.g., by placing them to the left of the empty seat and then to the right of the empty seat. If the second and third ladies have 5 seats between them, you only count that case once.
 
  • Like
Likes RoboNerd
  • #9
Charles Link said:
When you take the group of 4 spare seats that are together, you can put them to the left of the first lady, or between the first and second lady, or between the 2nd and third lady, but don't count them twice, e.g., by placing them to the left of the empty seat and then to the right of the empty seat. If the second and third ladies have 5 seats between them, you only count that case once.
I see.

Thank you very much. Let me try and solve this problem now... I will get back to you (G-d willing) with a response.
 
  • Like
Likes Charles Link
  • #10
RoboNerd said:
I see.

Thank you very much. Let me try and solve this problem now... I will get back to you (G-d willing) with a response.
O.K.

Isn't there a possibility that the four chairs are to be broken into a 4 groups of 1 chairs for insertion?
 
  • #11
Yes, they can be individuals. That one I didn't mention above, but it was sort of "to be understood", in my explanation. ## \\ ##Just for one additional input: Take the case of 2 and 2 spare seats. You basically have 9 places to put them, (you must put them in different places), and I believe there are (9)(8)/2 ways you can put them. The 4 together is also an easy one to count. The 3 and 1 is also not difficult to count. ## \\ ## The hardest one is the individuals, but I think with about 5 minutes of work, you could tally the individual case. In fact, instead of tallying, why not just (9)(8)(7)(6)/(4!)?
 
  • #12
Charles Link said:
I believe there are (9)(8)/2 ways you can put them.

I understand that there are 9 possible slots for the first one and 8 possible slots for the second one, but why did you divide them by two?
 
  • #13
Please see the last edited addition (post 11) of computing the individuals instead of tallying. ## \\ ## And to answer the above question, the factor of 2 is a 2! because the spare seats are indistinguishable. You are counting states. You put the first one in 9 places and the second one in 8 more. If they had tags on them to tell them apart, then it would be 72. Instead, it is only 36. ## \\ ## And I think with the 3 and 1, you will find there are (9)(8) because, unlike the 2 and 2 case, the 3 and 1 are distinguishable (it is like they have tags).
 
Last edited:
  • #14
And one case I did overlook was the 1, 1, and two. That one should not be too difficult to count, but I'll let you try to compute it, and I will try to confirm your answer. ## \\ ## Editing: Yes, I computed it=it is really rather straightforward.
 
Last edited:
  • #15
I think you can simplify this a little. You have 8 women to seat. In between each woman you need to seat at least one man. How many ways could you choose 7 men to sit in those slots? Now you have four men left. Each can sit in one of the seven slots between two women or in additional slots at each end of the row, so there are 9 slots to allocate the remaining four men to. If you take it step by step, you can write out a simple expression using factorials, binomial coefficients, and stars and bars.
 
  • #16
tnich said:
I think you can simplify this a little. You have 8 women to seat. In between each woman you need to seat at least one man. How many ways could you choose 7 men to sit in those slots? Now you have four men left. Each can sit in one of the seven slots between two women or in additional slots at each end of the row, so there are 9 slots to allocate the remaining four men to. If you take it step by step, you can write out a simple expression using factorials, binomial coefficients, and stars and bars.
That's basically what we have done, but we don't need to compute the number of ways the seven men can be put into those slots. It would appear that the different cases of the 4 remaining seats need to be treated separately depending upon how they get grouped together. I don't think one simple combinatorial expression will treat them, but the computation of the combinations for these is readily performed.
 
  • #17
Charles Link said:
That's basically what we have done, but we don't need to compute the number of ways the seven men can be put into those slots. It would appear that the different cases of the 4 remaining seats need to be treated separately depending upon how they get grouped together. I don't think one simple combinatorial expression will treat them, but the computation of the combinations for these is readily performed.
The multichoose function (stars and bars) will give you the number of ways to assign 4 men to 9 slots.
 
  • Like
Likes Charles Link
  • #18
tnich said:
The multichoose function (stars and bars) will give you the number of ways to assign 4 men to 9 slots.
Upon further study, yes, I think that is correct. I'd like to compare answers to the longer way of counting them, but I think it would arrive at the same result. ## \\ ## Editing: Yes, the results agree. And for the 9 slots, it is really represented by 8 women,(not 9), and 4 men to get the number of combinations. It only took a couple of minutes to do the long way, but the calculation suggested by @tnich is easier.
 
Last edited:
  • #19
It is much easier to do it the other way around. First seet the 11 men and then distribute the women by selecting 8 of the 12 possible slots. Of course taking permutations into account.
 
  • Like
Likes tnich

1. What is a combination question on seating?

A combination question on seating is a type of problem that involves arranging a group of people in a specific order or pattern, such as around a table or in a row of seats. These questions typically involve using combinations and permutations to determine the total number of possible arrangements.

2. How do I approach solving a combination question on seating?

To solve a combination question on seating, start by identifying the number of people and the number of seats or positions available. Then, determine if the order of the people matters, as this will affect whether to use combinations or permutations. Finally, use the appropriate formula to calculate the total number of possible arrangements.

3. Can you give an example of a combination question on seating?

Sure, here's an example: In a row of 6 seats, how many ways can 4 people be seated if the order doesn't matter? In this case, we would use combinations and the formula nCr = n! / (r!(n-r)!). Plugging in our values, we get 6C4 = 6! / (4!(6-4)!) = 15 ways.

4. What is the difference between combinations and permutations in a seating question?

In a combination question on seating, the order of the people doesn't matter. For example, if Mary, John, and Sarah are sitting in a row, it doesn't matter if Mary is in the first or second seat. In a permutation question, the order does matter. Using the same example, if Mary, John, and Sarah are sitting at a round table, the seating arrangement would be different if Mary was in the first or second seat.

5. How can I use combinations and permutations in real life situations?

Combinations and permutations are commonly used in real life situations such as seating arrangements for events, lottery number combinations, and password combinations. They can also be used in statistics and probability to calculate the likelihood of certain outcomes. Knowing how to use these mathematical concepts can help in solving a variety of problems in everyday life.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
3K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
4K
  • Precalculus Mathematics Homework Help
Replies
4
Views
574
Replies
19
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
9K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
5K
  • Biology and Medical
Replies
15
Views
1K
Back
Top