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

• If $k = n/2$ then aren't there two ways to do it? E.g. (12),(34),(56) and (23),(45),(61) – Ned May 16 '17 at 19:58
• @Ned: oops, you're absolutely right. Edited! – gogurt May 16 '17 at 20:24

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.

• I have failed to understand this answer. – Fimpellizieri May 16 '17 at 21:35
• @Fimpellizieri at which part do you fail to understand? I can add more detail? – Sean English May 16 '17 at 22:00
• Ok, I understand it now. I agree it is correct. I would probably write it in a different way that makes it more evident how stars and bars are used here. – Fimpellizieri May 16 '17 at 22:27
• @Fimpellizieri Yeah, I was trying to avoid going into the details of choosing with repetition. Maybe if I have time later I will add more detail about how the choosing works. – Sean English May 16 '17 at 22:35
• I also think the cases could be simplified. Fix a vertex $v$, and there are three cases: (1) $v$ lies in on the left end of a chosen pair (of adjacent edges/vertices); (2) $v$ lies on the right end of a chosen pair; or (3) $v$ does not belong to a chosen pair. Cases (1) and (2) have the same number of configurations and account for the first expression in your answer (also explains why there's a $2$ multiplying the coefficient), while case (3) accounts for the second expression in your answer. – Fimpellizieri May 16 '17 at 23:06