Ciclos de puntos igualmente espaciados en un círculo

Question

Toma $n$ puntos igualmente espaciados en un círculo. Conéctalos mediante un ciclo(circuito) con $n$ segmentos de línea. Dos ciclos se consideran equivalentes si son iguales cuando se giran o se reflejan. ¿Cuántos ciclos hay?

También puede verse como una secuencia de números enteros.

Tome una secuencia de números enteros $a_i(1 \leq i \leq n, \: 1 \leq a_i \leq n, \: a_i \neq a_j)$ . Dos secuencias $a_n, \: b_n$ se consideran equivalentes si existen algunos enteros $k, \: l$ tal que $a_i \equiv b_{i+l \bmod n}+k(\bmod n)$ o $a_{i+l} \equiv -b_{i+l \bmod n}+k(\bmod n)$

Answer 1

Esto es A000940 . Los números crecen con bastante rapidez, por lo que para muchas aplicaciones, buscar un número en esa lista podría ser suficiente. Citaré los términos hasta el 20-gon:

 3                1
 4                2
 5                4
 6               12
 7               39
 8              202
 9             1219
10             9468
11            83435
12           836017
13          9223092
14        111255228
15       1453132944
16      20433309147
17     307690667072
18    4940118795869
19   84241805734539
20 1520564059349452

Utilicé el siguiente código ingenuo de python para enumerar los primeros elementos e identificar la secuencia:

import itertools

def f(n):
    r = set()
    for p in itertools.permutations(range(n)):
        # cyclical shifts, correspond to a change in starting point:
        s = set(p[i:] + p[:i] for i in range(n))
        # include the reversed tuples, traverse path in opposite direction:
        s |= set([tuple(reversed(i)) for i in s])
        # modulo-add an integer to all elements, represents a rotation:
        s = set(tuple((i + k) % n for k in j) for i in range(n) for j in s)
        # also modulo-negate the elements, represents a reflection:
        s |= set(tuple(n - j - 1 for j in i) for i in s)
        s = frozenset(s)
        r.add(s)
    return r

for n in range(1, 10):
    print("{} {}".format(n, len(f(n))))

Hmmm. Ahora que lo pienso, ese código de Maple que se da ahí podría leerse como una fórmula:

$$f(n)= \frac1{4n^2}\left( \sum_{d\mid n}\left(\left(\varphi\left(\frac nd\right)\right)^2 \cdot d!\cdot\left(\frac nd\right)^d\right) +\begin{cases} 2^{\frac{n-1}2}\cdot n^2\cdot\left(\frac{n-1}2\right)! & \text{for $ n $ odd} \\ 2^{\frac{n}2}\cdot\frac{n(n+6)}4\cdot\left(\frac{n}2\right)! & \text{for $ n $ even} \end{cases} \right)$$