Symmetry factors in graphs I am not a professional mathematician, therefore my question may be not perfectly well posed, but I am in search of some ideas or references, not necessarily of a solution to my problem.
Suppose I have a set of points, such that I can join them with a line only in pairs.
According to this rule when $n=2$ I have $\langle 12\rangle$ meaning that the points 1---2 have been connected by a line. I have made up a classification such that this corresponds to $(1,0)$ where $$(a,b)\equiv(\text{contiguous points joined},\text{intersections between joining lines})$$
(clearer below).
In $n=4$ (I am not interested in an odd number of points for obvious reasons) I have two subsets $\langle 12\rangle\langle 34\rangle$, $\langle 14\rangle\langle23\rangle$ and $\langle13\rangle\langle24\rangle$ which respectively have $(2,0)$ and $(0,1)$ according to my arbitrary classification. Indeed, when drawing these graphs by disposing the points clockwise in increasing order on the corners of a square one finds precisely that the first two connect contigous points without intersections while the third connects non-contiguos points with one interesection.
In the case $n=6$ the situation is naturally more complicated and I have found:
2 graphs with (3,0)
3 graphs with (2,0)
6 graphs with (1,1)
3 graphs with (0,2)
1 graph with (0,3)
one can clearly see this by disposing the points in creasing number on the corners of an hexagon. There are a total of fifteen graphs, and indeed I have verified that the total number of graphs goes as $(2n-1)!!$. So far so good.
My actual problem is that I need to evaluate an object that I can put in the form:
$$U_n = \frac{1}{n}\sum_{\sigma\in{1,2,3,\ldots,n}} S(\sigma)\langle \sigma(1)\sigma(2)\rangle\langle \sigma(2)\sigma(3)\rangle\ldots\langle \sigma(n-1)\sigma(n)\rangle$$
where the sum is over the set of permutations. When performing the calculation numerically (I am trying to find an analytical formula) I have found that the  numbers $S(\sigma)$ that I suppose are some kind of symmetry factors are:
\begin{align}
&n=2\quad (1,0)\rightarrow S_1=\frac{1}{6}\\\\
&n=4\quad 2\times(2,0)\rightarrow S_1 = \frac{1}{8}\quad (1,1)\rightarrow S_2 = \frac{1}{6}\\\\
&n=6\quad 2\times(3,0)\rightarrow S_1 = \frac{1}{16}\quad 3\times(2,0)\rightarrow S_2 = \frac{1}{8}\\
&\qquad\quad6\times(1,1)\rightarrow S_3 = \frac{1}{8}\quad 3\times(0,2)\rightarrow S_4 = \frac{1}{6}\\
&\qquad\quad (0,3)\rightarrow S_3 = \frac{1}{12}
\end{align}
are actually independent of the permutations but crucially depend on this classification I have made.
I haven't been able to find a pattern or something easy to discern to extract these $S_n$. I don't even know if my classification is somewhat useful or not to distinguish the various graphs. Is there a theory regarding these objects?
Edit for the comment:
The S factors is obtainable as follows:
we take the points to be on a circle and count their connections trought the circle too.  Set for instance $n=2$ then you have $1$ and $2$ connected by a string and then by two semicircles, therefore we can write it as $\langle 12\rangle^3$ then we can borrow a formula from physics:
$$\frac{1}{S}=g \prod_n \left( n!\right)^{\alpha_n}$$
$g$ is the number of of interchanges of vertices leaving the diagram topologically unchanged (i.e. leaves the brackets the same considering the connections are symmetric), and $\alpha_n$ is the number of vertex pairs connected by $n$ identical lines. Therefore, for the diagram in $n=2$ we have only two vertices so $g=1$ and there are $\alpha_3=1$ and so:
$S=\frac{1}{6}$.
In $n=4$ we have for one of the diagrams (same for the other) $(2,0)$ an expression of the form $\langle 12\rangle^2\langle2 3\rangle\langle 34\rangle^2\langle 4 1\rangle$ which means that $\alpha_2=2$ and $g=2$ beacuse we can either exchange the pair $(1,2)$ with $(3,4)$ or $1$ with $4$ with $4$ and $2$ with $3$ while leaving the diagram unchanged. Therefore $S_1=\frac{1}{8}$.
The diagram $(0,1)$ can be written as $\langle 12\rangle\langle2 3\rangle\langle 34\rangle\langle 4 1\rangle\langle 1 3\rangle\langle 12\rangle$ so all $\alpha=0$ and there is only the $g$ factor, but the permutations of 4 points on a circle should be $g=3!$. Therefore $S_2=\frac{1}{6}$.
Then my question probably amounts to: is there a way to compute $g$ which is not by tedious inspection of these diagram functions which I have written in a few cases $f(1,2,3,.\ldots,n) = \langle 12\rangle^\beta_1\ldots\langle n 1\rangle^\beta_n$? Or at least is there an efficient way of inspecting them? Because as of now I am left with a lot of guess work.
 A: If I understand correctly, the $\alpha_n, n\geq 3$ must be all zeros starting from four vertices. $g$ is computed by taking the size of the automorphism group of the underlying graph, and by dividing it by the size of the automorphism group composed of automorphisms that are only cyclic permutations of the vertices around the main circle (this is a subgroup of the automorphism group). Let's call it the cyclic automorphism group.
Computing the size of the cyclic automorphism group is easy since there is only a linear number of automorphisms to check.
Computing the size of the automorphism group is a bit trickier. In general, it is hard to find the automorphism group of a given graph (checking if there is a non-trivial automorphism is GI-complete). However, we know here that the diagrams you are considering correspond exactly to the hamiltonian cubic graphs.
For example, for $n=6$, the configuration (0,3) gives graph $K_{3,3}$ which has an automorphism group of size 72, but all $6$ rotations are isomorphisms, so we have $g=72/6=12$. As $\alpha_2 = 0$, it matches the $S_n$ you gave.
You can find a set of generators for the automorphism group of a cubic graph in polynomial time for cubic graphs (and in general for graphs of bounded valence). See Luks, Eugene M., Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. Syst. Sci. 25, 42-65 (1982). ZBL0493.68064.
In practice, you can use the Nauty library for finding the size of the automorphism group efficiently.
Note that the number of automorphisms is not related to the number of crossings, but the combinatorics are rather complex, and you should not expect an analytical formula to get the number of non-isomorphic chord diagrams. You can see the related OEIS entries for some references: non-isomorphic chord diagrams, non-isomorphic chord diagrams not allowing reflections
