Intervals of balanced binary trees in the Tamari lattice

Details Intervals of balanced binary trees in the Tamari lattice Intervals of balanced binary trees in the Tamari lattice

2011-07-18

arxiv.org/abs/1107.3472v2

Theoretical Computer Science, 420, 1--27, 2012

Mathematics

Combinatorics

38 pages

Scientific paper

10.1016/j.tcs.2011.11.020

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

Affiliated with

Also associated with

No associations

Rating

Intervals of balanced binary trees in the Tamari lattice does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Intervals of balanced binary trees in the Tamari lattice, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intervals of balanced binary trees in the Tamari lattice will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-271873