login
Number of aperiodic cycle necklaces with n vertices.
8

%I #14 Aug 19 2019 16:11:15

%S 1,0,0,0,2,7,51,300,2238,18028,164945,1662067,18423138,222380433,

%T 2905942904,40864642560,615376173176,9880203467184,168483518571789,

%U 3041127459127222,57926238289894992,1161157775616335125,24434798429947993043,538583682037962702384

%N Number of aperiodic cycle necklaces with n vertices.

%C We define an aperiodic cycle necklace to be an equivalence class of (labeled, undirected) Hamiltonian cycles under rotation of the vertices such that all n of these rotations are distinct.

%H Andrew Howroyd, <a href="/A324513/b324513.txt">Table of n, a(n) for n = 1..200</a>

%H Gus Wiseman, <a href="/A324513/a324513.png">Inequivalent representatives of the a(6) = 7 aperiodic cycle necklaces</a>.

%H Gus Wiseman, <a href="/A324513/a324513_1.png">Inequivalent representatives of the a(7) = 51 aperiodic cycle necklaces</a>.

%F a(n) = A324512(n)/n.

%F a(2*n+1) = A064852(2*n+1)/2 for n > 0; a(2*n) = (A064852(2*n) - A002866(n-1))/2 for n > 1. - _Andrew Howroyd_, Aug 16 2019

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

%t Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&&UnsameQ@@Table[Nest[rotgra[#,n]&,#,j],{j,n}]&]],{n,8}]

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

%Y Cf. A000740, A000939, A001037 (binary Lyndon words), A008965, A059966 (Lyndon compositions), A060223 (normal Lyndon words), A061417, A064852 (if cycle is oriented), A086675, A192332, A275527, A323866 (aperiodic toroidal arrays), A323871.

%Y Cf. A306669, A324461, A324462, A324512, A324514.

%K nonn

%O 1,5

%A _Gus Wiseman_, Mar 04 2019

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