Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

marked as duplicate by Gerry Myerson, Brian M. Scott, tomasz, Chris Eagle, t.b. Aug 17 '12 at 11:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
1  
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$. –  Salazar Jul 6 '12 at 3:41
1  
@Salazar This is correct, except you mean $5 \choose 4$ and not $5 \choose 5$. –  Erick Wong Jul 6 '12 at 5:36
    
@Salazar What ErickWong says –  leonbloy Jul 6 '12 at 12:05
add comment

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.

  1. Fix $M_1$
  2. $2\cdot{{5}\choose{2}}=20$ ways of putting women next to $M_1$
  3. 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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.