Number of ways to pick $k$ pairs of adjacent edges from regular $n$-gon This might be a duplicate (sorry), but I can't seem to figure out a neat closed form for this.
Question: Suppose I have a regular $n$-gon and I want to pick exactly $k$ pairs of adjacent edges from it, where $k < [n/2]$. How many different ways are there to do this?
Obviously, if $k = n/2$ and $n$ is even, then there are only 2 ways to do this. But if $k < n/2$ then it starts to get complicated. It starts to depend on the distance between pairs.
For example, if $n=6$ and $k=2$, then the pairs could themselves be adjacent (i.e. make up a path of length 4) and there are 6 different combinations of possible 4-paths. But the pairs could also be opposite each other (i.e. the pairs have an edge between them on either side). Then there are also 3 ways to arrange those for a total of 6.
 A: Instead of thinking of this as choosing pairs of edges, we can choose vertices that are all at distance at least two from each other. We will have $k$ points, and we can think of each of these points as also forbidding their clockwise neighbors, so this accounts for $2k$ points. We then just need to choose how to squeeze the rest of the points in between these.
We need two cases. Let the vertices be labelled $1,\dots,n$. If $1$ or $n$ is chosen, then we need to choose how to distribute $n-2k$ vertices into $k$ pockets($k-1$ pockets between each chosen vertex and one pocket either before the first chosen vertex or after the last chosen vertex.) This contributes
$$2\cdot MC(k,n-2k)$$
ways, where $MC(a,b)$ is the number of ways to choose $b$ things from $a$ with repetition.
If neither $1$ nor $n$ is chosen, then we have $k+1$ forbidden vertices since there must be a gap of at least two between the first and last chosen vertices, and we have $k+1$ pockets(one before the first chosen vertex, one after the last vertex, and one in between each pair of chosen vertices), so this contributes
$$MC(k+1,n-2k-1)$$
ways.
Since $MC(a,b)=\binom{a+b-1}{b}$, we get a total of
$$2\binom{n-k-1}{n-2k}+\binom{n-k-1}{n-2k-1}$$
ways.
