OFFSET
1,10
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]
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.
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
EXAMPLE
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,
...
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 *)
PROG
(Sage)
def T(n, k):
return len(list(graphs(n, size=k)))
# Ralf Stephan, May 30 2014
(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
CROSSREFS
KEYWORD
AUTHOR
N. J. A. Sloane, Mar 15 1996
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
STATUS
approved