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

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

Offset

0,4

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, 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

Formula

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

Example

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}

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}]

Prog

(Python)
# see Ignatov links
# Dmitry I. Ignatov, Oct 14 2021

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.

Sequence in context: A086510 A356493 A334089 * A123113 A126742 A013051

Adjacent sequences: A326357 A326358 A326359 * A326361 A326362 A326363

Keyword

nonn,more

Author

Gus Wiseman, Jul 01 2019

Extensions

a(6) from Andrew Howroyd, Aug 14 2019

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

Status

approved