Find the number of ways $m_n$ of seating $n$ couples around a rectangular table such that no one is allowed to sit next to\across from his or her partner,.figure $(\text{I})$.
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$
$$\text{Figure (I)}$$
Denote by $z_n$ the number of seating $n$ couples around a rectangular table such that no one is allowed to sit next to his or her partner,and denote by $w_k$ the number of seatings under which some specified set of $k$ couples (and possibly some other couples) end up sitting across from their partner,so the answer follows from here and here:
$$
\underbrace{\sum_{k=0}^n(-1)^k\binom{n}{k}k!2^k(2n-2k)!\sum_{r=0}^k\binom{n-r}{r}\binom{n-(k-r)}{k-r}}_{\large z_n}-\underbrace{\sum_{k=1}^n(-1)^k\binom{n}{k}\binom{n}{k}k!\cdot2^{k}\binom{2n-2k}{n-k}\left(n-k\right)!^{2}}_{\large w_k}
$$
Which simplifies to:
$$
m_n=\sum_{k=0}^n(-1)^k\binom{n}{k}k!2^k(2n-2k)!\left[\sum_{r=0}^k\binom{n-r}{r}\binom{n-(k-r)}{k-r}-\binom{n}{k}\right]+(2n)!$$
But I think the formula is not true,since for $n=2$,$m_2=8$ (I’ve checked this by hand),but the formula gives $24$,which is wrong,can someone explain why that happened?
Best Answer
It would make more sense to add the $w_k$ sum rather than subtracting it. (A factor $(-1)^k$ is already included in each term of that sum.) But the bigger issue is that you seem to be assuming that the two types of disallowed configuration are mutually exclusive, when, in fact, it is perfectly possible to have some couples seated next to each other and other couples seated across from each other in the same configuration. Correcting the minus-sign issue will result in the correct answer for $n=2$, since for that small size the two types of disallowed configuration never occur together. But you will start to run into problems with $n=3$ when they do.
One viable approach would be to structure the answer in the same way as was done in the two linked questions: $$ m_n=\sum_{k=0}^n(-1)^k\frac{n!}{(n-k)!}2^k(2n-2k)!\Phi_{n,k}, $$ where $\Phi_{n,k}$ is the number of ways of placing $k$ non-overlapping dominoes on (equivalently the number of $k$-matchings of) the ladder graph with $n$ rungs. The Wolfram MathWorld article in the link gives a recurrence for the matching polynomials of ladder graphs, from which the coefficients $\Phi_{n,k}$ can be extracted. The recurrence is $$ \mu_n(x)=(x^2-2)\mu_{n-1}(x)-x^2\mu_{n-2}(x)+\mu_{n-3}(x), $$ with initial conditions $\mu_0(x)=1$, $\mu_1(x)=x^2-1$, and $\mu_2(x)=x^4-4x^2+2$. To obtain $\Phi_{n,k}$ from $\mu_n(x)$, extract the coefficient of $x^{2(n-k)}$ and multiply by $(-1)^k$.
We can do a few checks. For $n=2$, we have $\Phi_{2,0}=1$, $\Phi_{2,1}=4$, and $\Phi_{2,2}=2$. Using these in the expression above gives $$ \begin{aligned} m_2&=1\cdot1\cdot24\cdot1-2\cdot2\cdot2\cdot4+2\cdot4\cdot1\cdot2\\ &=24-32+16\\ &=8. \end{aligned} $$ For $n=3$ the recurrence gives $\mu_3(x)=x^6-7x^4+11x^2-3$, from which we conclude $\Phi_{3,0}=1$, $\Phi_{3,1}=7$, $\Phi_{3,2}=11$, and $\Phi_{3,3}=3$. Using these in the expression above, we find $$ \begin{aligned} m_3&=1\cdot1\cdot720\cdot1-3\cdot2\cdot24\cdot7+6\cdot4\cdot2\cdot11-6\cdot8\cdot1\cdot3\\ &=720-1008+528-144\\ &=96. \end{aligned} $$ This makes sense since for $n=3$ the members of each couple must sit on opposite sides of the table, which can be accomplished in $2^3$ ways. Then there are $3!$ ways to seat the people sitting on the front side of the table, and $D_3=2$ ways to seat the people sitting on the back side. Multiplying gives $2^3\cdot3!\cdot2=96.$
Added: Just to spell out the argument that I glossed over above as being done "in the same way as ... in the two linked questions:"
Let $E$ be the set of all pairs of seats that are either adjacent or across from each other. Let $e\in E$ and let $A_e$ be the set of seating arrangements in which the seats of $e$ are filled by a couple. Then the set of "bad" seating arrangements is $$ \bigcup_{e\in E}A_e. $$ To make an inclusion-exclusion argument run, we let $S\subseteq E$ and define $$ A_S=\bigcap_{e\in S}A_e. $$ Observe that $A_S$ is non-empty only when the seat pairs in $S$ are pairwise non-overlapping. In those cases where $A_S$ is non-empty, we have $$ |A_S|=\frac{n!}{(n-k)!}2^k(2n-2k)!, $$ where $|S|=k$. The factors in this expression are explained as follows: there are $\frac{n!}{(n-k)!}=\binom{n}{k}k!$ ways to assign couples to the seat pairs in $S$, $2^k$ ways to seat the chosen couples within their assigned seat pairs, and $(2n-2k)!$ ways to seat the remaining individuals.
We are now set up to use inclusion-exclusion, and we get $$ \begin{aligned} m_n&=\sum_{S\subseteq E}(-1)^{|S|}|A_S|\\ &=\sum_{k=0}^n\sideset{}{'}\sum_{|S|=k}(-1)^k \frac{n!}{(n-k)!}2^k(2n-2k)!, \end{aligned} $$ where the prime on the summation symbol in the second line indicates that the sum is restricted to subsets whose members are pairwise disjoint pairs of seats. The summand does not depend on the particular subset $S$, but only on its cardinality $k$, which leads to the expression in my original answer.