A324463 Number of graphical necklaces covering n vertices.

1, 0, 1, 2, 15, 156, 4665, 269618, 31573327, 7375159140, 3450904512841, 3240500443884718, 6113078165054644451, 23175001880311842459108, 176546824267008236554238517, 2701847513793569606737940203894, 83036203475880811677609125194805687

Offset

0,4

Comments

A graphical necklace is a simple graph that is minimal among all n rotations of the vertices. Alternatively, it is an equivalence class of simple graphs under rotation of the vertices. Covering means there are no isolated vertices. These are a kind of partially labeled graphs.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50

Gus Wiseman, The a(4) = 15 covering graphical necklaces, radial embedding.

Gus Wiseman, The a(5) = 156 covering graphical necklaces.

Formula

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

Example

Inequivalent representatives of the a(2) = 1 through a(4) = 15 graphical necklaces:
  {{12}}  {{12}{13}}      {{12}{34}}
          {{12}{13}{23}}  {{13}{24}}
                          {{12}{13}{14}}
                          {{12}{13}{24}}
                          {{12}{13}{34}}
                          {{12}{14}{23}}
                          {{12}{24}{34}}
                          {{12}{13}{14}{23}}
                          {{12}{13}{14}{24}}
                          {{12}{13}{14}{34}}
                          {{12}{13}{24}{34}}
                          {{12}{14}{23}{34}}
                          {{12}{13}{14}{23}{24}}
                          {{12}{13}{14}{23}{34}}
                          {{12}{13}{14}{23}{24}{34}}

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], #=={}||#==First[Sort[Table[Nest[rotgra[#, n]&, #, j], {j, n}]]]]&]], {n, 0, 5}]

Prog

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

Crossrefs

Cf. A000031, A002494, A006129, A008965, A184271, A192332 (non-covering case), A323858, A323859, A323870, A324461, A324462, A324464.

Sequence in context: A362364 A239107 A124548 * A139085 A268070 A204679

Adjacent sequences: A324460 A324461 A324462 * A324464 A324465 A324466

Keyword

nonn

Author

Gus Wiseman, Feb 28 2019

Extensions

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

Status

approved