This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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). 70
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,10 COMMENTS The index of T(n,k) in the sequence is ((n-2)^3-n+6*k+8)/6. T(n,k)=1 for k=n*(n-1)/2-1 and k=n*(n-1)/2 (therefore the pair {1,1} separates sublists for a given number of vertices (n>2)). 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 (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, 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 There are 2 connected graphs with 4 vertices and 3 edges up to isomorphy (first graph: ((1,2),(2,3),(3,4)); second graph: (1,2),(1,3),(1,4)). Index within the sequence is ((4-2)^3 - 4 + 6*3 + 8)/6 = 6. 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 *) PROG (Sage) def T(n, k):     return len(list(graphs(n, size=k))) # Ralf Stephan, May 30 2014 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). Index calculation for the current sequence: A000124; number of connected graphs for given number of vertices: A001349; number of graphs for given number of edges: A000664. Cf. also A000055. Sequence in context: A179008 A255252 A174985 * A039735 A283761 A171457 Adjacent sequences:  A008403 A008404 A008405 * A008407 A008408 A008409 KEYWORD nonn,tabf,nice,look AUTHOR N. J. A. Sloane, Mar 15 1996 EXTENSIONS Additional comments from Arne Ring (arne.ring(AT)epost.de), Oct 03 2002 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 20 10:20 EDT 2018. Contains 313915 sequences. (Running on oeis4.)