login
A367869
Number of labeled simple graphs covering n vertices and satisfying a strict version of the axiom of choice.
42
1, 0, 1, 4, 34, 387, 5596, 97149, 1959938, 44956945, 1154208544, 32772977715, 1019467710328, 34473686833527, 1259038828370402, 49388615245426933, 2070991708598960524, 92445181295983865757, 4376733266230674345874, 219058079619119072854095, 11556990682657196214302036
OFFSET
0,4
COMMENTS
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.
Number of labeled n-node graphs with at most one cycle in each component and no isolated vertices. - Andrew Howroyd, Dec 30 2023
LINKS
FORMULA
E.g.f.: exp(B(x) - x - 1) where B(x) is the e.g.f. of A129271. - Andrew Howroyd, Dec 30 2023
EXAMPLE
The a(3) = 4 graphs:
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Select[Tuples[#], UnsameQ@@#&]!={}&]], {n, 0, 5}]
PROG
(PARI) seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(sqrt(1/(1-t))*exp(t/2 - 3*t^2/4 - x)))} \\ Andrew Howroyd, Dec 30 2023
CROSSREFS
The connected case is A129271.
The non-covering case is A133686, complement A367867.
The complement is A367868, connected A140638 (unlabeled A140636).
A001187 counts connected graphs, A001349 unlabeled.
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.
A143543 counts simple labeled graphs by number of connected components.
Sequence in context: A307941 A084973 A234313 * A369191 A197921 A196692
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 08 2023
EXTENSIONS
Terms a(7) and beyond from Andrew Howroyd, Dec 30 2023
STATUS
approved