

A367862


Number of nvertex labeled simple graphs with the same number of edges as covered vertices.


33



1, 1, 1, 2, 20, 308, 5338, 105298, 2366704, 60065072, 1702900574, 53400243419, 1836274300504, 68730359299960, 2782263907231153, 121137565273808792, 5645321914669112342, 280401845830658755142, 14788386825536445299398, 825378055206721558026931, 48604149005046792753887416
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


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.


LINKS



FORMULA



EXAMPLE

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


MATHEMATICA

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


PROG

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


CROSSREFS

Counting all vertices (not just covered) gives A116508.
A143543 counts simple labeled graphs by number of connected components.


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



