|
%I M0014 N0780 #67 Feb 20 2023 22:08:38
%S 1,0,0,1,2,0,0,10,36,0,0,720,5600,0,0,703760,11220000,0,0,9168331776,
%T 293293716992,0,0,1601371799340544,102484848265030656,0,0,
%U 3837878966366932639744,491247277315343649710080,0,0
%N Number of self-complementary graphs with n nodes.
%C 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.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 139, Table 6.1.1.
%D R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Andrew Howroyd, <a href="/A000171/b000171.txt">Table of n, a(n) for n = 1..100</a>
%H H. Fripertinger, <a href="http://www.mathe2.uni-bayreuth.de/frib/html/book/hyl00_46.html">Self-complementary graphs</a>
%H Victoria Gatt, Mikhail Klin, Josef Lauri, Valery Liskovets, <a href="https://doi.org/10.1007/978-3-030-32808-5_2">From Schur Rings to Constructive and Analytical Enumeration of Circulant Graphs with Prime-Cubed Number of Vertices</a>, in Isomorphisms, Symmetry and Computations in Algebraic Graph Theory, (Pilsen, Czechia, WAGT 2016) Vol. 305, Springer, Cham, 37-65.
%H Richard A. Gibbs, <a href="https://doi.org/10.1016/0095-8956(74)90053-7">Self-complementary graphs</a> J. Combinatorial Theory Ser. B 16 (1974), 106--123. MR0347686 (50 #188). - _N. J. A. Sloane_, Mar 27 2012
%H Sebastian Jeon, Tanya Khovanova, <a href="https://arxiv.org/abs/2003.03870">3-Symmetric Graphs</a>, arXiv:2003.03870 [math.CO], 2020.
%H B. D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/data/graphs.html">Self-complementary graphs</a>
%H R. C. Read, <a href="https://doi.org/10.1112/jlms/s1-38.1.99">On the number of self-complementary graphs and digraphs</a>, J. London Math. Soc., 38 (1963), 99-104.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Self-ComplementaryGraph.html">Self-Complementary Graph</a>
%H D. Wille, <a href="https://doi.org/10.1016/0095-8956(78)90034-5">Enumeration of self-complementary structures</a>, J. Comb. Theory B 25 (1978) 143-150
%F a(4n) = A003086(2n).
%F a(4*n+1) = A047832(n), a(4*n+2) = a(4*n+3) = 0. - _Andrew Howroyd_, Sep 16 2018
%t <<Combinatorica`; Table[GraphPolynomial[n, x]/.x -> -1, {n, 1, 20}] (* _Geoffrey Critzer_, Oct 21 2012 *)
%t 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 edges[v_] := 4 Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + 2 Total[v];
%t 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!]];
%t Array[a, 40] (* _Jean-François Alcover_, Aug 26 2019, after _Andrew Howroyd_ *)
%o (PARI)
%o 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 edges(v) = {4*sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + 2*sum(i=1, #v, v[i])}
%o 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
%Y Cf. A047660, A051251, A047832.
%Y Cf. A008406 (triangle of coefficients of the "graph polynomial").
%K nonn,nice
%O 1,5
%A _N. J. A. Sloane_
%E More terms from Ronald C. Read and _Vladeta Jovovic_
|
