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:


*

*$CR(n, 1) = 1$

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

*$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.
 A: 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.
A: 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$.
