Relaxed Menage Problem - sitting arrangement for couples

Question

The original problem is this:

How many ways are there to seat n couples around a circular table such that no couple sits next to each other?

For an answer, I looked at the solution here:

https://math.dartmouth.edu/~doyle/docs/menage/menage/menage.html

This seems to be what I am looking for, but there somehting I don't understand.

On "Solution to the relaxed ménage problem" section, I don't understand how it got the equation for $d_k$. Can someone explain it?

Answer 1

Arranging $k$ identical non-overlapping dominoes on a circle of $2n$ labelled vertices is equivalent to circularly "choosing" $k$ vertices with at least $1$ unchosen vertex between each neighbouring pair: A "chosen" vertex is the anticlockwise of each pair of vertices covered by a domino.

The number of such circular "choices" either includes vertex $1$ or not:

• If vertex $1$ is included then, since we can't choose a vertex either side of $1$, there are $2n-3$ remaining vertices from which to linearly choose $k-1$ non-adjacent vertices in $\binom{2n-3-(k-2)}{k-1}=\binom{2n-k-1}{k-1}$ ways.
• If vertex $1$ is not included then there are $2n-1$ remaining vertices from which to linearly choose $k$ non-adjacent vertices in $\binom{2n-1-(k-1)}{k}=\binom{2n-k}{k}$ ways.

Hence, the number of ways of circularly choosing $k$ non-adjacent vertices from $2n$ is the sum of these two exhaustive and mutually exclusive cases:

$$\begin{align}d_k&=\binom{2n-k-1}{k-1}+\binom{2n-k}{k}\\[1ex] &=\frac{k}{2n-k}\binom{2n-k}{k}+\binom{2n-k}{k}\\[1ex] &=\left(\frac{k}{2n-k}+1\right)\binom{2n-k}{k}\\[1ex] &=\frac{2n}{2n-k}\binom{2n-k}{k}\tag*{$\blacksquare$}\end{align}$$

as required.