A003086 Number of self-complementary digraphs with n nodes. (Formerly M3404)

1, 1, 4, 10, 136, 720, 44224, 703760, 179228736, 9168331776, 9383939974144, 1601371799340544, 6558936236286040064, 3837878966366932639744, 62879572771326489528942592, 128777257564337108286016980992

Offset

1,3

References

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 140, 243.

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

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

Mathematica

Table[GraphPolynomial[n, x, Directed]/.x -> -1, {n, 1, 20}]  (* Geoffrey Critzer, Oct 21 2012 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := 4 Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + Sum[2 v[[i]] - 1, {i, 1, Length[v]}];
a[n_] := (s = 0; Do[s += permcount[2 p]*2^edges[p]*If[OddQ[n], n *4^Length[p], 1], {p, IntegerPartitions[n/2 // Floor]}]; s/n!);
Array[a, 16] (* Jean-François Alcover, Aug 26 2019, after Andrew Howroyd *)

Prog

(PARI)
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {4*sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, 2*v[i]-1)}
a(n) = {my(s=0); forpart(p=n\2, s+=permcount(2*Vec(p))*2^edges(p)*if(n%2, n*4^#p, 1)); s/n!} \\ Andrew Howroyd, Sep 16 2018

Crossrefs

Cf. A000171, A002785.

Sequence in context: A347818 A273517 A370687 * A102958 A321795 A220197

Adjacent sequences: A003083 A003084 A003085 * A003087 A003088 A003089

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

More terms from Ronald C. Read and Vladeta Jovovic.

Status

approved