# How many ways to select $k$ vertices of an $n$-gon?

I have a regular $n$-gon, of which I have to select $k$ vertices. The selections must be rotationally distinct; two selections would be considered equivalent if one is a rotation of the other. For example, if I have a square, and I want to select 2 vertices, there are only 2 possible ways to do that according to the constraint. One is "x - x -", another is "x x - -".

If we denote the function by $CR(n,k)$, then these are the trivial cases:

1. $CR(n, 1) = 1$

2. $CR(n, 2) = \lfloor\frac{n}{2}\rfloor$

3. $CR(n, k) = CR(n, n - k)$

I am quite short of ideas on how to find the recurrence or closed formula of this problem, or if this problem has any closed form / recurrence solution at all. Any help with a bit detailed walk through would be much appreciated.

• What do you mean by selection must be rotationally invariant? – Anurag A May 28 '15 at 19:07
• Supposing, I have a 4-gon and I have to select 2 vertices. Hence, these two selections are the same. x-x-, -x-x. These selections are the same, x--x, xx--, -xx-, --xx – sarker306 May 28 '15 at 19:09
• The following MSE meta link has a section on enumerating necklaces and bracelets. – Marko Riedel May 28 '15 at 19:51
• One way to think about this (perhaps the best way) is the group action of cyclic rotations on the subsets of vertices. Rotations preserve the number of vertices in a subset (obviously), so the counting comes down to counting orbits of the $k$-subsets of $n$-vertices under those rotations. – hardmath May 28 '15 at 19:53

As the OP seems interested in fixing $k$ and letting $n$ vary we will do an example to show how this might work.

By the Polya Enumeration Theorem what we have here is $$[z^k] Z(C_n)(1+z)$$ with $Z(C_n)$ the cycle index of the cyclic group which is $$Z(C_n) = \frac{1}{n}\sum_{d|n} \varphi(d) a_d^{n/d}.$$

The desired quantity is thus given by $$[z^k] Z(C_n)(1+z) = [z^k] \frac{1}{n}\sum_{d|n} \varphi(d) (1+z^d)^{n/d}.$$

This is $$\frac{1}{n}\sum_{d|n, d|k} \varphi(d) [z^k] (1+z^d)^{n/d}$$ or $$\frac{1}{n}\sum_{d|n, d|k} \varphi(d) {n/d \choose k/d} = \frac{1}{n}\sum_{d|\gcd(n,k)} \varphi(d) {n/d \choose k/d}.$$

For $k=4$ starting at $n=1$ we obtain the sequence $$0, 0, 0, 1, 1, 3, 5, 10, 14, 22, 30, 43, 55, 73,\ldots$$ which points us to OEIS A008610 where we find confirmation.

Another interesting one is $k=6$ which yields $$0, 0, 0, 0, 0, 1, 1, 4, 10, 22, 42, 80, 132, 217, 335, 504,\ldots$$ which points to OEIS A032191.

A Maple session with these looks like this:

> with(numtheory):
> Q := (n,k) -> 1/n*add(phi(d)*binomial(n/d,k/d), d in divisors(gcd(n,k)));
Q := (n, k) -> add(numtheory:-phi(d) binomial(n/d, k/d),

d  in  numtheory:-divisors(gcd(n, k)))/n

> seq(Q(n,8), n=1..18);
0, 0, 0, 0, 0, 0, 0, 1, 1, 5, 15, 43, 99, 217, 429, 810, 1430, 2438


which incidentally is OEIS A032193.

• It'll be a sin by my side not to refer you to my similiar question here: math.stackexchange.com/questions/1294224/… . Perhaps you'll be able to help :) I apologize, OP! Really am! – Matan May 28 '15 at 20:40
• I have been following your question for three hours. @Matan , felt really intrigued. – sarker306 May 28 '15 at 20:45
• How wonderful to hear. Thanks! I update it on regular basis and work on it when I have time. Keep track of it :) @sarker306 – Matan May 28 '15 at 20:49

Taking the necklace proof for Fermat's Little Theorem as inspiration:

For $n,k$ coprime, every possible selection has $n$ rotations. So

$$CR(n,k) = \frac 1n{n \choose k}$$

Otherwise letting $d=\gcd(n,k)$, we need to account for those choices where there is a repeat pattern smaller than $n$, which will be all possible choices over the shorter interval with the reduced number of choices (but repeated through the entire set):

\begin{align} CR(n,k) &= \frac 1n\left[{n \choose k} - {n/d \choose k/d }\right] + CR\left(\frac nd, \frac kd \right) \\ &=\frac 1n\left[{n \choose k} - {n/d \choose k/d }\right] + \frac 1d {n/d \choose k/d } \end{align}

since $\gcd(\frac nd, \frac kd)=1$

And also note that $CR(n,0)=1$ and $CR(n,n)=1$.

• Any explanation? Or any source where the derivation is explained? – sarker306 May 28 '15 at 19:25
• Joffan, if you could please refer here math.stackexchange.com/questions/1294224/… for a related problem I asked I will be grateful. Perhaps you'll be able to help. – Matan May 28 '15 at 19:26
• @sarker306 If you review the necklace proof of Fermat's Little theorem I think you'll understand where this comes from. If I have time I'll add to it. – Joffan May 28 '15 at 19:34
• I get CR(6,3) = 25/6 when I apply your solution. – TokenToucan May 28 '15 at 20:17
• CR(n, 2) has its correct value when n is odd, not even. But really thanks for bringing in this gcd issue, it seems to be a right step to the right direction, I didn't suspect it before. I'll think it through the night. – sarker306 May 28 '15 at 20:25