The following is problem 19 in Chapter 2 from Richard Stanley's Enumerative Combinatorics, vol. 1 (2nd ed.):

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

According to Stanley, the solution is $\displaystyle \sum_{n=o}^k (-1)^n\frac{2k}{2k-n}\binom{2k-n}{n}(2k-2n-1)!!$, where $(2m-1)!!=1\cdot 3 \cdot 5 \cdots (2m-1)$.

I know that the number of ways to form $k-n$ pairs from a group of $2k-2n$ people is $(2k-2n-1)!!=1\cdot 3\cdot 5\cdots (2k-2n-1)$. Let $f(2k-2n)$ be the number of ways to form $k-n$ pairs from a group of $2k-2n$ people. We choose a person to pick a partner for. This person has $2k-2n-1$ possible partners they can be paired up with. Now there remain $2k-2n-2$ people who have yet to be paired up. We obtain the recursion $$f(2k-2n)=(2k-2n-1)f(2k-2n-2).$$ It follows inductively that $f(2k-2n)=(2k-2n-1)!!$.

I know there is an inclusion-exclusion argument lurking here. I want to set up the solution to this problem using inclusion-exclusion, but I cannot understand what $\binom{2k-n}{n}$ is counting. Any help is greatly appreciated!! Thank you.


The inclusion-exclusion is around the number of pairs of adjacent people.
How many ways are there to pick $n$ pairs of adjacent people? Either $2k$ and $1$ are a pair, and then pick $n-1$ pairs from a row of $2k-2$ people, or they aren't, and you want $n$ pairs from a row of $2k$ people. I did this to deal with the circular symmetry of the problem.
Using stars and bars, there are $2k-2n$ people not among the $n$ pairs, and $2k-2n+1$ gaps to put the $n$ pairs. Remember each pair is a pair of adjacent people.


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.