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

2, 3, 10, 347, 79814832

Offset

1,1

Comments

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

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

Links

Table of n, a(n) for n=1..5.

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.

Example

For n = 3 the a(3) = 10 antichains are:
  {}
  {1/2/3}
  {1/23}
  {12/3}
  {13/2}
  {1/23, 12/3}
  {1/23, 13/2}
  {12/3, 13/2}
  {1/23, 12/3, 13/2}
  {123}.
Here we have used the usual shorthand notation for set partitions where 1/23 denotes {{1}, {2,3}}.

Prog

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

Crossrefs

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

Sequence in context: A358391 A132536 A322067 * A290638 A330294 A270442

Adjacent sequences: A302247 A302248 A302249 * A302251 A302252 A302253

Keyword

nonn,hard,more

Author

John Machacek, Apr 04 2018

Status

approved