login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A140638 Number of connected graphs on n labeled nodes that contain at least two cycles. 31
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
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.
Sequence in context: A027510 A354026 A232454 * A367868 A299036 A112905
KEYWORD
nonn
AUTHOR
Washington Bomfim, May 21 2008
EXTENSIONS
Definition clarified by Andrew Howroyd, Jan 15 2022
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)