# Find the number of ways $z_n$ of seating $n$ couples around a rectangular table such that no one is allowed to sit next to his or her partner

Find the number of ways $$z_n$$ of seating $$n$$ couples around a rectangular table such that no one is allowed to sit next to his or her partner.figure $$(\text{I})$$.

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$$ $$\text{Figure (I)}$$ First we should find the number of ways that $$2n$$ people can sit around the table,we choose $$n$$ of $$2n$$ people to sit on one of the sides of the table in $$\binom{2n}{n}$$ ways,besides for the people sitting on each sides of the table there are $$n!$$ permutations,and so by the multiplicative law:$$\binom{2n}{n}\left(n!\right)^{2}=\left(2n\right)!$$

Denote by $$w_k$$ the number of seatings under which some specified set of $$k$$ couples (and possibly some other couples) end up sitting next to their partner:

$$z_n=\left|\bigcap_{i=1}^{n}\overline{A_i}\right|=\left(2n\right)!-\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{k=0}^{n}\left(-1\right)^{k}\binom{n}{k}w_{k}$$

Now it's left to determine a formula for $$w_k$$:

This is where I cannot continue,I thought that the formula maybe is :

$$w_k=\binom{2n}{2k}k!\cdot2^{k}\left(2n-2k\right)!$$

(Decide where the k couples go, and which couple goes where, and which partner takes which seat, and where the $$2n-2k$$ individuals go.)

However after some thought,I figured out that this is not true,since it may happen that one of the husbands/wives be left unpaired,so what is the strategy to solve the problem?

The number of ways of forming $$k$$ non-overlapping pairs of adjacent seats is $$\sum_{r=0}^k\binom{n-r}{r}\binom{n-(k-r)}{k-r}.$$ The two binomial coefficients come from the answer to this question applied with parameters $$n-1$$ and $$r$$ for the seats on the front side of the table and parameters $$n-1$$ and $$k-r$$ for the seats on the back side of the table. The reason for $$n-1$$ is that the leftmost chair in a pair can't be the rightmost seat in the row.

Using this result and the principle of inclusion-exclusion, the number of arrangements is $$\sum_{k=0}^n(-1)^k\frac{n!}{(n-k)!}2^k(2n-2k)!\sum_{r=0}^k\binom{n-r}{r}\binom{n-(k-r)}{k-r}.$$ In this expression, $$\frac{n!}{(n-k)!}$$ is the number of ways of assigning couples to the chosen pairs of seats, $$2^k$$ is the number of ways of assigning members of the couples to seats, and $$(2n-2k)!$$ is the number of ways of assigning the remaining individuals to seats.

For $$n=0$$, $$1$$, $$2$$, $$3, \ldots$$ the values of this expression are $$1,\ 2,\ 16,\ 336,\ 16512,\ 1428480,\ \ldots$$

• Can you please give me a proof of the first expression,it's totally new to me
– user771003
May 20, 2020 at 14:38
• The two binomial factors are just the answer to this earlier question applied with parameters $n-1$ and $r$ for the bottom side of the table and parameters $n-1$ and $k-r$ for the top side of the table. The reason for $n-1$ is that the leftmost chair in a pair can't be the rightmost seat in the row. May 20, 2020 at 14:46
• Thanks for your explanations.I think before permuting the remaining $2n-2nk$ individuals,we need to select them,since we choose $r$ vertices from on of the sides of the table,hence $n-2r$ vertices has left,and we need to choose $n-2r$ individuals from the $2n-2k$ people to sit there,this can be done in $\binom{2n-2k}{n-2r}$ ways,the other $n-2k+2r$ individuals should sit on the other side of the table,besides this unpaired people on the both sides have $\left(n-2r\right)!\left(n-2k+2r\right)!$ permutations,so I think the formula is ....:
– user771003
May 20, 2020 at 15:39
• $$\sum_{r=0}^{k}\binom{n-r}{r}\binom{n-(k-r)}{k-r}\binom{2n-2k}{n-2r}\left(n-2r\right)!\left(n-2k+2r\right)!$$ $$\left(2n-2k\right)!\sum_{r=0}^{k}\binom{n-r}{r}\binom{n-(k-r)}{k-r}$$ Which is what you said,I was just a little confusing about the process,it seems convincing to first select which people are going to sit on which sides of the table and then permuting them,instead of permuting them directly,both ways gives the same answer,however I think you already have done my process and then you typed the simplified form.
– user771003
May 20, 2020 at 15:39
• But permuting them without first selecting them does not seem correct (If I'm wrong please let me know).
– user771003
May 20, 2020 at 15:56