Cuántos $n$ -¿hay estrellas puntiagudas?

Question

Digamos que tenemos $n$ puntos distintos espaciados uniformemente en un círculo. Defina una estrella como un gráfico conectado con estos puntos como vértices y con $n$ aristas, no habiendo dos que tengan los mismos puntos finales. Consideramos que dos estrellas son equivalentes si sólo se diferencian por una rotación (si se diferencian por una reflexión las considero objetos diferentes). Me gustaría saber cuántas estrellas diferentes hay en $n$ puntos.

Por ejemplo, sólo hay dos estrellas de 4 puntas: un cuadrado y una pajarita. Hay cuatro estrellas de 5 puntas:

Y creo que hay doce estrellas de 6 puntas: (No estoy completamente seguro de haber agotado las posibilidades de 6 puntos).

Una rápida búsqueda en la enciclopedia online de secuencias de números enteros no ha revelado ningún candidato obvio.

Otra forma de formular la pregunta: Dejemos que $\rho = (1 2 \ldots n)\in S_n$ . Digamos que dos permutaciones $\sigma, \tau\in S_n$ son equivalentes si $\sigma = \rho^{-k}\tau\rho^k$ para algunos $k$ . ¿Cuántas clases de equivalencia contienen el orden $n$ ¿permutaciones?

Answer 1

Lo que buscamos son: permutaciones cíclicas no triviales, con desplazamientos e inversiones que cuentan como idénticas.

Sin el requisito del turno, hay $(N-1)!$ diferentes permutaciones cíclicas. El desplazamiento nos permite reducirlo hasta un factor de $2N$ aunque no todas las permutaciones serán tan complacientes. Por ejemplo, aunque hay seis permutaciones cíclicas diferentes de 4, dos de ellas ( 0123 y 0321 ) aparecen como cuadrados idénticos y cuatro ( 0132 , 0213 , 0231 y 0312 ) aparecen como pajaritas. Técnicamente hay una simetría máxima de 8 pliegues, pero, como se muestra, nada nos lleva allí en $N=4$ . El más pequeño al que le pasa eso está en $N=6$ : deben estar libres de simetrías de rotación y reflexión, como tus dibujos cuarto y quinto.

Para los relativamente pequeños $N$ En este caso, no tenemos que preocuparnos demasiado por las optimizaciones (existen, pero muchas de ellas también requerirían la poda del árbol de permutaciones antes de que alcance su longitud total para ser útiles, lo cual es complejo), así que simplemente escribiremos algo de código y veremos qué sucede.

El código está aquí; edite la línea 3 ( N = 6 ) para ver diferentes tamaños. https://ideone.com/5PSyOJ

A su diagrama le faltan dos entradas para $N=6$ , mostrados aquí, ACEBDF y ABECFD. Me parece interesante que no sean imágenes especulares entre sí.

Para $N$ de $4$ a través de $10$ obtenemos $2, 4, 14, 54, 332, 2246,$ y $18264$ polígonos distintos. Esto es Entrada OEIS A000939, Número de n-gons no equivalentes .

Answer 2

Derivar la fórmula general para esta secuencia (y su análogo insensible a la reflexión) es precisamente el contenido de:

Golomb, S.W.; Welch, L.R., " Sobre la enumeración de polígonos ", Amer. Math. Monthly , 67 (1960), 349-353.

Los autores derivan el resultado como una aplicación inteligente de Lemma de Burnside dando para el recuento de $n$ -estrellas puntiagudas $$ E(n) = \left\{ \begin{array}{ll} F(n) , & \textrm{$n$ odd}\\ F(n) + \displaystyle{\frac{1}{2 n^2} \cdot 2^{n / 2} {n \choose 2} {n \choose 2}!}, & \textrm{$n$ even} \end{array} \right. , $$ donde $$F(n) := \frac{1}{2 n^2} \sum_{d \mid n} \phi^2\left(\frac{n}{d}\right) d! \left(\frac{n}{d}\right)^d .$$ Aquí, $\phi$ es el Función totiente de Euler .

Como ha señalado la respuesta de Dan Uznanski, se trata de la OEIS A000939 , Número de n-gons no equivalentes .

Nota: Como observa la respuesta de Empy2, el procedimiento de cálculo debería ser más fácil para los primos $n$ . En efecto, para los primos Impares $p$ la fórmula anterior se simplifica a $$E(p) = \frac{1}{2 p} [(p - 1)^2 + (p - 1)!] .$$ Se deduce del hecho de que $E(p)$ es un número entero que $p \mid [(p - 1)^2 + (p - 1)!]$ y reordenando se obtiene $$(p - 1)! \equiv -1 \pmod p ,$$ que recupera una dirección de Teorema de Wilson .

Answer 3

Hay $6!=720$ ciclos para $n=7$ . Tres patrones tienen una simetría de 7 pliegues, y están cubiertos por 2 ciclos cada uno - hacia adelante y hacia atrás. Todos los demás no tienen simetría y están cubiertos por 14 ciclos cada uno: hacia adelante, hacia atrás y siete rotaciones. Por lo tanto, hay $6/2+714/14=54$ patrones para $n=7$ .
Compuesto $n$ son más difíciles, por supuesto.