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). For instance, applying this law with x = a, y = bc, and z = d gives the expansion (a(bc))d = a((bc)d), so in the ordering of the Tamari lattice (a(bc))d ≤ a((bc)d).
In this partial order, any two groupings g1 and g2 have a greatest common predecessor, the meetg1 ∧ g2, and a least common successor, the joing1 ∨ 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:
It is the
poset of sequences of n integers a1, ..., an, ordered coordinatewise, such that i ≤ ai ≤ n and if i ≤ j ≤ ai then aj ≤ ai (
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).
It is the poset of
triangulations of a convex n-gon, ordered by flip operations that substitute one diagonal of the polygon for another.
Notation
The Tamari lattice of the groupings of n+1 objects is called Tn. 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.
Huang, Samuel;
Tamari, Dov (1972), "Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law", Journal of Combinatorial Theory, Series A, 13: 7–13,
doi:
10.1016/0097-3165(72)90003-9,
MR0306064.