In how many ways 5 couples can be seated around a circular table with some conditions attached?

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.

Tags:

Combinatorics

Related

Are there $f:\mathbb{R}^{+}\times\mathbb R^+\rightarrow\mathbb{R}^{+}$ associative and not conjugate to the addition? Direction of a Point in a Vector Field Why can't $\int x(x-3)^8\ dx$ be integrated by parts? Using roots of unity to factorize polynomials Are functions that sum to zero over vertices of similar polygons identically zero? Bijection between Dyck paths with $k$ peaks and $n+1-k$ peaks Is the space of maps which satisfy this vanishing condition finite-dimensional? To clarify my doubt over my wrong approach in combination question How many real roots does $x^4 - 4x^3 + 4x^2 - 10$ have? Why should we care about syntactic proofs if we can show semantically that statements are true? What references should I follow if I want to learn more about semantic entailment in multi-valued logics? The number of roots of a polynomial $p(x)=x^{12}+x^8+x^4+1$ in $\mathbb{F}_{11^2}$.

Recent Posts