A324513 Number of aperiodic cycle necklaces with n vertices.

1, 0, 0, 0, 2, 7, 51, 300, 2238, 18028, 164945, 1662067, 18423138, 222380433, 2905942904, 40864642560, 615376173176, 9880203467184, 168483518571789, 3041127459127222, 57926238289894992, 1161157775616335125, 24434798429947993043, 538583682037962702384

Offset

1,5

Comments

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

Gus Wiseman, Inequivalent representatives of the a(6) = 7 aperiodic cycle necklaces.

Gus Wiseman, Inequivalent representatives of the a(7) = 51 aperiodic cycle necklaces.

Formula

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

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

Mathematica

rotgra[g_, m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m, 1, k+1])];
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}]

Prog

(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

Crossrefs

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.

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

Sequence in context: A363862 A340027 A362340 * A086902 A265042 A249754

Adjacent sequences: A324510 A324511 A324512 * A324514 A324515 A324516

Keyword

nonn

Author

Gus Wiseman, Mar 04 2019

Extensions

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

Status

approved