1

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})$.

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$enter image description here $$\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?

1 Answers1

0

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.

Will Orrick
  • 18,220
  • You are right,I think my formula should be $$\sum_{k=0}^{n}\left(-1\right)^{k}\binom{n}{k}w_{k}$$ Where $w_k$ in the number of seating of $n$ couples under which $k$ couples end up sitting across from their partner (and there does exist any couples sitting next to their partner),on the other hand $w_k$ is :$$\binom{n}{k}k!2^kz_{2n-2k}$$ (Decide where the $k$ couples go, and which couple goes where, and which partner takes which seat) ,where $z_{2n-2k}$ is the number of ways of seating $n-k$ couples under which no one is allowed to sit next to his or her partner. –  May 21 '20 at 06:05
  • I don't think that is going to work. You can't use the multiplication principle (multiplying $\binom{n}{k}k!2^k$ by $z_{2n-2k}$) since $z_k$ isn't well-defined. Depending on how you sat the $k$ couples, the number of ways of seating the remaining $n-k$ couples with no one next to his or her partner will differ. For example, if $n=4$ and $k=2$ then if I seat someone in seat $1$ with her/his partner across, and someone else in seat $3$ with her/his partner across, then all $4!$ ways of seating the remaining people in seats $2$ and $4$ and the seats across are allowed. But if I seat the... – Will Orrick May 21 '20 at 12:46
  • ...first two couples in seats $1$ and $4$ and the seats across, then I will be more restricted in what I can do with seats $2$ and $3$, so not all $4!$ permutations are allowed. – Will Orrick May 21 '20 at 12:47
  • It seems to me that the issue with your proposed solution to this problem is very similar to the issue with the inclusion-exclusion argument that you were trying to make here. In both problems you have two kinds of constraints and in both you are adopting the strategy of subtracting the configurations that violate one of the constraints, and then separately subtracting the configurations that violate the other constraint. This leaves you having to make some... – Will Orrick May 21 '20 at 17:12
  • ...kind of adjustment, like adding back the configurations that violate both constraints. It seems to me that it is simpler in both problems to deal with configurations that violate either constraint than it would be to deal with configurations that violate both constraints (or configurations that violate one constraint but not the other). In other words, it seems more strategic to use "or" than to use "and". – Will Orrick May 21 '20 at 17:14
  • I don't get why we have $$ \sum_{k=0}^n(-1)^k\frac{n!}{(n-k)!}2^k(2n-2k)! $$,besides seeing these new articles like the two you've mentioned disappoints me,since I'm totally new to these questions,my combinatorics is awful and I even don't know where to start ,the two links you've mentioned seems advanced and it's like I should skip this question (however neither of these questions are homework questions and no one is going to ask me about them,because of my interest I'm following the questions),anyway thank you so much for your consecutive comments/helps –  May 21 '20 at 17:23
  • I have added something to the post to explain exactly how the inclusion-exclusion argument is structured and where the factors in the summand come from. If the graph theory language is troubling you, don't hesitate to ask, and I'll try to explain further. I noticed when reading the Bogart and Doyle paper mentioned in the comments here that this problem is one of the exercises they pose at... – Will Orrick May 22 '20 at 04:07
  • ...the end of the paper. Is that where you found the problem? I'm somewhat surprised to see it there, since it seems substantially harder than the original ménage problem. It's possible I'm missing something, and there's a simpler solution to be found. I hope you don't get discouraged. There's always more to learn, even after spending many years studying these things. – Will Orrick May 22 '20 at 04:40
  • You are right,the first time I tried to solve the problem,I wonder why ménage problem is famous to be unsolved for years,however the other problem seems to be more difficult. –  May 22 '20 at 06:52