login
A326360
Number of maximal antichains of nonempty, non-singleton subsets of {1..n}.
9
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.
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.
Sequence in context: A086510 A356493 A334089 * A123113 A126742 A013051
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