A000717 -id:A000717 - 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

A331505 Number of labeled graphs with n nodes and floor(n/2) edges.

Original entry on oeis.org

1, 1, 3, 15, 45, 455, 1330, 20475, 58905, 1221759, 3478761, 90858768, 256851595, 8093990190, 22760723700, 840261910995, 2353351951665, 99615373765775, 278110855548955, 13278694407181203, 36976937738226486

Offset: 1

Washington Bomfim, Jan 18 2020

Considering the permutation model of graph evolution (see the Flajolet reference) with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at the critical point n is Pp(n) = A302112(n)/a(2n). Note that a(2n) is the number of labeled graphs with 2n nodes and n edges.
Since a(2n) = C(C(2n, 2), n) we have Pp(n)= A302112(n)/C(C(2n, 2), n).
Therefore, by Vaclav Kotesovec's approximation in A302112, Pp(n) ~ e^(3/4) * P(n), where P(n) = c1 / n^(1/6) is the corresponding probability in the uniform model. Cf. A331500.
If t < n, P(n) is a lower bound of P(t). If t > n, P(n) is an upper bound of P(t). Here P(t) is the probability of an acyclic graph in time t.
Concerning the permutation model, the presence of cycles in graphs evolving near the critical time should be estimated by the above approximation.

			a(4) is 15 because for n = 4, floor(n/2) = 2, and there are two graphs with four points and two edges. See the figure below or the J. Riordan reference.
The non-isomorphic graphs with four nodes and two edges along with the corresponding number of labeled graphs are as follows:
.
  *--*     *  *
  |        |  |
  |        |  |
  *  *     *  *
   12        3
Pp(2) = A302112(2)/a(4) = 15/15 = 1. All the graphs with four nodes and two edges are acyclic.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 109.

Washington Bomfim, Approximation of Pp(n)
P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.
Carlos R. Lucatero, Combinatorial Enumeration of Graphs.

Cf. A000717, A084546, A331504, A302112 (numerators of Pp(n)), A331500, A331501.

C(x, y) = binomial(x, y);
a(n) = C(C(n,2), n\2);
A302112(n)={my(S=0, j); /* From Jon E. Schoenfield's formula in A302112. */
for(j = 0, n,
   S+=(-1/2)^j* C(n, j) * C(2*n-1, n+j-1) * (2*n)^(n-j) * (n+j)!
   );
(1/n!)*S
}; /* end A302112(n) */
c1 = (2/3)^(1/3) * sqrt(Pi) / gamma(1/3);
UpBoundP(n) = c1 / n^(1/6);            /* Approximation for P(n) */
UpBoundPp(n) = exp(3/4) * UpBoundP(n); /* Approximation for Pp(n) */
Pp(n) = A302112(n)/a(2*n);
Ratio(n) = UpBoundPp(n) / Pp(n);

a(n) = C( C(n,2), floor(n/2) ).

A371161 Maximum number of unlabeled graphs with at most n nodes such that neither one is a subgraph of another.

Original entry on oeis.org

1, 1, 1, 2, 3, 7, 26, 157, 1687

Offset: 0

Max Alekseyev, Mar 13 2024

Width of the poset of unlabeled graphs of order at most n with the subgraph relationship.

a(n) >= A000717(n).

Cf. A000717, A006897, A371162.

A331504 Number of labeled graphs with n nodes and floor(n*(n-1)/4) edges.

Original entry on oeis.org

1, 1, 3, 20, 252, 6435, 352716, 40116600, 9075135300, 4116715363800, 3824345300380220, 7219428434016265740, 27217014869199032015600, 205397724721029574666088520, 3136262529306125724764953838760

Offset: 1

Washington Bomfim, Jan 18 2020

nonn

The expected number of edges of a random graph is n*(n - 1)/4. [See the Cieslik reference.]

			a(4) is 20 because for n=4, floor(n*(n-1)/4) = 3, and there are A000717(4) = 3 graphs with four points and three edges. See figure below or J. Riordan reference.
The non-isomorphic graphs with four nodes and three edges along with the corresponding number of labeled graphs are as follows:
.
  *--*     *--*        *
  | /      |           |
  |/ *     |           |
  *        *--*     *--*--*
   4        12         4

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 109.

Dietmar Cieslik, Counting Networks.
Carlos R. Lucatero, Combinatorial Enumeration of Graphs.

Cf. A000717 ("unlabeled case"), A084546.

a(n) = binomial(binomial(n,2), n*(n-1)\4);

a(n) = binomial(binomial(n,2), floor(n*(n-1)/4)).

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

A331505 Number of labeled graphs with n nodes and floor(n/2) edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A371161 Maximum number of unlabeled graphs with at most n nodes such that neither one is a subgraph of another.

Views

Author

Keywords

Comments

Crossrefs

A331504 Number of labeled graphs with n nodes and floor(n*(n-1)/4) edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A054927 Number of connected unlabeled graphs having n nodes and ceiling(n(n-1)/4) edges such that the complement is also connected.

Views

Author

Keywords

Comments

Links

Formula

Extensions