A367862 Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.

1, 1, 1, 2, 20, 308, 5338, 105298, 2366704, 60065072, 1702900574, 53400243419, 1836274300504, 68730359299960, 2782263907231153, 121137565273808792, 5645321914669112342, 280401845830658755142, 14788386825536445299398, 825378055206721558026931, 48604149005046792753887416

Offset: 0

Author

Gus Wiseman, Dec 07 2023

Keywords

• nonn

Comments

Unlike the connected case (A057500), these graphs may have more than one cycle; for example, the graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}} has multiple cycles.

Examples

			Non-isomorphic representatives of the a(4) = 20 graphs:
  {}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,4},{2,3}}
  {{1,2},{1,3},{2,4},{3,4}}
		

Links

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

Crossrefs

The connected case is A057500, unlabeled A001429.

Counting all vertices (not just covered) gives A116508.

The covering case is A367863, unlabeled A006649.

For set-systems we have A367916, ranks A367917.

A001187 counts connected graphs, A001349 unlabeled.

A003465 counts covering set-systems, unlabeled A055621, ranks A326754.

A006125 counts graphs, A000088 unlabeled.

A006129 counts covering graphs, A002494 unlabeled.

A058891 counts set-systems, unlabeled A000612, without singletons A016031.

A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.

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

A143543 counts simple labeled graphs by number of connected components.

A323818 counts connected set-systems, unlabeled A323819, ranks A326749.

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

Cf. A006126, A316983, A321405, A326754, A326870, A326877, A367770, A367901, A367902, A367903.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[#]==Length[Union@@#]&]],{n,0,5}]

PARI

\\ Here b(n) is A367863(n)
b(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n))
a(n) = sum(k=0, n, binomial(n,k) * b(k)) \\ Andrew Howroyd, Dec 29 2023

Formula

Binomial transform of A367863.

Extensions

Terms a(8) and beyond from Andrew Howroyd, Dec 29 2023