Tamari lattice

In mathematics, a Tamari lattice, introduced by Dov Tamari (1962), 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 ((ab)c)d, (ab)(cd), (a(bc))d, a((bc)d), and a(b(cd)).

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 (xy)z = x(yz).

The Hasse diagram of this lattice is isomorphic to the graph of vertices and edges of an associahedron.

The Tamari lattice can also be described in several other equivalent ways: The Tamari lattice of the groupings of n+1 objects is called Tn.

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.