# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a008406
Showing 1-1 of 1

%I A008406 #143 Jan 09 2024 16:55:55
%S A008406 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,
%T A008406 24,21,15,9,5,2,1,1,1,1,2,5,10,21,41,65,97,131,148,148,131,97,65,41,
%U A008406 21,10,5,2,1,1,1,1,2,5,11,24,56,115,221,402,663,980,1312,1557,1646,1557
%N 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).
%C A008406 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]
%D A008406 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 264.
%D A008406 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
%D A008406 F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
%D A008406 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
%D A008406 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
%D A008406 R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
%H A008406 R. W. Robinson, <a href="/A008406/b008406.txt">Rows 1 to 20 of triangle, flattened</a>
%H A008406 Leonid Bedratyuk, <a href="http://arxiv.org/abs/1512.06355">A new formula for the generating function of the numbers of simple graphs</a>, arXiv:1512.06355 [math.CO], 2015.
%H A008406 FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000081">The number of edges of a graph.</a>
%H A008406 R. J. Mathar, <a href="http://arxiv.org/abs/1709.09000">Statistics on Small Graphs</a>, arXiv:1709.09000 [math.CO] (2017) Table 65.
%H A008406 Sriram V. Pemmaraju, <a href="http://www.cs.uiowa.edu/~sriram/Combinatorica/index.html">Combinatorica 2.0</a>
%H A008406 Marko R. Riedel, <a href="http://math.stackexchange.com/questions/2187019/">Number of distinct connected digraphs</a>
%H A008406 Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/graphs/">Small graphs</a>
%H A008406 S. S. Skiena, <a href="http://www.cs.sunysb.edu/~algorith/files/generating-graphs.shtml">Generating graphs</a>
%H A008406 Peter Steinbach, <a href="/A008406/a008406.txt">Field Guide to Simple Graphs, Volume 2</a>, Overview of the 12 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H A008406 Peter Steinbach, <a href="/A008406/a008406_1.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 1
%H A008406 Peter Steinbach, <a href="/A008406/a008406_2.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 2
%H A008406 Peter Steinbach, <a href="/A008406/a008406_3.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 3
%H A008406 Peter Steinbach, <a href="/A008406/a008406_4.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 4
%H A008406 Peter Steinbach, <a href="/A008406/a008406_5.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 5
%H A008406 Peter Steinbach, <a href="/A008406/a008406_6.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 6
%H A008406 Peter Steinbach, <a href="/A008406/a008406_7.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 7
%H A008406 Peter Steinbach, <a href="/A008406/a008406_8.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 8
%H A008406 Peter Steinbach, <a href="/A008406/a008406_9.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 9
%H A008406 Peter Steinbach, <a href="/A008406/a008406_10.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 10
%H A008406 Peter Steinbach, <a href="/A008406/a008406_11.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 11
%H A008406 Peter Steinbach, <a href="/A008406/a008406_12.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 12
%H A008406 James Turner and William H. Kautz, <a href="http://dx.doi.org/10.1137/1012125">A survey of progress in graph theory in the Soviet Union</a> SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 19.
%H A008406 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>
%H A008406 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SimpleGraph.html">Simple Graph</a>
%H A008406 A. E. Yurtsun, <a href="http://dx.doi.org/10.1007/BF01085184">Principles of enumeration of the number of graphs</a>, Ukrainian Mathematical Journal, January-February, 1967, Volume 19, Issue 1, pp 123-125, DOI 10.1007/BF01085184.
%F A008406 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
%e A008406 Triangle begins:
%e A008406 1,
%e A008406 1,1,
%e A008406 1,1,1,1,
%e A008406 1,1,2,3,2,1,1, [graphs with 4 nodes and from 0 to 6 edges]
%e A008406 1,1,2,4,6,6,6,4,2,1,1,
%e A008406 1,1,2,5,9,15,21,24,24,21,15,9,5,2,1,1,
%e A008406 1,1,2,5,10,21,41,65,97,131,148,148,131,97,65,41,21,10,5,2,1,1,
%e A008406 ...
%p A008406 seq(seq(GraphTheory:-NonIsomorphicGraphs(v,e),e=0..v*(v-1)/2),v=1..9); # _Robert Israel_, Dec 22 2015
%t A008406 << Combinatorica`; Table[CoefficientList[GraphPolynomial[n, x], x], {n, 8}] // Flatten (* _Eric W. Weisstein_, Mar 20 2013 *)
%t A008406 << Combinatorica`; Table[NumberOfGraphs[v, e], {v, 8}, {e, 0, Binomial[v, 2]}] // Flatten (* _Eric W. Weisstein_, May 17 2017 *)
%t A008406 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];
%t A008406 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]}];
%t A008406 row[n_] := Module[{s = 0}, Do[s += permcount[p]*edges[p, 1 + x^#&], {p, IntegerPartitions[n]}]; s/n!] // Expand // CoefficientList[#, x]&;
%t A008406 Array[row, 8] // Flatten (* _Jean-François Alcover_, Jan 07 2021, after _Andrew Howroyd_ *)
%o A008406 (Sage)
%o A008406 def T(n,k):
%o A008406     return len(list(graphs(n, size=k)))
%o A008406 # _Ralf Stephan_, May 30 2014
%o A008406 (PARI)
%o A008406 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}
%o A008406 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)))}
%o A008406 G(n, A=0) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i+A)); s/n!}
%o A008406 { for(n=1, 7, print(Vecrev(G(n)))) } \\ _Andrew Howroyd_, Oct 22 2019, updated  Jan 09 2024
%Y A008406 Row sums give A000088.
%Y A008406 Cf. A046742, A046751, A000717, A001432, A001431, A001430, A001433, A001434, A048179, A048180 etc.
%Y A008406 Cf. also A039735, A002905, A054924 (connected), A084546 (labeled graphs).
%Y A008406 Row lengths: A000124; number of connected graphs for given number of vertices: A001349; number of graphs for given number of edges: A000664.
%Y A008406 Cf. also A000055.
%K A008406 nonn,tabf,nice,look
%O A008406 1,10
%A A008406 _N. J. A. Sloane_, Mar 15 1996
%E A008406 Additional comments from Arne Ring (arne.ring(AT)epost.de), Oct 03 2002
%E A008406 Text belonging in a different sequence deleted by _Peter Munn_, Mar 20 2021

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE