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

[devjoe.livejournal.com]

Another way to compute these is to figure that most of them are asymmetric, and appear 2N times among the 2^N configurations. Some smaller number of patterns are mirror-symmetric but not rotationally symmetric, and appear N times among the 2N configurations. Some others are rotationally symmetric, and I think due to the geometry here, these are always mirror symmetric also. If N is prime, these have to be N-way rotationally symmetric and each of these contributes once. If N is not prime, then there can also be configurations which are rotationally symmetric by factors of N.

For each of these cases, compute the total number of configurations without bothering to verify that it is not in a more-symmetric case, which is some power of 2. Then use inclusion-exclusion to figure the number of these in each case, and add up the results.

Example for N=7:
No symmetry: 2^21 = 2097152
Mirror symmetry: For any given mirror, exactly 3 connections are bisected by it and the other 18 form 9 mirror pairs, so 2^12 = 4096
Full symmetry: This requires that all connections of the same type are present or all are absent. There are three types of connections with 7 in each. So this is 2^3 = 8.
Out of the 4096, exclude 8 fully symmetric cases. The remaining 4088 have only mirror symmetry.
Out of the 20971528 fully symmetric cases appear once each, and 4088 mirror-symmetric cases appear 7 times each. This leaves 2068528 cases which form 147752 sets of 14 rotations and reflections.
Then 147752 + 4088 + 8 = 151848, without doing any iteration over 2^21 cases.

This gets harder when N is not prime, but grows only with the number of factors of N.

[cnoocy]

Hmm. I don't think your assumption about rotational symmetry holds for non-prime N (see for example the 10th graph in Order 4, the Z-shaped one) but I'll need some time to assimilate the rest of this.