Cycles of equally spaced points on a circle

Question

Take $n$ equally spaced points on a circle. Connect them by a cycle(circuit) with $n$ line segments. Two cycles are considered equivalent if same when rotated or reflected. How many cycles are there?

It can also be viewed as integer sequence.

Take an integer sequence $a_i(1 \leq i \leq n, \: 1 \leq a_i \leq n, \: a_i \neq a_j)$. Two sequences $a_n, \: b_n$ are considered equivalent if there exists some integers $k, \: l$ such that $a_i \equiv b_{i+l \bmod n}+k(\bmod n)$ or $a_{i+l} \equiv -b_{i+l \bmod n}+k(\bmod n)$

Answer 1

This is A000940. The numbers grow fairly quickly, so for many applications, looking up a number in that list might be enough. I'll quote the terms up to the 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

I used the following naive python code to enumerate the first few items and identify the sequence:

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. Come to think of it, that Maple code given there could indeed be read as a formula:

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