|
%I #55 Mar 20 2024 18:12:23
%S 1,1,1,1,2,2,1,1,3,5,5,4,2,1,1,6,13,19,22,20,14,9,5,2,1,1,11,33,67,
%T 107,132,138,126,95,64,40,21,10,5,2,1,1,23,89,236,486,814,1169,1454,
%U 1579,1515,1290,970,658,400,220,114,56,24,11,5,2,1,1,47,240,797,2075,4495
%N Triangle read by rows: T(n,k) = number of nonisomorphic connected graphs with n vertices and k edges (n >= 1, n-1 <= k <= n(n-1)/2).
%C The index of the T(n,k) in the sequence is ((n-2)^3 - n + 6*k + 8)/6.
%C T(n,k)=1 for k = n*(n-1)/2-1 and k = n*(n-1)/2 (therefore {1,1} separates sublists for given numbers of vertices (n > 2)).
%H T. D. Noe, <a href="/A076263/b076263.txt">Rows 1 to 16 of triangle, flattened</a> (from Gordon Royle's website)
%H Keith M. Briggs, <a href="http://keithbriggs.info/cgt.html">Combinatorial Graph Theory.</a>
%H Sriram V. Pemmaraju, <a href="https://homepage.divms.uiowa.edu/~sriram/Combinatorica/index.html">The Combinatorica Project</a>
%H Marko R. Riedel, <a href="http://math.stackexchange.com/questions/2187019/">Number of distinct connected digraphs</a>, Math StackExchange.
%H Marko Riedel, <a href="/A076263/a076263_2.maple.txt">Maple code for sequences A008406 and A076263 including cycle indices.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph.</a>
%e 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 = 5.
%e Triangle begins:
%e 1;
%e 1;
%e 1, 1;
%e 2, 2, 1, 1;
%e 3, 5, 5, 4, 2, 1, 1;
%e 6, 13, 19, 22, 20, 14, 9, 5, 2, 1, 1;
%e 11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1;
%t NumberOfConnectedGraphs[vertices_, edges_] := Plus @@ ConnectedQ /@ ListGraphs[vertices, edges] /. {True->1, False ->0}
%t (* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) Table[Plus @@ ConnectedQ /@ ListGraphs[Vert, i] /. {True -> 1, False -> 0}, {Vert, 8}, {i, Vert - 1, Vert*(Vert - 1)/2}]
%Y Row lengths (excluding first row): A000124. Number of connected graphs for given number of vertices: A001349. Number of connected graphs for given number of edges: A002905.
%Y Number of entries in the n-th row is A152947. Row sums give A001349.
%Y Starting each row from k=0 gives A054924, which is the main entry for this triangle.
%K nonn,tabf
%O 1,5
%A Arne Ring (arne.ring(AT)epost.de), Oct 03 2002
%E Corrected by _Keith Briggs_ and _Robert G. Wilson v_, May 01 2005
%E Rows 5, 6 & 7 from _Robert G. Wilson v_, Jun 21 2005
%E More terms from _Keith Briggs_, Jun 28 2005
%E Name corrected by _Andrey Zabolotskiy_, Nov 20 2017
|
