0
$\begingroup$

I have a problem counting the number of ways one can seat people around a circular table.

When ordering does not matter, $n$ people can sit around the table $n!$ ways, and then, because rotations are over counted and there are $n$ rotations of the table, we have that the number of ways is $(n-1)!$.

Now, when saying that if $n$ was an even number with half women and half men, how many ways to arrange them if no one can sit beside someone of the same sex?

I have read answers online, and they all say arrange the $(n/2)!$ women in a circle, divide by the number of rotations so you get $(n/2-1)!$ and then arrange the men so that you get $(n/2-1)!(n/2)!$.

My question here is: Why do we not divide by $n$ as before, if we once again have all those extra rotations?

$\endgroup$
  • $\begingroup$ The strategy here is to consider that the men are indistinguishable (presumably) and so are the women, so you are permuting $n$ indistinguishable men among $n$ indistinguishable women. The fact that the table is round and one can rotate it is irrelevant. Consider that the seats are numbered and you are assigning seats to every individual. $\endgroup$ – Anthony P Nov 10 '16 at 16:25
  • $\begingroup$ Are there any added restrictions, like alternating man and woman? $\endgroup$ – DJohnM Nov 10 '16 at 16:25
  • $\begingroup$ @DJohnM yes, they have to alternate $\endgroup$ – Guacho Perez Nov 10 '16 at 16:46
  • $\begingroup$ @AnthonyP but then, if I considered numbered seats, the answer to how many ways can $n$ people be arranged round a table would be $n!$ and not $(n-1)!$ $\endgroup$ – Guacho Perez Nov 10 '16 at 17:25
3
$\begingroup$

In how many ways can $k$ men and $k$ women be seated at a round table if the men and women alternate seats?

Let Amanda be one of the women. We seat Amanda first. This determines which $k - 1$ seats are available to the other women. The remaining $k - 1$ women can be seated in these seats in $(k - 1)!$ ways as we proceed clockwise around the circle relative to Amanda. The men can be seated in $k!$ ways as we proceed clockwise around the circle relative to Amanda. Hence, the number of permissible seating arrangements is $$(k - 1)!k!$$

You asked why the answer is not $$\frac{k!k!}{2k} = \frac{(k - 1)!k!}{2}$$

Observe that if there is only one man and one woman at the table, this answer yields $1/2$ seating arrangements.

What went wrong?

Suppose Amanda is one of the women, and she is seated first. Since the men and women must alternate, seating Amanda determines in which $k$ seats the women will sit. Hence, there are only $k$ rotations that preserve a given arrangement of the women. Moreover, once the women are seated, the men cannot be rotated without changing the relative order of the people in the seating arrangement. Hence, the number of distinguishable seating arrangements is $$\frac{k!k!}{k} = (k - 1)!k!$$

$\endgroup$
  • 1
    $\begingroup$ To loosely summarize: it's because if you rotate the men one way and the women another, you get a different seating arrangement. +1. $\endgroup$ – Wildcard Aug 26 '17 at 1:43
-1
$\begingroup$

After getting this wrong, I now realize that a choice is made by virtue of seating a man first, or a woman, and this choice has consequences. If a woman is seated first, the other (n/2 -1) women can be seated in the remaining (n/2 - 1) female chair slots, so there are (n/2 -1)! possibilities. The (n/2) men can then occupy the (n/2) remaining chairs freely, multiplying the seating arrangements by (n/2)!.

The rotations are not overcounted, as no choice was counted for the first-seated person's choice of chair, even though there were n empty chairs. Answer:

(n/2 - 1)! * (n/2)! seating positions

$\endgroup$
  • 1
    $\begingroup$ If $n = 2$, your answer gives $1/2$ permissible seating arrangements. $\endgroup$ – N. F. Taussig Aug 26 '17 at 0:09
  • $\begingroup$ Good catch, N.F.. After correction, the answer for the case of n=2 persons is but 1 seating arrangement (swapping seats considered a rotation and thus an overcount). $\endgroup$ – pbierre Aug 27 '17 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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