# 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
Full Text:
##### References:
  Bergeron, F., Combinatorics of r-Dyck paths, r-Parking functions, and the r-Tamari lattices  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  Cigler, J., Some remarks on Catalan families, Eur. J. Comb., 8, 261-267 (1987) · Zbl 0641.05003  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  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  Edelman, P. H., Chain enumeration and noncrossing partitions, Discrete Math., 31, 2, 171-180 (1980) · Zbl 0443.05011  Foissy, L., Free and cofree Hopf algebras, J. Pure Appl. Algebra, 216, 2, 480-494 (2012) · Zbl 1241.16021  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  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  Hivert, F., Combinatoire des fonctions quasi-symétriques (1999), Marne-la-Vallée, Thèse de Doctorat  Hivert, F., Hecke algebras, difference operators, and quasi-symmetric functions, Adv. Math., 155, 181-238 (2000) · Zbl 0990.05129  Hivert, F.; Novelli, J.-C.; Thibon, J.-Y., The algebra of binary search trees, Theor. Comput. Sci., 339, 129-165 (2005) · Zbl 1072.05052  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  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  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  Lascoux, A.; Schützenberger, M. P., Le monoïde plaxique, Quad. Ric. Sci., 109, 129-156 (1981) · Zbl 0517.20036  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  Lascoux, A.; Leclerc, B.; Thibon, J.-Y., The plactic monoid, (Lothaire, M., Algebraic Combinatorics on Words (2002), Cambridge University Press), Chapter 5  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  Littelman, P., A plactic algebra for semisimple Lie algebras, Adv. Math., 124, 312-331 (1996) · Zbl 0892.17009  Loday, J.-L.; Ronco, M. O., Hopf algebra of the planar binary trees, Adv. Math., 139, 2, 293-309 (1998) · Zbl 0926.16032  Macdonald, I. G., Symmetric Functions and Hall Polynomials (1995), Clarendon Press: Clarendon Press Oxford · Zbl 0899.05068  Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177, 967-982 (1995) · Zbl 0838.05100  Melnikov, A., On orbital variety closures in $$\mathfrak{sl}_n$$. I. Induced Duflo order, J. Algebra, 271, 1, 179-233 (2004) · Zbl 1077.17008  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  Novelli, J.-C., m-dendriform algebras  Novelli, J.-C.; Thibon, J.-Y., Construction of dendriform trialgebras, C. R. Acad. Sci., Paris, 342, 365-369 (2006) · Zbl 1101.17003  Novelli, J.-C.; Thibon, J.-Y., Hopf algebras and dendriform structures arising from parking functions, Fundam. Math., 193, 189-241 (2007) · Zbl 1127.16033  Novelli, J.-C.; Thibon, J.-Y., Noncommutative symmetric functions and Lagrange inversion, Adv. Appl. Math., 40, 8-35 (2008) · Zbl 1133.05101  Novelli, J.-C.; Thibon, J.-Y., Polynomial realizations of some trialgebras, (FPSAC’06. FPSAC’06, San-Diego (2006))  Novelli, J.-C.; Thibon, J.-Y., Duplicial algebras and Lagrange inversion  Nzeutchap, Janvier, Correspondances de Schensted-Fomin, Algèbres de Hopf et graphes gradués en dualité (2008), Université de Rouen, Thèse de Doctorat  Poirier, S.; Reutenauer, C., Algèbre de Hopf des tableaux, Ann. Sci. Math. Qué., 19, 79-90 (1995) · Zbl 0835.16035  Pons, V., Combinatoire algébrique liée aux ordres sur les permutations (2013), Université Paris-Est, Thèse de Doctorat  Song, C., The generalized Schroeder theory, Electron. J. Comb., 12, Article #R53 pp. (2005)  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.