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

Author

Peter J. Cameron

Keywords

• nonn
• nice

Links

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

Crossrefs

Cf. A000088, A000171.

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

Programs

Mathematica

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

PARI

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

Formula

Average of A000088 and A000171.

Extensions

More terms from Vladeta Jovovic, Jul 19 2000

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