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

Author

N. J. A. Sloane, Mar 15 1996

Keywords

• nonn
• tabf
• nice
• look

Comments

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]

Examples

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

References

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

Links

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

Crossrefs

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.

Programs

Maple

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

Mathematica

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

PARI

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

Sage

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

Formula

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

Extensions

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