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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008406 Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2). 69
1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 1, 2, 5, 9, 15, 21, 24, 24, 21, 15, 9, 5, 2, 1, 1, 1, 1, 2, 5, 10, 21, 41, 65, 97, 131, 148, 148, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1, 1, 1, 2, 5, 11, 24, 56, 115, 221, 402, 663, 980, 1312, 1557, 1646, 1557 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,10

COMMENTS

The index of 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 the pair {1,1} separates sublists for a given number of vertices (n>2)).

REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 264.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.

F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

LINKS

R. W. Robinson, Rows 1 to 20 of triangle, flattened

Leonid Bedratyuk, A new formula for the generating function of the numbers of simple graphs, arXiv:1512.06355 [math.CO], 2015.

FindStat - Combinatorial Statistic Finder, The number of edges of a graph.

R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) Table 65.

Sriram V. Pemmaraju, Combinatorica 2.0

Gordon Royle, Small graphs

S. S. Skiena, Generating graphs

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Overview of the 12 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 1

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 2

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 3

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 4

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 5

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 6

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 7

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 8

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 9

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 10

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 11

Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 12

James Turner, William H. Kautz, A survey of progress in graph theory in the Soviet Union SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 19.

Eric Weisstein's World of Mathematics, Connected Graph

Eric Weisstein's World of Mathematics, Simple Graph

A. E. Yurtsun, Principles of enumeration of the number of graphs, Ukrainian Mathematical Journal, January-February, 1967, Volume 19, Issue 1, pp 123-125, DOI 10.1007/BF01085184.

FORMULA

O.g.f. for n-th row: 1/n! Sum_g det(1-g z^2)/det(1-g z) where g runs through the natural matrix representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, Sep 23 2014

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,1,1,1,

1,1,2,3,2,1,1, [graphs with 4 nodes and from 0 to 6 edges]

1,1,2,4,6,6,6,4,2,1,1,

1,1,2,5,9,15,21,24,24,21,15,9,5,2,1,1,

1,1,2,5,10,21,41,65,97,131,148,148,131,97,65,41,21,10,5,2,1,1,

...

MAPLE

seq(seq(GraphTheory:-NonIsomorphicGraphs(v, e), e=0..v*(v-1)/2), v=1..9); # Robert Israel, Dec 22 2015

MATHEMATICA

<< Combinatorica`; Table[CoefficientList[GraphPolynomial[n, x], x], {n, 8}] // Flatten (* Eric W. Weisstein, Mar 20 2013 *)

<< Combinatorica`; Table[NumberOfGraphs[v, e], {v, 8}, {e, 0, Binomial[v, 2]}] // Flatten (* Eric W. Weisstein, May 17 2017 *)

PROG

(Sage)

def T(n, k):

    return len(list(graphs(n, size=k)))

# Ralf Stephan, May 30 2014

CROSSREFS

Row sums give A000088.

Cf. A046742, A046751, A000717, A001432, A001431, A001430, A001433, A001434, A048179, A048180 etc.

Cf. also A039735, A002905, A054924 (connected), A084546 (labeled graphs).

Index calculation for the current sequence: A000124; number of connected graphs for given number of vertices: A001349; number of graphs for given number of edges: A000664.

Cf. also A000055.

Sequence in context: A179008 A255252 A174985 * A039735 A283761 A171457

Adjacent sequences:  A008403 A008404 A008405 * A008407 A008408 A008409

KEYWORD

nonn,tabf,nice,look

AUTHOR

N. J. A. Sloane, Mar 15 1996

EXTENSIONS

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

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 December 11 19:09 EST 2017. Contains 295919 sequences.