login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A367862 Number of n-vertex 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
Binomial transform of A367863.
EXAMPLE
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}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Length[#]==Length[Union@@#]&]], {n, 0, 5}]
PROG
(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
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.
Sequence in context: A124211 A277308 A128481 * A177397 A360342 A323574
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 07 2023
EXTENSIONS
Terms a(8) and beyond from Andrew Howroyd, Dec 29 2023
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 21 09:49 EDT 2024. Contains 373543 sequences. (Running on oeis4.)