1

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

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

1 Answers1

0

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 $$

Will Orrick
  • 18,220
  • Can you please give me a proof of the first expression,it's totally new to me –  May 20 '20 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. – Will Orrick May 20 '20 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 ....: –  May 20 '20 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.

     –  May 20 '20 at 15:39
  • But permuting them without first selecting them does not seem correct (If I'm wrong please let me know). –  May 20 '20 at 15:56
  • Well, $_nP_r=r!,_nC_r$, so it's all the same. In other words, you can either write $\frac{n!}{(n-r)}$ or you can write $\frac{n!}{(n-r)!r!}r!$. I think of $_nP_r=\frac{n!}{(n-r)!}$ as the number of ways of filling $r$ slots with items chosen from a set of size $n$,so I usually just go directly to that expression. – Will Orrick May 20 '20 at 16:27