# Cycles of equally spaced points on a circle

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

• What are your thoughts? What do you get for $n = 6$? – John Hughes Nov 11 '15 at 12:54
• Have you tried finding the numbers for say $n=1$ to $n=15$ and putting the sequence at o.e.i.s.? Maybe your sequence is there. – coffeemath Nov 11 '15 at 12:59
• @coffeemath: Using a naive approach I had trouble even for $n=9$, but fortunately the numbers up to $n=8$ were enough to uniquely identify the sequence. And the description was enough to know that it's the right one. – MvG Nov 12 '15 at 21:58
• The $+l$ in the left hand side of the second congruence seems wrong to me. Since you are talking about the equivalence of two sequneces, shouldn't these be $a$ and $b$ or similar? And how about an order reversal? Shouldn't you also include a case for $a_i\equiv b_{l-i\bmod n}+k\pmod n$ or similar? – MvG Nov 13 '15 at 0:57

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)

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