A324464 Number of connected graphical necklaces with n vertices.

1, 0, 1, 2, 13, 148, 4530, 266614, 31451264, 7366255436, 3449652145180, 3240150686268514, 6112883022923529310, 23174784819204929919428, 176546343645071836902594288, 2701845395848698682311893154024, 83036184895986451215378727412638816, 5122922885438069578928905234650082410736

Offset

0,4

Comments

A graphical necklace is a simple graph that is minimal among all n rotations of the vertices. Alternatively, it is an equivalence class of simple graphs under rotation of the vertices. These are a kind of partially labeled graphs.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50

Gus Wiseman, The a(4) = 13 connected graphical necklaces.

Gus Wiseman, The a(5) = 148 connected graphical necklaces.

Example

Inequivalent representatives of the a(2) = 1 through a(4) = 13 graphical necklaces:
  {{12}}  {{12}{13}}      {{12}{13}{14}}
          {{12}{13}{23}}  {{12}{13}{24}}
                          {{12}{13}{34}}
                          {{12}{14}{23}}
                          {{12}{24}{34}}
                          {{12}{13}{14}{23}}
                          {{12}{13}{14}{24}}
                          {{12}{13}{14}{34}}
                          {{12}{13}{24}{34}}
                          {{12}{14}{23}{34}}
                          {{12}{13}{14}{23}{24}}
                          {{12}{13}{14}{23}{34}}
                          {{12}{13}{14}{23}{24}{34}}

Mathematica

rotgra[g_, m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m, 1, k+1])];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], And[Union@@#==Range[n], Length[csm[#]]<=1, #=={}||#==First[Sort[Table[Nest[rotgra[#, n]&, #, j], {j, n}]]]]&]], {n, 0, 5}]

Prog

(PARI) \\ B(n, d) is graphs on n*d points invariant under 1/d rotation.
B(n, d)={2^(n*(n-1)*d/2 + n*(d\2))}
D(n, d)={my(v=vector(n, i, B(i, d)), u=vector(n)); for(n=1, #u, u[n]=v[n] - sum(k=1, n-1, binomial(n-1, k)*v[k]*u[n-k])); sumdiv(n, e, eulerphi(d*e) * moebius(e) * u[n/e] * e^(n/e-1))}
a(n)={if(n<=1, n==0, sumdiv(n, d, D(n/d, d))/n)} \\ Andrew Howroyd, Jan 24 2023

Crossrefs

Cf. A000031, A000939, A001187, A006125, A006129, A008965, A184271, A192332, A275527, A323858, A323859, A323870, A324461, A324462, A324463.

Sequence in context: A079330 A059367 A309799 * A364339 A204554 A069736

Adjacent sequences: A324461 A324462 A324463 * A324465 A324466 A324467

Keyword

nonn

Author

Gus Wiseman, Mar 01 2019

Extensions

Terms a(7) and beyond from Andrew Howroyd, Jan 24 2023

Status

approved