1
$\begingroup$

I was reading about relaxed ménage problem on this page:

The relaxed ménage problem asks for the number of $m_n$ ways of seating couples around a circular table, so that no one sits next to his or her partner. This is nearly the same as the ménage problem, only now we have relaxed the requirement that men and women alternate.

To determine $m_n$ , we begin with the set $S$ of all $\left(2n\right)!$ ways of seating the individuals around the table, and use inclusion-exclusion on the set of couples who end up sitting together. Let us call the elements of $S$ seatings, and let us denote by $w_k$ the number of seatings under which some specified set of $k$ couples (and possibly some other couples) end up sitting together. Clearly $w_k$, does not depend on the particular set of $k$ couples we choose, and so, by the principle of inclusion and exclusion, we have:

$$m_{n}=\sum_{k=0}^{n}\left(-1\right)^{k}\binom{n}{k}w_{k}$$


I don't know how the principle of inclusion and exclusion has been used here,so can someone please derive the formula and explain where does it come from?

$\endgroup$
2
  • $\begingroup$ The formula is just a rewriting of inclusion-exclusion principle, since there are $\binom nk $ ways to choose k couples out of $n $ and $w_k $ obviously does not depend on a particular choice. $\endgroup$ – user May 10 '20 at 8:13
  • $\begingroup$ Well the "rewriting of inclusion-exclusion principle" is what I don't get $\endgroup$ – user771003 May 10 '20 at 9:12
0
$\begingroup$

The general information about inclusion-exclusion principle can be found here. Below I will reproduce the most essential points important for understanding the particular problem.

In general the inclusion-exclusion principle states that for finite sets $A_1,\dots, A_n$, one has the identity: $$\left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| + \sum_{1 \leqslant i < j < k \leqslant n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.$$

In the applications it is common to see the principle expressed in its complementary form. That is, letting $S$ be a finite universal set containing all of the $A_i$ and letting $\bar A_{i}$ denote the complement of $A_i$ in $S$:

$$\left|\bigcap_{i=1}^n \bar{A_i}\right| = \left|S\setminus\bigcup_{i=1}^n A_i \right| =|S| - \sum_{i=1}^n |A_i| + \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| - \cdots + (-1)^n |A_1\cap\cdots\cap A_n|.\tag1$$

If the size, $w_k$, of the intersection sets appearing in the formula (1) depends only on the number of sets, $k$, in the intersections (i.e. $\forall i:\, |A_i|=w_1,\; \forall i<j:\, |A_i\cap A_j|\equiv w_2$, and so on), the expression can be simplified to: $$ \left|\bigcap_{i=1}^n \bar{A_i}\right| =\sum_{k=0}^n (-1)^{k}\binom nk w_k. $$

This is exactly the case in the considered problem, with $A_i$ being the set of all permutations with $i$-th couple sitting together.

$\endgroup$
11
  • $\begingroup$ Why can't we choose $k$ couples of $n$ wo end up sitting together and then permute the other couples? In my opinion we should subtract the permutations where at least $1$ couple end up sitting together from the whole permutations which is $\left(2n\right)!$,and denote $A_{i_1}$ to be the set of all permutations such that one couple end up sitting together,and denote $A_{i_1} \cap A_{i_2}$ to be the set of all permutations such that tow couples end up sitting together,and so on.This kind of computation is like what we do to determine the number of derangements on a set $[n]$. $\endgroup$ – user771003 May 12 '20 at 13:46
  • $\begingroup$ Here one performs essentially the same procedure. In the derangement problem $w_k= (n-k)!$, in the considered problem it will be different. $\endgroup$ – user May 12 '20 at 13:56
  • $\begingroup$ Why cannot we say : choose $k$ couples out if $n$ end up sitting together and then permute the others in $w_k=\left(2n-2k\right)!$ ways? $\endgroup$ – user771003 May 12 '20 at 14:21
  • $\begingroup$ The computation of the particular $w_k$ is already next question. Short answer: for the considered problem it is incorrect. This however has nothing to do with the inclusion-exclusion principle. $\endgroup$ – user May 12 '20 at 14:28
  • $\begingroup$ Thanks for the answer,but can you tell me why is not that correct? $\endgroup$ – user771003 May 12 '20 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy