|
%I #41 Aug 31 2023 12:00:20
%S 1,2,3,7,29,376,31746,123805914
%N Number of maximal antichains of subsets of {1..n}.
%C A set system (set of sets) is an antichain if no element is a subset of any other.
%H Dmitry I. Ignatov, <a href="https://doi.org/10.1007/978-3-031-40960-8_6">A Note on the Number of (Maximal) Antichains in the Lattice of Set Partitions</a>. In: Ojeda-Aciego, M., Sauerwald, K., Jäschke, R. (eds) Graph-Based Representation and Reasoning. ICCS 2023. Lecture Notes in Computer Science(). Springer, Cham.
%H Dmitry I. Ignatov, <a href="https://doi.org/10.1134/S1995080223010158">On the Number of Maximal Antichains in Boolean Lattices for n up to 7</a>. Lobachevskii J. Math., 44 (2023), 137-146.
%F For n > 0, a(n) = A326359(n) + 1.
%e The a(0) = 1 through a(3) = 7 maximal antichains:
%e {} {} {} {}
%e {1} {12} {123}
%e {1}{2} {1}{23}
%e {2}{13}
%e {3}{12}
%e {1}{2}{3}
%e {12}{13}{23}
%t stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
%t fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
%t Table[Length[fasmax[stableSets[Subsets[Range[n]],SubsetQ]]],{n,0,5}]
%t (* alternatively *)
%t maxachP[n_]:=FindIndependentVertexSet[
%t Flatten[Map[Function[s, Map[# \[DirectedEdge] s &, Most[Subsets[s]]]],
%t Subsets[Range[n]]]], Infinity, All];
%t Table[Length[maxachP[n]],{n,0,6}] (* _Mamuka Jibladze_, Jan 25 2021 *)
%o (GAP) LoadPackage("grape");
%o maxachP:=function(n) local g,G;
%o g:=Graph(Group(()), Combinations([1..n]), function(x, g) return x; end,
%o function(x, y) return not IsSubset(x, y) and not IsSubset(y, x); end, true);
%o G:=AutGroupGraph(g);
%o return Sum(CompleteSubgraphs(NewGroupGraph(G, g), -1, 2),
%o function(c) return Length(Orbit(G, c, OnSets)); end);
%o end;
%o List([0..7],maxachP); # _Mamuka Jibladze_, Jan 26 2021
%Y Antichains of sets are A000372.
%Y Minimal covering antichains are A046165.
%Y Maximal intersecting antichains are A007363.
%Y Maximal antichains of nonempty sets are A326359.
%Y Cf. A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305001, A305844, A326360, A326361, A326362, A326363.
%K nonn,more
%O 0,2
%A _Gus Wiseman_, Jul 01 2019
%E a(6)-a(7) from _Mamuka Jibladze_, Jan 26 2021
|
