A140638 - OEIS

A140638

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

0, 0, 0, 7, 381, 21748, 1781154, 249849880, 66257728763, 34495508486976, 35641629989151608, 73354595357480683904, 301272202621204113362497, 2471648811029413368450098688, 40527680937730440155535277704046, 1328578958335783199341353852258282496

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

OFFSET

1,4

COMMENTS

These are the connected graphs that are neither trees nor unicyclic.

Also connected non-choosable graphs covering n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The unlabeled version is A140636. The complement is counted by A129271. - Gus Wiseman, Feb 20 2024

REFERENCES

J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

LINKS

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

FORMULA

a(n) = A001187(n) - A129271(n).

a(n) = A001187(n) - A000272(n) - A057500(n).

MATHEMATICA

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}], Length[Intersection@@s[[#]]]>0&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];

Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[csm[#]]<=1&&Select[Tuples[#], UnsameQ@@#&]=={}&]], {n, 0, 5}] (* Gus Wiseman, Feb 19 2024 *)

PROG

(PARI) seq(n)={my(A=O(x*x^n), t=-lambertw(-x + A)); Vec(serlaplace( log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, A)) - log(1/(1-t))/2 - t/2 + 3*t^2/4), -n)} \\ Andrew Howroyd, Jan 15 2022

CROSSREFS

The unlabeled version is A140636.

Cf. A000272 (trees), A001187 (connected graphs), A057500 (connected unicyclic graphs).

The complement is counted by A129271, unlabeled A005703.

The non-connected complement is A133686, covering A367869.

The non-connected version is A367867, unlabeled A140637.

The non-connected covering version is A367868.

A006125 counts graphs, A000088 unlabeled.

A006129 counts covering graphs, A002494 unlabeled.

A143543 counts simple labeled graphs by number of connected components.

Cf. A001349, A116508, A355740, A367769, A367863, A367901, A367903, A370317.

Sequence in context: A027510 A354026 A232454 * A367868 A372814 A299036