• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Combination Question on seating

410
11
1. The problem statement, all variables and given/known data

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

2. Relevant equations

I have the combination and permutation equations

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

Charles Link

Homework Helper
Insights Author
Gold Member
2018 Award
4,268
1,785
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!.
 
410
11
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?
 

Charles Link

Homework Helper
Insights Author
Gold Member
2018 Award
4,268
1,785
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.
 
410
11
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?
 

Charles Link

Homework Helper
Insights Author
Gold Member
2018 Award
4,268
1,785
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!)
 
410
11
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
 

Charles Link

Homework Helper
Insights Author
Gold Member
2018 Award
4,268
1,785
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.
 
410
11
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.
 
410
11
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?
 

Charles Link

Homework Helper
Insights Author
Gold Member
2018 Award
4,268
1,785
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!)?
 
410
11
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?
 

Charles Link

Homework Helper
Insights Author
Gold Member
2018 Award
4,268
1,785
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:

Charles Link

Homework Helper
Insights Author
Gold Member
2018 Award
4,268
1,785
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:

tnich

Homework Helper
838
244
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.
 

Charles Link

Homework Helper
Insights Author
Gold Member
2018 Award
4,268
1,785
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.
 

tnich

Homework Helper
838
244
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.
 

Charles Link

Homework Helper
Insights Author
Gold Member
2018 Award
4,268
1,785
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:

Orodruin

Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
15,297
5,454
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.
 

Want to reply to this thread?

"Combination Question on seating" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top