A140636 Number of connected graphs on n unlabeled nodes that contain at least two cycles.

0, 0, 0, 2, 13, 93, 809, 11005, 260793, 11715808, 1006698524, 164059824899, 50335907853919, 29003487462805642, 31397381142761123838, 63969560113225175845492, 245871831682084026518599099, 1787331725248899088890197955308, 24636021429399867655322650752269938

Offset

1,4

Comments

Original name: number of unlabeled complex components with n nodes.

We can find in "The Birth of the Giant Component", p. 2, see the first link:

"As each of the random graphs evolved, the story went, never once was there more than a single 'complex' component; i.e. there never were two or more components present simultaneously that were neither trees nor unicyclic."

So a complex component is a connected graph that is neither a tree nor an unicyclic graph.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..50

Svante Janson, Donald E. Knuth, Tomasz Luczak and Boris Pittel, The Birth of the Giant Component, [DOI], Rand. Struct. Alg. 4 (3) (1993) 233-358

N. J. A. Sloane, Illustration of initial terms of A001349.

Formula

a(n) = A001349(n) - A005703(n).

a(n) = A001349(n) - A000055(n) - A001429(n).

Example

a(4) = 2. See the two complex components with 4 nodes in the Sloane illustration.

Crossrefs

The labeled version is A140638.

Cf. A001349, A000055, A001429, A005703.

Sequence in context: A199489 A300764 A209470 * A369413 A282724 A104255

Adjacent sequences: A140633 A140634 A140635 * A140637 A140638 A140639

Keyword

nonn

Author

Washington Bomfim, May 20 2008

Extensions

Name changed by Andrew Howroyd, Jan 16 2022

Status

approved