Unique connections of N circularly-spaced points

[cnoocy]

This is written up pretty informally. It's based on some doodling at work, which turned into a morning of coding a few weeks ago.

The problem is this: How many unique ways are there to connect N evenly spaced points? By "unique" I mean not having any rotations or reflections in the set. Here's the full sets for order 1 to 4:




The code I wrote uses python's long integer and bit arithmetic code to figure out the sequence up to order 8:
1:1
2:2
3:4
4:19
5:136
6:3036
7:151848
8:16814116

Essentially, I represent each possible connection of N points as a binary number, then determine whether any of its reflections or rotations has a lower value. If any do, it's not the "canonical" version of that set, and it gets discarded. The problem with this approach, though I think it's the fastest, is that the time taken goes up very quickly. 8 took 6 hours or so to run, and checked 2²⁸ configurations. 9 would check 2³⁶ configurations and would therefore take about 64 days.

So that's as far as I'm likely to take this investigation. I'm writing it up here for general interest, and for other people to pick it up if they like.

PDF including Order 5

Python code

Comments

[thedan.livejournal.com]

The cyclic subgroup is just rotations (no reflections).

The alternating subgroup is the set of "even" permutations. Basically, any permutation can be achieved by switching pairs of elements; if the number of pairs you switch is even, that permutation is in the alternating group. I have no clue how one would visualize this like the others in this setting.