A047832 -id:A047832 - 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

A052113 Number of self-complementary directed 2-multigraphs with loops on n nodes.

Original entry on oeis.org

1, 5, 41, 1023, 67173, 10771355, 5957216417, 6971880064072, 32181855124938673, 290910256437910060602, 11266525980714327353251353, 815201852317091835592374861144, 266236010885685869904935495261864265, 157899403462038839125137738939159318226008

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

V. Jovovic, On the number of m-place relations (in Russian), Logiko-algebraicheskie konstruktsii, Tver, 1992, 59-66.

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

Cf. A004105, A047832.

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]))}
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

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

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

Original entry on oeis.org

0, 1, 4, 52, 1504, 145984, 48461696, 56141454464, 229148544420864, 3333310786076963968, 174695272746603272722432, 33301710992539090379269318144, 23278728241293494481773139193036800, 60084295633556503802059558812644803074048, 576025077880237078776946485247979728479746359296

Offset: 0

Vladeta Jovovic, Jul 19 2000

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

Cf. A000171, A000595, A047832, A054960, A055973.

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(0)=0 prepended and terms a(13) and beyond from Andrew Howroyd, Apr 19 2020

A052152 Number of self-complementary directed 3-multigraphs with loops on 2n nodes.

Original entry on oeis.org

8, 8256, 1431787520, 48038430520647680, 330117345346734148058349568, 483957144078539402095793819136691273728, 155682086691161145712706205845400916732707415735140352

Offset: 1

Vladeta Jovovic, Jan 24 2000

nonn

Cf. A001374, A047832.

A051269 Number of self-complementary 3-place relations on a 2n-element set.

Original entry on oeis.org

8, 536887296, 6760803201217232481859791749120, 301541899055510925582216106793458790276811863115050592580304890195754352640

Offset: 1

Vladeta Jovovic

nonn

Cf. A047832.

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

A052113 Number of self-complementary directed 2-multigraphs with loops on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A052152 Number of self-complementary directed 3-multigraphs with loops on 2n nodes.

Views

Author

Keywords

Crossrefs

A051269 Number of self-complementary 3-place relations on a 2n-element set.

Views

Author

Keywords

Crossrefs