

A245567


Number of antichain covers of a labeled nset such that for every two distinct elements in the nset, there is a set in the antichain cover containing one of the elements but not the other.


10




OFFSET

0,1


COMMENTS

This is the number of antichain covers such that the induced partition contains only singletons. The induced partition of {{1,2},{2,3},{1,3},{3,4}} is {{1},{2},{3},{4}}, while the induced partition of {{1,2,3},{2,3,4}} is {{1},{2,3},{4}}.
This sequence is related to A006126. See 1st formula.
The sequence is also related to Dedekind numbers through Stirling numbers of the second kind. See 2nd formula.
Sets of subsets of the described type are said to be T_0.  Gus Wiseman, Aug 14 2019


LINKS

Table of n, a(n) for n=0..8.
Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.


FORMULA

A000372(n) = Sum_{k=0..n} S(n+1,k+1)*a(k).
a(n) = A006126(n)  Sum_{k=1..n1} S(n,k)*a(k).
Were n > 0 and S(n,k) is the number of ways to partition a set of n elements into k nonempty subsets.
Inverse binomial transform of A326950, if we assume a(0) = 1.  Gus Wiseman, Aug 14 2019


EXAMPLE

For n = 0, a(0) = 2 by the antisets {}, {{}}.
For n = 1, a(1) = 1 by the antiset {{1}}.
For n = 2, a(2) = 1 by the antiset {{1},{2}}.
For n = 3, a(3) = 5 by the antisets {{1},{2},{3}}, {{1,2},{1,3}}, {{1,2},{2,3}}, {{1,3},{2,3}}, {{1,2},{1,3},{2,3}}.


MATHEMATICA

dual[eds_]:=Table[First/@Position[eds, x], {x, Union@@eds}];
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
Table[Length[Select[Subsets[Subsets[Range[n]]], Union@@#==Range[n]&&stableQ[#, SubsetQ]&&UnsameQ@@dual[#]&]], {n, 0, 3}] (* Gus Wiseman, Aug 14 2019 *)


PROG

See http://www.kuleuvenkulak.be/CODeS/codesreports for a runnable jar file.


CROSSREFS

Cf. A000372 (Dedekind numbers), A006126 (Number of antichain covers of a labeled nset).
Sequences counting and ranking T_0 structures:
A000112 (unlabeled topologies),
A001035 (topologies),
A059201 (covering setsystems),
A245567 (antichain covers),
A309615 (covering setsystems closed under intersection),
A316978 (factorizations),
A319559 (unlabeled setsystems by weight),
A319564 (integer partitions),
A319637 (unlabeled covering setsystems),
A326939 (covering sets of subsets),
A326940 (setsystems),
A326941 (sets of subsets),
A326943 (covering sets of subsets closed under intersection),
A326944 (covering sets of subsets with {} and closed under intersection),
A326945 (sets of subsets closed under intersection),
A326946 (unlabeled setsystems),
A326947 (BIInumbers of setsystems),
A326948 (connected setsystems),
A326949 (unlabeled sets of subsets),
A326950 (antichains),
A326959 (setsystems closed under intersection),
A327013 (unlabeled covering setsystems closed under intersection),
A327016 (BIInumbers of topologies).
Sequence in context: A036563 A025264 A321716 * A204168 A216914 A216917
Adjacent sequences: A245564 A245565 A245566 * A245568 A245569 A245570


KEYWORD

nonn,hard,nice


AUTHOR

Patrick De Causmaecker, Jul 25 2014


EXTENSIONS

Definition corrected by Patrick De Causmaecker, Oct 10 2014


STATUS

approved



