login
Number of graphical necklaces covering n vertices.
6

%I #9 Aug 19 2019 16:59:03

%S 1,0,1,2,15,156,4665,269618,31573327,7375159140,3450904512841,

%T 3240500443884718,6113078165054644451,23175001880311842459108,

%U 176546824267008236554238517,2701847513793569606737940203894,83036203475880811677609125194805687

%N Number of graphical necklaces covering 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. Covering means there are no isolated vertices. These are a kind of partially labeled graphs.

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

%H Gus Wiseman, <a href="/A324463/a324463.png">The a(4) = 15 covering graphical necklaces, radial embedding</a>.

%H Gus Wiseman, <a href="/A324463/a324463_1.png">The a(5) = 156 covering graphical necklaces</a>.

%F a(n) = (1/n)*Sum{d|n} phi(n/d) * Sum_{k=0..d} (-1)^(d-k)*binomial(d,k)*2^( k*(k-1)*n/(2*d) + k*(floor(n/(2*d))) ). - _Andrew Howroyd_, Aug 19 2019

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

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

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

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

%e {{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 Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],#=={}||#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]]&]],{n,0,5}]

%o (PARI) a(n)={if(n<1, n==0, sumdiv(n, d, eulerphi(n/d)*sum(k=0, d, (-1)^(d-k)*binomial(d,k)*2^(k*(k-1)*n/(2*d) + k*(n/d\2))))/n)} \\ _Andrew Howroyd_, Aug 19 2019

%Y Cf. A000031, A002494, A006129, A008965, A184271, A192332 (non-covering case), A323858, A323859, A323870, A324461, A324462, A324464.

%K nonn

%O 0,4

%A _Gus Wiseman_, Feb 28 2019

%E Terms a(7) and beyond from _Andrew Howroyd_, Aug 19 2019