login
Number of maximal antichains of nonempty subsets of {1..n}.
13

%I #18 Aug 31 2023 10:02:30

%S 1,1,2,6,28,375,31745,123805913

%N Number of maximal antichains of nonempty 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.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) = A326358(n) - 1.

%e The a(0) = 1 through a(4) = 28 antichains:

%e {} {1} {12} {123} {1234}

%e {1}{2} {1}{23} {1}{234}

%e {2}{13} {2}{134}

%e {3}{12} {3}{124}

%e {1}{2}{3} {4}{123}

%e {12}{13}{23} {1}{2}{34}

%e {1}{3}{24}

%e {1}{4}{23}

%e {2}{3}{14}

%e {2}{4}{13}

%e {3}{4}{12}

%e {1}{2}{3}{4}

%e {12}{134}{234}

%e {13}{124}{234}

%e {14}{123}{234}

%e {23}{124}{134}

%e {24}{123}{134}

%e {34}{123}{124}

%e {1}{23}{24}{34}

%e {2}{13}{14}{34}

%e {3}{12}{14}{24}

%e {4}{12}{13}{23}

%e {12}{13}{14}{234}

%e {12}{23}{24}{134}

%e {13}{23}{34}{124}

%e {14}{24}{34}{123}

%e {123}{124}{134}{234}

%e {12}{13}{14}{23}{24}{34}

%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],{1,n}],SubsetQ]]],{n,0,5}]

%Y Antichains of nonempty sets are A014466.

%Y Minimal covering antichains are A046165.

%Y Maximal intersecting antichains are A007363.

%Y Maximal antichains of sets are A326358.

%Y Cf. A000372, A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305844, A307249, A326360, A326362, A326363.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Jul 01 2019

%E a(6) from _Andrew Howroyd_, Aug 14 2019

%E a(7) from _Dmitry I. Ignatov_, Oct 12 2021