Tamari lattice

In mathematics, the Tamari lattice of order n, introduced by and sometimes notated Tn or Yn, 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 ((xy)z) → (x(yz)). For instance, T3 contains five elements (((ab)c)d), ((ab)(cd)), ((a(bc))d), (a((bc)d)), and (a(b(cd))), with (((ab)c)d) n, as in the depiction of T4 shown in the figure.)

The number of elements in the Tamari lattice of order n is the nth Catalan number Cn. Its Hasse diagram is isomorphic to the skeleton of the associahedron of dimension n-1.

The lattice property for the order (i.e., that any two bracketings have a join and meet) 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 a1, ..., 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 .