An analogue of the plactic monoid for binary search trees. (Un analogue du monoïde plaxique pour les arbres binaires de recherche.) (French) Zbl 1013.05026

Summary: 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 J.-L. Loday and M. O. Ronco [Adv. Math. 139, 293-309 (1998; Zbl 0926.16032) and J. Algebr. Comb. 15, 253-270 (2002; Zbl 0998.05013)].


05C05 Trees
68R10 Graph theory (including graph drawing) in computer science
68P10 Searching and sorting
Full Text: DOI arXiv


[1] Björner, A.; Wachs, M., q-hook length formulas for forests, J. combin. theory ser. A, 52, 165-187, (1989) · Zbl 0697.06002
[2] Björner, A.; Wachs, M., Permutation statistics and linear extensions of posets, J. combin. theory ser. A, 58, 85-114, (1991) · Zbl 0742.05084
[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, 328, 12, 1113-1116, (1999) · Zbl 0978.05072
[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 · Zbl 1027.05107
[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., 3, 357-404, (1994) · Zbl 0810.05005
[7] Frame, J.S.; de B. Robinson, G.; Thrall, R.M., The hook graphs of the symmetric groups, Canadian J. math., 6, 316-324, (1954) · Zbl 0055.25404
[8] Knuth, D.E., The art of computer programming, vol. 3, sorting and searching, (1973), Addison-Wesley · Zbl 0302.68010
[9] Krob, D.; Thibon, J.-Y., Noncommutative symmetric functions IV: quantum linear groups and Hecke algebras at q=0, J. algebraic combin., 6, 4, 339-376, (1997) · Zbl 0881.05120
[10] Lascoux, A.; Schützenberger, M.-P., Le monoı̈de plaxique, (), 129-156 · Zbl 0517.20036
[11] Loday, J.-L.; Ronco, M.O., Hopf algebra of the planar binary trees, Adv. math., 139, 2, 293-309, (1998) · Zbl 0926.16032
[12] Loday, J.-L.; Ronco, M.O., Order structure on the algebra of permutations and of planar binary trees, J. algebraic combin., 15, 3, 253-270, (2002) · Zbl 0998.05013
[13] Lothaire, M., Algebraic combinatorics on words, (2002), Cambridge University Press Cambridge · Zbl 1001.68093
[14] Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and Solomon descent algebra, J. algebra, 177, 892-967, (1995) · Zbl 0838.05100
[15] Poirier, S.; Reutenauer, C., Algèbres de Hopf de tableaux, Ann. sci. math. Québec, 19, 1, 79-90, (1995) · Zbl 0835.16035
[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., 119, (1972) · Zbl 0246.05007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.