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

[joxn]

Every canonical form has a dual which can be gotten by inverting the status of every link. (The dual is not going to be in what you call the "canonical form" because it certainly won't be the least integer, but just redefine what you mean by "canonical form" :-)

You don't have to worry about stealing my thunder on the other stuff; if I beat you to getting it coded up I'll post something.