A000171 -id:A000171 - cp's OEIS frontend

A007869 Number of complementary pairs of graphs on n nodes. Also number of unlabeled graphs with n nodes and an even number of edges.

1, 1, 2, 6, 18, 78, 522, 6178, 137352, 6002584, 509498932, 82545586656, 25251015686776, 14527077828617744, 15713242984902154384, 32000507852263779299344, 122967932076766466347469888, 893788862572805850273939095424, 12318904626562502262191503745716384

Offset: 1

Peter J. Cameron

Andrew Howroyd, Table of n, a(n) for n = 1..50
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Nevena Francetić, Sarada Herke, and Ian M. Wanless, Parity of Sets of Mutually Orthogonal Latin Squares, arXiv:1703.04764 [math.CO], 2017. See Section 4.1.
Tadeusz Sozański, Enumeration of weak isomorphism classes of signed graphs, J. Graph Theory 4 (1980), no. 2, 127-144. (Zentralblatt 434 #05059)
Ferenc Szöllosi, The two-distance sets in dimension four, arXiv:1806.07861 [math.MG], 2018. See Table 1.

Cf. A000088, A000171.

Cf. A054960 for graphs with an odd number of edges.

Needs["Combinatorica`"]; Table[Total[Table[NumberOfGraphs[n,m],{m,0,Binomial[n,2],2}]],{n,1,15}]  (* Geoffrey Critzer, Oct 20 2012; modified by Harvey P. Dale, Aug 08 2013 *)

a(n)={local(p=vector(n));
my(S=0, J() = sum(j=0, floor((n-1)/2), p[2*j+1]),
    I2() = (sum(i=1, n, sum(j=1, n, p[i]*p[j]*gcd(i, j))) - J())/2,
    M1() = (abs((p[1]-0)*(p[1]-1)) + sum(j=2, n, if(0!=(j%4), p[j], 0))),
inc()=!forstep(i=n, 1, -1, p[i]n, p[i]=n); next(2))); t==n && S+=(if(M1() == 0, 2^I2()/prod(i=1, n, i^p[i]*p[i]!), 0) + 2^I2()/prod(i=1, n, i^p[i]*p[i]!))/2); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 02 2021

Average of A000088 and A000171.

More terms from Vladeta Jovovic, Jul 19 2000

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

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

A047660 Number of self-complementary 2-plexes.

Original entry on oeis.org

1, 1, 0, 1, 2, 40, 0, 703760, 131328, 300241541128192, 0, 28170013344558609991874248704, 24595658799308603392, 9502080486519653717758562294813775233459455787008, 0

Offset: 1

N. J. A. Sloane

E. M. Palmer, On the number of n-plexes, Discrete Math., 6 (1973), 377-390.

Cf. A000171, A051251.

More terms from Vladeta Jovovic

A051251 Number of self-complementary 3-plexes.

Original entry on oeis.org

1, 1, 1, 0, 0, 0, 0, 128, 16384, 33554432, 1466015678464, 0, 0, 0, 0, 53919893334301279589334030174039266539571147379908773492703549718528, 63657374260452690195888927762793067532858387480466469420624374174610161798791164116074496

Offset: 1

Vladeta Jovovic

nonn

Cf. A000171, A047660.

A054931 Number of unlabeled connected graphs up to complementarity.

Original entry on oeis.org

1, 0, 0, 1, 5, 34, 331, 4949, 123764, 5713987, 497201633, 81514244540, 25084892188043, 14476409634230317, 15684138157859087576, 31969052260961397580693, 122903899605317560183278680, 893542862676093238616261481156, 12317116802837365393131147013965260

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. A001349, A000088, A000171.

A001349 = Cases[Import["https://oeis.org/A001349/b001349.txt", "Table"], {, }][[All, 2]];
A000088 = Cases[Import["https://oeis.org/A000088/b000088.txt", "Table"], {, }][[All, 2]];
A000171 = Cases[Import["https://oeis.org/A000171/b000171.txt", "Table"], {, }][[All, 2]];
a[n_] := A001349[[n+1]] - (1/2) A000088[[n+1]] + (1/2) A000171[[n]];
Array[a, 50] (* Jean-François Alcover, Aug 26 2019 *)

a(n) = A001349(n) - (1/2)*A000088(n) + (1/2)*A000171(n). (see Eq. (4) in Liskovets) - Emeric Deutsch, Nov 18 2004

More terms from Emeric Deutsch, Nov 18 2004

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

A055973 Number of unlabeled digraphs with loops (relations) on n nodes and with an even number of arcs.

Original entry on oeis.org

1, 1, 6, 52, 1540, 145984, 48467296, 56141454464, 229148555640864, 3333310786076963968, 174695272746896566439424, 33301710992539090379269318144, 23278728241293494584257987458067456, 60084295633556503802059558812644803074048, 576025077880237078776946976495257043823396069376

Offset: 0

Vladeta Jovovic, Jul 19 2000

Also relations considered equivalent when isomorphic and when complemented. - Christian G. Bower, Jan 05 2004

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

Cf. A000171, A000595, A007869, A047832, A054928, A055974.

a(2*n) = (A000595(2*n) + A047832(n))/2; a(2*n+1) = A000595(2*n+1)/2.
a(n) = (A000595(n) + A000171(2*n+1))/2.
a(n) = sum {1*s_1+2*s_2+...=n, 1*t_1+2*t_2=2} (fixA[s_1, s_2, ...;t_1, t_2]/(1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!)) where fixA[...] = prod {i, j>=1} ( (sum {d|lcm(i, j)} (d*t_d))^(gcd(i, j)*s_i*s_j)) - Christian G. Bower, Jan 05 2004

a(0)=1 prepended and terms a(13) and beyond from Andrew Howroyd, Apr 19 2020

Showing 1-10 of 16 results. Next

cp's OEIS Frontend

A007869 Number of complementary pairs of graphs on n nodes. Also number of unlabeled graphs with n nodes and an even number of edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A003086 Number of self-complementary digraphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A054960 Number of unlabeled graphs with n nodes and an odd number of edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A047832 Number of self-complementary binary relations on a 2n-element set.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

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

A047660 Number of self-complementary 2-plexes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A051251 Number of self-complementary 3-plexes.

Views

Author

Keywords

Crossrefs