Tamari lattice

In mathematics, the Tamari lattice of order n, introduced by Dov Tamari (1962) 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 ((xy)z) → (x(yz)). For instance, T₃ contains five elements (((ab)c)d), ((ab)(cd)), ((a(bc))d), (a((bc)d)), and (a(b(cd))), with (((ab)c)d) < ((ab)(cd)) < (a(b(cd))) and (((ab)c)d) < ((a(bc))d) < (a((bc)d)) < (a(b(cd))). (The outermost pair of parentheses is redundant and often omitted when naming the elements of T_n, as in the depiction of T₄ shown in the figure.)

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 (i.e., that any two bracketings have a join and meet) is non-trivial and was first established rigorously by (Friedman & Tamari 1967), with another simpler proof later given by (Huang & Tamari 1972).

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 (Huang & Tamari 1972).
• 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 (Knuth 2005).