The OEIS is supported by the many generous donors to the OEIS Foundation.
%I M1253 N0479 #360 Oct 27 2024 12:12:37
%S 1,1,2,4,11,34,156,1044,12346,274668,12005168,1018997864,165091172592,
%T 50502031367952,29054155657235488,31426485969804308768,
%U 64001015704527557894928,245935864153532932683719776,1787577725145611700547878190848,24637809253125004524383007491432768
%N Number of simple graphs on n unlabeled nodes.
%C Euler transform of the sequence A001349.
%C Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 430.
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
%D F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
%D Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.
%D M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
%D Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
%D M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22.
%D R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
%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 Keith M. Briggs, <a href="/A000088/b000088.txt">Table of n, a(n) for n = 0..87</a> (From link below)
%H R. Absil and H. Mélot, <a href="http://arxiv.org/abs/1304.7993">Digenes: genetic algorithms to discover conjectures about directed and undirected graphs</a>, arXiv preprint arXiv:1304.7993 [cs.DM], 2013.
%H Natalie Arkus, Vinothan N. Manoharan and Michael P. Brenner. <a href="http://arxiv.org/abs/1011.5412"> Deriving Finite Sphere Packings</a>, arXiv:1011.5412 [cond-mat.soft], Nov 24, 2010. (See Table 1.)
%H Leonid Bedratyuk and Anna Bedratyuk, <a href="http://www.proceedings.bas.bg/cgi-bin/mitko/0DOC_abs.pl?2016_3_02">A new formula for the generating function of the numbers of simple graphs</a>, Comptes rendus de l'Académie Bulgare des Sciences, Tome 69, No 3, 2016, p.259-268.
%H Benjamin A. Blumer, Michael S. Underwood and David L. Feder, <a href="http://arxiv.org/abs/1111.5032">Single-qubit unitary gates by graph scattering</a>, arXiv:1111.5032 [quant-ph], 2011.
%H Keith M. Briggs, <a href="http://keithbriggs.info/cgt.html">Combinatorial Graph Theory</a> [Gives first 140 terms]
%H Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, <a href="http://arxiv.org/abs/1204.3549">House of Graphs: a database of interesting graphs</a>, arXiv preprint arXiv:1204.3549 [math.CO], 2012.
%H P. Butler and R. W. Robinson, <a href="/A002218/a002218.pdf">On the computer calculation of the number of nonseparable graphs</a>, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102.
%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/S0167-5060(08)70569-7">Some sequences of integers</a>, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H P. J. Cameron and C. R. Johnson, <a href="http://dx.doi.org/10.1016/j.disc.2004.10.029">The number of equivalence patterns of symmetric sign patterns</a>, Discr. Math., 306 (2006), 3074-3077.
%H Gi-Sang Cheon, Jinha Kim, Minki Kim and Sergey Kitaev, <a href="https://arxiv.org/abs/1803.01055">On k-11-representable graphs</a>, arXiv:1803.01055 [math.CO], 2018.
%H CombOS - Combinatorial Object Server, <a href="http://combos.org/nauty">Generate graphs</a>
%H Karen M. Daehli, Sarah A Obead, Hsuan-Yin Lin, and Eirik Rosnes, <a href="https://arxiv.org/abs/2401.06125">Improved Capacity Outer Bound for Private Quadratic Monomial Computation</a>, arXiv:2401.06125 [cs.IR], 2024.
%H R. L. Davis, <a href="http://dx.doi.org/10.1090/S0002-9939-1953-0055294-2">The number of structures of finite relations</a>, Proc. Amer. Math. Soc. 4 (1953), 486-495.
%H J. P. Dolch, <a href="/A001349/a001349.pdf">Names of Hamiltonian graphs</a>, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
%H Peter Dukes, <a href="http://www.math.uvic.ca/courses/2019s/math422/a01/M422-notes.pdf">Notes for Math 422: Enumeration and Ramsey Theory</a>, University of Victoria BC Canada (2019). See page 36.
%H D. S. Dummit, E. P. Dummit and H. Kisilevsky, <a href="http://arxiv.org/abs/1512.06480">Characterizations of quadratic, cubic, and quartic residue matrices</a>, arXiv preprint arXiv:1512.06480 [math.NT], 2015.
%H Steven R. Finch, <a href="https://doi.org/10.1017/9781316997741">Mathematical Constants II</a>, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
%H Mareike Fischer, Michelle Galla, Lina Herbst, Yangjing Long, and Kristina Wicke, <a href="https://arxiv.org/abs/1810.06853">Non-binary treebased unrooted phylogenetic networks and their relations to binary and rooted ones</a>, arXiv:1810.06853 [q-bio.PE], 2018.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, 2009; see page 105.
%H E. Friedman, <a href="/A000088/a000088a.gif">Illustration of small graphs</a>
%H Harald Fripertinger, <a href="http://www.mathe2.uni-bayreuth.de/frib/html/book/hyl00_41.html">Graphs</a>
%H Scott Garrabrant and Igor Pak, <a href="http://www.math.ucla.edu/~pak/papers/PatternAvoid10.pdf">Pattern Avoidance is Not P-Recursive</a>, preprint, 2015.
%H Lee M. Gunderson and Gecia Bravo-Hermsdorff, <a href="https://arxiv.org/abs/2002.03959">Introducing Graph Cumulants: What is the Variance of Your Social Network?</a>, arXiv:2002.03959 [math.ST], 2020.
%H P. Hegarty, <a href="http://arxiv.org/abs/1212.4303">On the notion of balance in social network analysis</a>, arXiv preprint arXiv:1212.4303 [cs.SI], 2012.
%H S. Hougardy, <a href="http://www.or.uni-bonn.de/~hougardy/">Home Page</a>
%H S. Hougardy, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.021">Classes of perfect graphs</a>, Discr. Math. 306 (2006), 2529-2571.
%H Richard Hua and Michael J. Dinneen, <a href="https://doi.org/10.1007/s42979-019-0020-1">Improved QUBO Formulation of the Graph Isomorphism Problem</a>, SN Computer Science (2020) Vol. 1, No. 19.
%H A. Itzhakov and M. Codish, <a href="http://arxiv.org/abs/1511.08205">Breaking Symmetries in Graph Search with Canonizing Sets</a>, arXiv preprint arXiv:1511.08205 [cs.AI], 2015-2016.
%H Dan-Marian Joiţa and Lorentz Jäntschi, <a href="https://doi.org/10.3390/math5040084">Extending the Characteristic Polynomial for Characterization of C_20 Fullerene Congeners</a>, Mathematics (2017), 5(4), 84.
%H Vladeta Jovovic, <a href="/A063843/a063843.rtf">Formulae for the number T(n,k) of n-multigraphs on k nodes</a>
%H Maksim Karev, <a href="http://arxiv.org/abs/1404.0026">The space of framed chord diagrams as a Hopf module</a>, arXiv preprint arXiv:1404.0026 [math.GT], 2014.
%H J. M. Larson, <a href="https://www.sas.upenn.edu/polisci/sites/www.sas.upenn.edu.polisci/files/Larson_cheaters_Feb2014.pdf">Cheating Because They Can: Social Networks and Norm Violators</a>, 2014. See Footnote 11.
%H Steffen Lauritzen, Alessandro Rinaldo and Kayvan Sadeghi, <a href="https://arxiv.org/abs/1709.03885">On Exchangeability in Network Models</a>, arXiv:1709.03885 [math.ST], 2017.
%H O. B. Lupanov, <a href="http://new.math.msu.su/department/dm/dmmc/PUBL2/Lupanov-graph.pdf">On asymptotic estimates of the number of graphs and networks with n edges</a>, Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
%H M. D. McIlroy, <a href="/A000088/a000088.pdf">Calculation of numbers of structures of relations on finite sets</a>, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
%H B. D. McKay, <a href="http://www.csse.uwa.edu.au/~gordon/remote/graphs/graphcount">Maple program</a> (used to redirect to <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/graphs/graphcount">here</a>).
%H B. D. McKay, <a href="/A000088/a000088_1.txt">Maple program</a> [Cached copy, with permission]
%H B. D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/data/graphs.html">Simple graphs</a>
%H A. Milicevic and N. Trinajstic, <a href="http://www.sicmm.org/~FAMNIT-knjiga/wwwANG/web-pages/405_469_tcm18-67839%5B1%5D.pdf">Combinatorial Enumeration in Chemistry</a>, Chem. Modell., Vol. 4, (2006), pp. 405-469.
%H Angelo Monti and Blerina Sinaimeri, <a href="https://arxiv.org/abs/2410.16023">Effects of graph operations on star pairwise compatibility graphs</a>, arXiv:2410.16023 [cs.DM], 2024. See p. 16.
%H W. Oberschelp, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002298732">Kombinatorische Anzahlbestimmungen in Relationen</a>, Math. Ann., 174 (1967), 53-78.
%H M. Petkovsek and T. Pisanski, <a href="http://hrcak.srce.hr/file/4232">Counting disconnected structures: chemical trees, fullerenes, I-graphs and others</a>, Croatica Chem. Acta, 78 (2005), 563-567.
%H G. Pfeiffer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting Transitive Relations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
%H E. M. Palmer, <a href="/A000088/a000088_EMP.pdf">Letter to N. J. A. Sloane, no date</a>
%H Marko Riedel, <a href="http://www.roard.com/docs/cookbook/cbsu5.html#x8-170001.5">Nonisomorphic graphs</a>.
%H Marko Riedel, <a href="/A000088/a000088_4.maple.txt">Compact Maple code for cycle index, sequence values and ordinary generating function by the number of edges.</a>
%H R. W. Robinson, <a href="http://dx.doi.org/10.1016/S0021-9800(70)80089-8">Enumeration of non-separable graphs</a>, J. Combin. Theory 9 (1970), 327-356.
%H Sage, <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.html">Common Graphs (Graph Generators)</a>
%H S. S. Skiena, <a href="http://www.cs.sunysb.edu/~algorith/files/generating-graphs.shtml">Generating graphs</a>
%H N. J. A. Sloane, <a href="/A000088/a000088.gif">Illustration of initial terms</a>
%H Quico Spaen, Christopher Thraves Caro and Mark Velednitsky, <a href="https://doi.org/10.1007/s00454-019-00114-w">The Dimension of Valid Distance Drawings of Signed Graphs</a>, Discrete & Computational Geometry (2019), 1-11.
%H P. R. Stein, <a href="/A004250/a004250.pdf">On the number of graphical partitions</a>, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]
%H Peter Steinbach, <a href="/A000088/a000088.txt">Field Guide to Simple Graphs, Volume 1</a>, Overview of the 17 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H Peter Steinbach, <a href="/A000088/a000088_1.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 1
%H Peter Steinbach, <a href="/A000088/a000088_2.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 2
%H Peter Steinbach, <a href="/A000088/a000088_3.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 3
%H Peter Steinbach, <a href="/A000088/a000088_4.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 4
%H Peter Steinbach, <a href="/A000088/a000088_5.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 5
%H Peter Steinbach, <a href="/A000088/a000088_6.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 6
%H Peter Steinbach, <a href="/A000088/a000088_7.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 7
%H Peter Steinbach, <a href="/A000088/a000088_8.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 8
%H Peter Steinbach, <a href="/A000088/a000088_9.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 9
%H Peter Steinbach, <a href="/A000088/a000088_10.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 10
%H Peter Steinbach, <a href="/A000088/a000088_11.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 11
%H Peter Steinbach, <a href="/A000088/a000088_12.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 12
%H Peter Steinbach, <a href="/A000088/a000088_13.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 13
%H Peter Steinbach, <a href="/A000088/a000088_14.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 14
%H Peter Steinbach, <a href="/A000088/a000088_15.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 15
%H Peter Steinbach, <a href="/A000088/a000088_16.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 16
%H Peter Steinbach, <a href="/A000088/a000088_17.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 17
%H J. M. Tangen and N. J. A. Sloane, <a href="/A000666/a000666.pdf">Correspondence, 1976-1976</a>
%H James Turner and William H. Kautz, <a href="http://dx.doi.org/10.1137/1012125">A survey of progress in graph theory in the Soviet Union</a> SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18.
%H S. Uijlen and B. Westerbaan, <a href="http://arxiv.org/abs/1412.8544">A Kochen-Specker system has at least 22 vectors</a>, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.
%H Mark Velednitsky, <a href="https://marvel2010.github.io/static/Dissertation_Velednitsky_Final.pdf">New Algorithms for Three Combinatorial Optimization Problems on Graphs</a>, Ph. D. Dissertation, University of California, Berkeley (2020).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SimpleGraph.html">Simple Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DegreeSequence.html">Degree Sequence</a>
%H E. M. Wright, <a href="http://dx.doi.org/10.1007/BF01350794">The number of graphs on many unlabelled nodes</a>, Mathematische Annalen, December 1969, Volume 183, Issue 4, 250-253
%H E. M. Wright, <a href="http://dx.doi.org/10.1090/S0002-9904-1972-13097-0 ">The number of unlabelled graphs with many nodes and edges</a> Bull. Amer. Math. Soc. Volume 78, Number 6 (1972), 1032-1034.
%H Chris Ying, <a href="https://arxiv.org/abs/1902.06192">Enumerating Unique Computational Graphs via an Iterative Graph Invariant</a>, arXiv:1902.06192 [cs.DM], 2019.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference). - _Vladeta Jovovic_ and _Benoit Cloitre_, Feb 01 2003
%F a(n) = 2^binomial(n, 2)/n!*[1+2*n$2*2^{-n}+8/3*n$3*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1). - _Keith Briggs_, Oct 24 2005
%F From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
%F a(n) = a(n, 2), where a(n, t) is the number of t-uniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).
%F a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n} per(c)*2^f(c), where:
%F ..per(c) = 1/(Product_{i=1..n} c_i!*i^c_i);
%F ..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2+...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);
%F ..ord(c) = lcm{i : c_i>0};
%F ..y(r, k; c) = Sum_{s|r : gcd(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th power of a permutation of type c. (End)
%F a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.]. - _N. J. A. Sloane_, Nov 11 2013
%F For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - _N. J. A. Sloane_, Apr 08 2014
%F a(n) = G(1) where G(z) = (1/n!) Sum_g det(I-g z^2)/det(I-g z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - _Leonid Bedratyuk_, May 02 2015
%F From _Keith Briggs_, Jun 24 2016: (Start)
%F a(n) = 2^binomial(n,2)/n!*(
%F 1+
%F 2^( -n + 1)*n$2+
%F 2^(-2*n + 3)*n$3*(n-7/3)+
%F 2^(-3*n + 6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
%F 2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
%F 2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
%F 2^(-6*n + 21)*n$7*(2048*n^5/45 - 18416*n^4/9 + 329288*n^3/9 - 131680816*n^2/405 + 193822388*n/135 - 7143499196/2835) + ...),
%F where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
%F (End)
%F a(n) = 1/n*Sum_{k=1..n} a(n-k)*A003083(k). - _Andrey Zabolotskiy_, Aug 11 2020
%p # To produce all graphs on 4 nodes, for example:
%p with(GraphTheory):
%p L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency): # _N. J. A. Sloane_, Oct 07 2013
%p seq(GraphTheory[NonIsomorphicGraphs](n,output=count),n=1..10); # _Juergen Will_, Jan 02 2018
%p # alternative Maple program:
%p b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
%p +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
%p add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
%p end:
%p a:= n-> b(n$2, []):
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Aug 14 2019
%t Needs["Combinatorica`"]
%t Table[NumberOfGraphs[n], {n, 0, 19}] (* _Geoffrey Critzer_, Mar 12 2011 *)
%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_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
%t a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
%t Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Jul 05 2018, after _Andrew Howroyd_ *)
%t b[n_, i_, l_] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1 )/2]+Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
%t a[n_] := b[n, n, {}];
%t a /@ Range[0, 20] (* _Jean-François Alcover_, Dec 03 2019, after _Alois P. Heinz_ *)
%o (Sage)
%o def a(n):
%o return len(list(graphs(n)))
%o # _Ralf Stephan_, May 30 2014
%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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
%o a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 22 2017
%o (Python)
%o from itertools import combinations
%o from math import prod, factorial, gcd
%o from fractions import Fraction
%o from sympy.utilities.iterables import partitions
%o def A000088(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # _Chai Wah Wu_, Jul 02 2024
%Y Partial sums of A002494.
%Y Cf. A000666 (graphs with loops), A001349 (connected graphs), A002218, A006290, A003083.
%Y Column k=1 of A063841.
%Y Column k=2 of A309858.
%Y Row sums of A008406.
%Y Cf. also A000055, A000664.
%Y Partial sums are A006897.
%K core,nonn,nice
%O 0,3
%A _N. J. A. Sloane_
%E Harary gives an incorrect value for a(8); compare A007149