A001434 - OEIS

A001434

Number of graphs with n nodes and n edges.
(Formerly M1653 N0647)

1, 0, 0, 1, 2, 6, 21, 65, 221, 771, 2769, 10250, 39243, 154658, 628635, 2632420, 11353457, 50411413, 230341716, 1082481189, 5228952960, 25945377057, 132140242356, 690238318754, 3694876952577, 20252697246580, 113578669178222, 651178533855913, 3813856010041981

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

The labeled version is A116508. - Gus Wiseman, Feb 22 2024

REFERENCES

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

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 1..40 from Sean A. Irvine)

CombOS - Combinatorial Object Server, Generate graphs

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.

EXAMPLE

From Gus Wiseman, Feb 22 2024: (Start)

Representatives of the a(0) = 1 through a(5) = 6 graphs:

{} . . {12,13,23} {12,13,14,23} {12,13,14,15,23}

{12,13,24,34} {12,13,14,23,24}

{12,13,14,23,25}

{12,13,14,23,45}

{12,13,14,25,35}

{12,13,24,35,45}

(End)

MATHEMATICA

(* first do *) Needs["Combinatorica`"] (* then *) Table[ NumberOfGraphs[n, n], {n, 24}] (* Robert G. Wilson v, Mar 22 2011 *)

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];

Table[Length[Union[brute /@ Subsets[Subsets[Range[n], {2}], {n}]]], {n, 0, 5}] (* Gus Wiseman, Feb 22 2024 *)

PROG

(PARI) a(n) = polcoef(G(n, O(x*x^n)), n) \\ G defined in A008406. - Andrew Howroyd, Feb 02 2024

CROSSREFS

The connected case is A001429, labeled A057500.

The covering case is A006649, labeled A367863.

Diagonal n = k of A008406.

The labeled version is A116508.

The version with loops is A368598, connected A368983.

Allowing up to n edges gives A370315, labeled A369192.

A000088 counts unlabeled graphs, labeled A006125.

A001349 counts unlabeled connected graphs, labeled A001187.