2
$\begingroup$

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?

$\endgroup$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.