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!
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$.
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{.}$$