A076263 - OEIS

%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