|
|
A003086
|
|
Number of self-complementary digraphs with n nodes.
(Formerly M3404)
|
|
9
|
|
|
1, 1, 4, 10, 136, 720, 44224, 703760, 179228736, 9168331776, 9383939974144, 1601371799340544, 6558936236286040064, 3837878966366932639744, 62879572771326489528942592, 128777257564337108286016980992
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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!);
|
|
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
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|