How many ways to seat $n$ couples so that each husband's neighbors can only be his wife or another gentleman?

Solution 1:

(Edits: Missed a factorial term, added numerical values in example.)

Denote $a_n$ to be this number of arrangements of $n$ couples.

We will show we can produce a sum formula for $a_n$, namely $$ a_n = 2 \sum_{k=1}^{n} {n!}{(n-k)!}{n-k+\lceil\frac{k+1}{2}\rceil-1\choose n-k}{n-k+\lceil\frac{k}{2}\rceil-1\choose n-k}. $$ by refining it by the number of places where a husband/wife couple actually sit next to each other. With this sum expression for $a_n$ we can then algebraically demonstrate the recursion $a_{n+1}=n(n+1)(a_n+a_{n-1})$. (Note. This isn't a bijective approach as I liked, but it at least can be used to prove the recursion in principle.) Okay let's begin.

As noted by many others, a husband can only sit next to his wife but no other women, and vice versa. So we identify where this occurs. The number of such occurrence is at least 1, and at most $n$, for $n$ couples. So a typical arrangement is something like this: $$ (\text{some group of men})\fbox{MW}(\text{some group of women})\fbox{WM}\cdots\fbox{MW}\cdots $$

Let us call such pair $\fbox{MW}$ or $\fbox{WM}$ a lucky couple. Denote a space to be the group of positions between lucky couples.

So let us derive an expression for $a_n$. Note that we can exchange the wife with the corresponding husband, we know $a_n = 2\cdot\sum\cdots$, and so let us look at the cases where the sequence starts with a man.

By way of example, we will do $n=5$ to illustrate $a_5$ and use it to infer $a_n$: Assuming the arrangement starts with a man,

Case $\cdots \fbox{MW}\cdots$, exactly 1 lucky couple:

There are $(_5P_1)=5$ many ways to pick this lucky couple. Then of the remaining $4$ men, they need to be placed in one space (to the left of the lucky couple), and the remain $4$ women, they need to be placed in one space (to the right of the lucky couple). So we have $$ (_5P_1)(4!)(4!) = 2880 $$

Case $\cdots \fbox{MW}\cdots\fbox{WM}\cdots$, exactly 2 lucky couples:

There are $(_5P_2)=5\cdot 4$ many ways to pick these two lucky couples. Then of the remaining $3$ men, they need to be arranged and placed in two possible spaces, and the remaining $3$ women need to be arranged and placed in one possible space. So we have $$ (_5P_2)m(3,2)m(3,1) = 2880, $$ where $m(a,b)$ denotes the number of ways to arrange $a$ people into $b$ spaces. By stars and bars this is just $m(a,b) = {a+b-1\choose a}a!$.

Case $\cdots \fbox{MW}\cdots\fbox{WM}\cdots\fbox{MW}\cdots$, exactly 3 lucky couples:

With the same reasoning as before, we see this is $$ (_5P_3)m(2,2)m(2,2) = 2160 $$

Case $\cdots \fbox{MW}\cdots\fbox{WM}\cdots\fbox{MW}\cdots\fbox{WM}\cdots$, exactly 4 lucky couples:

With the same reasoning as before, we see this is $$ (_5P_4)m(1,3)m(1,2) = 720 $$

Case $\cdots \fbox{MW}\cdots\fbox{WM}\cdots\fbox{MW}\cdots\fbox{WM}\cdots\fbox{MW}\cdots$, exactly 5 lucky couples:

With the same reasoning as before, we see this is $$ (_5P_5)m(0,3)m(0,3) = 120 $$

Now observe well that if we start the arrangement with a man, having $k=1,2,3,4,5,\ldots$ lucky couples give $1,2,2,3,3,4,4,\ldots$ many spaces for the remaining men, while $1,1,2,3,3,4,4,\ldots$ many spaces for the remaining women. That is, we have $\lceil\frac{k+1}{2}\rceil$ spaces and $\lceil\frac{k}{2}\rceil$ spaces for the remaining men and women, respectively.

Putting everything together (and not forgetting a factor of 2 as we can exchange men and women), we have $$ a_5 = 2 \sum_{k=1}^{5}(_5P_k)m(n-k,\lceil\frac{k+1}{2}\rceil)m(n-k,\lceil\frac{k}{2}\rceil)\\ =2(2880+2880+2160+720+120 )=17520 \quad(\text{checks out!}) $$

So in general we have $$ a_n = 2 \sum_{k=1}^{n}(_nP_k)m(n-k,\lceil\frac{k+1}{2}\rceil)m(n-k,\lceil\frac{k}{2}\rceil) \\ \implies a_n = 2 \sum_{k=1}^{n} \frac{n!}{(n-k)!}{n-k+\lceil\frac{k+1}{2}\rceil-1\choose n-k}(n-k)!{n-k+\lceil\frac{k}{2}\rceil-1\choose n-k}(n-k)!\\ \implies a_n = 2 \sum_{k=1}^{n} {n!}{(n-k)!}{n-k+\lceil\frac{k+1}{2}\rceil-1\choose n-k}{n-k+\lceil\frac{k}{2}\rceil-1\choose n-k}. $$ (try the formula here with SageMath .)

By being careful with even and odd cases of $k$, you may be able to simplify $a_{n}+a_{n-1}$ to obtain the recursion.