Find the number of $n$ husband's placing

Solution 1:

We have $2n$ adjacency conditions (one on each side of each wife), and we want exactly $r$ of them to be fulfilled. If there are $a_k$ ways to choose $k$ particular conditions and fulfil them, then exactly $r$ conditions can be fulfilled in

$$ \sum_{k=r}^n(-1)^{k-r}\binom kra_k $$

ways (see Generalised inclusion-exclusion principle). (The sum only goes up to $n$ because at most $n$ conditions can be fulfilled simultaneously.)

To figure out in how many ways we can fulfil $k$ adjacency conditions, denote by $L_i$ and $R_i$ the conditions that the $i$-th wife has her husband to her left and right, respectively (with $i$ increasing to the right). Then $L_i$ and $R_i$ preclude each other (a wife can't have her husband on both sides) and $L_i$ and $R_{i-1}$ preclude each other (two neighbouring wives can't both have their husband between them). If we arrange the conditions like this:

$$ L_1\quad L_2\quad L_3\quad\cdots\quad L_{n-1}\quad L_n\\ \;\;\;\;\;\;\;\;R_1\quad R_2\quad R_3\quad\cdots\quad R_{n-1}\quad R_n $$

then we can simultaneously fulfil two conditions as long as they don't immediately follow each other if we zig-zag between the two rows.

Thus, to choose $k$ conditions to fulfil, we need to choose $k$ out of the $2n$ conditions so that no two of them are adjacent in the cyclical zig-zag order, and then we can place the remaining $n-k$ husbands in the remaining $n-k$ chairs in $(n-k)!$ ways. Thus, $k$ conditions can be chosen and fulfilled in

$$ a_k=\left(\binom{2n-k+1}k-\binom{2n-k-1}{k-2}\right)(n-k)! $$

ways (see Proof - number of ways $k$ persons can be selected from $n$ persons sitting around a round table where no two adjacent persons can be selected .).

Thus, the desired count is

\begin{eqnarray*} &&\sum_{k=r}^n(-1)^{k-r}\binom kr\left(\binom{2n-k+1}k-\binom{2n-k-1}{k-2}\right)(n-k)! \\ &=& \frac{(-1)^r}{r!}\sum_{k=r}^n\frac{(-1)^k(2n-k)!(n-k)!}{(k-r)!(2n-2k+1)!}\left(2n-k+1-\frac{k(k-1)}{2n-k}\right) \\ &=& \frac{(-1)^r\cdot2n}{r!}\sum_{k=r}^n\frac{(-1)^k(2n-k-1)!(n-k)!}{(k-r)!(2n-2k)!}\;. \end{eqnarray*}

This agrees with the numbers in the OEIS entry. (By the way, note that that entry makes heteronormative assumptions about married couples; see Heteronormativity and binary gender assumptions on meta.)