|
Search: id:A076263
|
|
|
| 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). |
|
+0
2
|
|
| 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; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
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 number of vertices (n>2).
|
|
LINKS
|
T. D. Noe, Rows 1 to 16 of triangle, flattened (from Gordon Royle's website)
Keith M. Briggs, Combinatorial Graph Theory.
Sriram V. Pemmaraju, Combinatorica 2.0
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
|
|
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))=6.
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
|
Index calculation for the current sequence: A000124. Number of connected graphs for given number of vertices: A001349. Number of connected graphs for given number of edges: A076265. Number of disconnected graphs for given number of vertices and edges: A076264. [The last two cross-references appear to be wrong! Perhaps A002905 is intended? - Keith Briggs (keith.briggs(AT)bt.com), Aug 26 2004
Number of entries in the n-th row is A001349. Row sums give A001349.
See A054924, which is the main entry for this triangle. Number of entries in the n-th row is A001349. Row sums give A001349.
Sequence in context: A135966 A060351 A076037 this_sequence A008302 A131791 A010358
Adjacent sequences: A076260 A076261 A076262 this_sequence A076264 A076265 A076266
|
|
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 (rgwv(AT)rgwv.com), Jun 21 2005
More terms from Keith Briggs (Keith.Briggs(AT)bt.com), Jun 28 2005
|
|
|
Search completed in 0.002 seconds
|
