2
$\begingroup$

In how many ways 5 couples can be seated around a circular table such that men and women sit alternatively and no person sits adjacent to his or her spouse ?

Edit: The chairs are alike! I have gone through few answers to the question where 5 couples are arranged in such a way that they don't sit together using inclusion and exclusion principle but I am not getting my way around when men and women also have to sit alternatively!

$\endgroup$
  • $\begingroup$ Are only the persons distinguishable? Or also the chairs maybe? $\endgroup$ – drhab Aug 10 at 11:39
  • 1
    $\begingroup$ Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be put on hold. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ – José Carlos Santos Aug 10 at 11:42
  • 2
    $\begingroup$ Start by placing the men around the table in every other chair. Then you only have to worry about how to place the women. Inclusion-exclusion should work for that, as each woman has two forbidden positions out of the five possible positions. $\endgroup$ – saulspatz Aug 10 at 12:06
2
$\begingroup$

There are $4!$ ways to place the men in such a way that men and women will sit alternatively.

Place them and label the spots where the men have taken their seats clockwise with $a,b,c,d,e$.

Now we will take a look at the possible configurations for women.

Without further conditions there are $5!$ configurations for women.

Let $A$ denote the set of these configurations where the man that sits at $a$ has his wife next to him.

This similar for $B,C,D,E$ where the capitals correspond with labels $b,c,d,e$ respectively.

The answer to the question is then $4!\left|A^{\complement}\cap B^{\complement}\cap C^{\complement}\cap D^{\complement}\cap E^{\complement}\right|=4!\left(5!-\left|A\cup B\cup C\cup D\cup E\right|\right)$ so it remains to find $\left|A\cup B\cup C\cup D\cup E\right|$.

This can be done by means of inclusion/exclusion. Up to a certain level we can also make use of symmetry (e.g. notice that of course $\left|A\cap B\right|=\left|B\cap C\right|$) but here we must be careful.

At first hand we find that: $$\left|A\cup B\cup C\cup D\cup E\right|=5\left|A\right|-5\left|A\cap B\right|-5\left|A\cap C\right|+5\left|A\cap B\cap C\right|+5\left|A\cap B\cap D\right|-5\left|A\cap B\cap C\cap D\right|+\left|A\cap B\cap C\cap D\cap E\right|$$

Then checking the cases one by one we find:

  • $\left|A\right|=2\times4!=48$
  • $\left|A\cap B\right|=3\times3!=18$
  • $\left|A\cap C\right|=4\times3!=24$
  • $\left|A\cap B\cap C\right|=4\times2!=8$
  • $\left|A\cap B\cap D\right|=6\times2!=12$
  • $\left|A\cap B\cap C\cap D\right|=5\times1!=5$
  • $\left|A\cap B\cap C\cap D\cap E\right|=2\times0!=2$

So our final answer is: $$4!\left(5!-5\times48+5\times18+5\times24-5\times8-5\times12+5\times5-26\right)=24\times13=312$$


I hope that I did not make any mistakes. Check me on it.

$\endgroup$
  • $\begingroup$ Thank you ! That was quite helpful. :D $\endgroup$ – Xellosprime Aug 14 at 14:55
  • $\begingroup$ You are very welcome. $\endgroup$ – drhab Aug 15 at 6:23
  • $\begingroup$ I finally got around to checking your answer this morning. While searching for the problem, I found an incorrect answer on the website Quora. $\endgroup$ – N. F. Taussig Sep 19 at 10:15
  • 1
    $\begingroup$ The question on Quora is different because it lifts the condition on alternating seating. This here is the well known Ménage problem whereas the one on Quora is just a straightforward application of inclusion-exclusion. $\endgroup$ – N. Shales Sep 19 at 13:43
  • 1
    $\begingroup$ @N.Shales Thank you for spotting this. I deleted my answer on Quora. $\endgroup$ – drhab Sep 19 at 14:05
1
$\begingroup$

There are $P(5)=(5-1)!=4!$ circular permuations of the $5$ men.

Now consider the arrangement: $*M_1*M_2*M_3*M_4*M_5$.

There are $3$ arrangements of $W_1$: $$1) *M_1*M_2\color{red}{W_1}M_3*M_4*M_5\\ 2) *M_1*M_2*M_3\color{red}{W_1}M_4*M_5\\ 3) *M_1*M_2*M_3*M_4\color{red}{W_1}M_5\\$$ There are $3,2$ and $2$ arrangements of $W_2$, respectively: $$\begin{align} 1) \ \ \ \ \ &I) \color{blue}{W_2}M_1*M_2\color{red}{W_1}M_3*M_4*M_5\\ \ \ \ \ \ \ \ \ &II) *M_1*M_2\color{red}{W_1}M_3\color{blue}{W_2}M_4*M_5\\ \ \ \ \ \ \ &III)*M_1*M_2\color{red}{W_1}M_3*M_4\color{blue}{W_2}M_5\\ 2) \ \ \ \ \ &I)\color{blue}{W_2}M_1*M_2*M_3\color{red}{W_1}M_4*M_5\\ &II)*M_1*M_2*M_3\color{red}{W_1}M_4\color{blue}{W_2}M_5\\ 3) \ \ \ \ \ &I)\color{blue}{W_2}M_1*M_2*M_3*M_4\color{red}{W_1}M_5\\ &II)*M_1*M_2*M_3\color{blue}{W_2}M_4\color{red}{W_1}M_5\\ \end{align}$$ There are $1,3,2,1,2,1,3$ arrangements of the rest women, respectively (verification is left as an exercise).

Due to symmetry, the final number of arrangements of the $5$ pairs is $4!\cdot 13=312$.

$\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.