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

2, 1, 1, 5, 76, 5993, 7689745, 2414465044600, 56130437141763247212112, 286386577668298408602599478477358234902247

Offset: 0

Author

Patrick De Causmaecker, Jul 25 2014

Keywords

• nonn
• hard
• nice
• more

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

Examples

			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}}.
		

Links

• Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.

Crossrefs

Cf. A000372 (Dedekind numbers), A006126 (Number of antichain covers of a labeled n-set).

Sequences counting and ranking T_0 structures:

A000112 (unlabeled topologies),

A001035 (topologies),

A059201 (covering set-systems),

A245567 (antichain covers),

A309615 (covering set-systems closed under intersection),

A316978 (factorizations),

A319559 (unlabeled set-systems by weight),

A319564 (integer partitions),

A319637 (unlabeled covering set-systems),

A326939 (covering sets of subsets),

A326940 (set-systems),

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 set-systems),

A326947 (BII-numbers of set-systems),

A326948 (connected set-systems),

A326949 (unlabeled sets of subsets),

A326950 (antichains),

A326959 (set-systems closed under intersection),

A327013 (unlabeled covering set-systems closed under intersection),

A327016 (BII-numbers of topologies).

Programs

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 *)

Formula

A000372(n) = Sum_{k=0..n} S(n+1,k+1)*a(k).

a(n) = A006126(n) - Sum_{k=1..n-1} 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

Extensions

Definition corrected by Patrick De Causmaecker, Oct 10 2014

a(9), based on A000372, from Patrick De Causmaecker, Jun 01 2023