A324462 Number of simple graphs covering n vertices with distinct rotations.

1, 0, 0, 3, 28, 765, 26958, 1887277, 252458904, 66376420155, 34508978662350, 35645504882731557, 73356937843604425644, 301275024444053951967585, 2471655539736990372520379226, 40527712706903544100966076156895, 1328579255614092949957261201822704816

Offset: 0

Author

Gus Wiseman, Feb 28 2019

Keywords

• nonn

Comments

A simple graph with n vertices has distinct rotations if all n rotations of its vertex set act on the edge set to give distinct graphs. It is covering if there are no isolated vertices. These are different from aperiodic graphs and acyclic graphs but are similar to aperiodic sequences (A000740) and aperiodic arrays (A323867).

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50
• Gus Wiseman, The a(4) = 28 graph covers with distinct rotations.
• Gus Wiseman, The a(4) = 28 graph covers with distinct rotations, radial embedding.

Crossrefs

Cf. A000088, A000740, A002494, A006125, A006129, A027375, A192332, A323863, A323864, A323867, A323869, A324461 (non-covering case), A324463, A324464.

Programs

Mathematica

rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],UnsameQ@@Table[Nest[rotgra[#,n]&,#,j],{j,n}]]&]],{n,0,5}]

PARI

a(n)={if(n<1, n==0, sumdiv(n, d, moebius(n/d)*sum(k=0, d, (-1)^(d-k)*binomial(d,k)*2^(k*(k-1)*n/(2*d) + k*(n/d\2)))))} \\ Andrew Howroyd, Aug 19 2019

Formula

a(n) = Sum{d|n} mu(n/d) * Sum_{k=0..d} (-1)^(d-k)*binomial(d,k)*2^( k*(k-1)*n/(2*d) + k*(floor(n/(2*d))) ) for n > 0. - Andrew Howroyd, Aug 19 2019

Extensions

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