A000664 Number of graphs with n edges.

1, 1, 2, 5, 11, 26, 68, 177, 497, 1476, 4613, 15216, 52944, 193367, 740226, 2960520, 12334829, 53394755, 239544624, 1111261697, 5320103252, 26237509076, 133087001869, 693339241737, 3705135967663, 20286965943329, 113694201046379, 651571521170323, 3815204365835840, 22806847476040913, 139088381010541237, 864777487052916454

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

These are simple graphs, unlabeled, with no isolated nodes, but are not necessarily connected.

Examples

			n=1: o-o (1)
n=2: o-o o-o, o-o-o (2)
n=3: o-o o-o o-o, o-o-o o-o, o-o-o-o, Y, triangle (5)
n=4: o-o o-o o-o o-o, o-o-o o-o o-o, o-o-o o-o-o, o-o o-o-o-o, o-o Y, o-o triangle,
o-o-o-o-o, >o-o-o, ><, square, triangle with tail (11)
		

References

• W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Max Alekseyev, Table of n, a(n) for n = 0..60
• Nicolas Borie, The Hopf Algebra of graph invariants, arXiv preprint arXiv:1511.05843 [math.CO], 2015.
• P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
• Fran Herr and Legrand Jones II, Iterated Jump Graphs, arXiv:2205.01796 [math.CO], 2022.
• M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Overview of the 11 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 1
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 2
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 3
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 4
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 6
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 7
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 8
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 9
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 10
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 11

Crossrefs

Cf. A002905, A008406, A053418.

Row sums of A275421.

Cf. also A000088, A000055.

Programs

Mathematica

<< Combinatorica`; Table[NumberOfGraphs[2 n, n], {n, 0, 10}] (* Eric W. Weisstein, Oct 30 2017 *)
<< Combinatorica`; Table[Coefficient[GraphPolynomial[2 n, x], x, n], {n, 0, 10}] (* Eric W. Weisstein, Oct 30 2017 *)

Formula

a(n) = A008406(2*n,n). - Max Alekseyev, Sep 13 2016

Euler transform of A002905 (ignoring A002905(0)). - Franklin T. Adams-Watters Jul 03 2009

Extensions

More terms from Vladeta Jovovic, Jan 08 2000, Aug 14 2007

Edited by N. J. A. Sloane, Feb 26 2008

Example for n=2 corrected by Adrian Falcone (falcone(AT)gmail.com), Jan 28 2009

Zeroth term inserted by Franklin T. Adams-Watters, Jul 03 2009

a(25)-a(26) from Max Alekseyev, Sep 19 2009

a(27)-a(60) from Max Alekseyev, Sep 07 2016