Counting men and women around a circular table such that no 2 men are seated next to each other

combinatorics

8,740

Solution 1

To begin with: I dont' think it's right to divide by 9. That would be right if you had counted as distinct configurations that differ only in rotations, but that's not the case. When you said "there are 5! ways to sit women..." you implied that you were counting only relative ordering of women, regardless of their "absolute" positions.

Furthermore: if you are counting different relative configuration of women (permutations), you must take into account that you are interested in ciclic permutations (the permutation 13245 is actually the same as 32451), so the number 5! is actually wrong.

Solution 2

A smaller example would make this easier.

2 men $M_{1,2}$ and 3 women $F_{1,2,3}$.

say I put $M_1$ somewhere. Because this is cyclic, this doesn't actually count as a 'choice'. I'll care about the positioning of everyone relative to $M_1$. This automatically takes care of any issues with the cyclical bit of the problem.

$M_1$ needs women to his left and right. There are $2{{3}\choose{2}}=6$ ways of doing this.

So now I have

__ . $F_{1,2,3}$ . $M_1$ . $F_{1,2,3}$ . __

and need to place the remaining two. You have one woman left, and one man. The only question is who gets which seat. With two ways of doing this, you get that there are $6\times 2=12$ valid seatings.

You can do a similar analysis with your problem. It's definitely redundant, but I find it easier to understand and justify.

Fix $M_1$
$2\cdot{{5}\choose{2}}=20$ ways of putting women next to $M_1$
More interesting. We have cases here. one where we include the double woman case now, and one where we don't.

if we don't, then we have to pick two men, of which there are $2{{3}\choose{2}}=6$ possibilities. Then two women, which gives $2{{4}\choose{2}}=12$ possibilities. The remaining woman goes on the end, but as it's cyclic it doesn't matter where she goes. In this case there are $20\times6\times12=1440$ possibilities.

if we do, then we pick one woman, and pick whether to put her on the right or left. There are $6$ ways of doing this. Then we pick two men, in one of $6$ ways as before. The remaining two women go on the ends, in one of two ways, and the remaining man takes the last spot. So there are $2$ ways to place the remaining women, which gives $20\times6\times6\times2=1440$ cases here as well. Adding together gives $2880$ ways overall.

8,740

Salazar

Updated on July 06, 2020

Comments

Salazar over 2 years

Possible Duplicate:
Circular Permutation

I was looking through old homework to work on my counting skills, and I had this problem that I didn't get right.

Question: In how many ways can 4 men and 5 women be seated around a circular table so that no 2 men are seated next to one another?

My Solution: First we sit the women, and leave an open spot in between each to assure a man doesn’t sit next to a man. There are 5! ways to do this. The there are 5 open spots, we only want to choose 4 of those for men to stay in, so $5 \choose 4$. Then there are 4! possible different ways to arrange the men 4 within those spaces. Finally, since the table is round, we want to make sure that rotating it doesn’t make a difference. We can rotate the table 9 times that will produce the same arrangement, thus divide by 9. With the product rule, we find that the total number of arrangements to be:

$$\frac{5!{5 \choose 4}4!}{9} = 1600$$

I believe I undercounted the total arrangements for this problem, but I am not sure where I went wrong.
Salazar over 10 years

Ahh, so just to clarify, does that mean that it would be $\frac{5!}{5}$ since there are 5 women, and thus give 5 repetitions in a circle. Since I didn't start a circle with all 9, then we don't divide by 9. Thus, now I would get $(5-1)! {5 \choose 5} 4! = 4!^2 \cdot 5$.
Erick Wong over 10 years

@Salazar This is correct, except you mean $5 \choose 4$ and not $5 \choose 5$.
leonbloy over 10 years

@Salazar What ErickWong says