login
A370317
Number of labeled graphs with n vertices (allowing isolated vertices) and n edges, such that the edge set is connected.
7
1, 0, 0, 1, 15, 252, 4905, 110715, 2864148, 83838720, 2744568522, 99463408335, 3955626143040, 171344363805582, 8031863998136355, 405150528051451000, 21884686370917378050, 1260420510502767861840, 77105349570138633021624, 4993117552678619556356085
OFFSET
0,5
LINKS
FORMULA
a(n) = n!*[x^n][y^n] exp(x)*(1 + log(Sum_{k>=0} (1 + y)^binomial(k, 2)*x^k/k!). - Andrew Howroyd, Feb 19 2024
EXAMPLE
The a(0) = 0 through a(4) = 15 graphs:
{} . . {{1,2},{1,3},{2,3}} {{1,2},{1,3},{1,4},{2,3}}
{{1,2},{1,3},{1,4},{2,4}}
{{1,2},{1,3},{1,4},{3,4}}
{{1,2},{1,3},{2,3},{2,4}}
{{1,2},{1,3},{2,3},{3,4}}
{{1,2},{1,3},{2,4},{3,4}}
{{1,2},{1,4},{2,3},{2,4}}
{{1,2},{1,4},{2,3},{3,4}}
{{1,2},{1,4},{2,4},{3,4}}
{{1,2},{2,3},{2,4},{3,4}}
{{1,3},{1,4},{2,3},{2,4}}
{{1,3},{1,4},{2,3},{3,4}}
{{1,3},{1,4},{2,4},{3,4}}
{{1,3},{2,3},{2,4},{3,4}}
{{1,4},{2,3},{2,4},{3,4}}
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[#]==n&&Length[csm[#]]<=1&]], {n, 0, 5}]
PROG
(PARI) a(n)=n!*polcoef(polcoef(exp(x + O(x*x^n))*(1 + 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.
This is the connected case of A116508.
Allowing any number of edges gives A287689.
Counting only covered vertices gives A370318.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, connected A001187.
A369192 counts graphs with at most n edges, covering A369191.
Sequence in context: A093147 A218192 A066410 * A116508 A055659 A218368
KEYWORD
nonn
AUTHOR
Gus Wiseman, Feb 17 2024
EXTENSIONS
a(8) onwards from Andrew Howroyd, Feb 19 2024
STATUS
approved