|
%I #36 Jun 02 2023 01:13:43
%S 2,1,1,5,76,5993,7689745,2414465044600,56130437141763247212112,
%T 286386577668298408602599478477358234902247
%N 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.
%C 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}}.
%C This sequence is related to A006126. See 1st formula.
%C The sequence is also related to Dedekind numbers through Stirling numbers of the second kind. See 2nd formula.
%C Sets of subsets of the described type are said to be T_0. - _Gus Wiseman_, Aug 14 2019
%H Patrick De Causmaecker and Stefan De Wannemacker, <a href="http://arxiv.org/abs/1407.4288">On the number of antichains of sets in a finite universe</a>, arXiv:1407.4288 [math.CO], 2014.
%F A000372(n) = Sum_{k=0..n} S(n+1,k+1)*a(k).
%F a(n) = A006126(n) - Sum_{k=1..n-1} S(n,k)*a(k).
%F Were n > 0 and S(n,k) is the number of ways to partition a set of n elements into k nonempty subsets.
%F Inverse binomial transform of A326950, if we assume a(0) = 1. - _Gus Wiseman_, Aug 14 2019
%e For n = 0, a(0) = 2 by the antisets {}, {{}}.
%e For n = 1, a(1) = 1 by the antiset {{1}}.
%e For n = 2, a(2) = 1 by the antiset {{1},{2}}.
%e 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}}.
%t dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
%t stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
%t Table[Length[Select[Subsets[Subsets[Range[n]]],Union@@#==Range[n]&&stableQ[#,SubsetQ]&&UnsameQ@@dual[#]&]],{n,0,3}] (* _Gus Wiseman_, Aug 14 2019 *)
%o See http://www.kuleuven-kulak.be/CODeS/codesreports for a runnable jar file.
%Y Cf. A000372 (Dedekind numbers), A006126 (Number of antichain covers of a labeled n-set).
%Y Sequences counting and ranking T_0 structures:
%Y A000112 (unlabeled topologies),
%Y A001035 (topologies),
%Y A059201 (covering set-systems),
%Y A245567 (antichain covers),
%Y A309615 (covering set-systems closed under intersection),
%Y A316978 (factorizations),
%Y A319559 (unlabeled set-systems by weight),
%Y A319564 (integer partitions),
%Y A319637 (unlabeled covering set-systems),
%Y A326939 (covering sets of subsets),
%Y A326940 (set-systems),
%Y A326941 (sets of subsets),
%Y A326943 (covering sets of subsets closed under intersection),
%Y A326944 (covering sets of subsets with {} and closed under intersection),
%Y A326945 (sets of subsets closed under intersection),
%Y A326946 (unlabeled set-systems),
%Y A326947 (BII-numbers of set-systems),
%Y A326948 (connected set-systems),
%Y A326949 (unlabeled sets of subsets),
%Y A326950 (antichains),
%Y A326959 (set-systems closed under intersection),
%Y A327013 (unlabeled covering set-systems closed under intersection),
%Y A327016 (BII-numbers of topologies).
%K nonn,hard,nice,more
%O 0,1
%A _Patrick De Causmaecker_, Jul 25 2014
%E Definition corrected by _Patrick De Causmaecker_, Oct 10 2014
%E a(9), based on A000372, from _Patrick De Causmaecker_, Jun 01 2023
| 