We introduce a monoid structure on the set of binary search trees, by a
process very similar to the construction of the plactic monoid, the
Robinson-Schensted insertion being replaced by the binary search tree
insertion. This leads to a new construction of the algebra of Planar Binary
Trees of Loday-Ronco, defining it in the same way as Non-Commutative Symmetric
Functions and Free Symmetric Functions. We briefly explain how the main known
properties of the Loday-Ronco algebra can be described and proved with this
combinatorial point of view, and then discuss it from a representation
theoretical point of view, which in turns leads to new combinatorial properties
of binary trees.
%0 Generic
%1 citeulike:71453
%A Hivert, F.
%A Novelli, J.
%A Thibon, J.
%D 2004
%K algebra binary search trees
%T The Algebra of Binary Search Trees
%U http://arxiv.org/abs/math.CO/0401089
%X We introduce a monoid structure on the set of binary search trees, by a
process very similar to the construction of the plactic monoid, the
Robinson-Schensted insertion being replaced by the binary search tree
insertion. This leads to a new construction of the algebra of Planar Binary
Trees of Loday-Ronco, defining it in the same way as Non-Commutative Symmetric
Functions and Free Symmetric Functions. We briefly explain how the main known
properties of the Loday-Ronco algebra can be described and proved with this
combinatorial point of view, and then discuss it from a representation
theoretical point of view, which in turns leads to new combinatorial properties
of binary trees.
@misc{citeulike:71453,
abstract = {We introduce a monoid structure on the set of binary search trees, by a
process very similar to the construction of the plactic monoid, the
Robinson-Schensted insertion being replaced by the binary search tree
insertion. This leads to a new construction of the algebra of Planar Binary
Trees of Loday-Ronco, defining it in the same way as Non-Commutative Symmetric
Functions and Free Symmetric Functions. We briefly explain how the main known
properties of the Loday-Ronco algebra can be described and proved with this
combinatorial point of view, and then discuss it from a representation
theoretical point of view, which in turns leads to new combinatorial properties
of binary trees.},
added-at = {2007-08-18T13:22:24.000+0200},
author = {Hivert, F. and Novelli, J. and Thibon, J.},
biburl = {https://www.bibsonomy.org/bibtex/26b71bd27edb4fe1cf484f1209ebe95a1/a_olympia},
citeulike-article-id = {71453},
description = {citeulike},
eprint = {math.CO/0401089},
interhash = {f4d1ca16d8597cfe462405799794681a},
intrahash = {6b71bd27edb4fe1cf484f1209ebe95a1},
keywords = {algebra binary search trees},
month = {January},
timestamp = {2007-08-18T13:22:57.000+0200},
title = {The Algebra of Binary Search Trees},
url = {http://arxiv.org/abs/math.CO/0401089},
year = 2004
}