cp's OEIS Frontend

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

%I A370318 #18 Mar 29 2025 07:09:28
%S A370318 0,0,0,1,19,307,5237,99137,2098946,49504458,1291570014,37002273654,
%T A370318 1156078150969,39147186978685,1428799530304243,55933568895261791,
%U A370318 2338378885159906196,103995520598384132516,4903038902046860966220,244294315694676224001852,12827355456239840407125363
%N A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.
%C A370318 The case of an empty edge set is excluded.
%H A370318 Andrew Howroyd, <a href="/A370318/b370318.txt">Table of n, a(n) for n = 0..100</a>
%F A370318 Binomial transform of A057500 (if the null graph is not connected).
%F A370318 a(n) = n!*[x^n][y^n] exp(x*y)*(-x + log(Sum_{k>=0} (1 + y)^binomial(k, 2)*x^k/k!)). - _Andrew Howroyd_, Feb 19 2024
%t A370318 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 A370318 Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Length[#]==Length[Union@@#] && Length[csm[#]]==1&]],{n,0,5}]
%o A370318 (PARI) \\ Compare A370317; use A057500 for efficiency.
%o A370318 a(n)=n!*polcoef(polcoef(exp(x*y + O(x*x^n))*(-x+log(sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2)*x^k/k!, O(x*x^n)))), n), n) \\ _Andrew Howroyd_, Feb 19 2024
%Y A370318 The covering case is A057500, which is also the covering case of A370317.
%Y A370318 This is the connected case of A367862, covering A367863.
%Y A370318 A001187 counts connected graphs, A001349 unlabeled.
%Y A370318 A006125 counts graphs, A000088 unlabeled.
%Y A370318 A006129 counts covering graphs, A002494 unlabeled.
%Y A370318 A062734 counts connected graphs by edge count.
%Y A370318 A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
%Y A370318 A143543 counts simple labeled graphs by number of connected components.
%Y A370318 A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
%Y A370318 Cf. A001429, A006649, A061540, A116508, A323818, A367916, A368951, A369197.
%K A370318 nonn
%O A370318 0,5
%A A370318 _Gus Wiseman_, Feb 18 2024