cp's OEIS Frontend

A002785 Number of self-complementary oriented graphs with n nodes.

%I A002785 M0375 N0141 #40 Jan 07 2021 15:09:19
%S A002785 1,1,2,2,8,12,88,176,2752,8784,279968,1492288,95458560,872687552,
%T A002785 111698291584,1787154671104,457509297625088,13013584213369088,
%U A002785 6662951988432581120,341143107490935724032,349330527429800077778944,32519496073514216703585280
%N A002785 Number of self-complementary oriented graphs with n nodes.
%C A002785 Also, self-converse tournaments. - _Brendan McKay_, Dec 31 2020
%C A002785 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
%D A002785 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002785 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002785 Andrew Howroyd, <a href="/A002785/b002785.txt">Table of n, a(n) for n = 1..100</a>
%H A002785 Alastair Farrugia, <a href="http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf">Self-complementary graphs and generalizations: a comprehensive reference</a>, M.Sc. Thesis, University of Malta, August 1999.
%H A002785 M. R. Sridharan, <a href="/A002785/a002785.pdf"> Self-complementary and self-converse oriented graphs </a>, Nederl. Akad. Wetensch. Proc. Ser. A 73=Indag. Math. 32 1970 441-447. [Annotated scanned copy]
%H A002785 Peter Steinbach, <a href="/A000664/a000664_11.pdf">Field Guide to Simple Graphs, Volume 4</a>, Part 11 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%F A002785 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
%p A002785 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)
%t A002785 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];
%t A002785 edges[v_] := 2*Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i-1}], {i, 2, Length[v]}]+Total[v];
%t A002785 oddp[v_] := Module[{i}, For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1];
%t A002785 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!];
%t A002785 Array[a, 22] (* _Jean-François Alcover_, Jan 07 2021, after _Andrew Howroyd_ *)
%o A002785 (PARI)
%o A002785 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}
%o A002785 edges(v) = {2*sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i])}
%o A002785 oddp(v) = {for(i=1, #v, if(bitand(v[i], 1)==0, return(0))); 1}
%o A002785 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
%Y A002785 Cf. A000171, A003086, A005639.
%K A002785 nonn,nice,easy
%O A002785 1,3
%A A002785 _N. J. A. Sloane_
%E A002785 More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
%E A002785 a(1)-a(2) prepended by _Andrew Howroyd_, Sep 16 2018