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.

[devjoe.livejournal.com]

Oh, right. There are also other cases where you have less-than-N-way rotational symmetry without mirror symmetry. I was thinking that when you have K-way rotational symmetry, you can always pick an axis a symmetry that bisects one of the lines, but when you have multiple sets of lines, there may not be one mirror axis that works for both. For instance, for N=8, take a square of connections that each skip one node, and also connect each of these four nodes to the (previously skipped) node to its left.

What is still true is that when you have N-way symmetry, you have to take complete sets of N like connections and/or the complete set of N/2 connections through the center, and each one of those sets has mirror symmetry with respect to all the possible axes, so the combination of these sets does also.

Also when N is even, you have axes of symmetry that go through the nodes, and axes of symmetry that go between the nodes, while with odd N all the axes of symmetry are equivalent. So it is actually quite a bit more complicated for even N. Still, with some more work it should be possible to compute these directly without having to go through exponentially increasing numbers of cases.

This is the kind of problem I expect to see come up on Project Euler. (Except then I would have to compute the sum of all distinct ways to draw lines from 1 to 100 points, mod 10^8, or some other crazy calculation to show that I really understand all the intricacies of the problem. Here, I was just trying to get you started on a new way to think about the problem.)

[rhu]

Would it be more efficient to work up rather than down? That is, for each point N, if N is not already marked as redundant, compute the set of values >N which are equivalent, and mark them as redundant.

Probably not a significant gain, but worth throwing out there.

[cnoocy]

That would be a lot more efficient. Unfortunately, it requires keeping an array of size 2^n2-n in memory, which gets hairy very quickly.

[rhu]

Eh, memory's cheap. :-)

[cnoocy]

I didn't mean to shut you down earlier. That's actually very useful, and has some similarities to an approach I discussed with someone on IM this afternoon, but I don't want to steal his thunder if he posts more about his approach later.

[rhu]

I didn't take it as a shut-down. No worries.

[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.

[thedan.livejournal.com]

This seems like a specific example of a more general question. Let S be the permutation group on an n-element set X, and let H be a subgroup of S. Any element of S induces a map from graphs with vertices in X to other maps with vertices in X. Set two graphs equivalent if they are mapped to each other by elements of H, and count the equivalence classes produced by that relation. The problem you're studying is the example of this where H is the dihedral group (rotations and reflections).

The general question seems like a very natural thing to study, and the dihedral group is one of the most natural subgroups to use (along with, say, the cyclic group and the alternating group), so I would have guessed this would already be in the literature. But the sequence of numbers you generated doesn't appear in Sloane's integer sequence database, so perhaps this is unexplored territory.

You could also break the problem down further looking for numbers of the form F(n,k), where k is the number of edges in the graph. I'd be curious what, for example, the sequence F(n,n) looks like.

[cnoocy]

Interesting. I'll have to read up on the cyclic and alternating group. I'm already looking at the problem of f(n,k) as part of an alternate programming approach, so I may post some values of that later tonight.

[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.

[cnoocy]

Here's a quick breakdown of F(n,k) for n < 8. Note that F(n,n) is 0 for n<3. I haven't looked at this in depth, so I'll be staring at it as well.

1
1	1
1	1	1	1
1	2	4	5	4	2	1
1	2	7	16	26	32	26	16	7	2	1
1	3	14	50	133	280	457	580	580	457	280	133	50	14	3	1
1	3	21	109	459	1512	3972	8451	14724	21226	25446	25446	21226	14724	8451	3972	1512	459	109	21	3	1

[cnoocy]

And here's F(n,k) for n < 11 and k < 5:

1
1	1
1	1	1	1
1	2	4	5	4
1	2	7	16	26
1	3	14	50	133
1	3	21	109	459
1	4	34	234	1359
1	4	46	432	3381
1	5	66	770	7667