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.

Can someone please explain how to solve circular permutation sums. I just cannot seem to understand them.

eg.

$\text{(4)}$ The number of ways in which $6$ men and $5$ women can dine at a round table if no two women are to sit together is given by

  • $\text{(a)}$ $6!*5!$

  • $\text{(b)}$ $50$

  • $\text{(c)}$ $5!*4!$

  • $\text{(d)}$ $7!*5!$

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

First seat the $6$ men. If they were seated in a row, there would be $6!$ possible permutations of them. However, they’re actually seated around a circular table, which changes things. The six permutations $ABCDEF,BCDEFA,CDEFAB,DEFABC,EFABCD$, and $FABCDE$ are the same when the men are sitting in a circle: the only differences is where in the circle you started the list. Thus, each arrangement of the men around the table corresponds to $6$ permutations in a straight line, and there are therefore only $\frac{6!}6=5!$ possible arrangements of the men around the table. (This is a useful general fact: there are $(n-1)!$ circular permutations of $n$ things.)

Now we seat the $5$ women. There are $6$ positions available between adjacent men, so we have $6$ possible ways to seat the first woman. If we put another woman between the same two men, she’d be sitting next to the first woman; we don’t want that, so we have to seat her in one of the other $5$ gaps between adjacent men. That leaves $4$ open gaps for the third women, $3$ for the fourth woman, and $2$ for the last woman, so altogether we can seat the women in $6\cdot5\cdot4\cdot3\cdot2=6!$ different ways.

Combining the two results, we see that the $11$ people can be seated in $5!\cdot6!$ different orders around the table if no two women sit next to each other.

share|improve this answer
    
Thanks a lot. :) –  Ashu Jun 16 '12 at 11:45
add comment

Firstly let the 6 men sit at the table, this can happen in $(6 - 1)!$ ways. Then there are 6 spots between the men for the women to sit. This can be done in $6.5.4.3.2 = 6!$ ways, hence you have the answer $6!*5!$.

share|improve this answer
    
Aside from the fact that there are only 5 women, not 6, how does this account for the restriction that no two women are to sit together? –  user22805 Jun 16 '12 at 9:18
    
@David: Serkan’s answer is entirely correct, and I’ve upvoted it. I provided another essentially equivalent answer only because I’ve the impression that the OP could use a little more explanation of the reasoning. –  Brian M. Scott Jun 16 '12 at 10:20
    
@Serkan So, where there are 11 seats at the table, you're not actually letting the men sit first. You're just letting them choose the order in which they will sit, once the women have chosen their spots. This is a bit different from what your answer actually says. If you can amend your answer, I will remove my downvote. –  user22805 Jun 16 '12 at 10:21
    
@David: Oh, for Pete’s sake. You might as well complain because a native speaker would say ‘sit at the table’, not ‘sit on the table’. How do you know that there aren’t $12$ seats, with the men taking every second seat in some order? The reasoning is both correct and clear, if tersely expressed. –  Brian M. Scott Jun 16 '12 at 10:43
    
+1 bcoz ur answer was helpful but i wanted an explaination for my question. –  Ashu Jun 16 '12 at 11:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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