6
$\begingroup$

$4$ married couples and $2$ single men sit at a circular table. In how many ways can they sit so that a man can't sit next to a woman who is not his wife?

I have tried but I am not sure to the following answer :

First, the husbands sit in the circular table of which the possible ways is $3!$.

The wives should sit next to her husband which is only $1$ way.

The two men can only be put between two husbands in only $2$ ways and they then can be permuted in $2$ ways. So the number of ways is $4$.

By applying the multiplication principle, the total number of ways for this possibility is $3! \times 4$ = $24$.

The second possibility is similar which is making the wives sit first and put each husband next to his own wife and then put the single men. The total number of ways is also $24$.

So the answer is $24 + 24 = 48$.

$\endgroup$
4
$\begingroup$

As each woman has two neighbors, one way to have a woman not sit next to a man who is not her husband is to line up husband$_1$ wife$_1$ wife$_2$ husband$_2$ twice. Then we have three ways to pair up the couples and two ways to flip each pair left/right. We might as well put the leftmost of the pair including husband A at seat $1$ to break the rotational symmetry. Then there are three groups of seats for the other married couple and a factor two for placing the single men. Total is $$3 \cdot 2^2 \cdot 3 \cdot 2=72$$
The other way to deal with the women is to place all four together in some order, $4!$ ways and seat the husbands of the end ones next to them. Again break the symmetry by seating the leftmost woman in seat $1$. Now you can arrange the other four men any way you want, another $4!$ ways, giving $$4!^2=576$$ The total is then $$72+576=648$$

$\endgroup$
  • $\begingroup$ Do you think OP wants to consider rotational overcounts? $\endgroup$ – K. Jiang Feb 20 '16 at 13:42
  • $\begingroup$ +1 for rechecking an earlier answer that had been wrong. $\endgroup$ – Oscar Lanzi Feb 21 '16 at 3:38
0
$\begingroup$

I get 648.

The women must sit in two pairs of adjacent seats, and if the pairs are separated there must be at least two intervening positions (for different husbands) in each direction.

This leads to three distinct arrangements for the women: 1-2-3-4, 1-2-5-6, 1-2-6-7. In the first case two men must sit next to their respecive wives in positions 5 and 10, while the other four men sit in any fashion that choose in positions 6-7-8-9. Thus 24×24 = 576 permutations. For the second arrangement of the women, all four husbands must sit next to their wives leaving only the two single men with any free choice. Thus 24×2 = 48 permutations.

The third female arrangement is tricky, in fact I had to edit my answer because I got it wrong the first time. If we count 24 permjtations for the women and two for the single men we seem to get 48. But because the women (and their husbands) are in a twofold rotationally symmetric arrangemet only half of these 48 are actually distinct. So we can really count only 24 additional permutations to go with the 576+48 from the other cases. Total: 648.

$\endgroup$

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.