Tamari Lattice
Tamari Lattice
There are multiple ways to parenthesize a sequence of factors two at a time. For instance, , , and can be grouped as either or ; the Catalan numbers count the number of ways this is possible for factors. The groupings form a partially ordered set, where one grouping covers another if the first can be transformed into the second by taking a subelement of the form and replacing it with . In these transformations, , , and can be a single factor or a product of factors. These partially ordered sets form a lattice called the Tamari lattice.
a
b
c
(a(bc))
((ab)c)
n
x(yz)
(xy)z
x
y
z
This Demonstration shows graphs formed by lattices generated from factor sequences of different lengths, where each vertex label is a polygon triangulation corresponding to a particular grouping of factors.