6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by selection must be rotationally invariant? $\endgroup$ – Anurag A May 28 '15 at 19:07
  • $\begingroup$ 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 $\endgroup$ – sarker306 May 28 '15 at 19:09
  • 2
    $\begingroup$ The following MSE meta link has a section on enumerating necklaces and bracelets. $\endgroup$ – Marko Riedel May 28 '15 at 19:51
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath May 28 '15 at 19:53
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Matan May 28 '15 at 20:40
  • $\begingroup$ I have been following your question for three hours. @Matan , felt really intrigued. $\endgroup$ – sarker306 May 28 '15 at 20:45
  • $\begingroup$ How wonderful to hear. Thanks! I update it on regular basis and work on it when I have time. Keep track of it :) @sarker306 $\endgroup$ – Matan May 28 '15 at 20:49
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Any explanation? Or any source where the derivation is explained? $\endgroup$ – sarker306 May 28 '15 at 19:25
  • $\begingroup$ 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. $\endgroup$ – Matan May 28 '15 at 19:26
  • $\begingroup$ @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. $\endgroup$ – Joffan May 28 '15 at 19:34
  • $\begingroup$ I get CR(6,3) = 25/6 when I apply your solution. $\endgroup$ – TokenToucan May 28 '15 at 20:17
  • $\begingroup$ 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. $\endgroup$ – sarker306 May 28 '15 at 20:25

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.