Intervals of balanced binary trees in the Tamari lattice
We show that the set of balanced binary trees is closed by interval in the Tamari lattice. We establish that the intervals [T, T']. where T and T' are balanced binary trees are isomorphic as posets to a hypercube. We introduce synchronous grammars that allow to generate treelike structures and obtain fixed-point functional equations to enumerate these. We also introduce imbalance tree patterns and show that they can be used to describe some sets of balanced binary trees that play a particular role in the Tamari lattice. Finally, we investigate other families of binary trees that are also closed by interval in the Tamari lattice. (C) 2011 Elsevier B.V. All rights reserved.
balanced binary tree tamari lattice poset grammar fixed-point functional equation generating series