A326358 Number of maximal antichains of subsets of {1..n}.

1, 2, 3, 7, 29, 376, 31746, 123805914

Offset

0,2

Comments

A set system (set of sets) is an antichain if no element is a subset of any other.

Links

Table of n, a(n) for n=0..7.

Dmitry I. Ignatov, A Note on the Number of (Maximal) Antichains in the Lattice of Set Partitions. In: Ojeda-Aciego, M., Sauerwald, K., Jäschke, R. (eds) Graph-Based Representation and Reasoning. ICCS 2023. Lecture Notes in Computer Science(). Springer, Cham.

Dmitry I. Ignatov, On the Number of Maximal Antichains in Boolean Lattices for n up to 7. Lobachevskii J. Math., 44 (2023), 137-146.

Formula

For n > 0, a(n) = A326359(n) + 1.

Example

The a(0) = 1 through a(3) = 7 maximal antichains:
  {}  {}   {}      {}
      {1}  {12}    {123}
           {1}{2}  {1}{23}
                   {2}{13}
                   {3}{12}
                   {1}{2}{3}
                   {12}{13}{23}

Mathematica

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]]]];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n]], SubsetQ]]], {n, 0, 5}]
(* alternatively *)
maxachP[n_]:=FindIndependentVertexSet[
  Flatten[Map[Function[s, Map[# \[DirectedEdge] s &, Most[Subsets[s]]]],
    Subsets[Range[n]]]], Infinity, All];
Table[Length[maxachP[n]], {n, 0, 6}] (* Mamuka Jibladze, Jan 25 2021 *)

Prog

(GAP) LoadPackage("grape");
      maxachP:=function(n) local g, G;
       g:=Graph(Group(()), Combinations([1..n]), function(x, g) return x; end,
          function(x, y) return not IsSubset(x, y) and not IsSubset(y, x); end, true);
       G:=AutGroupGraph(g);
       return Sum(CompleteSubgraphs(NewGroupGraph(G, g), -1, 2),
              function(c) return Length(Orbit(G, c, OnSets)); end);
     end;
       List([0..7], maxachP); # Mamuka Jibladze, Jan 26 2021

Crossrefs

Antichains of sets are A000372.

Minimal covering antichains are A046165.

Maximal intersecting antichains are A007363.

Maximal antichains of nonempty sets are A326359.

Cf. A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305001, A305844, A326360, A326361, A326362, A326363.

Sequence in context: A072469 A004062 A037151 * A008840 A268477 A156313

Adjacent sequences: A326355 A326356 A326357 * A326359 A326360 A326361

Keyword

nonn,more

Author

Gus Wiseman, Jul 01 2019

Extensions

a(6)-a(7) from Mamuka Jibladze, Jan 26 2021

Status

approved