zbMATH — the first resource for mathematics

The algebra of binary search trees. (English) Zbl 1072.05052
Summary: 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.

05E05 Symmetric functions and generalizations
68P05 Data structures
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI arXiv
[1] M. Aguiar, N. Bergeron, F. Sottile, Combinatorial Hopf Algebra and generalized Dehn-Sommerville relations, Compos. Math., to appear. · Zbl 1092.05070
[2] J.-C. Aval, F. Bergeron, N. Bergeron, Ideals of quasi-symmetric functions and super-covariant polynomials for \(S_n\), Adv. Math. 181 (2) (2004) 353-367. · Zbl 1031.05127
[3] Björner, A.; Wachs, M., q-hook length formulas for forests, J. combin. theory ser. A, 52, 165-187, (1989) · Zbl 0697.06002
[4] Björner, A.; Wachs, M., Permutation statistics and linear extensions of posets, J. combin. theory ser. A, 58, 85-114, (1991) · Zbl 0742.05084
[5] G. Duchamp, F. Hivert, J.-C. Novelli, J.-Y. Thibon, Noncommutative symmetric functions VII, in preparation. · Zbl 1233.05200
[6] 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ér. I math., 328, 12, 1113-1116, (1999) · Zbl 0978.05072
[7] Duchamp, G.; Hivert, F.; Thibon, J.-Y., Noncommutative symmetric functions vifree quasi-symmetric functions and related algebras, Internat. J. algebra comput., 12, 671-717, (2002) · Zbl 1027.05107
[8] Fomin, S., Duality of graded graphs, J. algebra combin., 3, 357-404, (1994) · Zbl 0810.05005
[9] Frame, J.S.; Robinson, G.deB.; Thrall, R.M., The hook graphs of the symmetric groups, Canad. J. math., 6, 316-324, (1954) · Zbl 0055.25404
[10] L. Geissinger, Hopf algebras of symmetric functions and class functions. Combinatoire et représentation du groupe symétrique (Actes Table Ronde C.N.R.S., Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976) Lecture Notes in Mathematics, Vol. 579, Springer, Berlin, 1977, pp. 168-181.
[11] I. Gessel, Multipartite P-partitions and inner product of skew Schur functions, in: C. Greene (Ed.), Combinatorics and Algebra, Contemporary Mathematics, Vol. 34, 1984, pp. 289-301.
[12] Hivert, F.; Novelli, J.-C.; Thibon, J.-Y., Un analogue du monoı¨de plaxique pour LES arbres binaires de recherche, C. R. acad. sci. Paris Sér I math., 332, 577-580, (2002) · Zbl 1013.05026
[13] Hivert, F.; Novelli, J.-C.; Thibon, J.-Y., Sur quelques propriétés de l’algèbre des arbres binaires, C. R. acad. sci. Paris Sér I math., 337, 565-568, (2003) · Zbl 1029.05033
[14] Jimbo, M., A q-analogue of U(gl(N+1)), Hecke algebra and the yang – baxter equation, Lett. math. phys., 11, 247-252, (1986) · Zbl 0602.17005
[15] Kashiwara, M., Crystallizing the q-analogue of universal enveloping algebras, Comm. math. phys., 133, 249-260, (1991) · Zbl 0749.17017
[16] Knuth, D.E., Permutations, matrices and generalized Young tableaux, Pacific J. math., 34, 709-727, (1970) · Zbl 0199.31901
[17] D.E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010
[18] Krob, D.; Thibon, J.-Y., Noncommutative symmetric functions ivquantum linear groups and Hecke algebras at q=0, J. algebraic combin., 6, 4, 339-376, (1997) · Zbl 0881.05120
[19] Lascoux, A.; Leclerc, B.; Thibon, J.-Y., Crystal graphs and q-analogues of weight multiplicities for the root system an, Lett. math. phys., 35, 359-374, (1995) · Zbl 0854.17014
[20] Lascoux, A.; Leclerc, B.; Thibon, J.-Y., The plactic monoid, (), (Chapter 5)
[21] A. Lascoux, M.-P. Schützenberger, Le monoı¨de plaxique, in: A. De Luca (Ed.), Noncommutative Structures in Algebra and Geometric Combinatorics, Quadersni Ricerca Science, Vol. 109 (Rome, 1981), pp. 129-156.
[22] Littelmann, P., A plactic algebra for semisimple Lie algebras, Adv. math., 124, 312-331, (1996) · Zbl 0892.17009
[23] Loday, J.-L.; Ronco, M.O., Hopf algebra of the planar binary trees, Adv. math., 139, 2, 293-309, (1998) · Zbl 0926.16032
[24] 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
[25] Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and Solomon descent algebra, J. algebra, 177, 892-967, (1995) · Zbl 0838.05100
[26] Novelli, J.-C., On the hypoplactic monoid, Discrete math., 217, 315-336, (2000) · Zbl 0960.05106
[27] Novelli, J.-C.; Pak, I.; Stoyanovskii, A.V., A direct bijective proof of the hook-length formula, Discrete math. theor. comput. sci., 1, 53-67, (1997) · Zbl 0934.05125
[28] J.-C. Novelli, J.-Y. Thibon, A Hopf algebra of parking functions, preprint, math.CO/0312126, 2003.
[29] Poirier, S.; Reutenauer, C., Algèbres de Hopf de tableaux, Ann. sci. math. Québec, 19, 1, 79-90, (1995) · Zbl 0835.16035
[30] C. Reutenauer, Free Lie algebras, Oxford, 1993.
[31] Ronco, M.O., Primitive elements in a free dendriform Hopf algebra, Contemp. maths., 267, 245-264, (2000) · Zbl 0974.16035
[32] Schensted, C., Longest increasing and decreasing subsequences, Canad. J. math., 13, 178-191, (1961) · Zbl 0097.25202
[33] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, \(\sim\) · Zbl 1274.11001
[34] Stanley, R.P., Ordered structures and partitions, () · Zbl 0246.05007
[35] R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole Mathematical Series, Pacific Grove, 1986. · Zbl 0608.05001
[36] Stanley, R.P., ()
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.