×

zbMATH — the first resource for mathematics

Hopf algebras of \(m\)-permutations, \((m + 1)\)-ary trees, and \(m\)-parking functions. (English) Zbl 1436.16047
The Loday-Ronco Hopf algebra of planar binary trees can be seen as a Hopf subalgebra of the algebra of permutations, generated by sum of permutations given by the sylvester congruence; similarly, the plactic congruence gives a Hopf subalgebra of standard Young tableaux. For both these subalgebras, the product is given by intervals in suitable posets, respectively Tamari for trees and Melnikov for tableaux.
These results are generalized to a family of Hopf algebras indexed by a positive integer \(m\). A \(m\)-permutation is a shuffle of \(m\) permutations of the same length; they generate a Hopf algebra. Similar objects are defined on \(m\)-packed words and on \(m\)-parking functions. Three congruences are defined on \(m\)-permutations: the sylvester one, giving a Hopf subalgebra of \(m+1\)-ary planar trees, which product is given by intervals in the \(m\)-Tamari posets; the metasylvester one, giving a Hopf subalgebra of decreasing \(m+1\)-ary trees (as these objects are not in bijections with \(m\)-permutations, except if \(m=1\)); the hyposylvester one, giving a Hopf subalgebran such that the dimension of the graded components of degree \(n\) is \((m+1)^{n-1}\). Similar results are given for \(m\)-packed words and \(m\)-parking functions. The dimensions of the components of all these Hopf algebras are computed, giving a link with \(m\)-Narayana polynomials.

MSC:
16T30 Connections of Hopf algebras with combinatorics
05E05 Symmetric functions and generalizations
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bergeron, F., Combinatorics of r-Dyck paths, r-Parking functions, and the r-Tamari lattices
[2] Châtel, G.; Pons, V., Counting smaller trees in the Tamari order, (Proceedings of the 25th Conference “Formal Power Series and Algebraic Combinatorics”. Proceedings of the 25th Conference “Formal Power Series and Algebraic Combinatorics”, Paris (2013)) · Zbl 1294.05186
[3] Cigler, J., Some remarks on Catalan families, Eur. J. Comb., 8, 261-267 (1987) · Zbl 0641.05003
[4] Duchamp, G.; Hivert, F.; Thibon, J.-Y., Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras, Int. J. Algebra Comput., 12, 671-717 (2002) · Zbl 1027.05107
[5] Duchamp, G.; Hivert, F.; Novelli, J.-C.; Thibon, J.-Y., Noncommutative symmetric functions VII: free quasi-symmetric functions revisited, Ann. Comb., 15, 655-673 (2011) · Zbl 1233.05200
[6] Edelman, P. H., Chain enumeration and noncrossing partitions, Discrete Math., 31, 2, 171-180 (1980) · Zbl 0443.05011
[7] Foissy, L., Free and cofree Hopf algebras, J. Pure Appl. Algebra, 216, 2, 480-494 (2012) · Zbl 1241.16021
[8] Foissy, L.; Novelli, J.-C.; Thibon, J.-Y., Polynomial realizations of some combinatorial Hopf algebras, J. Noncommut. Geom., 8, 1, 141-162 (2014) · Zbl 1290.05153
[9] Gelfand, I. M.; Krob, D.; Lascoux, A.; Leclerc, B.; Retakh, V. S.; Thibon, J.-Y., Noncommutative symmetric functions, Adv. Math., 112, 218-348 (1995) · Zbl 0831.05063
[10] Hivert, F., Combinatoire des fonctions quasi-symétriques (1999), Marne-la-Vallée, Thèse de Doctorat
[11] Hivert, F., Hecke algebras, difference operators, and quasi-symmetric functions, Adv. Math., 155, 181-238 (2000) · Zbl 0990.05129
[12] Hivert, F.; Novelli, J.-C.; Thibon, J.-Y., The algebra of binary search trees, Theor. Comput. Sci., 339, 129-165 (2005) · Zbl 1072.05052
[13] Hivert, F.; Novelli, J.-C.; Thibon, J.-Y., Trees, functional equations and combinatorial Hopf algebras, Eur. J. Comb., 29, 1682-1695 (2008) · Zbl 1227.05272
[14] Janson, S.; Kuba, M.; Panholzer, A., Generalized Stirling permutations, families of increasing trees and urn models, J. Comb. Theory, Ser. A, 118, 94-114 (2011) · Zbl 1230.05100
[15] Krob, D.; Thibon, J.-Y., Noncommutative symmetric functions IV: quantum linear groups and Hecke algebras at \(q = 0\), J. Algebraic Comb., 6, 339-376 (1997) · Zbl 0881.05120
[16] Lascoux, A.; Schützenberger, M. P., Le monoïde plaxique, Quad. Ric. Sci., 109, 129-156 (1981) · Zbl 0517.20036
[17] Lascoux, A.; Leclerc, B.; Thibon, J.-Y., Crystal graphs and q-analogues of weight multiplicities for the root system \(A_n\), Lett. Math. Phys., 35, 359-374 (1995) · Zbl 0854.17014
[18] Lascoux, A.; Leclerc, B.; Thibon, J.-Y., The plactic monoid, (Lothaire, M., Algebraic Combinatorics on Words (2002), Cambridge University Press), Chapter 5
[19] Leroux, P., A simple symmetry generating operads related to rooted planar m-ary trees and polygonal numbers, J. Integer Seq., 10, 4 (2007), Article 07.4.7, 23 pp · Zbl 1140.05329
[20] Littelman, P., A plactic algebra for semisimple Lie algebras, Adv. Math., 124, 312-331 (1996) · Zbl 0892.17009
[21] Loday, J.-L.; Ronco, M. O., Hopf algebra of the planar binary trees, Adv. Math., 139, 2, 293-309 (1998) · Zbl 0926.16032
[22] Macdonald, I. G., Symmetric Functions and Hall Polynomials (1995), Clarendon Press: Clarendon Press Oxford · Zbl 0899.05068
[23] Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177, 967-982 (1995) · Zbl 0838.05100
[24] Melnikov, A., On orbital variety closures in \(\mathfrak{sl}_n\). I. Induced Duflo order, J. Algebra, 271, 1, 179-233 (2004) · Zbl 1077.17008
[25] Novelli, J.-C., On the hypoplactic monoid, (Proceedings of the 8th Conference “Formal Power Series and Algebraic Combinatorics”. Proceedings of the 8th Conference “Formal Power Series and Algebraic Combinatorics”, Vienna (1997)) · Zbl 0960.05106
[26] Novelli, J.-C., m-dendriform algebras
[27] Novelli, J.-C.; Thibon, J.-Y., Construction of dendriform trialgebras, C. R. Acad. Sci., Paris, 342, 365-369 (2006) · Zbl 1101.17003
[28] Novelli, J.-C.; Thibon, J.-Y., Hopf algebras and dendriform structures arising from parking functions, Fundam. Math., 193, 189-241 (2007) · Zbl 1127.16033
[29] Novelli, J.-C.; Thibon, J.-Y., Noncommutative symmetric functions and Lagrange inversion, Adv. Appl. Math., 40, 8-35 (2008) · Zbl 1133.05101
[30] Novelli, J.-C.; Thibon, J.-Y., Polynomial realizations of some trialgebras, (FPSAC’06. FPSAC’06, San-Diego (2006))
[31] Novelli, J.-C.; Thibon, J.-Y., Duplicial algebras and Lagrange inversion
[32] Nzeutchap, Janvier, Correspondances de Schensted-Fomin, Algèbres de Hopf et graphes gradués en dualité (2008), Université de Rouen, Thèse de Doctorat
[33] Poirier, S.; Reutenauer, C., Algèbre de Hopf des tableaux, Ann. Sci. Math. Qué., 19, 79-90 (1995) · Zbl 0835.16035
[34] Pons, V., Combinatoire algébrique liée aux ordres sur les permutations (2013), Université Paris-Est, Thèse de Doctorat
[35] Song, C., The generalized Schroeder theory, Electron. J. Comb., 12, Article #R53 pp. (2005)
[36] The On-Line Encyclopedia of Integer Sequences (2010), published electronically at
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.