A noncommutative cycle index and new bases of quasi-symmetric functions and noncommutative symmetric functions. (English) Zbl 1460.16037

Summary: We define a new basis of the algebra of quasi-symmetric functions by lifting the cycle-index polynomials of symmetric groups to noncommutative polynomials with coefficients in the algebra of free quasi-symmetric functions, and then projecting the coefficients to QSym. By duality, we obtain a basis of noncommutative symmetric functions, for which a product formula and a recurrence in the form of a combinatorial complex are obtained. This basis allows to identify noncommutative symmetric functions with the quotient of \(\text{FQSym}\) induced by the pattern-replacement relation \(321\equiv 231\) and \(312\equiv 132\).


16T30 Connections of Hopf algebras with combinatorics
05E05 Symmetric functions and generalizations
05A18 Partitions of sets


Full Text: DOI arXiv


[1] Berg, C.; Bergeron, N.; Saliola, F.; Serrano, L.; Zabrocki, M., A lift of the Schur and Hall-Littlewood bases to non-commutative symmetric functions, Canad. J. Math., 66, 525-565 (2014) · Zbl 1291.05206
[2] Björner, A.; Wachs, M., \(q\)-hook-length formulas for forests, J. Combinatorial Theory, Ser. A, 52, 165-187 (1989) · Zbl 0697.06002
[3] L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University, 1968, 1-7.
[4] V. Fazel-Rezai, Equivalence Classes of Permutations Modulo Replacements Between 123 and Two-Integer Patterns.arXiv:1309.4802, 2013. · Zbl 1300.05009
[5] Gelfand, IM; Krob, D.; Lascoux, A.; Leclerc, B.; Retakh, VS; Thibon, J-Y, Noncommutative symmetric functions, Adv. Math., 112, 218-348 (1995) · Zbl 0831.05063
[6] D. Grinberg, Private communication, 2017.
[7] Hivert, F.; Novelli, J-C; Thibon, J-Y, The algebra of binary search trees, Theoretical Computer Science, 339, 129-165 (2005) · Zbl 1072.05052
[8] Hivertand J.-Y. Thibon, F.; Novelli, J.-C.; Tevlin, L., Permutation statistics related to a class of noncommutative symmetric functions and generalizations of the Genocchi numbers, Selecta Math. (N.S.), 15, 1, 105-119 (2009) · Zbl 1194.05161
[9] D. Krob, B. Leclerc, and J.-Y. Thibon, Noncommutative symmetric functions II: Transformations of alphabets, Intern. J. Alg. Comput. 7 no. 2, (1997), 181-264. · Zbl 0907.05055
[10] Krob, D.; Thibon, J-Y, Noncommutative symmetric functions IV : Quantum linear groups and Hecke algebras at \(q=0\), J. Alg. Comb., 6, 339-376 (1997) · Zbl 0881.05120
[11] W. Kuszmaul, Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns, Electronic Journal of Combinatorics 20 (4) (2013), #P10. arXiv:1304.5667v2. · Zbl 1295.05016
[12] W. Kuszmaul and Z. Zhou, Equivalence Classes in \(S_n\) for Three Families of Pattern-Replacement Relations, MIT PRIMES, 2013. http://web.mit.edu/primes/materials/2012/Kuszmaul-Zhou.pdf+
[13] 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
[14] Littelmann, P., A plactic algebra for semisimple Lie algebras, Adv. Math., 124, 312-331 (1996) · Zbl 0892.17009
[15] S. Linton, J. Propp, T. Roby, and J. West, Equivalence Relations of Permutations Generated by Constrained Transpositions. DMTCS Proceedings, North America, July 2010. http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAN0168+ · Zbl 1374.05008
[16] J.-L. Loday, Exponential series without denominators, Lie Theory and its Applications in Physics, IX International Workshop 2013. 10.1007/978-4-431-54270-4_7.
[17] Lothaire, M., Combinatorics on Words (1997), Cambridge: Cambridge University Press, Cambridge · Zbl 0874.20040
[18] Macdonald, IG, Symmetric functions and Hall polynomials (1995), Oxford: Clarendon Press, Oxford
[19] Novelli, J-C; Thibon, J-Y; Toumazet, F., Noncommutative Bell polynomials and the dual immaculate basis, Algebraic Combinatorics, 1, 5, 653-676 (2018) · Zbl 1433.16041
[20] Novelli, J-C; Thibon, J-Y, Hopf Algebras of \(m\)-permutations, \((m+1)\)-ary trees, and \(m\)-parking functions, Advances in Applied Mathematics, 117, 102019 (2020) · Zbl 1436.16047
[21] J. Nzeutchap, Correspondances de Schensted-Fomin, Algèbres de Hopf et graphes gradués en dualité, Thèse de Doctorat, Université de Rouen, 2008.
[22] A. Pierrot, D. Rossin, and J. West, Adjacent transformations in permutations. FPSAC 2011 Proceedings, Discrete Math. Theor. Comput. Sci. Proc., 2011. http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAO0167/3638 · Zbl 1355.05028
[23] Schimming, R.; Rida, SZ, Noncommutative Bell polynomials, Internat. J. Algebra Comput., 6, 635-644 (1996) · Zbl 0899.33006
[24] R. Stanley, An equivalence relation on the symmetric group and multiplicity-free flag \(h\)-vectors, Journal of Combinatorics 3 (2012) no. 3, 277-298. arXiv:1208.3540, 2012. · Zbl 1291.05012
[25] The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org, 2010.
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.