VOOZH about

URL: https://oeis.org/A076263

⇱ A076263 - OEIS

login
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).
3
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, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1, 23, 89, 236, 486, 814, 1169, 1454, 1579, 1515, 1290, 970, 658, 400, 220, 114, 56, 24, 11, 5, 2, 1, 1, 47, 240, 797, 2075, 4495
OFFSET
1,5
COMMENTS
The index of the T(n,k) in the sequence is ((n-2)^3 - n + 6*k + 8)/6.
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)).
LINKS
T. D. Noe, Rows 1 to 16 of triangle, flattened (from Gordon Royle's website)
Sriram V. Pemmaraju, The Combinatorica Project
Marko R. Riedel, Number of distinct connected digraphs, Math StackExchange.
Eric Weisstein's World of Mathematics, Connected Graph.
EXAMPLE
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.
Triangle begins:
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, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1;
MATHEMATICA
NumberOfConnectedGraphs[vertices_, edges_] := Plus @@ ConnectedQ /@ ListGraphs[vertices, edges] /. {True->1, False ->0}
(* 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}]
CROSSREFS
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.
Number of entries in the n-th row is A152947. Row sums give A001349.
Starting each row from k=0 gives A054924, which is the main entry for this triangle.
Sequence in context: A344567 A076037 A215563 * A272689 A274887 A008302
KEYWORD
nonn,tabf
AUTHOR
Arne Ring (arne.ring(AT)epost.de), Oct 03 2002
EXTENSIONS
Corrected by Keith Briggs and Robert G. Wilson v, May 01 2005
Rows 5, 6 & 7 from Robert G. Wilson v, Jun 21 2005
More terms from Keith Briggs, Jun 28 2005
Name corrected by Andrey Zabolotskiy, Nov 20 2017
STATUS
approved