# 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*). 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 *g*_{1} and *g*_{2} have a greatest common predecessor, the *meet* *g*_{1} ∧ *g*_{2}, and a least common successor, the *join* *g*_{1} ∨ *g*_{2}. 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 *n*th Catalan number.

The Tamari lattice can also be described in several other equivalent ways:

- It is the poset of sequences of
*n*integers*a*_{1}, ...,*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 binary trees with
*n*leaves, ordered by tree rotation operations. - It is the poset of ordered forests, in which one forest is earlier than another in the partial order if, for every
*j*, the*j*th node in a preorder traversal of the first forest has at least as many descendants as the*j*th 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[edit]

The Tamari lattice of the C_{n} groupings of *n*+1 objects is called T_{n}, but the corresponding associahedron is called K_{n+1}.

In *The Art of Computer Programming* T_{4} is called the *Tamari lattice of order 4* and its Hasse diagram K_{5} the *associahedron of order 4*.

## References[edit]

- Chapoton, F. (2005), "Sur le nombre d'intervalles dans les treillis de Tamari",
*Séminaire Lotharingien de Combinatoire*(in French),**55**(55): 2368, arXiv:math/0602368 , Bibcode:2006math......2368C, MR 2264942. - Csar, Sebastian A.; Sengupta, Rik; Suksompong, Warut (2014), "On a Subposet of the Tamari Lattice",
*Order*,**31**(3): 337–363, arXiv:1108.5690 , doi:10.1007/s11083-013-9305-5, MR 3265974. - Early, Edward (2004), "Chain lengths in the Tamari lattice",
*Annals of Combinatorics*,**8**(1): 37–43, doi:10.1007/s00026-004-0203-9, MR 2061375. - Friedman, Haya; Tamari, Dov (1967), "Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative",
*Journal of Combinatorial Theory*(in French),**2**(3): 215–242, doi:10.1016/S0021-9800(67)80024-3, MR 0238984. - Geyer, Winfried (1994), "On Tamari lattices",
*Discrete Mathematics*,**133**(1–3): 99–122, doi:10.1016/0012-365X(94)90019-1, MR 1298967. - 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, MR 0306064. - Knuth, Donald E. (2005), "Draft of Section 7.2.1.6: Generating All Trees",
*The Art of Computer Programming*,**IV**, p. 34. - Tamari, Dov (1962), "The algebra of bracketings and their enumeration",
*Nieuw Archief voor Wiskunde, Ser. 3*,**10**: 131–146, MR 0146227.