5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I don't see it, they really should explain where they get that from. But yes, it does look like some sort of inclusion-exclusion. $\endgroup$ – Jorge Fernández Hidalgo Mar 14 '15 at 15:54
  • $\begingroup$ If you go up to index $n$ you need to calculate $(-1)!!$. How is that defined? Edit: I guess $(-1)!! = 1$, right? $\endgroup$ – Rolf Sievers Mar 14 '15 at 16:44
  • $\begingroup$ I think $\binom{2n-k}{k}$ is supposed to be the number of ways to pick $k$ pairs of adjacent people in a circle of $2n$ people, no two pairs overlapping. But there are two ways to do that for $2n=4$ and $k=2$, whereas the formula would only give 1. It doesn't seem to take into account the fact that the first and last people might be paired. $\endgroup$ – Andrew Woods Mar 14 '15 at 16:50
2
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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

$\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.