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: 5-pointed stars

And I think there are twelve 6-pointed stars: 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?

up vote 6 down vote accepted

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!

Two polygons: ACEBDF and ABECFD

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.

  • Thanks for going above and beyond! Do you mind explaining the cycle function in your code? – vdbeek Nov 7 at 0:06
  • 1
    So, cycle works like this: it takes a permutation (which at this point is lacking the default 0) and an index, and rotates the whole thing around so that we get another permutation with the original index as the new permutation start. So if I have p=[2,4,1,3,5] and i=2, it plops a 0 on the end, then subtracts p[2]=1 from everything (now we've got [1,3,0,2,4,-1]), then mods those by 6 ([1,3,0,2,4,5]), then cycles it around so the 0 is at the beginning/end and then removes it so we're back to the normal state, which is [2,4,5,1,3] – Dan Uznanski Nov 7 at 0:51
  • Ahhh so if we fix p and let i vary cycle(p,i) gives all of the rotated copies of p? If this is the case we must be computing the same thing a lot. Is it possible to speed up the calculations by removing the rotated cycles from permutations while still inside the for loop? – vdbeek Nov 7 at 1:16
  • 1
    Indeed: we can store permutations we've found via cycle and reversal and check incoming permutations against that. ...But this has a downside: we now must store all those permutations! This gets untenably large quite quickly. Other optimizations include cutting off when we know that other versions will be smaller - since we enumerate permutations in lexicographic order, anything we find where the first element of the cycle is not the shortest can be cut short - and we can cut off whole sections of the permutation tree this way. But that means rewriting permutations to check substrings... – Dan Uznanski Nov 7 at 1:56

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.

  • A000939 is what you want. You must have missed two 6-stars. – Empy2 Nov 6 at 11:31

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.