Tamari lattice

In mathematics, the Tamari lattice of order n, introduced by and sometimes notated T_n or Y_n, is a partially ordered set in which the elements consist of all ways of bracketing a sequence of n+1 letters using n pairs of parentheses, with the ordering induced by only rightward applications of the associative law → . For instance, T₃ contains five elements d), ),, ), and, with d) < ) < and d) < < ) <.
The number of elements in the Tamari lattice of order n is the nth Catalan number C_n. Its Hasse diagram is isomorphic to the skeleton of the associahedron of dimension n-1.
The lattice property for the order is non-trivial and was first established rigorously by, with another simpler proof later given by.
The Tamari lattice can be described in several other equivalent ways:

It is the poset of binary trees with n nodes and n+1 leaves, ordered by tree rotation operations.
It is the poset of triangulations of a convex n-gon, ordered by flip operations that substitute one diagonal of the polygon for another.
It is the poset of sequences of n integers a₁, ..., a_n, ordered coordinatewise, such that i ≤ a_i ≤ n and if i ≤ j ≤ a_i then a_j ≤ a_i.
It is the poset of ordered forests, in which one forest is earlier than another in the partial order if, for every j, the jth node in a preorder traversal of the first forest has at least as many descendants as the jth node in a preorder traversal of the second forest.

Notation and indexing

The notation Y_n is sometimes used for the Tamari lattice of order n, which has the mnemonic value that the elements of the lattice may be considered as binary trees with n Y-shaped binary nodes. Note that the corresponding associahedron of dimension n-1 is notated K_n+1 since the indexing is by the number of leaves in the binary trees that form its vertices, rather than by the number of nodes.