|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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.
Starting each row from k=0 gives A054924, which is the main entry for this triangle.
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Arne Ring (arne.ring(AT)epost.de), Oct 03 2002
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|