A000088 -id:A000088 - cp's OEIS frontend

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

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

A000666 Number of symmetric relations on n nodes.

Original entry on oeis.org

1, 2, 6, 20, 90, 544, 5096, 79264, 2208612, 113743760, 10926227136, 1956363435360, 652335084592096, 405402273420996800, 470568642161119963904, 1023063423471189431054720, 4178849203082023236058229792, 32168008290073542372004082199424

Offset: 0

N. J. A. Sloane

Each node may or may not be related to itself.
Also the number of rooted graphs on n+1 nodes.
The 1-to-1 correspondence is as follows: Given a rooted graph on n+1 nodes, replace each edge joining the root node to another node with a self-loop at that node and erase the root node. The result is an undirected graph on n nodes which is the graph of the symmetric relation.
Also the number of the graphs with n nodes whereby each node is colored or not colored. A loop can be interpreted as a colored node. - Juergen Will, Oct 31 2011

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 101, 241.
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, Sept. 15, 1955, pp. 14-22.
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).

David Applegate, Table of n, a(n) for n = 0..80 [Shortened file because terms grow rapidly: see Applegate link below for additional terms]
David Applegate, Table of n, a(n) for n = 0..100
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
R. L. Davis, Structure of dominance relations, Bull. Math. Biophys., 16 (1954), 131-140. [Annotated scanned copy]
F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Am. Math. Soc. 78 (1955) 445-463, eq. (24).
Frank Harary, Edgar M. Palmer, Robert W. Robinson and Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
Adib Hassan, Po-Chien Chung and Wayne B. Hayes, Graphettes: Constant-time determination of graphlet and orbit identity including (possibly disconnected) graphlets up to size 8, arXiv:1708.04341 [cs.DS], 2017.
Mathematics Stack Exchange, Enumerating Graphs with Self-Loops, Jan 23 2014.
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]
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
W. Oberschelp, The number of non-isomorphic m-graphs, Presented at Mathematical Institute Oberwolfach, July 3 1967 [Scanned copy of manuscript]
W. Oberschelp, Strukturzahlen in endlichen Relationssystemen, in Contributions to Mathematical Logic (Proceedings 1966 Hanover Colloquium), pp. 199-213, North-Holland Publ., Amsterdam, 1968. [Annotated scanned copy]
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Marko Riedel, Maple code for sequence.
Marko Riedel et al., Enumerating Graphs with Self-Loops
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout
Sage, Common Graphs (Graph Generators)
Lorenzo Sauras-Altuzarra, Graphs
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
Eric Weisstein's World of Mathematics, Rooted Graph

Cf. A000595, A001172, A001174, A006905, A000250, A054921 (connected relations).

Maple
```
# see Riedel link above
```

Join[{1,2}, Table[CycleIndex[Join[PairGroup[SymmetricGroup[n]], Permutations[Range[n*(n-1)/2+1, n*(n+1)/2]], 2],s] /. Table[s[i]->2, {i,1,n^2-n}], {n,2,8}]] (* Geoffrey Critzer, Nov 04 2011 *)
Table[Module[{eds,pms,leq},
eds=Select[Tuples[Range[n],2],OrderedQ];
pms=Map[Sort,eds/.Table[i->Part[#,i],{i,n}]]&/@Permutations[Range[n]];
leq=Function[seq,PermutationCycles[Ordering[seq],Length]]/@pms;
Total[Thread[Power[2,leq]]]/n!
],{n,0,8}] (* This is after Geoffrey Critzer's program but does not use the (deprecated) Combinatorica package. - Gus Wiseman, Jul 21 2016 *)
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[Sum[GCD[v[[i]], v[[j]]], {j, 1, i-1}], {i, 2, Length[v]}] + Sum[Quotient[v[[i]], 2] + 1, {i, 1, Length[v]}];
a[n_] := a[n] = (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 17}] (* Jean-François Alcover, Nov 13 2017, 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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2 + 1)}
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 A000666(n): return int(sum(Fraction(1<>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

Euler transform of A054921. - N. J. A. Sloane, Oct 25 2018
Let G_{n+1,k} be the number of rooted graphs on n+1 nodes with k edges and let G_{n+1}(x) = Sum_{k=0..n(n+1)/2} G_{n+1,k} x^k. Thus a(n) = G_{n+1}(1). Let S_n(x_1, ..., x_n) denote the cycle index for Sym_n. (cf. the link in A000142).
Compute x_1*S_n and regard it as the cycle index of a set of permutations on n+1 points and find the corresponding cycle index for the action on the n(n+1)/2 edges joining those points (the corresponding "pair group"). Finally, by replacing each x_i by 1+x^i gives G_{n+1}(x). [Harary]
Example, n=2. S_2 = (1/2)*(x_1^2+x_2), x_1*S_2 = (1/2)*(x_1^3+x_1*x_2). The pair group is (1/2)*(x_1^2+x_1*x_2) and so G_3(x) = (1/2)*((1+x)^3+(1+x)*(1+x^2)) = 1+2*x+2*x^2+x^3; set x=1 to get a(2) = 6.
a(n) ~ 2^(n*(n+1)/2)/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016

Description corrected by Christian G. Bower
More terms from Vladeta Jovovic, Apr 18 2000
Entry revised by N. J. A. Sloane, Mar 06 2007

A000664 Number of graphs with n edges.

Original entry on oeis.org

1, 1, 2, 5, 11, 26, 68, 177, 497, 1476, 4613, 15216, 52944, 193367, 740226, 2960520, 12334829, 53394755, 239544624, 1111261697, 5320103252, 26237509076, 133087001869, 693339241737, 3705135967663, 20286965943329, 113694201046379, 651571521170323, 3815204365835840, 22806847476040913, 139088381010541237, 864777487052916454

Offset: 0

N. J. A. Sloane

These are simple graphs, unlabeled, with no isolated nodes, but are not necessarily connected.

			n=1: o-o (1)
n=2: o-o o-o, o-o-o (2)
n=3: o-o o-o o-o, o-o-o o-o, o-o-o-o, Y, triangle (5)
n=4: o-o o-o o-o o-o, o-o-o o-o o-o, o-o-o o-o-o, o-o o-o-o-o, o-o Y, o-o triangle,
o-o-o-o-o, >o-o-o, ><, square, triangle with tail (11)

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
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).

Max Alekseyev, Table of n, a(n) for n = 0..60
Nicolas Borie, The Hopf Algebra of graph invariants, arXiv preprint arXiv:1511.05843 [math.CO], 2015.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Fran Herr and Legrand Jones II, Iterated Jump Graphs, arXiv:2205.01796 [math.CO], 2022.
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Overview of the 11 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 11

Cf. A002905, A008406, A053418.
Row sums of A275421.
Cf. also A000088, A000055.

<< Combinatorica`; Table[NumberOfGraphs[2 n, n], {n, 0, 10}] (* Eric W. Weisstein, Oct 30 2017 *)
<< Combinatorica`; Table[Coefficient[GraphPolynomial[2 n, x], x, n], {n, 0, 10}] (* Eric W. Weisstein, Oct 30 2017 *)

a(n) = A008406(2*n,n). - Max Alekseyev, Sep 13 2016

Euler transform of A002905 (ignoring A002905(0)). - Franklin T. Adams-Watters Jul 03 2009

More terms from Vladeta Jovovic, Jan 08 2000, Aug 14 2007
Edited by N. J. A. Sloane, Feb 26 2008
Example for n=2 corrected by Adrian Falcone (falcone(AT)gmail.com), Jan 28 2009
Zeroth term inserted by Franklin T. Adams-Watters, Jul 03 2009
a(25)-a(26) from Max Alekseyev, Sep 19 2009
a(27)-a(60) from Max Alekseyev, Sep 07 2016

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 18, 14, 5, 1, 0, 1, 12, 35, 39, 21, 6, 1, 0, 1, 16, 62, 97, 72, 30, 7, 1, 0, 1, 20, 103, 212, 214, 120, 40, 8, 1, 0, 1, 25, 161, 429, 563, 416, 185, 52, 9, 1, 0, 1, 30, 241, 804, 1344, 1268, 732, 270, 65, 10, 1, 0

Offset: 1

Christian G. Bower, May 09 2000

Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - Michael Somos, Nov 02 2014

			From _Joerg Arndt_, Aug 18 2014: (Start)
Triangle starts:
01: 1
02: 1    0
03: 1    1    0
04: 1    2    1    0
05: 1    4    3    1    0
06: 1    6    8    4    1    0
07: 1    9   18   14    5    1    0
08: 1   12   35   39   21    6    1    0
09: 1   16   62   97   72   30    7    1    0
10: 1   20  103  212  214  120   40    8    1    0
11: 1   25  161  429  563  416  185   52    9    1    0
12: 1   30  241  804 1344 1268  732  270   65   10    1    0
13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0
...
The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 2 3 4 ]   1
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]   2
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]   2
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]   2
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]   3
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]   3
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]   2
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]   3
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]   4
:  O--o
:  .--o
:  .--o
:  .--o
:
This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
(End)
G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).

F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees

Row sums give A000081.
Columns 2 through 12: A002620(n-1), A055278-A055287.
Cf. A055288, A055289, A055290.
Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* Gus Wiseman, Mar 19 2018 *)

{T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - Michael Somos, Nov 02 2014
Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015

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

A000112 Number of partially ordered sets ("posets") with n unlabeled elements.

Original entry on oeis.org

1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, 46749427, 1104891746, 33823827452, 1338193159771, 68275077901156, 4483130665195087

Offset: 0

N. J. A. Sloane

Also number of fixed effects ANOVA models with n factors, which may be both crossed and nested.

			R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, page 98, Fig. 3-1 (or 2nd. ed., Fig. 3.1, p. 243) shows the unlabeled posets with <= 4 points.
From _Gus Wiseman_, Aug 14 2019: (Start)
Also the number of unlabeled T_0 topologies with n points. For example, non-isomorphic representatives of the a(4) = 16 topologies are:
  {}{1}{12}{123}{1234}
  {}{1}{2}{12}{123}{1234}
  {}{1}{12}{13}{123}{1234}
  {}{1}{12}{123}{124}{1234}
  {}{1}{2}{12}{13}{123}{1234}
  {}{1}{2}{12}{123}{124}{1234}
  {}{1}{12}{13}{123}{124}{1234}
  {}{1}{2}{12}{13}{123}{124}{1234}
  {}{1}{2}{12}{13}{123}{134}{1234}
  {}{1}{2}{3}{12}{13}{23}{123}{1234}
  {}{1}{2}{12}{13}{24}{123}{124}{1234}
  {}{1}{12}{13}{14}{123}{124}{134}{1234}
  {}{1}{2}{3}{12}{13}{23}{123}{124}{1234}
  {}{1}{2}{12}{13}{14}{123}{124}{134}{1234}
  {}{1}{2}{3}{12}{13}{14}{23}{123}{124}{134}{1234}
  {}{1}{2}{3}{4}{12}{13}{14}{23}{24}{34}{123}{124}{134}{234}{1234}
(End)

G. Birkhoff, Lattice Theory, 1961, p. 4.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.
E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date.
J. L. Davison, Asymptotic enumeration of partial orders. Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986). Congr. Numer. 53 (1986), 277--286. MR0885256 (88c:06001)
E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, pages 96ff; Vol. I, 2nd. ed., Chap. 3, pp. 241ff; Vol. 2, Problem 5.39, p. 88.
For further references concerning the enumeration of topologies and posets see under A001035.

David Wasserman, Table of n, a(n) for n = 0..16
R. Bayon, N. Lygeros, and J.-S. Sereni, New progress in enumeration of mixed models, Applied Mathematics E-Notes, 5 (2005), 60-65.
R. Bayon, N. Lygeros, and J.-S. Sereni, Nouveaux progrès dans l'énumération des modèles mixtes, in Knowledge discovery and discrete mathematics: JIM'2003, INRIA, Université de Metz, France, 2003, pp. 243-246.
Gunnar Brinkmann and Brendan D. McKay, Counting unlabeled topologies and transitive relations.
G. Brinkmann and B. D. McKay, Counting unlabeled topologies and transitive relations, J. Integer Sequences, Volume 8, 2005.
G. Brinkmann and B. D. McKay, Posets on up to 16 Points [On Brendan McKay's home page]
G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179.
Kim Ki-Hang Butler, The number of partially ordered sets, Journal of Combinatorial Theory, Series B 13.3 (1972): 276-289.
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]
Kim Ki-Hang Butler and Gaoacs Markowsky. The number of partially ordered sets. II., J. Korean Math. Soc 11 (1974): 7-17.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
C. Chaunier, Letter to N. J. A. Sloane, Jun 22 1993, with several attachments
C. Chaunier and N. Lygeros, The Number of Orders with Thirteen Elements, Order 9:3 (1992) 203-204. [See Chaunier letter]
C. Chaunier and N. Lygeros, Le nombre de posets à isomorphie près ayant 12 éléments Theoretical Computer Science, 123 p. 89-94, 1994.
C. Chaunier and N. Lygeros, Progrès dans l'énumération des posets, C. R. Acad. Sci. Paris 314 série I (1992) 691-694. [See Chaunier letter]
E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date [Annotated scanned copy]
Gábor Czédli, Minimum-sized generating sets of the direct powers of free distributive lattices, arXiv:2309.13783 [math.CO], 2023. See p. 14. See also CUBO, A Mathematical Journal, Vol. 26, no. 2, pp. 217-237, August 2024.
M. Erné and K. Stege, The number of partially ordered (labeled) sets, Preprint, 1989. (Annotated scanned copy)
Uli Fahrenberg, Christian Johansen, Georg Struth, and Ratan Bahadur Thapa, Generating Posets Beyond N, arXiv:1910.06162 [cs.FL], 2019.
S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
FindStat - Combinatorial Statistic Finder, Posets
R. Fraisse and N. Lygeros, Petits posets: dénombrement, représentabilité par cercles et compenseurs C. R. Acad. Sci. Paris, 313, I, 417-420, 1991.
E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961. [Annotated scanned copy]
G. Grekos, Letter to N. J. A. Sloane, Oct 31 1994, with attachments
M. Guay-Paquet, A modular relation for the chromatic symmetric functions of (3+1)-free posets, arXiv preprint arXiv:1306.2400 [math.CO], 2013.
Ann Marie Hess, Mixed Models Site
C. Joslyn, E. Hogan, and A. Pogel, Conjugacy and Iteration of Standard Interval Rank in Finite Ordered Sets, arXiv preprint arXiv:1409.6684 [math.CO], 2014.
Dongseok Kim, Young Soo Kwon, and Jaeun Lee, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550 [math.CO], 2012.
D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975) 205-220.
N. Lygeros, Calculs exhaustifs sur les posets d'au plus 7 éléments, SINGULARITE, vol. 2 n4 p. 10-24, avril 1991.
N. Lygeros and P. Zimmermann, Computation of P(14), the number of posets with 14 elements: 1.338.193.159.771
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Bob Proctor, Chapel Hill Poset Atlas
D. Rusin, Further information and references [Broken link]
D. Rusin, Further information and references [Cached copy]
Henry Sharp, Jr., Quasi-orderings and topologies on finite sets, Proceedings of the American Mathematical Society 17.6 (1966): 1344-1349. [Annotated scanned copy]
N. J. A. Sloane, List of sequences related to partial orders, circa 1972
N. J. A. Sloane, Classic Sequences
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Szilárd Szalay, The classification of multipartite quantum correlation, arXiv:1806.04392 [quant-ph], 2018.
N. L. White, Two letters to N. J. A. Sloane, 1970, with hand-drawn enclosure
J. A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970 [Annotated scanned copy]
J. A. Wright, Two related abstracts, 1970 and 1972 [Annotated scanned copies]
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
Stav Zalel, Covariant Growth Dynamics, arXiv:2302.10582 [gr-qc], 2023.
Index entries for sequences related to posets
Index entries for "core" sequences

Cf. A000798 (labeled topologies), A001035 (labeled posets), A001930 (unlabeled topologies), A006057.
Cf. A079263, A079265, A065066 (refined by maximal elements), A342447 (refined by number of arcs).
Row sums of A263859. Euler transform of A000608.
Cf. A316978, A319559, A326939, A326943, A326944, A326947.

a(15)-a(16) are from Brinkmann's and McKay's paper. - Vladeta Jovovic, Jan 04 2006

A005195 Number of forests with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, 8599, 20514, 49905, 122963, 307199, 775529, 1977878, 5086638, 13184156, 34402932, 90328674, 238474986, 632775648, 1686705630, 4514955632, 12132227370, 32717113805, 88519867048, 240235675303

Offset: 0

N. J. A. Sloane

Same as "Number of forests with n nodes that are perfect graphs" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015

Number of unlabeled acyclic graphs on n vertices. The labeled version is A001858. The covering case is A144958, connected A000055. - Gus Wiseman, Apr 29 2024

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 10 forests:
  {}  {}  {}    {}       {}          {}
          {12}  {12}     {12}        {12}
                {13,23}  {12,34}     {12,34}
                         {13,23}     {13,23}
                         {13,24,34}  {12,35,45}
                         {14,24,34}  {13,24,34}
                                     {14,24,34}
                                     {13,24,35,45}
                                     {14,25,35,45}
                                     {15,25,35,45}
(End)

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Forest.
Index entries for sequences related to forests

Cf. A095133 (by number of trees), A136605 (by number of edges).
A diagonal of A144215.
The connected case is A000055.
The labeled version is A001858.
The covering case is A144958, labeled A105784.
For triangles instead of cycles we have A006785, covering A372169.
Unique cycle: A236570 (labeled A372193), covering A372191 (labeled A372195).
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A000272, A002807, A054548, A137917, A367863, A372176.

EulerTransform[ seq_List ] := With[{m = Length[seq]}, CoefficientList[ Series[ Times @@ (1/(1 - x^Range[m])^seq), {x, 0, m}], x]];
b[n_] := b[n] = If[n <= 1, n, Sum[ Sum[ d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}]/(n - 1)];
a55[n_] := a55[n] = If[n == 0, 1, b[n] - (Sum[ b[k]*b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; A000055 = Table[ a55[n], {n, 1, 31}]; EulerTransform[ A000055 ] (* Jean-François Alcover, Mar 15 2012 *)

Euler transform of A000055: Product_{n>0} (1-x^n)^(-A000055(n)). a(n) = 1/n*Sum_{k=1..n} b(k)*a(n-k), where b(k) = Sum_{d divides k} d*A000055(d). - Vladeta Jovovic, Sep 05 2002
G.f.: exp(sum_{k>0} B(x^k)/k ), where B(x) = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + ... = C(x)-1 and C is the g.f. for A000055.
a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.9557652856519949747148..., c = 1.023158422... . - Vaclav Kotesovec, Nov 16 2014
First differences are A144958. - Gus Wiseman, Apr 29 2024

More terms from Vladeta Jovovic, Sep 05 2002

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

A116508 a(n) = C( C(n,2), n).

Original entry on oeis.org

1, 0, 0, 1, 15, 252, 5005, 116280, 3108105, 94143280, 3190187286, 119653565850, 4922879481520, 220495674290430, 10682005290753420, 556608279578340080, 31044058215401404845, 1845382436487682488000, 116475817125419611477660, 7779819801401934344268210

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Mar 21 2006

a(n) is the number of simple labeled graphs with n nodes and n edges. - Geoffrey Critzer, Nov 02 2014

These graphs are not necessarily covering, but the covering case is A367863, unlabeled A006649, and the unlabeled version is A001434. - Gus Wiseman, Dec 22 2023

			a(5) = C(C(5,2),5) = C(10,5) = 252.

Alois P. Heinz, Table of n, a(n) for n = 0..370

Main diagonal of A084546.
The unlabeled version is A001434, covering case A006649.
The connected case is A057500, unlabeled A001429.
For set-systems we have A136556, covering case A054780.
The covering case is A367863.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A133686 counts graphs satisfying a strict AOC, connected A129271.
A367867 counts graphs contradicting a strict AOC, connected A140638.
Cf. A001187, A003465, A143543, A305000, A367916, A367917.

[0] cat [(Binomial(Binomial(n+2, n), n+2)): n in [0..20]]; // Vincenzo Librandi, Nov 03 2014

a:= n-> binomial(binomial(n, 2), n):
seq(a(n), n=0..20);

nn = 18; f[x_, y_] :=
Sum[(1 + y)^Binomial[n, 2] x^n/n!, {n, 1, nn}]; Table[
n! Coefficient[Series[f[x, y], {x, 0, nn}], x^n y^n], {n, 1, nn}] (* Geoffrey Critzer, Nov 02 2014 *)
Table[Length[Subsets[Subsets[Range[n],{2}],{n}]],{n,0,5}] (* Gus Wiseman, Dec 22 2023 *)
Table[SeriesCoefficient[(1 + x)^(n*(n-1)/2), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Aug 06 2025 *)

from math import comb
def A116508(n): return comb(n*(n-1)>>1,n) # Chai Wah Wu, Jul 02 2024

[(binomial(binomial(n+2,n),n+2)) for n in range(-1, 17)] # Zerinvary Lajos, Nov 30 2009

a(n) ~ exp(n - 2) * n^(n - 1/2) / (sqrt(Pi) * 2^(n + 1/2)). - Vaclav Kotesovec, May 19 2020

a(n) = [x^n] (1+x)^(n*(n-1)/2). - Vaclav Kotesovec, Aug 06 2025

a(0)=1 prepended by Alois P. Heinz, Feb 02 2024

cp's OEIS Frontend

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

A000666 Number of symmetric relations on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A000664 Number of graphs with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Examples

Links