cp's OEIS Frontend

A076263 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).

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