¿De cuántas maneras para seleccionar $k$ vértices de una $n$-gon?

Question

Tengo un regular $n$-gon, de la que tengo para seleccionar $k$ vértices. Las selecciones deben ser rotacionalmente distintos; dos selecciones podría considerarse equivalente si uno es una rotación de los otros. Por ejemplo, si tengo un cuadrado, y quiero seleccionar 2 vértices, sólo hay 2 maneras posibles de hacer que de acuerdo a la restricción. Uno de ellos es "x - x", otra es "x x - -".

Si se denota la función de $CR(n,k)$, a continuación, estos son los casos triviales:

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

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

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

Estoy muy corto de ideas sobre cómo encontrar la recurrencia o cerrado fórmula de este problema, o si este problema tiene una forma cerrada / la recurrencia de la solución. Cualquier ayuda con un poco detallada de caminar a través de sería muy apreciada.

Answer 1

Como el OP parece interesado en la fijación de $k$ y dejando $n$ variar vamos a hacer un ejemplo para mostrar cómo podría funcionar esto.

Por el Polya Enumeración Teorema de lo que tenemos aquí es $$[z^k] Z(C_n)(1+z)$$ con $Z(C_n)$ el ciclo de índice de la cíclico grupo que es $$Z(C_n) = \frac{1}{n}\sum_{d|n} \varphi(d) a_d^{n/d}.$$

La cantidad deseada está dada por $$[z^k] Z(C_n)(1+z) = [z^k] \frac{1}{n}\sum_{d|n} \varphi(d) (1+z^d)^{n/d}.$$

Este es $$\frac{1}{n}\sum_{d|n, d|k} \varphi(d) [z^k] (1+z^d)^{n/d}$$ o $$\frac{1}{n}\sum_{d|n d|k} \varphi(d) {n/d \elegir k/d} = \frac{1}{n}\sum_{d|\gcd(n,k)} \varphi(d) {n/d \elegir k/d}.$$

Para $k=4$ a partir de a $n=1$ obtenemos la secuencia $$0, 0, 0, 1, 1, 3, 5, 10, 14, 22, 30, 43, 55, 73,\ldots$$ que nos señala OEIS A008610 donde nos encontramos con la confirmación.

Otro interesante es $k=6$ que los rendimientos de $$0, 0, 0, 0, 0, 1, 1, 4, 10, 22, 42, 80, 132, 217, 335, 504,\ldots$$ que apunta a OEIS A032191.

Una de Arce sesión con estos looks como este:

> con(numtheory): 
> P := (n,k) -> 1/n*añadir(phi(d)*binomial(n/d,k/d), d en divisores(mcd(n,k)));
Q := (n, k) -> add(numtheory:-phi(d) binomial(n/d, k/d),

 d en numtheory:-divisores(mcd(n, k)))/n

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

que por cierto es OEIS A032193.

Answer 2

Tomando el collar de la prueba de Fermat Poco Teorema como fuente de inspiración:

Para $n,k$ coprime, cada posible la selección ha $n$ rotaciones. Así

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

De lo contrario, dejando $d=\gcd(n,k)$, necesitamos tener en cuenta para esas elecciones donde hay una repetición de un patrón más pequeño que $n$, que va a ser todas las opciones posibles sobre el intervalo más corto con el número reducido de opciones (pero repite a través de todo el juego):

$$\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}$$

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

Y también tenga en cuenta que$CR(n,0)=1$$CR(n,n)=1$.