|
|
A002785
|
|
Number of self-complementary oriented graphs with n nodes.
(Formerly M0375 N0141)
|
|
4
|
|
|
1, 1, 2, 2, 8, 12, 88, 176, 2752, 8784, 279968, 1492288, 95458560, 872687552, 111698291584, 1787154671104, 457509297625088, 13013584213369088, 6662951988432581120, 341143107490935724032, 349330527429800077778944, 32519496073514216703585280
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Farrugia's Chapter 8 on enumeration of self-complementary and self-converse graphs and digraphs contains many explicit formulas as well as an in-depth discussion of the literature on this subject. - Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
|
|
REFERENCES
|
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 11 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
|
|
FORMULA
|
a(2*n) = Sum_{j partition of n & jk=0 if k even} [ Product_{k} 2^(k*jk^2-jk) * Product_{r<t} 2^(2*gcd(r, t)*jr*jt) / Product_{k} k^jk*jk! ]; a(2*n+1) = Sum_{j partition of n & jk=0 if k even} [ Product_{1<=r, t<=n} 2^(gcd(r, t)*jr*jt) / Product_{k} k^jk*jk! ]. - Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
|
|
MAPLE
|
with(combinat, partition): j:=proc(p) local k, jpart: jpart:=[seq(0, k=1..max(op(p)))]: for k from 1 to nops(p) do jpart[p[k]]:=jpart[p[k]]+1 od: RETURN(jpart): end; numeven:=jtot->2^add(add((2*igcd(r, t)*jtot[r]*jtot[t]), r=1..t-1)+(t*jtot[t]^2-jtot[t]), t=1..nops(jtot)); numodd:=jtot->mul(mul(2^(igcd(r, t)*jtot[r]*jtot[t]), r=1..nops(jtot)), t=1..nops(jtot)); den:=jtot->mul(k^jtot[k]*jtot[k]!, k=1..nops(jtot)); testj:=proc(jtot) local i: for i from 1 to floor(nops(jtot)/2) do if(jtot[2*i]<>0) then RETURN(0) fi od: RETURN(1) end; teven:=proc(n) local s, part, k, p, jtot: s:=0: part:=partition(n): for k from 1 to nops(part) do p:=part[k]: jtot:=j(p): if testj(jtot)=1 then s:=s+numeven(jtot)/den(jtot) fi od:RETURN(s): end; todd:=proc(n) local s, part, k, p, jtot: s:=0: part:=partition(n): for k from 1 to nops(part) do p:=part[k]: jtot:=j(p): if testj(jtot)=1 then s:=s+numodd(jtot)/den(jtot) fi od:RETURN(s): end; seq(op([todd(n), teven(n+1)]), n=1..12); (Pab Ter)
|
|
MATHEMATICA
|
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_] := 2*Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i-1}], {i, 2, Length[v]}]+Total[v];
oddp[v_] := Module[{i}, For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1];
a[n_] := Module[{s = 0}, Do[If[oddp[p] == 1, s += permcount[2*p]*2^edges[p]*If[OddQ[n], n*2^Length[p], 1]], {p, IntegerPartitions[Quotient[n, 2]]}]; 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) = {2*sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i])}
oddp(v) = {for(i=1, #v, if(bitand(v[i], 1)==0, return(0))); 1}
a(n) = {my(s=0); forpart(p=n\2, if(oddp(p), s+=permcount(2*Vec(p)) * 2^edges(p) * if(n%2, n*2^#p, 1))); s/n!} \\ Andrew Howroyd, Sep 16 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
|
|
STATUS
|
approved
|
|
|
|