login
Number of connected graphical necklaces with n vertices.
6

%I #10 Jan 24 2023 23:12:13

%S 1,0,1,2,13,148,4530,266614,31451264,7366255436,3449652145180,

%T 3240150686268514,6112883022923529310,23174784819204929919428,

%U 176546343645071836902594288,2701845395848698682311893154024,83036184895986451215378727412638816,5122922885438069578928905234650082410736

%N Number of connected graphical necklaces with n vertices.

%C 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.

%H Andrew Howroyd, <a href="/A324464/b324464.txt">Table of n, a(n) for n = 0..50</a>

%H Gus Wiseman, <a href="/A324464/a324464.png">The a(4) = 13 connected graphical necklaces</a>.

%H Gus Wiseman, <a href="/A324464/a324464_1.png">The a(5) = 148 connected graphical necklaces</a>.

%e Inequivalent representatives of the a(2) = 1 through a(4) = 13 graphical necklaces:

%e {{12}} {{12}{13}} {{12}{13}{14}}

%e {{12}{13}{23}} {{12}{13}{24}}

%e {{12}{13}{34}}

%e {{12}{14}{23}}

%e {{12}{24}{34}}

%e {{12}{13}{14}{23}}

%e {{12}{13}{14}{24}}

%e {{12}{13}{14}{34}}

%e {{12}{13}{24}{34}}

%e {{12}{14}{23}{34}}

%e {{12}{13}{14}{23}{24}}

%e {{12}{13}{14}{23}{34}}

%e {{12}{13}{14}{23}{24}{34}}

%t rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];

%t 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]]]]]]]]];

%t 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}]

%o (PARI) \\ B(n,d) is graphs on n*d points invariant under 1/d rotation.

%o B(n,d)={2^(n*(n-1)*d/2 + n*(d\2))}

%o 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))}

%o a(n)={if(n<=1, n==0, sumdiv(n, d, D(n/d,d))/n)} \\ _Andrew Howroyd_, Jan 24 2023

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

%K nonn

%O 0,4

%A _Gus Wiseman_, Mar 01 2019

%E Terms a(7) and beyond from _Andrew Howroyd_, Jan 24 2023