Treillis de Tamari

Chaque groupement décrit une façon de combiner les objets par une opération binaire, ou aussi l'ordre dans lequel on évalue les opérations; dans un treillis de Tamari, les divers groupements sont ordonnés : un groupement précède un autre si le deuxième s'obtient à partir du premier par l'application de la règle d'associativité (xy)z → x(yz) qui repousse les parenthèses vers la droite. Par exemple, on obtient (a(bc))d → a((bc)d), et dans le treillis de Tamari, on a (a(bc))d ≤ a((bc)d).

Pour l'ordre ainsi introduit, deux éléments ${\displaystyle x}$ et ${\displaystyle y}$ possèdent toujours une borne inférieure ${\displaystyle x\land y}$, et une borne supérieure ${\displaystyle x\lor y}$. Ainsi, le treillis de Tamari est bien un treillis au sens des ensembles ordonnés. Le plus grand élément est celui où les parenthésages se font le plus à gauche, et plus petit celui où les parenthésages sont le plus à droite. Le diagramme de Hasse de ce treillis est isomorphe au graphe d'un associaèdre. Le nombre d'éléments d'un treillis de Tamari pour une séquence de ${\displaystyle n}$ objets est le ${\displaystyle n}$^ième nombre de Catalan.

Le treillis de Tamari peut être décrit de plusieurs autres manières, toutes plus ou moins liées aux diverses interprétations des nombres de Catalan eux-mêmes :

• C'est l'ensemble des suites d'entiers ${\displaystyle (a_{1},\ldots ,a_{n})}$ tels que ${\displaystyle i\leq a_{i}\leq n}$ et, de plus, si ${\displaystyle i\leq j\leq a_{i}}$, alors ${\displaystyle a_{j}\leq a_{i}}$(Huang et Tamari 1972).
• C'est l'ensemble des arbres binaires, avec l'opération de rotation.
• C'est aussi l'ensemble des forêts ordonnées. Une forêt est inférieure à une autre si le ${\displaystyle j}$^ième nœud, dans un parcours préfixe de la première forêt a au moins autant de descendants que le ${\displaystyle j}$^ième nœud de la deuxième forêt (caractérisation citée dans : Knuth 2011, Section 7.2.1.6: Generating All Trees^[1]).
• C'est l'ensemble des triangulations d'un polygone convexe à n sommets, ordonnées par l'opération flip qui consiste à enlever une arête de la triangulation, et de la remplacer, dans le quadrilatère apparaissant, par la diagonale opposée (ceci résulte de la dualité entre arbres binaires et triangulations).
• C'est aussi l'ensemble des chemins de Dyck de longueur ${\displaystyle 2n}$, résultant du parcours des arbres binaires. L'ordre est induit par une rotation qui consiste à échanger un pas descendant avec le chemin de Dyck élémentaire (sans retour à 0) suivant.