A324461 Number of simple graphs with n vertices and distinct rotations.

1, 1, 0, 6, 48, 1020, 32232, 2097144, 268369920, 68719472640, 35184338533920, 36028797018963936, 73786976226114539520, 302231454903657293676480, 2475880078570197599844819072, 40564819207303340847860140736640, 1329227995784915854457062986570792960

Offset

0,4

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. 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) = 48 graphs with distinct rotations.

Formula

a(n > 0) = A306715(n) * n.

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

Mathematica

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

Prog

(PARI) a(n)={if(n==0, 1, sumdiv(n, d, moebius(d)*2^(n*(n/d-1)/2 + n*(d\2)/d)))} \\ Andrew Howroyd, Aug 15 2019
(Python)
from sympy import mobius, divisors
def A324461(n): return sum(mobius(m:=n//d)<<(n*(d-1)>>1)+d*(m>>1) for d in divisors(n, generator=True)) if n else 1 # Chai Wah Wu, Jul 03 2024

Crossrefs

Cf. A000088, A000740, A003436, A006125, A027375, A192314, A192332, A306669, A306715, A323860, A323864, A323867, A324462 (covering case), A324463, A324464.

Sequence in context: A267620 A275334 A192769 * A084259 A372454 A028308

Adjacent sequences: A324458 A324459 A324460 * A324462 A324463 A324464

Keyword

nonn

Author

Gus Wiseman, Feb 28 2019

Extensions

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

Status

approved