A003086 -id:A003086 - cp's OEIS frontend

A000171 Number of self-complementary graphs with n nodes.

1, 0, 0, 1, 2, 0, 0, 10, 36, 0, 0, 720, 5600, 0, 0, 703760, 11220000, 0, 0, 9168331776, 293293716992, 0, 0, 1601371799340544, 102484848265030656, 0, 0, 3837878966366932639744, 491247277315343649710080, 0, 0

Offset: 1

N. J. A. Sloane

a(n) = A007869(n)-A054960(n), where A007869(n) is number of unlabeled graphs with n nodes and an even number of edges and A054960(n) is number of unlabeled graphs with n nodes and an odd number of edges.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 139, Table 6.1.1.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
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).

Andrew Howroyd, Table of n, a(n) for n = 1..100
H. Fripertinger, Self-complementary graphs
Victoria Gatt, Mikhail Klin, Josef Lauri, Valery Liskovets, From Schur Rings to Constructive and Analytical Enumeration of Circulant Graphs with Prime-Cubed Number of Vertices, in Isomorphisms, Symmetry and Computations in Algebraic Graph Theory, (Pilsen, Czechia, WAGT 2016) Vol. 305, Springer, Cham, 37-65.
Richard A. Gibbs, Self-complementary graphs J. Combinatorial Theory Ser. B 16 (1974), 106--123. MR0347686 (50 #188). - _N. J. A. Sloane_, Mar 27 2012
Sebastian Jeon, Tanya Khovanova, 3-Symmetric Graphs, arXiv:2003.03870 [math.CO], 2020.
B. D. McKay, Self-complementary graphs
R. C. Read, On the number of self-complementary graphs and digraphs, J. London Math. Soc., 38 (1963), 99-104.
Eric Weisstein's World of Mathematics, Self-Complementary Graph
D. Wille, Enumeration of self-complementary structures, J. Comb. Theory B 25 (1978) 143-150

Cf. A047660, A051251, A047832.

Cf. A008406 (triangle of coefficients of the "graph polynomial").

< -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]}] + 2 Total[v];
a[n_] := Module[{s = 0}, Switch[Mod[n, 4], 2|3, 0, _, Do[s += permcount[4 p]*2^edges[p]*If[OddQ[n], n*2^Length[p], 1], {p, IntegerPartitions[ Quotient[n, 4]]}]; s/n!]];
Array[a, 40] (* Jean-François Alcover, Aug 26 2019, after Andrew Howroyd *)

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]))) + 2*sum(i=1, #v, v[i])}
a(n) = {my(s=0); if(n%4<2, forpart(p=n\4, s+=permcount(4*Vec(p)) * 2^edges(p) * if(n%2, n*2^#p, 1))); s/n!} \\ Andrew Howroyd, Sep 16 2018

a(4n) = A003086(2n).

a(4*n+1) = A047832(n), a(4*n+2) = a(4*n+3) = 0. - Andrew Howroyd, Sep 16 2018

More terms from Ronald C. Read and Vladeta Jovovic

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

Original entry on oeis.org

1, 1, 2, 2, 8, 12, 88, 176, 2752, 8784, 279968, 1492288, 95458560, 872687552, 111698291584, 1787154671104, 457509297625088, 13013584213369088, 6662951988432581120, 341143107490935724032, 349330527429800077778944, 32519496073514216703585280

Offset: 1

N. J. A. Sloane

Also, self-converse tournaments. - Brendan McKay, Dec 31 2020

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

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).

Andrew Howroyd, Table of n, a(n) for n = 1..100
Alastair Farrugia, Self-complementary graphs and generalizations: a comprehensive reference, M.Sc. Thesis, University of Malta, August 1999.
M. R. Sridharan, Self-complementary and self-converse oriented graphs , Nederl. Akad. Wetensch. Proc. Ser. A 73=Indag. Math. 32 1970 441-447. [Annotated scanned copy]
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.)

Cf. A000171, A003086, A005639.

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)

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!];
Array[a, 22] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

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

a(2*n) = Sum_{j partition of n & jk=0 if k even} [ Product_{k} 2^(k*jk^2-jk) * Product_{r

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005

a(1)-a(2) prepended by Andrew Howroyd, Sep 16 2018

A053468 Number of directed 3-multigraphs on n nodes.

Original entry on oeis.org

1, 10, 720, 703760, 9168331776, 1601371799340544, 3837878966366932639744, 128777257564337108286016980992, 61454877497308462618188532330410573824, 422314689395950135433730499958070655419345928192

Offset: 1

Vladeta Jovovic, Jan 13 2000

Andrew Howroyd, Table of n, a(n) for n = 1..40
Rebekka Willenberg, Self-Complementary Graphs and Digraphs. In search of a natural bijection, 2017.

Cf. A000273, A053467, A000171, A003086.

Table[CoefficientList[PairGroupIndex[SymmetricGroup[n],s,Ordered]/.Table[s[i]->4,{i,1,2 Binomial[n,2]}],x],{n,1,8}] (* Geoffrey Critzer, Oct 20 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_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v - 1];
a[n_] := (s=0; Do[s += permcount[p]*4^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Array[a, 15] (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)

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) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*4^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A053468(n): return int(sum(Fraction(1<<((sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))<<1)+sum(q*r**2 for q, r in p.items())-s<<1),prod(q**r*factorial(r) for q, r in p.items())) for s, p in partitions(n,size=True))) # Chai Wah Wu, Jul 10 2024

a(n) = A003086(2n) = A000171(4n). - Andrey Zabolotskiy, Feb 21 2021

A052112 Number of self-complementary directed 2-multigraphs on n nodes.

Original entry on oeis.org

1, 2, 14, 159, 7629, 599456, 226066304, 139178815861, 410179495378288, 2055126126323159298, 48234291396964332998082, 2016523952125103590736221923, 382812826011951187177138562992638, 135681830960694827549160289095792266106

Offset: 1

Vladeta Jovovic, Jan 21 2000

nonn

A 2-multigraph is similar to an ordinary graph except there are 0, 1 or 2 edges between any two nodes (self-loops are not allowed).

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

Cf. A053467, A003086, A053588.

permcount[v_List] := 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_List] := 2 Sum[Sum[If[EvenQ[v[[i]] v[[j]]], GCD[v[[i]], v[[j]]], 0], {j, 1, i - 1}], {i, 2, Length[v]}] + Sum[If[EvenQ[v[[i]]], v[[i]] - 1, 0], {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 25] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd *)

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, if(v[i]*v[j]%2==0, gcd(v[i],v[j])))) + sum(i=1, #v, if(v[i]%2==0, v[i]-1))}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ Andrew Howroyd, Sep 16 2018

Terms a(14) and beyond from Andrew Howroyd, Sep 16 2018

A054928 Number of complementary pairs of directed graphs on n nodes. Also number of unlabeled digraphs with n nodes and an even number of arcs.

Original entry on oeis.org

1, 2, 10, 114, 4872, 770832, 441038832, 896679948304, 6513978501814144, 170630215981070456064, 16261454692532635025585792, 5683372715412701087902846672384, 7334542846356464937798016155801130496, 35157828307617499760694672217473135511928832

Offset: 1

N. J. A. Sloane, May 24 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A000273, A003086, A007869, A054960, A055969.

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_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v - 1];
b[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
edges4[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]}];
c[n_] := (s = 0; Do[s += permcount[2 p]*2^edges4[p]*If[OddQ[n], n *4^Length[p], 1], {p, IntegerPartitions[n/2 // Floor]}]; s/n!);
a[n_] := (b[n] + c[n])/2;
Array[a, 14] (* Jean-François Alcover, Aug 26 2019, using Andrew Howroyd's code for b=A000273 and c=A003086 *)

Average of A000273 and A003086.

More terms from Vladeta Jovovic, Jul 19 2000

Terms a(14) and beyond from Andrew Howroyd, Sep 17 2018

A055969 Number of unlabeled digraphs with n nodes and an odd number of arcs.

Original entry on oeis.org

0, 1, 6, 104, 4736, 770112, 440994608, 896679244544, 6513978322585408, 170630215971902124288, 16261454692523251085611648, 5683372715412699486531047331840, 7334542846356464931239079919515090432, 35157828307617499760690834338506768579289088

Offset: 1

Vladeta Jovovic, Jul 19 2000

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

Cf. A054928, A007869, A054960.

A000273 = Cases[Import["https://oeis.org/A000273/b000273.txt", "Table"], {, }][[All, 2]];
A003086 = Cases[Import["https://oeis.org/A003086/b003086.txt", "Table"], {, }][[All, 2]];
a[n_] := (A000273[[n + 1]] - A003086[[n]])/2;
Array[a, 50] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd *)

a(n) = (A000273(n)-A003086(n))/2.

Terms a(14) and beyond from Andrew Howroyd, Sep 17 2018

A052151 Number of self-complementary directed 3-multigraphs on n nodes.

Original entry on oeis.org

1, 2, 32, 528, 131328, 22377984, 91628068864, 187650529822720, 12297831583666176000, 322380224569805856440320, 338040160454396241027914530816, 118153599638221082814732598131032064, 1982288462105132553530631056140022239461376

Offset: 1

Vladeta Jovovic, Jan 24 2000

nonn

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

Cf. A003086, A052112, A052152.

permcount[v_List] := 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_List] := 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_] := Module[{s = 0}, Do[s += permcount[2 p]*4^edges[p]*If[OddQ[n], n*16^Length[p], 1], {p, IntegerPartitions[Quotient[n, 2]]}]; s/n!];
Array[a, 25] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd *)

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))*4^edges(p)*if(n%2, n*16^#p, 1)); s/n!} \\ Andrew Howroyd, Sep 17 2018

Terms a(13) and beyond from Andrew Howroyd, Sep 17 2018

A054932 Number of unlabeled connected digraphs up to complementarity.

Original entry on oeis.org

1, 1, 7, 95, 4628, 760731, 439476534, 895794710762, 6512183359880844, 170617184427498641390, 16261113406024864291983616, 5683340191820651519596089554647, 7334531479545984537334675978032833750, 35157813638509073199087893774184443496308877

Offset: 1

N. J. A. Sloane, May 24 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A000273, A003085, A003086, A054931.

A054932 := proc(n)
    A003085(n)-(A000273(n)-A003086(n))/2 ;
end proc:
seq(A054932(n),n=1..13) ; # R. J. Mathar, Mar 04 2018

A000273 = Cases[Import["https://oeis.org/A000273/b000273.txt", "Table"], {, }][[All, 2]];
A003085 = Cases[Import["https://oeis.org/A003085/b003085.txt", "Table"], {, }][[All, 2]];
A003086 = Cases[Import["https://oeis.org/A003086/b003086.txt", "Table"], {, }][[All, 2]];
a[n_] := A003085[[n]] - (A000273[[n + 1]] - A003086[[n]])/2;
Array[a, 50] (* Jean-François Alcover, Sep 01 2019 *)

a(n) = A003085(n) - (A000273(n)-A003086(n))/2. - Andrew Howroyd, Sep 17 2018

Terms a(14) and beyond from Andrew Howroyd, Sep 17 2018

Showing 1-8 of 8 results.

cp's OEIS Frontend

A000171 Number of self-complementary graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A053468 Number of directed 3-multigraphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A052112 Number of self-complementary directed 2-multigraphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A054928 Number of complementary pairs of directed graphs on n nodes. Also number of unlabeled digraphs with n nodes and an even number of arcs.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A055969 Number of unlabeled digraphs with n nodes and an odd number of arcs.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A052151 Number of self-complementary directed 3-multigraphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions