How to seat $n$ couples (husbands and wives) in a line so that each husband's neighbors can only be his wife or another gentleman? I.e. his neighbor cannot be another woman that's not his wife.
There is a classical similar problem: In how many ways can n couples (husband and wife) be arranged on a bench so no wife would sit next to her husband?
But it's a bit different. In this case the husband can only be sitting with either his wife or another gentleman. Can the inclusion-exclusion principle still be applied on this problem? I can't think of a way..
[edit] through programmatical iteration, I found that the solution is http://oeis.org/A096121. But there isn't a proof to it. It's not hard to show that the rook problem is equivalent to this problem — one column is the wives and the other column is the husbands. The sequence of the locations of the rook is how you arrange the husbands and wives.
But I wonder how do you prove the recurrence formula $a_{n+1} = n(n+1)(a_n + a_{n-1})$ ?
Another formula in OEIS was given as $a_n = 2 \cdot n! \cdot b_n$ where $b_{n+1} = n b_n + b_{n-1}$. $b_n$ is defined in http://oeis.org/A102038 This formula seems a bit more approachable. If we know the solution where the rook starts in one column, we multiply it by 2 so we get the solution where the rook in either column. $n!$ is just the permutation of all the cells in one column. We can interpret the $2 \cdot n!$ part but not sure about the rest!
Best Answer
(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.