A326360 Number of maximal antichains of nonempty, non-singleton subsets of {1..n}.

1, 1, 1, 2, 13, 279, 29820, 123590767

Offset: 0

Author

Gus Wiseman, Jul 01 2019

Keywords

• nonn
• more

Comments

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

Examples

			The a(1) = 1 through a(4) = 13 maximal antichains:
  {}  {12}  {123}         {1234}
            {12}{13}{23}  {12}{134}{234}
                          {13}{124}{234}
                          {14}{123}{234}
                          {23}{124}{134}
                          {24}{123}{134}
                          {34}{123}{124}
                          {12}{13}{14}{234}
                          {12}{23}{24}{134}
                          {13}{23}{34}{124}
                          {14}{24}{34}{123}
                          {123}{124}{134}{234}
                          {12}{13}{14}{23}{24}{34}
		

Links

• Dmitry I. Ignatov, On the Number of Maximal Antichains in Boolean Lattices for n up to 7. Lobachevskii J. Math., 44 (2023), 137-146.
• Dmitry I. Ignatov, Supporting iPython code and input files for a(7) based on inequivalent maximal antichains for n=7 and related sequences, Github repository, section 3
• Dmitry I. Ignatov, PDF version of the supporting iPython notebook for a(7)
• Dmitry I. Ignatov, Supporting iPython notebook for a(7): A326360.ipynb

Crossrefs

Antichains of nonempty, non-singleton sets are A307249.

Minimal covering antichains are A046165.

Maximal intersecting antichains are A007363.

Maximal antichains of nonempty sets are A326359.

Cf. A000372, A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305844, A326358, A326361, A326362, A326363.

Programs

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],{2,n}],SubsetQ]]],{n,0,4}]

Python

# see Ignatov links
# Dmitry I. Ignatov, Oct 14 2021

Formula

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*A326359(k) for n >= 2. - Andrew Howroyd, Nov 19 2021

Extensions

a(6) from Andrew Howroyd, Aug 14 2019

a(7) from Dmitry I. Ignatov, Oct 14 2021