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.

$4$ married couples are to be seated on a circular table with $8$ identical seats. In how many ways can they be seated so that
(i) males and females sit alternately
and
(ii) no husband sits adjacent to his wife
There are so many cases that I get confused in between (Rather, I am starting to believe that writing down each case explicitly is easier than solving it using factorials). But then what if the question states $5$ couples instead of $4$. Can it be solved in general for $n$ couples too? Help.
$Note$- Conditions (i) and (ii) should hold simultaneously.

share|improve this question
1  
@Mathster: It used to be traditional to alternate men and women (assuming that there were equal numbers of each) and later the two genders would separate, thus widening the number of different people could talk to over the whole event. Not sitting husband and wife together is obvious, as they can talk to each other at home. –  Henry Mar 23 at 12:58
2  
This is the ménage problem and it is possible to give a general solution in terms of a recurrence, or a sum, or a closed form involving a modified Bessel function of the second kind. –  Henry Mar 23 at 13:07
1  
These are all the $12$ possible seating arrangements, where the couples are $(A, a), (B, b), (C, c), (D, d)$, and all arrangements have been rotated so that $A$ is in the first position: AbCaDcBd AbCdBaDc AbDaCdBc AbDcBaCd AcBaDbCd AcBdCaDb AcDaBdCb AcDbCaBd AdBaCbDc AdBcDaCb AdCaBcDb AdCbDaBc. If you don't actually want to treat rotations as equivalent, then there are $12 \times 8 = 96$ solutions, as the article on the ménage problem says. –  ShreevatsaR Mar 23 at 14:34

3 Answers 3

up vote 2 down vote accepted

For this particular problem there is an easy way to count (but right now I don't see how to generalise this to more than $4$ couples). One can first seat the women in $4$ alternating seats. Assuming you mean to identify rotationally symmetric arrangements this can be done in $3!=6$ ways: the first women serves as reference and here seat can be numbered 0, and seating the three other women is given by a bijection to the seats $2,4,6$. (If you also want to identify reflection symmetry, divide by $2$.)

Now to seat the men, there are two options for the husband of the lady in seat $0$, namely seats $3$ and $5$. But when this is done, the arrangement is fixed. Supposing he took seat $3$, then this seat is no longer available for the huband of the lady in seat $6$, who then must go to seat $1$; then the husband of the lady in seat $4$ must go to seat $7$, and the remaining husband to seat $5$. In case the first husband took seat $5$, the situation is similarly fixed, reasoning in the opposite direction. So in all there are $6\times 2=12$ solutions.

Added I finally found out that for $n$ couples the number is given (up to a factor $(n-1)!$ for seating the women first) by A000197 in OEIS. Presumably you can found useful things in the comments and formulas there.

share|improve this answer
    
Have you seen en.wikipedia.org/wiki/M%C3%A9nage_problem ? –  ShreevatsaR Mar 27 at 13:41
    
@ShreevatsaR: Yes, I've seen the link in the comment by Henry at the question since I made the addition to my question. I had not realised this was such an apparently well known problem. –  Marc van Leeuwen Mar 27 at 14:07

For part (i), we start with a male. There are $4$ ways to chose the first person. The person to his left is a female, so we choose one of the four females. Again, there are $4$ ways to do this. Now we have three males from which to choose. Do you see the logic? This problem is equivalent to the counting number of Hamiltonian Cycles in $K_{n, n}$.

For part (ii), start by choosing a starting person. There are $8$ ways to do this. There are $6 * 5$ ways to choose a person to the left ($p_{2}$) and a person to the right ($p_{3}$) of $p_{1}$, as we exclude $p_{1}$'s spouse. So now we have $6$ people left. Now how many ways can we seat someone to the left of $p_{2}$? Think along this logic.

Another good way to look at (ii) is as a derangement. We have four husbands and four wives. We consider the set $H = \{1, 2, 3, 4\}$ to represent husbands. In how many ways can we permute $H$ such that $H(i) \neq i$? There is an inclusion exclusion argument for this. Note the subfactorial approximation you may find by googling is just that- an approximation.

Edit: I did not realize both conditions had to hold.

This is still a bipartite Hamiltonian Circuit problem. Start by choosing a husband $h_{1}$. There are $4$ ways to do this. Then look at the wives set. We must have a wife on either side of the chosen husband that is different from this husband's spouse. Call these wives $w_{2}, w_{3}$. There are $\binom{3}{2}$ ways to accomplish this. We then look at a wife chosen, $w_{2}$. She has $2$ husbands to pick from other than her own. This new husband $h_{3}$ has two wives to choose from. Do you see the logic here? Can you continue from this point?

share|improve this answer
    
The conditions (i) and (ii) should hold simultaneously. –  Mridul Sachdeva Mar 23 at 5:35
    
Thank you for the clarification. I will edit my post. –  ml0105 Mar 23 at 5:49

I shall firstly assume numbered seats, and count ways in which at least 1 couple is together, at least 2 couples are together, etc and then apply inclusion-exclusion.

The items, in sequence, represent

a) Choose couples: 4c1, 4c2, 4c3, 4c4

b) Place them: 8/7 *7c1, 8/6 *6c2, 8/5 *5c3, 8/4 *4c4

[with 2 couples together, say, there are 2+4singles = 6 "blocks" available so the couples can be placed in 6c2 ways, multiplied by 8/6 because there are only 6 "blocks" against 8 positions]

c) Arrange them: 1!, 2!, 3!, 4!

d) Flip spouses: 2¹, 2², 2³, 2⁴

e) Permute rest: 6!, 4!, 2!, 0!

Applying inclusion-exclusion, number of ways =

8! - 4*8*1*2*6! + 6*20*2*4*4! -4*16*3!*8*2! +1*2*4!*16*1 = 11,904

Now we divide by 8 to take care of "identical seats" to get ans = 1488

You can now generalise this to take care of any number of couples !

edit

I erred by taking only condition (ii) into account, and solved instead another version of the ménage problem !

But re Marc's observation : is there a way to generalise beyond 4 for the correct problem ?

share|improve this answer
    
I think you're forgetting that men and women sit alternately: so you can't exactly treat a couple as a single entity, unless you know whether it's the woman or the man who comes earlier. –  ShreevatsaR Mar 23 at 12:56
    
That is accounted for by (c) "Flip spouses" –  true blue anil Mar 23 at 13:44
    
But you can't freely flip spouses, because the men and women have to sit alternately. –  ShreevatsaR Mar 23 at 13:53
    
Exhaustive enumeration shows that given a particular seating of the women, there are only two possible seatings of the men. So if you multiply that by $2 \times 4!$ ways to account for all possible ways of seating the women, and then divide by $8$ to account for rotational symmetry, you get the answer $12$ (as in Marc van Leeuwen's answer), rather than the huge number $1488$ in your answer. –  ShreevatsaR Mar 23 at 14:05
    
These are all the $12$ possible seating arrangements, where the couples are $(A, a), (B, b), (C, c), (D, d)$, and all arrangements have been rotated so that $A$ is in the first position: AbCaDcBd AbCdBaDc AbDaCdBc AbDcBaCd AcBaDbCd AcBdCaDb AcDaBdCb AcDbCaBd AdBaCbDc AdBcDaCb AdCaBcDb AdCbDaBc. –  ShreevatsaR Mar 23 at 14:33

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.