6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Could you edit your post to include your workings? What have you thought of, in trying to approach the problem? Where are you stuck? The more context you can provide with the question, the better we are able to help you specifically. $\endgroup$
    – amWhy
    Sep 18, 2017 at 19:33
  • $\begingroup$ @amWhy, ok i wrote. $\endgroup$
    – duncan
    Sep 18, 2017 at 20:17
  • $\begingroup$ duncan: Thanks, that should help! $\endgroup$
    – amWhy
    Sep 18, 2017 at 22:18
  • 2
    $\begingroup$ Check out oeis.org/A094314 at the OEIS. Even though the description there seems more general, the numbers match your problem here. $\endgroup$ Sep 20, 2017 at 0:14
  • 1
    $\begingroup$ I found something interesting math.dartmouth.edu/~doyle/docs/menage/menage/menage.html $\endgroup$
    – duncan
    Sep 20, 2017 at 16:18

1 Answer 1

2
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .