Tamari lattice


In mathematics, a Tamari lattice, introduced by , is a partially ordered set in which the elements consist of different ways of grouping a sequence of objects into pairs using parentheses; for instance, for a sequence of four objects abcd, the five possible groupings are d,, d, a, and a. Each grouping describes a different order in which the objects may be combined by a binary operation; in the Tamari lattice, one grouping is ordered before another if the second grouping may be obtained from the first by only rightward applications of the associative law z = x. For instance, applying this law with x = a, y = bc, and z = d gives the expansion d = a, so in the ordering of the Tamari lattice d ≤ a.
In this partial order, any two groupings g1 and g2 have a greatest common predecessor, the meet g1 ∧ g2, and a least common successor, the join g1 ∨ g2. Thus, the Tamari lattice has the structure of a lattice. The Hasse diagram of this lattice is isomorphic to the graph of vertices and edges of an associahedron. The number of elements in a Tamari lattice for a sequence of n + 1 objects is the nth Catalan number Cn.
The Tamari lattice can also be described in several other equivalent ways:
The Tamari lattice of the Cn groupings of n+1 objects is called Tn, but the corresponding associahedron is called Kn+1.
In The Art of Computer Programming T4 is called the Tamari lattice of order 4 and its Hasse diagram K5 the associahedron of order 4.