login
The number of antichains in the lattice of set partitions of an n-element set.
5

%I #23 Aug 20 2023 10:49:16

%S 2,3,10,347,79814832

%N The number of antichains in the lattice of set partitions of an n-element set.

%C Computing terms in this sequence is analogous to Dedekind's problem which asks for the number of antichains in the Boolean algebra.

%C This count includes the empty antichain consisting of no set partitions.

%H Dmitry I. Ignatov, <a href="https://doi.org/10.1007/978-3-031-40960-8_6">A Note on the Number of (Maximal) Antichains in the Lattice of Set Partitions</a>. In: Ojeda-Aciego, M., Sauerwald, K., Jäschke, R. (eds) Graph-Based Representation and Reasoning. ICCS 2023. Lecture Notes in Computer Science(). Springer, Cham.

%e For n = 3 the a(3) = 10 antichains are:

%e {}

%e {1/2/3}

%e {1/23}

%e {12/3}

%e {13/2}

%e {1/23, 12/3}

%e {1/23, 13/2}

%e {12/3, 13/2}

%e {1/23, 12/3, 13/2}

%e {123}.

%e Here we have used the usual shorthand notation for set partitions where 1/23 denotes {{1}, {2,3}}.

%o (Sage)

%o [Posets.SetPartitions(n).antichains().cardinality() for n in range(4)]

%Y Equals A302251 + 1, Cf. A000372, A007153, A003182, A014466.

%K nonn,hard,more

%O 1,1

%A _John Machacek_, Apr 04 2018