|
|
A324513
|
|
Number of aperiodic cycle necklaces with n vertices.
|
|
8
|
|
|
1, 0, 0, 0, 2, 7, 51, 300, 2238, 18028, 164945, 1662067, 18423138, 222380433, 2905942904, 40864642560, 615376173176, 9880203467184, 168483518571789, 3041127459127222, 57926238289894992, 1161157775616335125, 24434798429947993043, 538583682037962702384
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
|
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|