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

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)

Keith M. Briggs, Combinatorial Graph Theory.

Sriram V. Pemmaraju, The Combinatorica Project

Marko R. Riedel, Number of distinct connected digraphs, Math StackExchange.

Marko Riedel, Maple code for sequences A008406 and A076263 including cycle indices.

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

Adjacent sequences: A076260 A076261 A076262 * 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, Jun 21 2005

More terms from Keith Briggs, Jun 28 2005

Name corrected by Andrey Zabolotskiy, Nov 20 2017

Status

approved