Un analogue du monoı̈de plaxique pour les arbres binaires de recherche
[An analogue of the plactic monoid for binary search trees]
Comptes Rendus. Mathématique, Volume 335 (2002) no. 7, pp. 577-580.

We introduce a monoid structure on a certain set of labelled binary trees, by a process similar to the construction of the plactic monoid. This leads to a new interpretation of the algebra of planar binary trees of Loday–Ronco.

Nous introduisons une structure de monoı̈de sur un ensemble d'arbres binaires étiquetés, par un procédé analogue à la construction du monoı̈de plaxique. Nous en déduisons une nouvelle approche de l'algèbre des arbres binaires de Loday–Ronco.

Received:
Accepted:
Published online:
DOI: 10.1016/S1631-073X(02)02537-2
Hivert, Florent 1; Novelli, Jean-Christophe 1; Thibon, Jean-Yves 1

1 Institut Gaspard Monge, Université de Marne-la-Vallée, 77454 Marne-la-Vallée cedex, France
@article{CRMATH_2002__335_7_577_0,
     author = {Hivert, Florent and Novelli, Jean-Christophe and Thibon, Jean-Yves},
     title = {Un analogue du mono{\i}\ensuremath{\ddot{}}de plaxique pour les arbres binaires de recherche},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {577--580},
     publisher = {Elsevier},
     volume = {335},
     number = {7},
     year = {2002},
     doi = {10.1016/S1631-073X(02)02537-2},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1016/S1631-073X(02)02537-2/}
}
TY  - JOUR
AU  - Hivert, Florent
AU  - Novelli, Jean-Christophe
AU  - Thibon, Jean-Yves
TI  - Un analogue du monoı̈de plaxique pour les arbres binaires de recherche
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 577
EP  - 580
VL  - 335
IS  - 7
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/S1631-073X(02)02537-2/
DO  - 10.1016/S1631-073X(02)02537-2
LA  - fr
ID  - CRMATH_2002__335_7_577_0
ER  - 
%0 Journal Article
%A Hivert, Florent
%A Novelli, Jean-Christophe
%A Thibon, Jean-Yves
%T Un analogue du monoı̈de plaxique pour les arbres binaires de recherche
%J Comptes Rendus. Mathématique
%D 2002
%P 577-580
%V 335
%N 7
%I Elsevier
%U http://www.numdam.org/articles/10.1016/S1631-073X(02)02537-2/
%R 10.1016/S1631-073X(02)02537-2
%G fr
%F CRMATH_2002__335_7_577_0
Hivert, Florent; Novelli, Jean-Christophe; Thibon, Jean-Yves. Un analogue du monoı̈de plaxique pour les arbres binaires de recherche. Comptes Rendus. Mathématique, Volume 335 (2002) no. 7, pp. 577-580. doi : 10.1016/S1631-073X(02)02537-2. http://www.numdam.org/articles/10.1016/S1631-073X(02)02537-2/

[1] Björner, A.; Wachs, M. q-Hook length formulas for forests, J. Combin. Theory Ser. A, Volume 52 (1989), pp. 165-187

[2] Björner, A.; Wachs, M. Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A, Volume 58 (1991), pp. 85-114

[3] Duchamp, G.; Hivert, F.; Thibon, J.-Y. Une généralisation des fonctions quasi-symétriques et des fonctions symétriques non commutatives, C. R. Acad. Sci. Paris, Série I, Volume 328 (1999) no. 12, pp. 1113-1116

[4] G. Duchamp, F. Hivert, J.-Y. Thibon, Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras, Internat. J. Algebra Comput., à paraı̂tre

[5] G. Duchamp, F. Hivert, J.-Y. Thibon, Noncommutative symmetric functions VII, en préparation

[6] Fomin, S. Duality of graded graphs, J. Algebraic Combin., Volume 3 (1994), pp. 357-404

[7] Frame, J.S.; de B. Robinson, G.; Thrall, R.M. The hook graphs of the symmetric groups, Canadian J. Math., Volume 6 (1954), pp. 316-324

[8] Knuth, D.E. The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, 1973

[9] Krob, D.; Thibon, J.-Y. Noncommutative symmetric functions IV: Quantum linear groups and Hecke algebras at q=0, J. Algebraic Combin., Volume 6 (1997) no. 4, pp. 339-376

[10] Lascoux, A.; Schützenberger, M.-P. Le monoı̈de plaxique, Noncommutative Structures in Algebra and Geometric Combinatorics, Naples, 1978, Quad. Ricerca Sci., 109, CNR, Rome, 1981, pp. 129-156

[11] Loday, J.-L.; Ronco, M.O. Hopf algebra of the planar binary trees, Adv. Math., Volume 139 (1998) no. 2, pp. 293-309

[12] Loday, J.-L.; Ronco, M.O. Order structure on the algebra of permutations and of planar binary trees, J. Algebraic Combin., Volume 15 (2002) no. 3, pp. 253-270

[13] Lothaire, M. Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2002

[14] Malvenuto, C.; Reutenauer, C. Duality between quasi-symmetric functions and Solomon descent algebra, J. Algebra, Volume 177 (1995), pp. 892-967

[15] Poirier, S.; Reutenauer, C. Algèbres de Hopf de tableaux, Ann. Sci. Math. Québec, Volume 19 (1995) no. 1, pp. 79-90

[16] Ronco, M.O. Primitive elements in a free dendriform Hopf algebra, Contemp. Math., 267, 2000 (pp. 245–264)

[17] Stanley, R.P. Ordered structures and partitions, Mem. Amer. Math. Soc., Volume 119 (1972)

Cited by Sources: