Combinations/Permutations of Seating at a Circular Table

[annpaulveal]

Homework Statement

In how many ways can a group of 9 women and 6 men be seated at a circular table if no two men can be seated next to each other?

Homework Equations

The Attempt at a Solution

I have come up with a solution, but I'm unsure if my reasoning is correct...

First, I started with the 9 women. They can be arranged in 8! ways / 9 rotations = 4480 options.

Then, I drew a picture of a 12-person table, placing a man between each woman. This is where I think I may have done something wrong. The men can be placed in 5! ways, divided by 12 for rotations = 10 options.

Finally, I drew a picture of the 15-person table. The three remaining women can be placed in 36 different places, with three possibilities existing between each female/male pair. This can be calculated as 36 choose 3, divided by 15 rotations = 476 options.

The final answer would be all three options multiplied together, so 4480(10)(476).

As I said, I have a feeling that I did something wrong, so I would really appreciate some suggestions to get me back on track :)

 

[mfb]

I would not consider rotations for men and women separately - the circular symmetry just applies to the whole table, not to both genders separately. You can divide the total number by 15 afterwards, this should be easier.

The three remaining women can be placed in 36 different places, with three possibilities existing between each female/male pair.

But you already fixed the relative woman orientation!

I would begin with the men/women-combinations first, placing 3 women somewhere between existing men/women-pairs, and care about the individual men/women and the circular table afterwards.

 

[annpaulveal]

Okay, so you're saying I should start with a 12-person table, where the men and women can both be arranged in 5! ways, and then multiply this by 36 choose 3 for the three remaining women, and finally divide this by 15?

So, [(5!)(5!)(36 choose 3)] / 15?

 

[haruspex]

Are the positions around the table distinct? I.e. if one arrangement is a rotation of another, are these counted separately?

 

[mfb]

@haruspex: I think "circular table" implies that the positions are not distinct.

@annpaulveal: Why 5!? You have 15 distinct chairs to fill (imagine a line of 15 chairs, for example), they will lose their identity afterwards. And I don't think your new idea works.

 

[vela]

Okay, so you're saying I should start with a 12-person table, where the men and women can both be arranged in 5! ways, and then multiply this by 36 choose 3 for the three remaining women, and finally divide this by 15?

So, [(5!)(5!)(36 choose 3)] / 15?

Forget about how to arrange the individual women and men for right now. First figure out how many seating arrangements there are for the 6 men.

There are two ways I can think of to do this:

1. You have the 12 individuals at the 12-person table, and now you want to move them to the 15-person table without changing their order. How many ways can you do this?
2. Instead of concentrating on arranging the people, look at the 3 empty seats that will be left over. How many ways can you choose where the 3 empty seats go?

 

[haruspex]

@haruspex: I think "circular table" implies that the positions are not distinct.

Perhaps, but I think that makes the problem quite hard. Even if the positions are distinct, circular gives a different answer from a straight line, so that may be the point of specifying circular.

 

[haruspex]

I'm going to persist with the 'distinct positions' interpretation for now.
Try thinking of it in terms of which women get a man seated to their left.

 

[annpaulveal]

Are the positions around the table distinct? I.e. if one arrangement is a rotation of another, are these counted separately?

No, arrangements that are rotations of another are considered alike and should not be counted twice.

 

[haruspex]

No, arrangements that are rotations of another are considered alike and should not be counted twice.

In that case it's somewhat messy. (I don't see that as implied by the text in the OP. Is this additional information?) You have to consider various cases. I found it easiest to think in terms of groups of two or more women seated together. There are three possibilities for the groupings. Then think through how these groupings may be arranged around the table relative to each other. (I assume reflections are distinct.)
Fwiw, if seats were to be distinct, the answer is $\left(^{w}_m\right)+\left(^{w-1}_{m-1}\right)$.

 

[vela]

There are two ways I can think of to do this:

1. You have the 12 individuals at the 12-person table, and now you want to move them to the 15-person table without changing their order. How many ways can you do this?
2. Instead of concentrating on arranging the people, look at the 3 empty seats that will be left over. How many ways can you choose where the 3 empty seats go?

I've realized you need to keep the men-women pairs together. So you really have 6 pairs at the first table, and you need to seat them at the 15-seat table. This is what mfb said way back at the beginning.

It may help you to look at a case where it's easy to count by hand. For example, say you have two men and four women. You should be able to convince yourself the only ways you can arrange them are:

mWmWWW
mWWmWW
mWWWmW

Any other arrangement around a circular table would have the two men sitting next to each other. You don't need to include arrangements where a woman is very first because those arrangements are simply one of the above shifted cyclicly to the right. There are 2! ways to seat the men into the two m spots, and 4! ways to seat the women in the four W spots. In total, you have 2×24×3 ways to seat the group at the table without the men sitting next to each other.

So how do you come up with 3, the number of arrangements? In terms of pairs, you can look at the arrangements as

(MW)(MW)WW
(MW)W(MW)W
(MW)WW(MW)

Can you come up with an expression that counts these?

 

[haruspex]

mWmWWW
mWWmWW
mWWWmW

According to the additional information that rotational symmetries are to be factored out, the first and third of those are the same.

 

[vela]

Oy. OK, I'll leave this problem to you guys.

 

[jashua]

Think that you place 9 women around the circular table. As the question requires the number of circular permutations, there are (9-1)! ways to place 9 women. Now there are 9 spaces to place 6 men such that none of these 6 men sit next to each other. Then, just find the number of ways to place 6 men into these 9 spaces. After that simply by using the product rule, you should be able to find the result

 

[haruspex]

Think that you place 9 women around the circular table. As the question requires the number of circular permutations, there are (9-1)! ways to place 9 women.

I believe the women are to be considered indistinguishable from each other, the men indistinguishable from each other, and the seats indistinguishable beyond relative position (i.e. rotations of the arrangements are to be counted only once). All we care about is the pattern of Ms and Ws, like beads on a necklace.

 

[mfb]

I believe the women are to be considered indistinguishable from each other, the men indistinguishable from each other

I would be surprised by that. For distinguishable persons, I found a solution (it is not in this thread, but somewhere else). For indistinguishable persons, it is a bit easier, you can simply count the (few) possible cases.