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