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.