|
|
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
|
|
|
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 non-connected covering version is A367868.
A143543 counts simple labeled graphs by number of connected components.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|