Antichain

Author

Eric W. Weisstein
June 27, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/Antichain.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Antichain.html.

©2023 Wolfram Research, Inc. except for portions noted otherwise

Code

OrderedSubsetQ[l1_List,l2_List]:=Module[{i=Intersection[l1,l2]},
i==l1||i==l2
]

Antichains[n_]:=Module[{s=Subsets[Range[n]],i,a},
a=Flatten[Table[Subsets[s,{i}],{i,2^n}],1];
Select[a,Not[Or@@OrderedSubsetQ@@@Subsets[#,{2}]]&]
]

SubsetQ[{1,2,3},{3,1}]

OrderedSubsetQ[{1,2,3},{3,1}]

Enumerate

Do[
Print[{n,Length@Antichains[n]//Timing}],
{n,0,4}]

Length/@Table[Antichains[n],{n,0,4}]

TextGrid[Table[{n,Length[antichains=Antichains[n]],antichains},{n,4}],Dividers->All,Alignment->{{{Decimal},Left}}]