

A072446


Number of subsets S of the power set P{1,2,...,n} such that: {1}, {2},..., {n} are all elements of S; if X and Y are elements of S and X and Y have a nonempty intersection, then the union of X and Y is an element of S.


15




OFFSET

1,2


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 BIInumbers of these setsystems 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

Table of n, a(n) for n=1..6.
Wim van Dam, Sub Power Set Sequences
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).
Cf. A102896, A306445, A326872, A326873.
Sequence in context: A051009 A324616 A060942 * A220113 A015181 A012378
Adjacent sequences: A072443 A072444 A072445 * A072447 A072448 A072449


KEYWORD

nonn


AUTHOR

Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002


STATUS

approved



