Balanced binary trees in the Tamari lattice

MaRDI QIDQ4591337zbMATH OpenFDO

Authors Samuele Giraudo

Publication date 14 November 2017

Full work available at URL https://arxiv.org/abs/1009.4774, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAN0152

zbMATH Keywords

balanced treescombinatoricsgenerating seriesgrammarsposetsTamari lattice

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Combinatorics of partially ordered sets (06A07)

Abstract: We show that the set of balanced binary trees is closed by interval in the Tamari lattice. We establish that the intervals [T0, T1] where T0 and T1 are balanced trees are isomorphic as posets to a hypercube. We introduce tree patterns and synchronous grammars to get a functional equation of the generating series enumerating balanced tree intervals.

Recommendations

• Intervals of balanced binary trees in the Tamari lattice
• On the number of intervals in Tamari lattices
• Counting smaller trees in the Tamari order
• Two bijections on Tamari intervals
• Counting smaller elements in the Tamari and \(m\)-Tamari lattices

Cited in

(8)

• Cubic realizations of Tamari interval lattices
• The pruning-grafting lattice of binary trees
• The Dyck pattern poset
• Balanced ordered trees
• On a subposet of the Tamari lattice
• Rank-Balanced Trees
• Counting smaller trees in the Tamari order
• Intervals of balanced binary trees in the Tamari lattice

This page was built for publication: Balanced binary trees in the Tamari lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4591337)