A001349 -id:A001349 - cp's OEIS frontend

A000088 Number of simple graphs on n unlabeled nodes.

1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768

Offset: 0

N. J. A. Sloane

Euler transform of the sequence A001349.

Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 430.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
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).
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.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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).

Keith M. Briggs, Table of n, a(n) for n = 0..87 (From link below)
R. Absil and H. Mélot, Digenes: genetic algorithms to discover conjectures about directed and undirected graphs, arXiv preprint arXiv:1304.7993 [cs.DM], 2013.
Natalie Arkus, Vinothan N. Manoharan and Michael P. Brenner. Deriving Finite Sphere Packings, arXiv:1011.5412 [cond-mat.soft], Nov 24, 2010. (See Table 1.)
Leonid Bedratyuk and Anna Bedratyuk, A new formula for the generating function of the numbers of simple graphs, Comptes rendus de l'Académie Bulgare des Sciences, Tome 69, No 3, 2016, p.259-268.
Benjamin A. Blumer, Michael S. Underwood and David L. Feder, Single-qubit unitary gates by graph scattering, arXiv:1111.5032 [quant-ph], 2011.
Keith M. Briggs, Combinatorial Graph Theory [Gives first 140 terms]
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, House of Graphs: a database of interesting graphs, arXiv preprint arXiv:1204.3549 [math.CO], 2012.
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, 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]
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron and C. R. Johnson, The number of equivalence patterns of symmetric sign patterns, Discr. Math., 306 (2006), 3074-3077.
Gi-Sang Cheon, Jinha Kim, Minki Kim and Sergey Kitaev, On k-11-representable graphs, arXiv:1803.01055 [math.CO], 2018.
CombOS - Combinatorial Object Server, Generate graphs
Karen M. Daehli, Sarah A Obead, Hsuan-Yin Lin, and Eirik Rosnes, Improved Capacity Outer Bound for Private Quadratic Monomial Computation, arXiv:2401.06125 [cs.IR], 2024.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
Peter Dukes, Notes for Math 422: Enumeration and Ramsey Theory, University of Victoria BC Canada (2019). See page 36.
D. S. Dummit, E. P. Dummit and H. Kisilevsky, Characterizations of quadratic, cubic, and quartic residue matrices, arXiv preprint arXiv:1512.06480 [math.NT], 2015.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Mareike Fischer, Michelle Galla, Lina Herbst, Yangjing Long, and Kristina Wicke, Non-binary treebased unrooted phylogenetic networks and their relations to binary and rooted ones, arXiv:1810.06853 [q-bio.PE], 2018.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 105.
E. Friedman, Illustration of small graphs
Harald Fripertinger, Graphs
Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015.
Lee M. Gunderson and Gecia Bravo-Hermsdorff, Introducing Graph Cumulants: What is the Variance of Your Social Network?, arXiv:2002.03959 [math.ST], 2020.
P. Hegarty, On the notion of balance in social network analysis, arXiv preprint arXiv:1212.4303 [cs.SI], 2012.
S. Hougardy, Home Page
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Richard Hua and Michael J. Dinneen, Improved QUBO Formulation of the Graph Isomorphism Problem, SN Computer Science (2020) Vol. 1, No. 19.
A. Itzhakov and M. Codish, Breaking Symmetries in Graph Search with Canonizing Sets, arXiv preprint arXiv:1511.08205 [cs.AI], 2015-2016.
Dan-Marian Joiţa and Lorentz Jäntschi, Extending the Characteristic Polynomial for Characterization of C_20 Fullerene Congeners, Mathematics (2017), 5(4), 84.
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes
Maksim Karev, The space of framed chord diagrams as a Hopf module, arXiv preprint arXiv:1404.0026 [math.GT], 2014.
J. M. Larson, Cheating Because They Can: Social Networks and Norm Violators, 2014. See Footnote 11.
Steffen Lauritzen, Alessandro Rinaldo and Kayvan Sadeghi, On Exchangeability in Network Models, arXiv:1709.03885 [math.ST], 2017.
O. B. Lupanov, On asymptotic estimates of the number of graphs and networks with n edges, Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
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. [Annotated scanned copy]
B. D. McKay, Maple program (used to redirect to here).
B. D. McKay, Maple program [Cached copy, with permission]
B. D. McKay, Simple graphs
A. Milicevic and N. Trinajstic, Combinatorial Enumeration in Chemistry, Chem. Modell., Vol. 4, (2006), pp. 405-469.
Angelo Monti and Blerina Sinaimeri, Effects of graph operations on star pairwise compatibility graphs, arXiv:2410.16023 [cs.DM], 2024. See p. 16.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
E. M. Palmer, Letter to N. J. A. Sloane, no date
Marko Riedel, Nonisomorphic graphs.
Marko Riedel, Compact Maple code for cycle index, sequence values and ordinary generating function by the number of edges.
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
Sage, Common Graphs (Graph Generators)
S. S. Skiena, Generating graphs
N. J. A. Sloane, Illustration of initial terms
Quico Spaen, Christopher Thraves Caro and Mark Velednitsky, The Dimension of Valid Distance Drawings of Signed Graphs, Discrete & Computational Geometry (2019), 1-11.
P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Overview of the 17 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 11
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 12
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 13
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 14
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 15
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 16
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18.
S. Uijlen and B. Westerbaan, A Kochen-Specker system has at least 22 vectors, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.
Mark Velednitsky, New Algorithms for Three Combinatorial Optimization Problems on Graphs, Ph. D. Dissertation, University of California, Berkeley (2020).
Eric Weisstein's World of Mathematics, Simple Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Degree Sequence
E. M. Wright, The number of graphs on many unlabelled nodes, Mathematische Annalen, December 1969, Volume 183, Issue 4, 250-253
E. M. Wright, The number of unlabelled graphs with many nodes and edges Bull. Amer. Math. Soc. Volume 78, Number 6 (1972), 1032-1034.
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.
Index entries for "core" sequences

Partial sums of A002494.
Cf. A000666 (graphs with loops), A001349 (connected graphs), A002218, A006290, A003083.
Column k=1 of A063841.
Column k=2 of A309858.
Row sums of A008406.
Cf. also A000055, A000664.
Partial sums are A006897.

# To produce all graphs on 4 nodes, for example:
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency): # N. J. A. Sloane, Oct 07 2013
seq(GraphTheory[NonIsomorphicGraphs](n,output=count),n=1..10); # Juergen Will, Jan 02 2018
# alternative Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> b(n$2, []):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 14 2019

Needs["Combinatorica`"]
Table[NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)
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[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)
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}]];
a[n_] := b[n, n, {}];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2019, after Alois P. Heinz *)

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, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000088(n): return int(sum(Fraction(1<>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

def a(n):
    return len(list(graphs(n)))
# Ralf Stephan, May 30 2014

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
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
From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
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).
a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n} per(c)*2^f(c), where:
..per(c) = 1/(Product_{i=1..n} c_i!*i^c_i);
..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);
..ord(c) = lcm{i : c_i>0};
..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)
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
For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014
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
From Keith Briggs, Jun 24 2016: (Start)
a(n) = 2^binomial(n,2)/n!*(
   1+
   2^(  -n +  1)*n$2+
   2^(-2*n +  3)*n$3*(n-7/3)+
   2^(-3*n +  6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
   2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
   2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
   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) + ...),
where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
(End)
a(n) = 1/n*Sum_{k=1..n} a(n-k)*A003083(k). - Andrey Zabolotskiy, Aug 11 2020

Harary gives an incorrect value for a(8); compare A007149

A002494 Number of n-node graphs without isolated nodes.

Original entry on oeis.org

1, 0, 1, 2, 7, 23, 122, 888, 11302, 262322, 11730500, 1006992696, 164072174728, 50336940195360, 29003653625867536, 31397431814147073280, 63969589218557753586160, 245871863137828405125824848, 1787331789281458167615194471072, 24636021675399858912682459613241920

Offset: 0

N. J. A. Sloane

Number of unlabeled simple graphs covering n vertices. - Gus Wiseman, Aug 02 2018

			From _Gus Wiseman_, Aug 02 2018: (Start)
Non-isomorphic representatives of the a(4) = 7 graphs:
  (12)(34)
  (12)(13)(14)
  (12)(13)(24)
  (12)(13)(14)(23)
  (12)(13)(24)(34)
  (12)(13)(14)(23)(24)
  (12)(13)(14)(23)(24)(34)
(End)

F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
W. L. Kocay, Some new methods in reconstruction theory, Combinatorial Mathematics IX, 952 (1982) 89--114. [From Benoit Jubin, Sep 06 2008]
W. L. Kocay, On reconstructing spanning subgraphs, Ars Combinatoria, 11 (1981) 301--313. [From Benoit Jubin, Sep 06 2008]
J. H. Redfield, The theory of group-reduced distributions, Amer. J. Math., 49 (1927), 433-435; reprinted in P. A. MacMahon, Coll. Papers I, pp. 805-827.
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).

T. D. Noe, Table of n, a(n) for n=0..75 (using A000088)
P. C. Fishburn and W. V. Gehrlein, Niche numbers, J. Graph Theory, 16 (1992), 131-139.
R. J. Mathar, Illustrations (2023)
J. H. Redfield, The theory of group-reduced distributions [Annotated scan of pages 452 and 453 only]
Eric Weisstein's World of Mathematics, Isolated Point.
Eric Weisstein's World of Mathematics, Graphical Partition
Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.

Equals first differences of A000088. Cf. A006129 (labeled), A001349 (connected, inv. Euler Transf).
Cf. also A006647, A006648, A006649, A006650, A006651.
Cf. A000612, A001187, A055621, A304998.

b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> b(n$2, [])-`if`(n>0, b(n-1$2, []), 0):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 14 2019

<< MathWorld`Graphs`
Length /@ (gp = Select[ #, GraphicalPartitionQ] & /@
Graphs /@ Range[9])
nn = 20; g = Sum[NumberOfGraphs[n] x^n, {n, 0, nn}]; CoefficientList[Series[ g (1 - x), {x, 0, nn}], x]  (*Geoffrey Critzer, Apr 14 2012*)
sysnorm[m_]:=If[Union@@m!=Range[Max@@Flatten[m]],sysnorm[m/.Rule@@@Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}]],First[Sort[sysnorm[m,1]]]];
sysnorm[m_,aft_]:=If[Length[Union@@m]<=aft,{m},With[{mx=Table[Count[m,i,{2}],{i,Select[Union@@m,#>=aft&]}]},Union@@(sysnorm[#,aft+1]&/@Union[Table[Map[Sort,m/.{par+aft-1->aft,aft->par+aft-1},{0,1}],{par,First/@Position[mx,Max[mx]]}]])]];
Table[Length[Union[sysnorm/@Select[Subsets[Select[Subsets[Range[n]],Length[#]==2&]],Union@@#==Range[n]&]]],{n,6}] (* Gus Wiseman, Aug 02 2018 *)
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}]];
a[n_] := b[n, n, {}] - If[n > 0, b[n-1, n-1, {}], 0];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2019, after Alois P. Heinz *)

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A002494(n): return int(sum(Fraction(1<>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))-sum(Fraction(1<>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-1))) if n else 1 # Chai Wah Wu, Jul 03 2024

O.g.f.: (1-x)*G(x) where G(x) is o.g.f. for A000088. - Geoffrey Critzer, Apr 14 2012

a(n) = A327075(n)+A001349(n). - R. J. Mathar, Nov 21 2023

More terms from Vladeta Jovovic, Apr 10 2000

a(0) added from David W. Wilson, Aug 24 2008

A008406 Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 1, 2, 5, 9, 15, 21, 24, 24, 21, 15, 9, 5, 2, 1, 1, 1, 1, 2, 5, 10, 21, 41, 65, 97, 131, 148, 148, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1, 1, 1, 2, 5, 11, 24, 56, 115, 221, 402, 663, 980, 1312, 1557, 1646, 1557

Offset: 1

N. J. A. Sloane, Mar 15 1996

T(n,k)=1 for n>=2 with k=0, k=1, k=n*(n-1)/2-1 and k=n*(n-1)/2 (therefore the quadruple {1,1,1,1} marks the transition to the next sublist for a given number of vertices (n>2)). [Edited by Peter Munn, Mar 20 2021]

			Triangle begins:
1,
1,1,
1,1,1,1,
1,1,2,3,2,1,1, [graphs with 4 nodes and from 0 to 6 edges]
1,1,2,4,6,6,6,4,2,1,1,
1,1,2,5,9,15,21,24,24,21,15,9,5,2,1,1,
1,1,2,5,10,21,41,65,97,131,148,148,131,97,65,41,21,10,5,2,1,1,
...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 264.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

R. W. Robinson, Rows 1 to 20 of triangle, flattened
Leonid Bedratyuk, A new formula for the generating function of the numbers of simple graphs, arXiv:1512.06355 [math.CO], 2015.
FindStat - Combinatorial Statistic Finder, The number of edges of a graph.
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017) Table 65.
Sriram V. Pemmaraju, Combinatorica 2.0
Marko R. Riedel, Number of distinct connected digraphs
Gordon Royle, Small graphs
S. S. Skiena, Generating graphs
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Overview of the 12 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 11
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 12
James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 19.
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Simple Graph
A. E. Yurtsun, Principles of enumeration of the number of graphs, Ukrainian Mathematical Journal, January-February, 1967, Volume 19, Issue 1, pp 123-125, DOI 10.1007/BF01085184.

Row sums give A000088.
Cf. A046742, A046751, A000717, A001432, A001431, A001430, A001433, A001434, A048179, A048180 etc.
Cf. also A039735, A002905, A054924 (connected), A084546 (labeled graphs).
Row lengths: A000124; number of connected graphs for given number of vertices: A001349; number of graphs for given number of edges: A000664.
Cf. also A000055.

seq(seq(GraphTheory:-NonIsomorphicGraphs(v,e),e=0..v*(v-1)/2),v=1..9); # Robert Israel, Dec 22 2015

<< Combinatorica`; Table[CoefficientList[GraphPolynomial[n, x], x], {n, 8}] // Flatten (* Eric W. Weisstein, Mar 20 2013 *)
<< Combinatorica`; Table[NumberOfGraphs[v, e], {v, 8}, {e, 0, Binomial[v, 2]}] // Flatten (* Eric W. Weisstein, May 17 2017 *)
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_, t_] := Product[Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/ g]^g,{j, 1, i-1}], {i, 2, Length[v]}]*Product[c = v[[i]]; t[c]^Quotient[ c-1, 2]*If[OddQ[c], 1, t[c/2]], {i, 1, Length[v]}];
row[n_] := Module[{s = 0}, Do[s += permcount[p]*edges[p, 1 + x^#&], {p, IntegerPartitions[n]}]; s/n!] // Expand // CoefficientList[#, x]&;
Array[row, 8] // Flatten (* 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,t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i],v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
G(n, A=0) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i+A)); s/n!}
{ for(n=1, 7, print(Vecrev(G(n)))) } \\ Andrew Howroyd, Oct 22 2019, updated  Jan 09 2024

def T(n,k):
    return len(list(graphs(n, size=k)))
# Ralf Stephan, May 30 2014

O.g.f. for n-th row: 1/n! Sum_g det(1-g z^2)/det(1-g z) where g runs through the natural matrix 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, Sep 23 2014

Additional comments from Arne Ring (arne.ring(AT)epost.de), Oct 03 2002

Text belonging in a different sequence deleted by Peter Munn, Mar 20 2021

A057500 Number of connected labeled graphs with n edges and n nodes.

Original entry on oeis.org

0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840, 25201854045, 787368574080, 26667815195274, 973672928417280, 38132879409281475, 1594927540549217280, 70964911709203684440, 3347306760024413356032, 166855112441313024389625, 8765006377126199463936000

Offset: 1

Qing-Hu Hou and David C. Torney (dct(AT)lanl.gov), Sep 01 2000

Equivalently, number of connected unicyclic (i.e., containing one cycle) graphs on n labeled nodes. - Vladeta Jovovic, Oct 26 2004

a(n) is the number of trees on vertex set [n] = {1,2,...,n} rooted at 1 with one marked inversion (an inversion is a pair (i,j) with i > j and j a descendant of i in the tree). Here is a bijection from the title graphs (on [n]) to these marked trees. A title graph has exactly one cycle. There is a unique path from vertex 1 to this cycle, first meeting it at k, say (k may equal 1). Let i and j be the two neighbors of k in the cycle, with i the larger of the two. Delete the edge k<->j thereby forming a tree (in which j is a descendant of i) and take (i,j) as the marked inversion. To reverse this map, create a cycle by joining the smaller element of the marked inversion to the parent of the larger element. a(n) = binomial(n-1,2)*A129137(n). This is because, on the above marked trees, the marked inversion is uniformly distributed over 2-element subsets of {2,3,...,n} and so a(n)/binomial(n-1,2) is the number of trees on [n] (rooted at 1) for which (3,2) is an inversion. - David Callan, Mar 30 2007

			E.g., a(4)=15 because there are three different (labeled) 4-cycles and 12 different labeled graphs with a 3-cycle and an attached, external vertex.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
C. L. Mallows, Letter to N. J. A. Sloane, 1980.
R. J. Riddell, Contributions to the theory of condensation, Dissertation, Univ. of Michigan, Ann Arbor, 1951.

Alois P. Heinz, Table of n, a(n) for n = 1..300 (terms n = 1..50 from Washington G. Bomfim)
Federico Ardila, Matthias Beck, Jodi McWhirter, The Arithmetic of Coxeter Permutahedra, arXiv:2004.02952 [math.CO], 2020.
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 133.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
Younng-Jin Kim and Woong Kook, Winding number and Cutting number of Harmonic cycle, arXiv:1812.04930 [math.CO], 2018.
C. L. Mallows, Letter to N. J. A. Sloane, 1980
Marko Riedel et al., Non-isomorphic, connected, unicyclic graphs, Math Stackexchange, November 2018. (Proof of closed form by Cauchy Coefficient Formula / Lagrange Inversion.)
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.

A diagonal of A343088.
Cf. A000272 = labeled trees on n nodes; connected labeled graphs with n nodes and n+k edges for k=0..8: this sequence, A061540, A061541, A061542, A061543, A096117, A061544, A096150, A096224.
Cf. A001429 (unlabeled case), A052121.
For any number of edges we have A001187, unlabeled A001349.
This is the connected and covering case of A116508.
For #edges <= #nodes we have A129271, covering A367869.
For #edges > #nodes we have A140638, covering A367868.
This is the connected case of A367862 and A367863, unlabeled A006649.
The version with loops is A368951, unlabeled A368983.
This is the covering case of A370317.
Counting only covering vertices gives A370318.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
Cf. A062734, A098909, A123527, A129137, A133686, A143543, A323818, A367916, A367917, A369191, A369197.

egf:= -1/2*ln(1+LambertW(-x)) +1/2*LambertW(-x) -1/4*LambertW(-x)^2:
a:= n-> n!*coeff(series(egf, x, n+3), x, n):
seq(a(n), n=1..25);  # Alois P. Heinz, Mar 27 2013

nn=20; t=Sum[n^(n-1) x^n/n!, {n,1,nn}]; Drop[Range[0,nn]! CoefficientList[Series[Log[1/(1-t)]/2-t^2/4-t/2, {x,0,nn}], x], 1]  (* Geoffrey Critzer, Oct 07 2012 *)
a[n_] := (n-1)!*n^n/2*Sum[1/(n^k*(n-k)!), {k, 3, n}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jan 15 2014, after Vladeta Jovovic *)
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[#]==n&&Length[csm[#]]<=1&]],{n,0,5}] (* Gus Wiseman, Feb 19 2024 *)

# Warning: Floating point calculation. Adjust precision as needed!
from mpmath import mp, chop, gammainc
mp.dps = 200; mp.pretty = True
for n in (1..100):
    print(chop((n^(n-2)*(1-3*n)+exp(n)*gammainc(n+1, n)/n)/2))
# Peter Luschny, Jan 27 2016

The number of labeled connected graphs with n nodes and m edges is Sum_{k=1..n} (-1)^(k+1)/k*Sum_{n_1+n_2+..n_k=n, n_i>0} n!/(Product_{i=1..k} (n_i)!)* binomial(s, m), s=Sum_{i..k} binomial(n_i, 2). - Vladeta Jovovic, Apr 10 2001
E.g.f.: (1/2) Sum_{k>=3} T(x)^k/k, with T(x) = Sum_{n>=1} n^(n-1)/n! x^n. R. J. Riddell's thesis contains a closed-form expression for the number of connected graphs with m nodes and n edges. The present series applies to the special case m=n.
E.g.f.: -1/2*log(1+LambertW(-x))+1/2*LambertW(-x)-1/4*LambertW(-x)^2. - Vladeta Jovovic, Jul 09 2001
Asymptotic expansion (with xi=sqrt(2*Pi)): n^(n-1/2)*[xi/4-7/6*n^(-1/2)+xi/48* n^(-1)+131/270*n^(-3/2)+xi/1152*n^(-2)+4/2835*n^(-5/2)+O(n^(-3))]. - Keith Briggs, Aug 16 2004
Row sums of A098909: a(n) = (n-1)!*n^n/2*Sum_{k=3..n} 1/(n^k*(n-k)!). - Vladeta Jovovic, Oct 26 2004
a(n) = Sum_{k=0..C(n-1,2)} k*A052121(n,k). - Alois P. Heinz, Nov 29 2015
a(n) = (n^(n-2)*(1-3*n)+exp(n)*Gamma(n+1,n)/n)/2. - Peter Luschny, Jan 27 2016
a(n) = A062734(n,n+1) = A123527(n,n). - Gus Wiseman, Feb 19 2024

More terms from Vladeta Jovovic, Jul 09 2001

A367867 Number of labeled simple graphs with n vertices contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 0, 0, 7, 416, 24244, 1951352, 265517333, 68652859502, 35182667175398, 36028748718835272, 73786974794973865449, 302231454853009287213496, 2475880078568912926825399800, 40564819207303268441662426947840, 1329227995784915869870199216532048487

Offset: 0

Gus Wiseman, Dec 07 2023

nonn

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

In the connected case, these are just graphs with more than one cycle.

			Non-isomorphic representatives of the a(4) = 7 graphs:
  {{1,2},{1,3},{1,4},{2,3},{2,4}}
  {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

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

The complement is A133686, connected A129271, covering A367869.
The connected case is A140638 (graphs with more than one cycle).
The covering case is A367868.
For set-systems we have A367903, ranks A367907.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A143543 counts simple labeled graphs by number of connected components.
Cf. A057500, A116508, A326754, A355739, A355740, A367769, A367770, A367863, A367901, A367902, A367904.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Select[Tuples[#],UnsameQ@@#&]=={}&]],{n,0,5}]

a(n) = A006125(n) - A133686(n). - Andrew Howroyd, Dec 30 2023

Terms a(7) and beyond from Andrew Howroyd, Dec 30 2023

A002218 Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n nodes.

Original entry on oeis.org

0, 1, 1, 3, 10, 56, 468, 7123, 194066, 9743542, 900969091, 153620333545, 48432939150704, 28361824488394169, 30995890806033380784, 63501635429109597504951, 244852079292073376010411280, 1783160594069429925952824734641, 24603887051350945867492816663958981

Offset: 1

N. J. A. Sloane

By definition, a(n) gives the number of graphs with zero cutpoints. - Travis Hoppe, Apr 28 2014
For n > 2, a(n) is also the number of simple biconnected graphs on n nodes. - Eric W. Weisstein, Dec 07 2021
This sequence follows R. W. Robinson's definition of a nonseparable graph which includes K_2 but not the singleton graph K_1. This definition is most suited to graphical enumeration. Other authors sometimes include K_1 as a block or exclude K_2 as not 2-connected. - Andrew Howroyd, Feb 26 2023

P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, 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.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 188.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.
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..40 [terms 1..26 from R. W. Robinson]
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, 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]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
R. W. Robinson, Computer print-out of first 26 terms [Annotated scanned copy]
R. W. Robinson, Tables
R. W. Robinson, Tables [Local copy, with permission]
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
R. W. Robinson and T. R. S. Walsh, Inversion of cycle index sum relations for 2- and 3-connected graphs, J. Combin. Theory Ser. B. 57 (1993), 289-308.
R. W. Robinson and T. R. S. Walsh, Inversion of cycle index sum relations for 2- and 3-connected graphs, J. Combin. Theory Ser. B. 57 (1993), 289-308.
Andrés Santos, Density Expansion of the Equation of State, in A Concise Course on the Theory of Classical Liquids, Volume 923 of the series Lecture Notes in Physics, pp 33-96, 2016. DOI:10.1007/978-3-319-29668-5_3. See Reference 40.
Andrew J. Schultz and David A. Kofke, Fifth to eleventh virial coefficients of hard spheres, Phys. Rev. E 90, 023301, 4 August 2014
D. Stolee, Isomorph-free generation of 2-connected graphs with applications, arXiv preprint arXiv:1104.5261 [math.CO], 2011.
Rodrigo Stange Tessinari, Marcia Helena Moreira Paiva, Maxwell E. Monteiro, Marcelo E. V. Segatto, Anilton Garcia, George T. Kanellos, Reza Nejabati, and Dimitra Simeonidou, On the Impact of the Physical Topology on the Optical Network Performance, IEEE British and Irish Conference on Optics and Photonics (BICOP 2018), London.
Eric Weisstein's World of Mathematics, Biconnected Graph
Eric Weisstein's World of Mathematics, k-Connected Graph

Column k=0 of A325111 (for n>1).
Column sums of A339070.
Row sums of A339071.
The labeled version is A013922.
Cf. A000088 (graphs), A001349 (connected graphs), A006289, A006290, A004115 (rooted case), A010355 (by edges), A241767.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(g=graphsSeries(n), gc=sLog(g), gcr=sPoint(gc)); intformal(x*sSolve( sLog( gcr/(x*sv(1)) ), gcr ), sv(1)) + sSolve(subst(gc, sv(1), 0), gcr)}
{ my(N=12); Vec(OgfSeries(cycleIndexSeries(N)), -N) } \\ Andrew Howroyd, Dec 28 2020

More terms from Ronald C. Read. Robinson and Walsh list the first 26 terms.
a(1) changed from 0 to 1 by Eric W. Weisstein, Dec 07 2021
a(1) restored to 0 by Andrew Howroyd, Feb 26 2023

cp's OEIS Frontend

A126060 Incorrect version of A001349.

Views

Author

Keywords

References

A182179 a(n) = |A001349(n) - A004251(n)|.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A000088 Number of simple graphs on n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A002494 Number of n-node graphs without isolated nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A008406 Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A057500 Number of connected labeled graphs with n edges and n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A367867 Number of labeled simple graphs with n vertices contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments