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 ((xy)z)&nbsp;→&nbsp;(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 , 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₁,&nbsp;...,&nbsp;a_n, ordered coordinatewise, such that i&nbsp;≤&nbsp;a_i&nbsp;≤&nbsp;n and if i&nbsp;≤&nbsp;j&nbsp;≤&nbsp;a_i then a_j&nbsp;≤&nbsp;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.

References

• .
• .
• .
• .
• .
• .
• .
• .