4
$\begingroup$

In how many ways can 10 people be seated in a circle if:

1) there are 5 men and 5 women and no two men and no two women can sit next to each other?

2)six of them are men and they must sit next to each other?

3) there are four married couples and each husband must sit next to his wife?

I gave a try at solving each of there but am no sure if I did it correctly because I am not sure how to take the circular table into account when counting:

1) first we choose the 5 men or women out of the 10 people $\binom{10}{5}$, then there is $5!$ ways of arranging them, then the remaining people have $5!$ ways of being arranged so my answer would be $\binom{10}{5}$$(5!)^2$

2) choose 6 men out of 10 people $\binom{10}{6}$, then there is $6!$ arrangements for them to sit next to each other, then the remaining women can be seated in $4!$ arrangements so my answer would be

$\binom{10}{6}$$6!$$4!$

3)take each couple as one person, so now there is only 6 people. There is $6!$ different arrangements for everyone to be seated then the two people that are not in a couple can be arranged in $(2!)^2$ ways so my answer would be $6!(2!)^2$

$\endgroup$
  • 1
    $\begingroup$ The convention with a circular table is that two arrangements that are the same if we rotate the table (or equivalently the people) are equivalent. So roughly in effect one should divide by $10$. But your counts are not right. $\endgroup$ – André Nicolas Oct 28 '15 at 3:58
1
$\begingroup$

1) Since two arrangements are considered equivalent if they only differ by a rotation, let us imagine one of the people is the Queen, and one of the chairs is a throne. The Queen sits down on the throne. Now the places occupied by women are determined, but the women can be permuted in these positions in $4!$ ways. Then the men can be inserted in the empty spots in $5!$ ways, for a total of $4!5!$.

2) Again there is a throne, and we can suppose that there is a man on the throne, and all the men are in the five chairs counterclockwise from the throne. The men can be permuted in $6!$ ways, and the women inserted in the empty spots in $4!$ ways.

3) Again the Queen (who is married) sits on the throne. Her husband has $2$ choices. Now there are $3$ couples left, and $2$ singles. We can think of these as $5$ objects, which can be permuted in $5!$ ways, and then, as in your solution, the couples can have members switched in $2^3$ ways, for a total of $(2)(5!)(2^3)$.

Remark: We can solve all of these problems by considering the chairs to be labelled, and count the possible seatings. Then divide the number of labelled seatings by $10$ to deal with the fact that two seatings that are rotationally equivalent are considered the same. But the trick used in the solutions often gives a more concrete visualization.

$\endgroup$
  • $\begingroup$ Why is it that for the first one when the Queen sits on the chair the rest of the women are permuted in $4!$ ways where as when the man sits on the chair its $6!$ as opposed to $5!$? $\endgroup$ – user273323 Oct 28 '15 at 4:17
  • 2
    $\begingroup$ The man is not a specific person. Here is another way of doing the $6$ men $4$ women problem. The leftmost man position can be any of $10$. Then the men can be permuted in $6!$ ways, women in $4!$, (sort of) total $(10)(6!)(4!)$, except we must now divide by $10$ since two arrangements that can be brought into coincidence by a rotation are considered equivalent. $\endgroup$ – André Nicolas Oct 28 '15 at 4:29
  • 1
    $\begingroup$ We could sit the King on the throne, but then there are several ways to choose the seats for the remaining $5$ men, $0$ to $5$ the left of the King. That gives $(6)(5!)(4!)$. $\endgroup$ – André Nicolas Oct 28 '15 at 4:34
  • 1
    $\begingroup$ For (2), another way is to visualize it as the sole way of placing two arcs of men and women completing a circle. But the men and women can be permuted within their arcs. $\endgroup$ – true blue anil Oct 28 '15 at 4:38
  • $\begingroup$ @AndréNicolas The Queen sits down on the throne. After this 9 chairs are left but no 2 women can sit next to each other, there has to be one empty chair between each woman, hence factorial formula n choose k = 9 choose 4 =$\binom{9}{4}$ does not apply. This leaves us with 4 women and 4 chairs, hence $4!$. Rest 5 chairs and 5 men are left and all chairs are alternate, hence $5!$ ways. Since we want men and women here, we will multiply than add. So, total $5! * 4!$. Did I get the reasoning correct ? $\endgroup$ – Arnuld Nov 27 '18 at 6:52

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.