Find the number of $n$ husband's placing

Question

Let there be $n$ pairs of husband-wife, and a round table with $2n$ chairs. Suppose that $n$ wives are already sat down, and between any two neighboring wives there is exactly one free chair (there is an alternation of empty chairs and occupied wives, $\dots,\text{chair}_n,\text{wife}_1,\text{chair}_1,\text{wife}_2, \text{chair}_2,\dots$). Find the number of $n$ husband's placing on the remaining chairs, where only $r$ husbands, $ 0 \leq r \leq n $, are directly near with their wives?

I think, about Inclusion–exclusion principle in this issue; we can called $\alpha_i$ - "$i$-th man sitting with his wife". Then look at $ \alpha_{i_1}\alpha_{i_2}\cdots\alpha_{i_r}$ - "$\geq r$ husbands sitting near their wives": $$ n! - |\bar\alpha_{i_1}\bar\alpha_{i_2}\cdots\bar\alpha_{i_r}| = |\alpha_{i_1}\cup\alpha_{i_2}\cup\dots\cup\alpha_{i_r}| = |\alpha_{i_1}| + |\alpha_{i_2}| +\dots + |\alpha_{i_r}| - |\alpha_{i_1}\alpha_{i_2}| - |\alpha_{i_1}\alpha_{i_3}| - \dots - |\alpha_{i_r}\alpha_{i_{r-1}}| + \dots + (-1)^{r}|\alpha_{i_1}\alpha_{i_2}\cdots\alpha_{i_r}|$$

If we know about $A_{\geq r}$, we can find $A_{=r} = A_{\geq r} - A_{\geq r+1}$. I stuck with calculation of it; or may be my $\alpha_i$ are not adequate for this problem.

Answer 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.)