A358562 The number of antichains in the Tamari lattice of order n.

2, 3, 8, 83, 28984, 138832442543

Offset

1,1

Comments

Also the number of order ideals (down-sets) for the Tamari lattice of order n.

References

D. Tamari, The algebra of bracketings and their enumeration, Nieuw Archief voor Wiskunde, Series 3, 10 (1962), 131-146.

Links

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

S. Huang and D. Tamari, Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law, J. of Comb. Theory, Series A, 13 (1972), 7-13.

Dmitry I. Ignatov, Supporting iPython code and input files for counting (maximal) antichains of the Tamari partition lattice up to n=6, Github repository.

Wikipedia, Tamari lattice

Example

For n=3 the a(3)=8 antichains are {}, {((ab)c)d}, {(ab)(cd)}, {(a(bc))d}, {(ab)(cd), (a(bc))d}, {a((bc)d)}, {(ab)(cd), a((bc)d)}, {a(b(cd))}.

Crossrefs

Cf. A000372 (number of antichains in the Boolean lattice).

Cf. A302250 (number of antichains in the lattice of set partitions).

Cf. A358391 (number of antichains in the Kreweras lattice of non-crossing set partitions of an n-element set).

Cf. A143673 (number of antichains in the lattice of Dyck paths).

Cf. A027686.

Sequence in context: A042815 A191353 A319218 * A368246 A243954 A005008

Adjacent sequences: A358559 A358560 A358561 * A358563 A358564 A358565

Keyword

nonn,hard,more

Author

Dmitry I. Ignatov, Nov 22 2022

Status

approved