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.

0, 0, 0, 1, 19, 307, 5237, 99137, 2098946, 49504458, 1291570014, 37002273654, 1156078150969, 39147186978685, 1428799530304243, 55933568895261791, 2338378885159906196, 103995520598384132516, 4903038902046860966220, 244294315694676224001852, 12827355456239840407125363

Offset

0,5

Comments

The case of an empty edge set is excluded.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..100

Formula

Binomial transform of A057500 (if the null graph is not connected).

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

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}]], Length[#]==Length[Union@@#] && Length[csm[#]]==1&]], {n, 0, 5}]

Prog

(PARI) \\ Compare A370317; use A057500 for efficiency.
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

Crossrefs

The covering case is A057500, which is also the covering case of A370317.

This is the connected case of A367862, covering A367863.

A001187 counts connected graphs, A001349 unlabeled.

A006125 counts graphs, A000088 unlabeled.

A006129 counts covering graphs, A002494 unlabeled.

A062734 counts connected graphs by edge count.

A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.

A143543 counts simple labeled graphs by number of connected components.

A367867 = graphs contradict strict AoC, connected A140638, covering A367868.

Cf. A001429, A006649, A061540, A116508, A323818, A367916, A368951, A369197.

Sequence in context: A074460 A267010 A182460 * A032631 A142430 A180845

Adjacent sequences: A370315 A370316 A370317 * A370319 A370320 A370321

Keyword

nonn

Author

Gus Wiseman, Feb 18 2024

Status

approved