In mathematics, a Tamari lattice, introduced by , is a

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...

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 mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary op ...

; 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 In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...

(''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''₁ and ''g''₂ have a greatest common predecessor, the ''meet'' ''g''₁ ∧ ''g''₂, and a least common successor, the ''join'' ''g''₁ ∨ ''g''₂. Thus, the Tamari lattice has the structure of a

lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an ornam ...

. The

Hasse diagram In order theory, a Hasse diagram (; ) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set ''(S, ≤)'' one represents ea ...

of this lattice is

isomorphic In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...

to the graph of vertices and edges of an

associahedron In mathematics, an associahedron is an -dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a string of letters, and the edges correspond to single application of ...

. The number of elements in a Tamari lattice for a sequence of ''n'' + 1 objects is the ''n''th

Catalan number In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...

C_''n''. The Tamari lattice can also be described in several other equivalent ways: *It is the

poset In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...

of sequences of ''n'' integers ''a''₁, ..., ''a''_''n'', ordered coordinatewise, such that ''i'' ≤ ''a''_''i'' ≤ ''n'' and if ''i'' ≤ ''j'' ≤ ''a''_''i'' then ''a''_''j'' ≤ ''a''_''i'' . *It is the poset of

binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...

s with ''n'' leaves, ordered by

tree rotation In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape ...

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 In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...

traversal of the first forest has at least as many descendants as the ''j''th node in a preorder traversal of the second forest . *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 C_''n'' groupings of ''n''+1 objects is called T_''n'', but the corresponding

is called K_''n''+1. In ''

The Art of Computer Programming ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of compu ...

'' T₄ is called the ''Tamari lattice of order 4'' and its Hasse diagram K₅ the ''associahedron of order 4''.

References

*. *. *. *. *. *. *. *{{citation , last = Tamari , first = Dov , author-link = Dov Tamari (mathematician) , mr = 0146227 , journal = Nieuw Archief voor Wiskunde , series=Series 3 , pages = 131–146 , title = The algebra of bracketings and their enumeration , volume = 10 , year = 1962. Lattice theory