|
|
A072444
|
|
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. The sets S are counted modulo permutations on the elements 1,2,...,n.
|
|
11
|
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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 unlabeled connectedness systems on n vertices without singleton edges. Non-isomorphic representatives of the a(3) = 6 connectedness systems without singletons are:
{}
{{1,2}}
{{1,2,3}}
{{2,3},{1,2,3}}
{{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}
(End)
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
a(3) = 6 because of the 6 sets: {{1}, {2}, {3}}; {{1}, {2}, {3}, {1, 2}}; {{1}, {2}, {3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
|
|
CROSSREFS
|
Unlabeled set-systems closed under union are A193674.
Unlabeled connectedness systems are A326867.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|