login
A072446
Number of connectedness systems on n vertices that contain all singletons.
15
1, 1, 2, 12, 420, 254076, 18689059680
OFFSET
0,3
COMMENTS
From Gus Wiseman, Jul 31 2019: (Start)
If we define a connectedness system to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges, then a(n) is the number of connectedness systems on n vertices without singleton edges. The BII-numbers of these set-systems are given by A326873. The a(3) = 12 connectedness systems without singletons are:
{}
{{1,2}}
{{1,3}}
{{2,3}}
{{1,2,3}}
{{1,2},{1,2,3}}
{{1,3},{1,2,3}}
{{2,3},{1,2,3}}
{{1,2},{1,3},{1,2,3}}
{{1,2},{2,3},{1,2,3}}
{{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}
(End)
LINKS
Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.
FORMULA
a(n) = A326866(n)/2^n. - Gus Wiseman, Jul 31 2019
EXAMPLE
a(3)=12 because of the 12 sets:
{{1}, {2}, {3}};
{{1}, {2}, {3}, {1, 2}};
{{1}, {2}, {3}, {1, 3}};
{{1}, {2}, {3}, {2, 3}};
{{1}, {2}, {3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {2, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}};
{{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2, n}]], SubsetQ[#, Union@@@Select[Tuples[#, 2], Intersection@@#!={}&]]&]], {n, 0, 3}] (* Gus Wiseman, Jul 31 2019 *)
CROSSREFS
The unlabeled case is A072444.
Exponential transform of A072447 (the connected case).
The case with singletons is A326866.
Binomial transform of A326877 (the covering case).
Sequence in context: A051009 A324616 A060942 * A220113 A015181 A012378
KEYWORD
nonn
AUTHOR
Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002
EXTENSIONS
a(6) corrected and definition reformulated by Christian Sievers, Oct 26 2023
a(0)=1 prepended by Sean A. Irvine, Oct 02 2024
STATUS
approved