A358563 The number of maximal antichains in the Tamari lattice of order n.

1, 2, 4, 26, 1979, 161117453

Offset

1,2

Comments

Also the number of maximal order ideals in the Tamari lattice of order n.

Maximal antichains are those which cannot be extended without violating the antichain condition.

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=5, Github repository.

Wikipedia, Tamari lattice

Example

The line (Hasse) diagram of the Tamari lattice for n=3 is
     ((ab)c)d
      /     \
 (a(bc))d (ab)(cd)
     |       /
  a((bc)d)  /
      \    /
     a(b(cd))
with the a(3)=4 maximal antichains {((ab)c)d}, {(ab)(cd), (a(bc))d}, {(ab)(cd), a((bc)d)}, {a(b(cd))}.

Crossrefs

Cf. A358562 (number of antichains in the Tamari lattice).

Cf. A326358 (number of maximal antichains in the Boolean lattice).

Cf. A358041 (number of maximal antichains in the lattice of set partitions of an n-element set).

Cf. A358390 (number of maximal antichains in the Kreweras lattice of non-crossing set partitions).

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

Sequence in context: A240040 A088888 A102996 * A189896 A095182 A104465

Adjacent sequences: A358560 A358561 A358562 * A358564 A358565 A358566

Keyword

nonn,hard,more

Author

Dmitry I. Ignatov, Nov 22 2022

Status

approved