1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ I have failed to understand this answer. $\endgroup$ – Fimpellizieri May 16 '17 at 21:35
  • $\begingroup$ @Fimpellizieri at which part do you fail to understand? I can add more detail? $\endgroup$ – Sean English May 16 '17 at 22:00
  • $\begingroup$ 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. $\endgroup$ – Fimpellizieri May 16 '17 at 22:27
  • $\begingroup$ @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. $\endgroup$ – Sean English May 16 '17 at 22:35
  • $\begingroup$ 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. $\endgroup$ – Fimpellizieri May 16 '17 at 23:06

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.