A054780 -id:A054780 - cp's OEIS frontend

A370317 Number of labeled graphs with n vertices (allowing isolated vertices) and n edges, such that the edge set is connected.

1, 0, 0, 1, 15, 252, 4905, 110715, 2864148, 83838720, 2744568522, 99463408335, 3955626143040, 171344363805582, 8031863998136355, 405150528051451000, 21884686370917378050, 1260420510502767861840, 77105349570138633021624, 4993117552678619556356085

Offset: 0

Gus Wiseman, Feb 17 2024

nonn

			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}}

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

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.
Cf. A000169, A001862, A054780, A062740, A129271, A367863, A369193, A369197.

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}]

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

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

a(8) onwards from Andrew Howroyd, Feb 19 2024

A368731 Number of non-isomorphic n-element sets of nonempty subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 10, 97, 2160, 126862, 21485262, 11105374322, 18109358131513, 95465831661532570, 1660400673336788987026, 96929369602251313489896310, 19268528295096123543660356281600, 13203875101002459910158494602665950757, 31517691852305548841992346407978317698725021

Offset: 0

Gus Wiseman, Jan 07 2024

nonn

			Non-isomorphic representatives of the a(3) = 10 set-systems:
  {{1},{2},{3}}
  {{1},{2},{1,2}}
  {{1},{2},{1,3}}
  {{1},{2},{1,2,3}}
  {{1},{1,2},{1,3}}
  {{1},{1,2},{2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}

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

The case of graphs is A001434, labeled A116508.
Labeled version is A136556, covering A054780, binomial transform of A367916.
The case of labeled covering graphs is A367863, binomial transform A367862.
These include the set-systems ranked by A367917.
The covering case is A368186, for graphs A006649, connected A057500.
Requiring all edges to be singletons or pairs gives A368598.
A003465 counts covers with any number of edges, unlabeled A055621.
A046165 counts minimal covers, ranks A309326.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
Cf. A000088, A007716, A283877, A367901, A367902, A367903, A368599.

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Subsets[Subsets[Range[n],{1,n}],{n}]]],{n,0,4}]

a(n) = polcoef(G(n, n), n) \\ G defined in A368186. - Andrew Howroyd, Jan 11 2024

Terms a(6) and beyond from Andrew Howroyd, Jan 11 2024

cp's OEIS Frontend

A370317 Number of labeled graphs with n vertices (allowing isolated vertices) and n edges, such that the edge set is connected.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions