A Noncommutative Cycle Index and New Bases of Quasi-symmetric Functions and Noncommutative Symmetric Functions
- PDF / 619,947 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 297 Views
Annals of Combinatorics
A Noncommutative Cycle Index and New Bases of Quasi-symmetric Functions and Noncommutative Symmetric Functions Jean-Christophe Novelli, Jean-Yves Thibon and Fr´ed´eric Toumazet Abstract. 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 quasisymmetric 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 FQSym induced by the patternreplacement relation 321 ≡ 231 and 312 ≡ 132. Mathematics Subject Classification. 16T30, 05E05, 05A18. Keywords. Noncommutative symmetric functions, Quasi-symmetric functions, Dendriform algebras.
1. Introduction mn 1 m2 For a partition μ = 1m1 2m2 · · · nmn of n, the coefficient of pμ = pm 1 p2 · · · pn in the polynomial hn (p1 , . . . , pn ) defined by h0 = 1 and the recursion:
nhn = hn−1 p1 + hn−2 p2 + · · · + pn
(1)
is the number of permutations of cycle type μ, divided by n!. Thus, hn is the cycle index of the symmetric group Sn , and if the pk are interpreted as the power sums symmetric functions, then hn is the complete symmetric function (sum of all monomials of degree n), cf. [18]. There is a noncommutative analogue of this polynomial, which defines the so-called noncommutative power sums of the first kind Ψn in terms of the noncommutative complete functions Sn [5]: nSn = Sn−1 Ψ1 + Sn−2 Ψ2 + · · · + Ψn . 0123456789().: V,-vol
(2)
J.-C. Novelli et al.
It is not difficult to see that the coefficient cI in n! ΨI cI ΨI = n!Sn = i1 (i1 + i2 ) · · · (i1 + i2 + · · · ir ) I
(3)
I
counts the permutations with ordered cycle type I; that is, the composition consisting of the lengths of the cycles, ordered by increasing values of their maxima. For example: 4!h4 = p1111 + 6p211 + 3p22 + 8p31 + 6p4 , 1111
4!S4 = Ψ
112
+ 3Ψ
121
+ 2Ψ
13
+ 6Ψ
(4) 211
+Ψ
22
+ 3Ψ
31
+ 2Ψ
+ 6Ψ4 ,
(5)
the three transpositions of ordered cycle type (1, 1, 2) being (1)(2)(43), (1)(3)(42), and (2)(3)(41), while (1)(32)(4) and (2)(31)(4) are of type (1, 2, 1), and (21)(3)(4) is of type (2, 1, 1). Setting yn = (n − 1)!pn and Yn = (n − 1)!Ψn , which amounts to forgetting the order inside the cycles, n!hn and n!Sn become, respectively, the usual exponential Bell polynomial Bn (y1 , . . . , yn ), whose coefficients count set partitions according to the sizes of the blocks, and its natural noncommutative analogue [23] refining this counting according to a canonical ordering of the blocks. This situation has been exploited in [19] to define further generalizations of the Bell polynomials, whose coefficients live in the algebra of free quasisymmetric functions and encode the set partitions counted by the original coefficients in a way preserving their algebraic properties. The commutative images of
Data Loading...
