A140638 - OEIS

%I #26 Feb 21 2024 22:48:35

%S 0,0,0,7,381,21748,1781154,249849880,66257728763,34495508486976,

%T 35641629989151608,73354595357480683904,301272202621204113362497,

%U 2471648811029413368450098688,40527680937730440155535277704046,1328578958335783199341353852258282496

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

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

%C 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

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

%H Andrew Howroyd, <a href="/A140638/b140638.txt">Table of n, a(n) for n = 1..50</a>

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

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

%t 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]]]]]]]]];

%t 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 *)

%o (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

%Y The unlabeled version is A140636.

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

%Y The complement is counted by A129271, unlabeled A005703.

%Y The non-connected complement is A133686, covering A367869.

%Y The non-connected version is A367867, unlabeled A140637.

%Y The non-connected covering version is A367868.

%Y A006125 counts graphs, A000088 unlabeled.

%Y A006129 counts covering graphs, A002494 unlabeled.

%Y A143543 counts simple labeled graphs by number of connected components.

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

%K nonn

%O 1,4

%A _Washington Bomfim_, May 21 2008

%E Definition clarified by _Andrew Howroyd_, Jan 15 2022