number of pairs formed from $2n$ people sitting in a circle

Question

I am trying to understand the solution to the following problem:

Suppose that $2n$ persons are sitting in a circle. In how many ways can they form $n$ pairs if no two adjacent persons can form a pair. Express your answer as a finite sum.

It turns out that the solution is $\displaystyle \sum_{k=0}^n (-1)^k\binom{2n-k}{k}(2n-2k-1)!!$, where $(2m-1)!!=1\cdot 3\cdot 5\cdots (2m-1)$.

Clearly there is some inclusion-exclusion argument going on here. The first term of the sum (when $k=0$) is $\binom{2n}{0}(2n-1)!!=(1\cdot 3\cdots (2n-1))$. This is the number of $n$ pairs we can form with $2n$ people, since the first person has $2n-1$ choices, the second person has $2m-3$ choices, etc. I cannot tell what $\binom{2n-k}{k}$ is counting.

Any help is greatly appreciated!

Answer 1

I think the binomial term, representing the number of ways to pick $k$ pairs of adjacent people in a circle of $2n$ people, should in general $(k>0)$ be $$\left(\binom{2n-k}{k}+\binom{2n-k-1}{k-1}\right)$$

Model the circle of people with a necklace of black and white beads, with the arbitrarily chosen "first" person just clockwise of the clasp. Let's say that each of the $k$ black beads represents the first person (encountered moving clockwise) of an adjacent pair. Then, to make sure that no black beads are next to each other, we glue a white bead to the clockwise side of each black bead.

There are now $2n-k$ moving parts, of which $k$ are pairs of beads.

• If the first and last people in the circle are not part of a pair, there are $\binom{2n-k}{k}$ ways to place the pairs on the necklace.

• If the first and last people in the circle are in a pair, there are $(2n-2)-(k-1)$ or $2n-k-1$ other moving parts, of which $k-1$ are pairs.

For the case $k=0$ the formula above gives $\binom{2n}0+\binom{2n-1}{-1}=1+0=1,$ and for $k=n$ it gives $2$.

Answer 2

I side with Andrew Woods on this question. The correct coefficient to use is $$P(n,k) = \left(\binom{2n-k}{k}+\binom{2n-k-1}{k-1}\right)\text{,}$$ the number of ways to distribute $k$ non-overlapping pairs in a circle of $2n$ items.

$$\text{Andrew}(n) = \sum_{k=0}^{n} (-1)^k \left(\binom{2n-k}{k}+\binom{2n-k-1}{k-1}\right)(2n-2k-1)!!$$

This does not give the same result as your formula. For example see $n=3$ where $4$ seatings are possible. Andrew's formula correctly computes this but yours returns $5$. Your formula is still close though: $$\text{Andrew}(n) = \text{Sam}(n) - \text{Sam(n-1)}$$

I didn't check that formally but numerically it holds: https://gist.github.com/roSievers/051dc9c7a736e3d959e7

Here is another way reason about $P(n,k)$:

First we need to remember that there are $\binom{n+k}{k}$ ways to split a string of lenght $n$ at $k$ position. (splitting twice at the same position is allowed) To count pair distributions, fix one “index person” consider two cases:

Case 1: The index person is not themself part of a pair and $2k$ persons get paired up. Then split the remaining $2n-2k-1$ people at $k$ positions and place a pairs at all the places you cut. $$\binom{2n-2k-1+k}{k} = \binom{2n-k-1}{k}$$

Case 2: The index person is either the left or right member of a pair. I.e. this case appears twice. Another $2k-2$ people are in other pairs. The remaining $2n-2k$ people need to be split at $k-1$ positions to insert pairs. $$2\cdot \binom{2n-2k+k}{k-1} = 2 \cdot \binom{2n-k}{k-1}$$

Adding those cases gives you $$P(n,k) = \binom{2n-k-1}{k} + 2 \cdot \binom{2n-k}{k-1} = \binom{2n-k}{k} + \cdot \binom{2n-k}{k-1}\text{.}$$