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

Author

Arne Ring (arne.ring(AT)epost.de), Oct 03 2002

Keywords

• nonn
• tabf

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

Examples

			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;
		

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.

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.

Programs

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}]

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