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:
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?
$\endgroup$ 01 Answer
$\begingroup$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.
$\endgroup$
