How many $n$-pointed stars are there?

Question

Say we have $n$ distinct points spaced evenly in a circle. Define a star as a connected graph with these points as vertices and with $n$ edges, no two having the same endpoints. We think of two stars as being equivalent if they differ only by a rotation (if they differ by a reflection I consider them as different objects). I'd like to know how many different stars there are on $n$ points.

For example there are only two 4-pointed stars: a square and a bowtie. There are four 5-pointed stars:

And I think there are twelve 6-pointed stars: (I'm not completely sure that I have exhausted the possibilities for 6 points).

A quick search of the online encyclopedia of integer sequences hasn't revealed any obvious candidates.

Another way to phrase the question: Let $\rho = (1 2 \ldots n)\in S_n$. Say that two permutations $\sigma, \tau\in S_n$ are equivalent if $\sigma = \rho^{-k}\tau\rho^k$ for some $k$. How many equivalence classes contain order $n$ permutations?

Answer 1

What we seek are: nontrivial cyclic permutations, with shifts and reversals counting as identical.

Without the shift requirement, there are $(N-1)!$ different cyclic permutations. Shifting allows us to reduce that by up to a factor of $2N$, though not every permutation will be so accommodating. For instance, while there are six different cyclic 4-permutations, two of them (0123 and 0321) appear as identical squares and four (0132, 0213, 0231, and 0312) appear as bowties. Technically there's a maximal 8-fold symmetry but, as shown, nothing gets us there on $N=4$. The smallest that that happens to is on $N=6$: they must be free of both rotation and reflection symmmetries, like your fourth and fifth drawings.

For relatively small $N$, we don't have to worry too terribly much about optimizations (they exist but many of them would also require pruning of the permutation tree before it reaches full length to be useful, which is complex), so we'll just write some code and see what happens.

The code is here; edit line 3 (N = 6) to see different sizes. https://ideone.com/5PSyOJ

Your diagram is missing two entries for $N=6$, shown here, ACEBDF and ABECFD. I find it interesting that they are not mirror images of each other!

For $N$ from $4$ through $10$, we get $2, 4, 14, 54, 332, 2246,$ and $18264$ distinct polygons. This is OEIS entry A000939, Number of inequivalent n-gons.

Answer 2

There are $6!=720$ cycles for $n=7$. Three patterns have 7-fold symmetry, and are covered by 2 cycles each - forwards and backwards. All the others have no symmetry and are covered by 14 cycles each - forwards, backwards and seven rotations. So there are $6/2+714/14=54$ patterns for $n=7$.
Composite $n$ are trickier of course.

Answer 3

Deriving the general formula for this sequence (and its reflection-insensitive analogue) is precisely the content of:

Golomb, S.W.; Welch, L.R., "On the enumeration of polygons", Amer. Math. Monthly, 67 (1960), 349-353.

The authors derive the result as a clever application of Burnside's Lemma, giving for the count of $n$-pointed stars $$ 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. , $$ where $$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 .$$ Here, $\phi$ is the Euler totient function.

As Dan Uznanski's answer has pointed out, this is OEIS A000939, Number of inequivalent n-gons.

Remark As Empy2's answer observes, the procedure for computing should be easier for prime $n$. Indeed, for odd primes $p$ the above formula simplifies to $$E(p) = \frac{1}{2 p} [(p - 1)^2 + (p - 1)!] .$$ It follows from the fact that $E(p)$ is an integer that $p \mid [(p - 1)^2 + (p - 1)!]$, and rearranging gives $$(p - 1)! \equiv -1 \pmod p ,$$ which recovers one direction of Wilson's Theorem.