login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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)) = 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: A002905.

Number of entries in the n-th row is A152947. Row sums give A001349.

Transpose of A054924, which is the main entry for this triangle.

Sequence in context: A290252 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 (Keith.Briggs(AT)bt.com), Jun 28 2005

Name corrected by Andrey Zabolotskiy, Nov 20 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 16 09:54 EDT 2018. Contains 313791 sequences. (Running on oeis4.)