• Source: 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 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:

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 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 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.




References


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, vol. IV, p. 34.
Tamari, Dov (1962), "The algebra of bracketings and their enumeration", Nieuw Archief voor Wiskunde, Series 3, 10: 131–146, MR 0146227.

Kata Kunci Pencarian:

• Kekisi (tatanan)
• Tamari lattice
• Tamari
• Lattice (order)
• Associahedron
• Dov Tamari
• 68 (number)
• Haya Freedman
• Matrix chain multiplication
• Catalan number
• Associative property