COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

arXiv:math.CO/0605262 v1 10 May 2006

FLORENT HIVERT, JEAN-CHRISTOPHE NOVELLI, AND JEAN-YVES THIBON
Abstract. We propose several constructions of commutative or cocommutative
Hopf algebras based on various combinatorial structures, and investigate the relations between them. A commutative Hopf algebra of permutations is obtained by ageneral construction based on graphs, and its non-commutative dual is realized inthree different ways, in particular as the Grossman-Larson algebra of heap ordered
trees. Extensions to endofunctions, parking functions, set compositions, set partitions, planar binary trees and rooted forests are discussed. Finally, we introduce
one-parameter families interpolating between different structures constructed on
the same combinatorial objects.

Contents
1. Introduction
2. A commutative Hopf algebra of endofunctions
3. A commutative Hopf algebra of permutations
3.1. The Hopf algebra of bijective endofunctions
3.2. Duality
3.3. Cyclic tensors and SQSym
3.4. Interpretation of H(V )3.5. Subalgebras of SQSym
3.6. Quotients of WSym
3.7. The stalactic monoid
3.8. Other Hopf algebras derived from the stalactic congruence
4. Structure of SSym
4.1. A realization of SSym
4.2. Quotients of ΦSym
5. Parking functions and trees
5.1. A commutative algebra of parking functions
5.2. From labelled to unlabelled parking graphs
5.3. Binary trees and nondecreasing parking functions
5.4. From nondecreasing parking functions to rooted forests
6. Quantum versions
6.1. Quantum quasi-symmetric functions
6.2. Quantum free quasi-symmetric functions
Acknowledgements
References
1

2
2
5
5
6
7
9
10
12
13
14
18
18
23
23
23
24
25
25
25
25
26
28
29

2

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

1. Introduction
Many examples of Hopf algebras based on combinatorial structures are known.
Among these, algebras based on permutations and planar binary trees play a prominent role, and arise in seemingly unrelated contexts [21, 19, 8, 5]. As Hopf algebras,
both are noncommutative and non cocommutative, and in fact self-dual.
More recently, cocommutative Hopf algebras of binary trees and permutations
have been constructed [22, 2]. In [22], binary trees arise as sums over rearrangements
classes in an algebra of parking functions, while in [2], cocommutative Hopf algebras
are obtained as the graded coalgebras associated with coradical fitrations.
In [25], a general method for constructing commutative Hopf algebras based on
various kind of graphs has been presented. The aim of this note is to investigate
Hopf algebras based on permutations and trees constructed by the method developed in [25]. These commutative algebras are, by definition, realized in terms ofpolynomials in an infinite set of doubly indexed indeterminates. The dual Hopf algebras are then realized by means of non commutative polynomials in variables aij . Weshow that these first resulting algebras are isomorphic (in a non trivial way) to theduals of those of [2], and study some generalizations such as endofunctions, parking
functions, set partitions, trees, forests, and so on.
The possibility to obtain in an almost systematic way commutative, and in general non cocommutative, versions of the usual combinatorial Hopf algebras leads us
to conjecture that these standard versions should be considered as some kind ofquantum groups, i.e., can be incorporated into one-parameter families, containing
an enveloping algebra and its dual for special values of the parameter. A few results
supporting this point of view are presented in the final section.
In all the paper, K will denote a field of characteristic zero. All the notations
used here is as in [9, 25]. This paper is an expanded and updated version of the
preprint [14].
2. A commutative Hopf algebra of endofunctions
Permutations can be regarded in an obvious way as labelled and oriented graphs
whose connected components are cycles. Actually, arbitrary endofunctions (functions
from [n] := {1, . . . , n} to itself) can be regarded as labelled graphs, connecting i withf (i) for all i so as to fit in the framework of [25], where a general process for building
Hopf algebras of graphs is described.
In the sequel, we identify an endofunction f of [n] with the word(1)

wf = f (1)f (2) · · · f (n) ∈ [n]n .

Let {xi j | i, j ≥ 1} be an infinite set of commuting indeterminates, and let J be
the ideal of R = K [xi j | i, j ≥ 1] generated by the relations(2)

xi j xi k = 0 for all i, j, k.

For an endofunction f : [n] → [n], defineXxi1 if (1) · · · xin if (n) ,
(3)
Mf :=
i1 <···<inCOMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

3

in R/J .
It follows from [25], Section 4, that
Theorem 2.1. The Mf span a subalgebra EQSym of the commutative algebra R/J .
hMore precisely, there exist non-negative integers Cf,gsuch that
X
h
Cf,g
Mh .
(4)
Mf Mg =h

Example 2.2.
(5)

M1 M22 = M133 + M323 + M223 .

(6)

M1 M331 = M1442 + M4241 + M4431 + M3314 .

(7)

M12 M21 = M1243 + M1432 + M4231 + M1324 + M3214 + M2134 .

(8)

M12 M22 = M1244 + M1434 + M4234 + M1334 + M3234 + M2234 .

(9)

M12 M133 = 3M12355 + 2M12445 + 2M12545 + M13345 + M14345 + M15345 .

The shifted concatenation of two endofunctions f : [n] → [n] and g : [m] → [m] isthe endofunction h := f • g of [n + m] such that wh := wf • wg , that ish(i) = f (i) if i ≤ n(10)h(i) = n + g(i − n) if i > nhWe can now give a combinatorial interpretation of the coefficient Cf,g
: if f : [n] →[n] and g : [m] → [m], this coefficient is the number of permutations τ in the shuffle
product (1 . . . p) (p + 1 . . . p + n) such that(11)h = τ −1 ◦ (f • g) ◦ τ.

For example, with f = 12 and g = 22, one finds the set (see Equation (8))(12){1244, 1434, 4234, 1334, 3234, 2234}.

Now, still following [25], define a coproduct by(13)∆Mh :=

X

Mf ⊗ Mg .

(f,g);f •g=hThis endows EQSym with a (commutative, non cocommutative) Hopf algebra structure.

4

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

Example 2.3.
(14)

∆M626124 = M626124 ⊗ 1 + 1 ⊗ M626124 .

(15)∆M4232277 = M4232277 ⊗ 1 + M42322 ⊗ M22 + 1 ⊗ M4232277 .

Define a connected endofunction as a function that cannot be obtained by non
trivial shifted concatenation. For example, the connected endofunctions for n =1, 2, 3 are(16)

1,
11, 21, 22,111, 112, 121, 131, 211, 212, 221, 222, 231, 232,
233, 311, 312, 313, 321, 322, 323, 331, 332, 333,

and the generating series of their number begins with(17)

t + 3 t2 + 20 t3 + 197 t4 + 2511 t5 + 38924 t6 + 708105 t7 + 14769175 t8 .

Then, the definition of the coproduct of the Mf implies
Proposition 2.4. If (Sf ) denotes the dual basis of (Mf ), the graded dual ESym :=EQSym ∗ is free over the set(18){Sf | f connected}.

Indeed, Equation (13) is equivalent to(19)

Sf Sg = Sf •g .

Now, ESym being a graded connected cocommutative Hopf algebra, it follows
from the Cartier-Milnor-Moore theorem that
(20)

ESym = U(L),where L is the Lie algebra of its primitive elements. Let us now prove
Theorem 2.5. As a graded Lie algebra, the primitive Lie algebra L of ESym is freeover a set indexed by connected endofunctions.
Proof – Assume it is the case. By standard arguments on generating series, one
finds that the number of generators of L in degree n is equal to the number ofalgebraic generators of ESym in degree n, parametrized for example by connected
endofunctions. We will now show that L has at least this number of generatorsand that those generators are algebraically independent, determining completely thedimensions of the homogeneous components Ln of L whose generating series beginsby(21)

t + 3 t2 + 23 t3 + 223 t4 + 2800 t5 + 42576 t6 + 763220 t7 + 15734388 t8 + . . .

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

5

Following Reutenauer [28] p. 58, denote by π1 the Eulerian idempotent, that is, theendomorphism of ESym defined by π1 = log∗ (Id). It is obvious, thanks to thedefinition of Sf that(22)

π1 (Sf ) = Sf + · · · ,where the dots stand for terms Sg such that g is not connected. Since the Sf associated with connected endofunctions are independent, the dimension of Ln is at least
equal to the number of connected endofunctions of size n. So L is free over a set ofprimitive elements parametrized by connected endofunctions.
There are many Hopf subalgebras of EQSym which can be defined by imposing
natural restrictions to maps: being bijective (see Section 3), idempotent (f 2 = f ),involutive (f 2 = id), or more generally the Burnside classes (f p = f q ), and so on.
We shall start with the Hopf algebra of permutations.
3. A commutative Hopf algebra of permutations
We will use two different notations for permutations depending whether they are
considered as bijections from [1, n] onto itself or as product of cycles. In the firstcase, we will write σ = 31542 for the bijection σ where σ(i) = σi . In the second
case, the same permutation will be written σ = (1352)(4) since 31542 is composed of
two cycles : the cycle (1352) sending each element to the next one (circularly) in thesequence and the cycle (4) composed of only one element.
3.1. The Hopf algebra of bijective endofunctions. Let us define SQSym as thesubalgebra of EQSym spanned by theX
xi1 iσ(1) · · · xin iσ(n) ,
(23)
Mσ =
i1 <···<in

where σ runs over bijective endofunctions, i.e., permutations. Note that SQSym isalso isomorphic to the image of EQSym in the quotient of R/J by the relations(24)

xi k xj k = 0 for all i, j, k.

By the usual argument, it follows that
Proposition 3.1. The Mσ span a Hopf subalgebra SQSym of the commutative Hopf
algebra EQSym.
γ
As already mentionned, there exist non-negative integers Cα,βsuch thatX γ(25)
Mα Mβ =Cα,β Mγ .
γhThe combinatorial interpretation of the coefficients Cf,gseen in Section 2 can bereformulated in the special case of permutations. Write α and β as a union of disjoint
cycles. Split the set [n + m] into a set A of n elements, and its complement B, in
all possible ways. For each splitting, apply to α (resp. β) in A (resp. B) the unique

6

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

increasing morphism of alphabets from [n] to A (resp. from [m] to B) and return thelist of permutations with the resulting cycles. On the example α = (1)(2) = 12 andβ = (13)(2) = 321, this yields(26)(1)(2)(53)(4), (1)(3)(52)(4), (1)(4)(52)(3), (1)(5)(42)(3), (2)(3)(51)(4),(2)(4)(51)(3), (2)(5)(41)(3), (3)(4)(51)(2), (3)(5)(41)(2), (4)(5)(31)(2).

This set corresponds to the permutations and multiplicities of Equation (31).
A third interpretation of this product comes from the dual coproduct point of view:
γCα,βis the number of ways of getting (α, β) as the standardized words of pairs (a, b)of two complementary subsets of cycles of γ. For example, with α = 12, β = 321,and γ = 52341, one has three solutions for the pair (a, b), namely(27)((2)(3), (4)(51)), ((2)(4), (3)(51)), ((3)(4), (2)(51)),

which is coherent with Equations (26) and (31).
Example 3.2.
(28)

M12···n M12···p =




n+p
M12···(n+p) .
n(29)

M1 M21 = M132 + M213 + M321 .

(30)

M12 M21 = M1243 + M1324 + M1432 + M2134 + M3214 + M4231 .

(31)

M12 M321 = M12543 + M14325 + 2M15342 + M32145 + 2M42315 + 3M52341 .

(32)

M21 M123 = M12354 + M12435 + M12543 + M13245 + M14325+ M15342 + M21345 + M32145 + M42315 + M52341 .

(33)

M21 M231 = M21453 + M23154 + M24513 + M25431 + M34152+ M34521 + M35412 + M43251 + M43512 + M53421 .

3.2. Duality. Recall that the coproduct is given by(34)∆Mσ :=

X

Mα ⊗ Mβ .

(α,β);α•β=σAs in Section 2, this implies
Proposition 3.3. If (Sσ ) denotes the dual basis of (Mσ ), the graded dual SSym :=SQSym ∗ is free over the set(35){Sα | α connected}.

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

7

Indeed, Equation (34) is equivalent toSα Sβ = Sα•β .

(36)Note that SSym is both a subalgebra and a quotient of ESym, since SQSym isboth a quotient and a subalgebra of EQSym.
Now, as before, SSym being a graded connected cocommutative Hopf algebra, it
follows from the Cartier-Milnor-Moore theorem that(37)

SSym = U(L),where L is the Lie algebra of its primitive elements.
The same argument as in Section 2 proves
Theorem 3.4. The graded Lie algebra L of primitive elements of SSym is free overa set indexed by connected permutations.
Corollary 3.5. SSym is isomorphic to HO , the Grossman-Larson Hopf algebra ofheap-ordered trees [11].
According to [2], SQSym (= SSym∗ ) is therefore isomorphic to the quotient of
FQSym by its coradical filtration.
3.3. Cyclic tensors and SQSym. For a vector space V , let Γn V be the subspaceof V ⊗n spanned by cyclic tensors, i.e., sums of the form
n−1
X

(38)

(v1 ⊗ · · · ⊗ vn )γ k ,k=0where γ is the cycle (1, 2, . . . , n), the right action of permutations on tensors being
as usual(v1 ⊗ · · · ⊗ vn )σ = vσ(1) ⊗ · · · ⊗ vσ(n) .

(39)

Clearly, Γn V is stable under the action of GL(V ), and its character is the symmetricfunction “cyclic character” [30, 17]:
1X
n/d
(40)
ln(0) =
φ(d)pd ,n
d|nwhere φ is Euler’s function.
(0)
Let Ln be the subspace of CSn spanned by cyclic permutations. This is a submodule of CSn for the conjugation action ρτ (σ) = τ στ −1 with Frobenius characteristic(0)ln . Then one can define the analytic functor Γ [15, 20]:
X
(41)
Γ(V ) =
V ⊗n ⊗CSn L(0)
n .
n≥0

L

n

Let Γ(V ) = n≥1 Γ (V ). Its symmetric algebra H(V ) = S(Γ(V )) can be endowedwith a Hopf algebra structure, by declaring the elements of Γ(V ) primitive.

8

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBONAs an analytic functor, V 7→ H(V ) corresponds to the sequence of Sn -modules
Mn = CSn endowed with the conjugation action, that is,
M(42)
H(V ) =
V ⊗n ⊗CSn Mn ,
n≥0

 
w
so that basis elements of Hn (V ) can be identified with symbols
with w ∈ V ⊗nσ
and σ ∈ Sn subject to the equivalences −1   
w
wτ
(43)
.
−1 ≡
τ στ
σ
Let A := {an | n ≥ 1} be an infinite linearly ordered alphabet, and V = CA. We
identify a tensor product of letters ai1 ⊗ · · · ⊗ ain with the corresponding word w =ai1 . . . ain and denote by (w) ∈ Γn V the circular class of w. A basis of Hn (V ) is thengiven by the commutative products(44)m = (w1 ) · · · (wp ) ∈ S(ΓV )of circular words, with |w1 | + · · · + |wp | = n and |wi | ≥ 1 for all i.
With such a basis element, we can associate a permutation by the following standardization process. Fix a total order on circular words, for example the lexicographic
order on minimal representatives. Write m as a non-decreasing product(45)m = (w1 ) · · · (wp ) with (w1 ) ≤ (w2 ) ≤ · · · ≤ (wp ),and compute the ordinary standardization σ ′ of the word w = w1 · · · wp . Then, σ isthe permutation obtained by parenthesing the word σ ′ like m and interpreting thefactors as cycles. For example, if
m = (cba)(aba)(ac)(ba) = (aab)(ab)(ac)(acb)w = aababacacb(46)

σ ′ = 12637495 10 8
σ = (126)(37)(49)(5 10 8)
σ = (2, 6, 7, 9, 10, 1, 3, 5, 4, 8)

We set σ = cstd(m) and define it as the circular standardized of m.
Let Hσ (V ) be the subspace of Hn (V ) spanned by those m such that cstd(m) =σ, and let πσ : H(V ) → Hσ (V ) be the projector associated with the direct sum
decompositionMM
Hσ (V ).
(47)
H(V ) =
n≥0 σ∈Sn

Computing the convolution of such projectors then yields the following

Theorem 3.6. The πσ span a subalgebra of the convolution algebra Endgr H(V ),isomorphic to SQSym via πσ 7→ Mσ .

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

9Proof – First, note that πα ∗ πβ is a sum of πγ : indeed,πα ∗ πβ (m) = πα ∗ πβ (cstd(m)),(48)

since the circular standardized of a subword of m is equal to the circular standardizedof the same subword of cstd(m). SoX
σ(49)
πα ∗ πβ =
Dα,β
πσ .
σ

Now, by definition of πα and by the third interpretation of the product of the Mσ ,σσone concludes that Dα,βis equal to the Cα,βof Equation (25).
3.4. Interpretation of H(V ). The Hopf algebra H(V ) can be interpreted as analgebra of functions as follows. Assume V has dimension d, and let a1 , . . . , ad be abasis of V .
To the generator (ai1 · · · ain ) of H(V ), we associate the function of d matrices(50)

f(i1 ,...,in ) (A1 , . . . , Ad ) = tr(Ai1 · · · Ain ).

These functions are clearly invariant under simultaneous conjugation Ai 7→ MAi M −1 ,and it is easy to prove that they generate the ring of invariants of GL(N, C) in thesymmetric algebra
MN (C)⊕d ≃ MN (C) ⊗ V.

(51)

Indeed, let us set U = CN and identify MN (C) with U P⊗ U ∗ . Then,Pthe character ofn∗∨∨GL(U) in S (U ⊗ U ⊗ V ) is hn (XX N), where X = xi , X = x−1
i .
By the Cauchy formula,X(52)
hn (XX ∨ N) =sλ (NX)sλ (X ∨ ),λ⊢nand the dimension of the invariant subspace is

dim S n (U ⊗ U ∗ ⊗ V )GL(U ) = hhn (XX ∨N), 1iGL(U )X=
hsλ (NX), sλ (X)i
λ ⊢n

(53)

=

X

sλ ∗ sµ (N)hsλ , sµ i

λ, µ ⊢n=X(sλ ∗ sλ )(N).

λ ⊢nThe characteristic of the conjugation action of Sn on CSn is precisely
so this is the dimension of Hn (V ). We have therefore established:(d)P

λ⊢n (sλ ∗ sλ ),Theorem 3.7. Let FN be the algebra of GL(N, C)-invariant polynomial functions
on MN (C)⊕d ≃ MN (C) ⊗ V , endowed with the comultiplication(54)∆f (A′1 , . . . , A′d ; A′′1 , . . . , A′′d ) := f (A′1 ⊕ A′′1 , . . . , A′d ⊕ A′′d )10

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON(d)Then the map (ai1 · · · aik ) 7→ f(i1 ,...,ik ) is an epimorphism of bialgebras H(V ) → FN .
3.5. Subalgebras of SQSym.
3.5.1. Symmetric functions in noncommuting variables (dual). For a permutationσ ∈ Sn , let supp(σ) be the partition π of the set [n] whose blocks are the supportsof the cycles of σ. The sums
X
(55)
Uπ :=
Mσ
supp(σ)=π

span a Hopf subalgebra ΠQSym of SQSym, which is isomorphic to the graded dual of
the Hopf algebra of symmetric functions in noncommuting variables (such as in [29, 4],
not to be confused with Sym), which we will denote here by WSym(A), for Word
symmetric functions. Indeed, from the product rule of the Mσ given in Equation (25),
one easily findsX
Cππ′ ,π′′ Uπ ,(56)
Uπ′ Uπ′′ :=where Cππ′ ,π′′ is the number of ways of splitting the parts of π into two subpartitions
whose standardized words are π ′ and π ′′ . For example,
U{{1,2,4},{3}} U{{1}} = U{{1,2,4},{3},{5}} + 2U{{1,2,5},{3},{4}}(57)+ U{{1,3,5},{4},{2}} + U{{2,3,5},{4},{1}} .

The dual WSym(A) of ΠQSym is the subspace of K hAi spanned by the orbits ofS(A) on A∗ . These orbits are naturally labelled by set partitions of [n], the orbit
corresponding to a partition π being constituted of the words(58)

w = a1 . . . an ,such that ai = aj iff i and j are in the same block of π. The sum of these words will
be denoted by Mπ .
For example,X(59)
M{{1,3,6},{2},{4,5}} :=abacca.
a6=b;b6=c;a6=c

It is known that the natural coproduct of WSym (given as usual by the ordered
sum of alphabets) is cocommutative [4] and that WSym is free over connected set
partitions. The same argument as in Theorem 2.5 shows that ΠQSym ∗ is free overthe same graded set, hence that ΠQSym is indeed isomorphic to WSym∗ .
3.5.2. Quasi-symmetric functions. One can also embed QSym into ΠQSym: take as
total ordering on finite sets of integers {i1 < · · · < ir } the lexicographic order on thewords (i1 , . . . , ir ). Then, any set partition π of [n] has a canonical representative B
as a non-decreasing sequence of blocks (B1 ≤ B2 ≤ · · · ≤ Br ). Let I = K(π) be thecomposition (|B1 |, . . . , |Br |) of n. The sums
X
X
(60)
UI :=
Uπ =
Mσ
K(π)=I

K(σ)=ICOMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

11

where K(σ) denotes the ordered cycle type of σ, span a Hopf subalgebra of ΠQSym
and SQSym, which is isomorphic to QSym. Indeed, from the product rule of the Mσgiven in Equation (25), one easily finds
X
CII′ ,I ′′ UI ,(61)
UI ′ UI ′′ :=I

where CII′ ,I ′′ is the coefficient of I in I ′ I ′′ . For example,(62)

U(1,3,1) U(1,2) = 2U(1,1,2,3,1) + 2U(1,1,3,1,2) + 2U(1,1,3,2,1)+ U(1,2,1,3,1) + 2U(1,3,1,1,2) + U(1,3,1,2,1) .

3.5.3. Symmetric functions. Furthemore, if we denote by Λ(I) the partition associated with a composition I by sorting I and by Λ(π) the partition λ whose parts are
the sizes of the blocks of π, the sums
X
X
X
(63)
uλ :=
UI =
Uπ =
Mσ
Λ(I)=λΛ(π)=λZ(σ)=λwhere Z(σ) denotes the cycle type of σ, span a Hopf subalgebra of QSym, ΠQSym,
and SQSym, which is isomorphic to Sym (ordinary symmetric functions). As an
example of the product, one has(64)

u(3,3,2,1) u(3,1,1) = 9u(3,3,3,2,1,1,1) .

Indeed, it follows from Equation (61) that an explicit Hopf embedding of Sym into
SQSym is given by(65)

j : p∗λ → uλwhere p∗λ = pzλλ is the adjoint basis of products of power sums. The images of theusual generators of Sym under this embedding have simple expressions in terms of
the infinite matrix X = (xij )i,j≤1:(66)

j(pn ) = tr(X n )which implies that j(en ) is the sum of the diagonal minors of order n of X:
X X(67)j(en ) =ε(σ)xi1 iσ(1) . . . xin iσ(n)i1 <···<in σ∈Snand j(hn ) is the sum of the same minors of the permanent
X X
xi1 iσ(1) . . . xin iσ(n) .
(68)
j(hn ) =i1 <···<in σ∈Sn

More generally, the sum of the diagonal immanants of type λ givesX X
χλ (σ)xi1 iσ(1) . . . xin iσ(n) .
(69)
j(sλ ) =i1 <···<in σ∈Sn

12

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

3.5.4. Involutions. Finally, one can check that the Mσ with σ involutive span a Hopf
subalgebra of SQSym. Since the number of involutions of Sn is equal to the numberof standard Young tableaux of size n, this algebra can be regarded as a commutative
version of the Poirier-Reutenauer algebra [27] denoted by FSym and realized in [8].
Notice that this version is also isomorphic to the image of SQSym in the quotient of
R/J by the relations(70)

xij xjk = 0, for all i 6= k.

This construction generalizes to the algebras built on permutations of arbitrary given
order.
3.6. Quotients of WSym. Since we have built a subalgebra of ΠQSym isomorphic
to QSym, we can define an embedding(71)

i : QSym ֒→ ΠQSym = WSym∗ ,so that, dually, there is a Hopf epimorphism i∗ : WSym ։ Sym.
The dual basis V I of the UI defined in Equation 60 can be identified with equivalence classes of Sσ under the relation(72)′

Sσ ≃ Sσ iff K(σ) = K(σ ′ ).

The Sσ with σ a full cycle are primitive, so that we can take for Vn any sequence ofprimitive generators of Sym.
It turns out that there is another natural epimorphism from WSym to Sym.
Using the canonical ordering of set partitions introduced in Section 3.5, that is, thelexicographic ordering on the nondecreasing representatives of the blocks, we can as
above associate a composition K(π) with π and define an equivalence relation(73)

π ∼ π ′ iff K(π) = K(π ′ ).

Then, the ideal I of WSym generated by the differences(74)

π ∼ π′,

Mπ − Mπ′ ,is a Hopf ideal, and the quotient(75)

WSym/Iis isomorphic to Sym. The images VI of the Mπ by the canonical projection are
analogs of the monomial symmetric functions in Sym. Indeed, the commutative
image vλ of Mπ is proportional to a monomial function:
Y
(76)
vλ =
mi (λ)!mλ .
i

If we introduce the coefficients cλ by

v1n =

(77)

X

cλ vλ

λ⊢n

then, the multivariate polynomials(78)

Bn (x1 , . . . , xn ) =Xλ⊢ncλ xλ ,

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

13

where xλ := xλ1 · · · xλn , are the exponential Bell polynomials defined by
X tn
P
xn n
Bn (x1 , . . . , xn ) = e n≥1 n! t .
(79)
n!
n≥0
3.7. The stalactic monoid. The constructions of Section 3.6 can be interpreted interms of a kind of Robinson-Schensted correspondence and of a plactic-like monoid.
The stalactic congruence is the congruence ≡ on A∗ generated by the relationsa w a ≡ a a w,

(80)

for all a ∈ A and w ∈ A∗ .
Each stalactic class has a unique representative, its canonical representative of the
form
mr
1 m2
am
1 a2 . . . ar(81)

with ai 6= aj for i 6= j.
We can represent such a canonical word by a tableau-like planar diagram, e.g.,c a d bd bcdc3 ad3 b2 ←→ c

(82)

.

Now, there is an obvious algorithm, which consists in scanning a word from left toright and arranging its identical letters in columns, creating a new column to the rightwhen one scans a letter for the first time. Let us call P (w) the resulting canonicalword, or, equivalently, its planar representation. We can compute P (w) along with a
Q-symbol recording the intermediate shapes of the P -symbol. For example, to insert
w = cabccdbdd, we have the steps
c

c ,

−−−→

c

b

∅, ∅ −−−→

−−−→

1

−−−→

a

c a ,

1 2

−−−→

b

c a b ,

1 2 3

c a b
,
c

1 2 3
4

−−−→

c

c a b
c
,
c

1 2 3
4
5

−−−→

d

c a b dc,c

1 2 3 64
5c a b dcb,c

1 2 3 6
4
7
5

−−−→

d

c a b dcb d ,c

1 2 3 6
4
7 8
5

−−−→

d

c a b d
c
b d ,
c
d

1 2 3 647 8
59Clearly, the Q-symbol can be interpreted as a set partition of [n], whose blocks are
the columns. In our example,(83)

Q(cabccdbd) = {{1, 4, 5}, {2}, {3, 7}, {6, 8, 9}}.

We now see that the natural basis Mπ of WSym can be characterized as
X
(84)
Mπ =
w.
Q(w)=πThis is completely similar to the definition of the bases RI of Sym via the hypoplactic
congruence, of St of FSym via the plactic congruence, and of PT of PBT via thesylvester congruence [16, 8, 13].

14

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

Note that the defining relation of the stalactic monoid can be presented in a placticlike way as
a u ba ≡ a u ab(85)
for all a, b ∈ A and u ∈ A∗ .

3.8. Other Hopf algebras derived from the stalactic congruence. It is always interesting to investigate the behaviour of certain special classes of words underanalogs of the Robinson-Schensted correspondence. This section presents a few examples leading to interesting combinatorial sequences.
3.8.1. Parking functions. Recall that a word on A = {1, . . .} is a parking function if
its nondecreasing reordering u1 · · · uk satisfies ui ≤ i. The number of stalactic classesof parking functions of size n can be combinatorially determined as follows.
Since the congruence does not change the evaluation of a word, and since if a word
is a parking function, then all its permutations are, one can restrict to a rearrangement class, containing a unique nondecreasing parking function. Those are known tobe counted by Catalan numbers. Now, the rearrangement class of a nondecreasing
parking function p has exactly l! congruence classes if l is the number of different
letters of p.
The counting of nondecreasing parking functions p by their number of different
letters is obviously the same as the counting of Dyck paths by their number of peaks,
given by the Narayana triangle (sequence A001263 in [31]). To get the number ofstalactic classes of parking functions, one has to multiply the ith column by i!, that isthe definition of the unsigned Lah numbers (sequence A089231 in [31]), which countwith the additional parameter of number of lists, the number of sets of lists (sequence
A000262 in [31]), that is, the number of set partitions of [n] with an ordering insideeach block but no order among the blocks. The first values are(86)

1, 3, 13, 73, 501, 4051, 37633, 394353, 4596553, . . .

whereas the first rows of the Narayana and unsigned Lah triangles are
1
1 1
1 3 1
1 6 6 1
1 10 20 10 1
1 15 50 50 15 1

1
1 2
1 6
6
1 12 3624
1 20 120 240 120
1 30 300 1200 1800 720

Figure 1. The Narayana and unsigned Lah triangles.
One can also obtain this last result by pure algebraic calculations as follows. The
Frobenius characteristic of the representation of Sn on PFn is
1
1 X
(87)
ch(PFn ) =mµ (n + 1)hµ (X).
hn ((n + 1)X) =
n+1
n+1
µ⊢n

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

15

In this expression, each hµ (X) is the characteristic of the permutation representation on a rearrangement class of words, with µ1 occurrences of some letter i1 , µ2
of some other letter i2 , and so on. Hence, the number of stalactic classes in eachsuch rearrangement class is l(µ)!, and the total number of stalactic classes of parking
functions is
1 X
mµ (n + 1)l(µ)!
(88)
an =
n + 1 µ⊢nPSince g(z) = n≥0 z n ch(PFn ) solves the functional equation [26]X(89)g(z) =
z n hn (X)g(z)n ,n≥0

we see that the exponential generating function is
X zn Z ∞(90)
A(z) =αn =e−x g(z)dx,n!
0
n≥0
in the special case where hn = x for all n ≥ 1, that is(91)

g(z) = 1 + x

zg(z)
1 − zg(z)so that(92)

A(z) = exp



z
1−z



.

Hence, αn is the number of ‘sets of lists’, giving back sequence A000262 of [31]. It
would be interesting to find a natural bijection between the stalactic classes of parking
functions and sets of lists, compatible with the algebraic structures.
Now, recall that the Hopf algebra of parking functions PQSym∗ is spanned bypolynomialsX(93)
Ga (A) :=w.
Park(w)=a

As usual, it is easy to show that the equivalence defined by(94)Ga′ (A) ≡ Ga′′ (A)iff a′ and a′′ are stalactically congruent, is such that the quotient PQSym∗ / ≡ is a
Hopf algebra.
3.8.2. Endofunctions. The same methods allow to see that the number βn of stalactic
classes of endofunctions on n letters is given by
 
n 
X
n−1 n
k!
(95)
βn =
k
k−1
k=0
It is sequence A052852 of [31], whose first terms are(96)

1, 4, 21, 136, 1045, 9276, 93289, 1047376, 12975561, 175721140, . . .

16

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

and whose exponential generating series iszz(97)
e 1−z .
1−z
As before, the classes counted by those numbers can be counted with the additionnal
parameter given by the number of different letters of their representatives, so that
one gets a new triangle, the Endt triangle. Moreover, this triangle is obtained bymultiplying column i by i! from a more classical triangle, counting the integer compositions of 2n in n parts with a given number of ones, the Tw triangle. Here are
the first rows of both triangles:
1
2 2
3 12
6
4 36
72
24
5 80 360 380 120
6 150 1200 3600 3600 720

1
2 1
3 6
1
4 18 121
5 40 60 20 1
6 75 200 150 30 1

Figure 2. The Tw and Endt triangles.
From the algebraic point of view, the Frobenius characteristic of [n]n isX(98)ch([n]n ) = hn (nX) =mµ (n)hµ (X),µ⊢nPso that βn = µ⊢n mµ (n)l(µ)!, and the same method gives directly the exponential
generating series of βn .
′′′As above, the quotient of EQSym by Sf ≡ Sf iff f ′ and f ′′ are stalacticallycongruent is a Hopf algebra.
3.8.3. Initial words. Recall that initial words are words on the alphabet of integers
so that, if letter n appears in w, then n − 1 also appears. The same method allows
to see that the number γn of stalactic classes of initial words on n letters is

n 
X
n−1
k!
(99)
γn =
k−1
k=0

It is sequence A001339 of [31], whose first terms are(100)

1, 3, 11, 49, 261, 1631, 11743, 95901, 876809, 8877691, 98641011, . . .

and whose exponential generating series isez(101)(1 − z)2
As before, the classes counted by those numbers can be counted with the additionnal
parameter given by the number of different letters of their representatives, so that
one gets a new triangle, the Arr triangle. Moreover, this triangle is obtained by

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

1
1
1
1
1
1

17

1
1 2
1 4 6
1 6 18 24
1 8 36 96 120
1 10 60 240 600 720

1
2 1
3 3 1
4 6 4 1
5 10 10 5 1

Figure 3. The Pascal and Arr triangles.
multiplying column i by i! in the Pascal triangle. Here are the first rows of both
triangles:
Again, the stalactic quotient of WQSym [24, 12] is a Hopf algebra.
3.8.4. Generic case. Let A be an alphabet, and V = CA. The generic symmetricfunctionXl(µ)!mµ (X)
(102)
fn =
µ⊢n

is the character of GL(V ) in the image of V ⊗n in the quotient of T (V ) ∼ K hAi by
the stalactic congruence. It is Schur-positive, and can be explicitly expanded on the
Schur basis. Indeed, one has
n
X
(103)
fn =
ck s(n−k,k) .
k=0

The coefficients ck are given by sequence A000255 of [31], whose first terms are(104)

1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, . . .

To see this, write again(105)

l(µ)! =

Z ∞tl(µ) e−t dt.

0

Then
(106)

f=

X

fn =

n≥0

and

(107)

X
µ

l(µ)

t

mµ =

Y
i≥1

Z ∞

e−t



Y 1 − (1 − t)xi

0

txi
1+
1 − xi

=

X
µ

i≥1

=

tl(µ) mµ dt.

X

1 − xi(t − 1)k ek (X)

k≥0

Since
(108)

Z ∞
0

e−t (t − 1)k dt = dk ,

!

X
l≥0

!

hl (X) .

18

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

the number of derangements in Sn , we have finally
n
XX
(109)
f=
dk ek (X)hn−k (X).
n≥0 k=0

Expanding(110)

ek hn−k = s(n−k,1k ) + sn−k+1,1k−1 ,we get Formula (103). Alternatively, we can express ck as
Z ∞
(111)
ck =
e−t t(t − 1)k dt
0since the term of degree n in Equation (107) isnX(t − 1)k s(n−k,1k ) .
(112)
t
k=0

The exponential generating series of these numbers is given by
e−z
.
(113)
(1 − z)2
4. Structure of SSym
4.1. A realization of SSym. In the previous section, we have built a commutative
algebra of permutations SQSym from explicit polynomials on a set of auxiliary variables xi j . One may ask whether its non-commutative dual admits a similar realizationin terms of non-commuting variables ai j .
We shall find such a realization, in a somewhat indirect way, by first building fromscratch a Hopf algebra of permutations ΦSym ⊂ K h ai j | i, j ≥ 1 i, whose operations
can be described in terms of the cycle structure of permutations. Its coproduct turns
out to be cocommutative, and the isomorphism with SSym follows as above fromthe Cartier-Milnor-Moore theorem.
Let {ai j , i, j ≥ 1} be an infinite set of non-commuting indeterminates. We use thebiword notation     
ii1
ini1 . . . in,(114)
ai j ≡
···
≡
j
j1
jn
j1 . . . jn

Let σ ∈ Sn and let (c1 , . . . , ck ) be a decomposition of σ into disjoint cycles. Withany cycle, one associates its cycle words, that is, the words obtained by reading the
successive images of any element of the cycle. For example, the cycle words associatedwith the cycle (1342) are 1342, 2134, 3421, 4213. For all word w, we denote by C(w)the cycle associated with the inverse of its standardized word.
We now define
Xx
(115)
φσ :=
,
a
x,a

where the sum runs over all words x such that xi = xj iff i and j belong to the same
cycle of σ, and such that the standardized word of the subword x of a whose letter

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

19

positions belong to cycle cl satisfied C(x) = cl . By extension, such biwords will besaid to have σ as cycle decomposition.
Note that any biword appears in the expansion of exactly one φσ .
Example 4.1.
(116)

φ12 =

Xx y
x6=y(117)

φ41352 =ab.

X

x6=y;Std(abde)−1 =1342, 2134, 3421, or 4213




xxyxx
.
abcde

Theorem 4.2. The φσ span a subalgebra ΦSym of K h aij | i, j ≥ 1 i. More precisely,(118)

φα φβ =

X

σ
gα,β
φσ ,

σ
where gα,β∈ {0, 1}. Moreover, ΦSym is free over the set(119){φα | α connected}.

Proof – Let σ ′ and σ ′′ be two permutations and let w be a biword appearing in φσ′ φσ′′ .
The multiplicity of w is 1. To get the first part of the theorem, we only need to provethat all words w ′ appearing in the same φσ as w also appear in this product. Givena letter x appearing in the first row of w at some positions, the subwords a of theelements of φσ taken from the second row at those positions, have the same image
by C as the corresponding element of w.
Thus, we onyl have to prove that all words w having the same image by C satisfy
that all their prefixes (and suffixes) of a given length have also same image by C. It
is sufficient to prove the result on permutations. Now, given two permutations σ andτ , σ −1 and τ −1 are cycle words of the same cycle, iff for some k, τ = γ k σ where γ isthe cyclic permutation (12 · · · n). Since is also the case for the standardized words ofthe prefixes of both permutations of a given length, the property holds.
Moreover, any biword can be uniquely written as a concatenation of a maximal
number of biwords such that no letter appears in the first row of two different biwords
and that the letters of the second row of a biword are all smaller than the letters of
the second row of the next one. This proves that the φα where α is connected are
free. The usual generating series argument then proves that those elements generate
ΦSym.
To give the precise expression of the product φα φβ , we first need to define two
operations on cycles.
The first operation is just the circular shuffle on disjoint cycles: if c′1 and c′′1 are
two disjoint cycles, their cyclic shuffle c′1 c′′1 is the set of cycles c1 such that theircycle words are obtained by applying the usual shuffle on the cycle words of c′1 andc′′1 . This definition makes sense because a shuffle of cycle words associated with twowords on disjoint alphabets splits as a union of cyclic classes.

20

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBONFor example, the cyclic shuffle (132) (45) gives the set of cycles(120){(13245), (13425), (13452), (14325), (14352), (14532),(13254), (13524), (13542), (15324), (15342), (15432)}.

These cycles correspond to the following list of permutations which are those appearing in Equation (127), except for the first one which will be found later:(121){ 34251, 35421, 31452, 45231, 41532, 41253,
35214, 34512, 31524, 54213, 51423, 51234}.

Let us now define an operation on two sets C1 and C2 of disjoint cycles. We callmatching a list of all those cycles, some of the cycles being paired, always one of C1
with one of C2 . The cycles remaining alone are considered to be associated with theempty cycle. With all matchings associate the set of sets of cycles obtained by theof any pair of cycles. The union of those sets of cycles is denoted
cyclic productby C1 ⌣C2 .
For example, the matchings corresponding to C1 = {(1), (2)} and C2 = {(3), (4)}
are:
(122)
{(1)}{(2)}{(3)}{(4)}, {(1)}{(2), (3)}{(4)}, {(1)}{(2), (4)}{(3)},{(1), (3)}{(2)}{(4)}, {(1), (3)}{(2), (4)}, {(1), (4)}{(2)}{(3)}, {(1), (4)}{(2), (3)},and the product C1 ⌣C2 is then{(1), (2), (3), (4)}, {(1), (23), (4)}, {(1), (24), (3)},(123){(13), (2), (4)}, {(13), (24)}, {(14), (2), (3)}, {(14), (23)}.
Remark that this calculation is identical with the Wick formula in quantum field
theory (see [6] for an explanation of this coincidence).
We are now in a position to describe the product φσ φτ :Proposition 4.3. let C1 be the cycle decomposition of σ and C2 be the cycle decomposition of τ , shifted by the size of σ. Then the permutations indexing the elements
appearing in the product φσ φτ are the permutations whose cycle decompositions belong
to C1 ⌣C2 .
Proof – Recall that the product φσ φτ is a sum of biwords with multiplicity one
since a word appears in exactly one φσ . So we only have to prove that biwords
appearing in φσ φτ are the same as biwords whose cycle decomposition are in C1 ⌣C2 .
First, by definition of the cyclic shuffle and of operation ⌣, if a biword has its cycle
decomposition in C1 ⌣C2 , its prefix of size n has cycle decomposition C1 whereas its
suffix of size p has cycle decomposition C2 , where n (resp. p) is the size of C1 (resp.
C2 ).
Conversely, let w1 (resp. w2 ) be a biword with cycle decomposition C1 (resp. C2 )and let us consider w = w1 · w2 . For all letters in the first row of w, either it only
appears in w1 , either only in w2 , or in both w1 and w2 . In the first two cases, we
obtain the corresponding cycle of C1 (or C2 , shifted). In the last case, the cycle
decomposition of the word of the second row corresponding to this letter belongs toCOMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

21

the cyclic shuffle of the corresponding cycles of C1 and C2 (hence matching those
two cycles). Indeed, if Std−1 (w1 ) is a cycle word of c1 and Std−1 (w2 ) is a cycle wordof c2 , then Std−1 (w) is a cycle word of an element of the cyclic shuffle c1 c2 : it isalready known when Std−1 (w1 ) = c1 and Std−1 (w2 ) = c2 since it is the definitionof FQSym [8] and cyclying c1 or c2 only amounts to cycle c2 , hence copying thedefinition of the cyclic shuffle.
For example, with σ = τ = 12, one finds that C1 = {(1), (2)} and C2 = {(3), (4)}.
It is then easy to check that one goes from Equation (123) to Equation (125) bycomputing the corresponding permutations.
Example 4.4.
(124)

φ12 φ21 = φ1243 + φ1342 + φ1423 + φ3241 + φ4213 .

(125)

φ12 φ12 = φ1234 + φ1324 + φ1432 + φ3214 + φ3412 + φ4231 + φ4321 .

(126)

φ1 φ4312 = φ15423 + φ25413 + φ35421 + φ45123 + φ51423 .

(127)

φ312 φ21 = φ31254 + φ31452 + φ31524 + φ34251 + φ34512 + φ35214 + φ35421+ φ41253 + φ41532 + φ45231 + φ51234 + φ51423 + φ54213 .

Let us recall a rather general recipe to obtain the coproduct of a combinatorial Hopf
algebra from a realization in terms of words on an ordered alphabet X. Assume that
X is the ordered sum of two mutually commuting alphabets X ′ and X ′′ . Then define
the coproduct as ∆(F ) = F (X ′ +̇X ′′ ), identifying F ′ ⊗ F ′′ with F ′ (X ′ )F ′′ (X ′′ ) [8, 23].
There are many different ways to define a coproduct on ΦSym compatible withthe realization since there are many ways to order an alphabet of biletters: order
the letters of the first alphabet, order the letters of the second alphabet, or orderlexicographically with respect to one alphabet and then to the second.
In the sequel, we only consider the coproduct obtained by ordering the biletterswith respect to the first alphabet so that φσ is primitive if σ consists of only one cycle.
More precisely, thanks to the definition of the φ, it is easy to see that it corresponds
to the unshuffling of the cycles of a permutation:(128)∆φσ :=

X

φα ⊗ φβ ,(α,β)

where the sum is taken over all pairs of permutations (α, β) such that α is obtainedby renumbering the elements of a subset of cycles of σ (preserving the relative orderof values), and β by doing the same on the complementary subset of cycles. For
example, if σ = (1592)(36)(4)(78), the subset (1592)(4) gives α = (1452)(3) and
β = (12)(34).

22

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

Example 4.5.
(129)

∆φ12 = φ12 ⊗ 1 + 2φ1 ⊗ φ1 + 1 ⊗ φ12 .

(130)∆φ312 = φ312 ⊗ 1 + 1 ⊗ φ312 .

(131) ∆φ4231 = φ4231 ⊗ 1 + 2φ321 ⊗ φ1 + φ21 ⊗ φ12 + φ12 ⊗ φ21 + 2φ1 ⊗ φ321 + 1 ⊗ φ4231 .
The following theorem is a direct consequence of the definition of the coproducton the realization.
Theorem 4.6. ∆ is an algebra morphism, so that ΦSym is a graded bialgebra (forthe grading deg φσ = n if σ ∈ Sn ). Moreover, ∆ is cocommutative.
The same reasoning as in Section 3 shows that
Theorem 4.7. SSym and ΦSym are isomorphic as Hopf algebras.
To get the explicit isomorphism sending φ to S, let us first recall that a connected
permutation is a permutation σ such that σ([1, k]) 6= [1, k] for any k ∈ [1, n − 1]. Any
permutation σ has a unique maximal factorization σ = σ1 • · · · • σr into connected
permutations. We then define(132)

S′σ := φσ1 · · · φσr .

Then
(133)

S′σ = φσ1 •···•σr +

X

φµ

µ

where all permutations µ have strictly less cycles than r. So the S′ form a basisof ΦSym. Moreover, they are a multiplicative basis with product given by shifted
concatenation of permutations, so that they multiply as the S do. Moreover, thecoproduct of S′σ is the same as for φσ , so the same as for Sσ . So both bases S and S′
have the same product and the same coproduct. This proves
Proposition 4.8. The linear map Sσ 7→ S′σ realizes the Hopf isomorphism between
SSym and ΦSym.
There is another natural isomorphism: define
Xx
′′
(134)
Sσ :=
,
a
x,a

where the sum runs over all words x such that xi = xj if (but not only if) i and jbelong the same cycle of σ and such that the standardized word of the subword of aconsisting of the indices of cycle cl is equal to the inverse of the standardized wordof a cycle word of cl .

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

23

That both bases S′ and S′′ have the same product and coproduct comes from thefact that if (c1 ) · · · (cp ) is the cycle decomposition of σ,
(135)

X

S′′σ =

φ(c) .

(c);(c)∈(c1 )⌣(c2 )⌣···⌣(cp )For example,(136)

S′′2431 = S′′(124)(3) = φ(124)(3) + φ(1423) + φ(1234) + φ(1324)= φ2431 + φ4312 + φ2341 + φ3421 .

4.2. Quotients of ΦSym. Let I be the ideal of ΦSym generated by the differences
φσ − φτ(137)

where σ and τ have the same cycle type.
The definitions of its product and coproduct directly imply that I is a Hopf ideal.
Since the cycle types are parametrized by integer partitions, the quotient ΦSym/I
has a basis Yλ , corresponding to the class of φσ , where σ has λ as cycle type.
From Equations (124)-(127), one finds:
Example 4.9.
(138)
(139)

Y112 = Y1111 + 2Y22 + 4Y211 .

Y11 Y2 = Y211 + 4Y31 ,Y1 Y4 = Y41 + 4Y5 ,Y3 Y2 = Y32 + 12Y5 .

Theorem 4.10. ΦSym/I is isomorphic to Sym, the Hopf algebra of ordinary symmetric functions,
If one writes λ = (λ1 , . . . , λp ) = (1m1 , . . . , k mk ), an explicit isomorphism is given
by
(140)

Qk

Yλ 7→ Qp

i=1 mi !

j=1 (λj − 1)!

mλ .

Proof – This follows from the description of φσ φτ given in Proposition 4.3.
5. Parking functions and trees
5.1. A commutative algebra of parking functions. It is also possible to build
a commutative pendant of the Hopf algebra of parking functions introduced in [22]:let PFn be the set of parking functions of length n. For a ∈ PFn , set, as before
(141)

Ma :=

X

xi1 ia(1) · · · xin ia(n) .

i1 <···<inThen, using once more the same arguments of Section 2, we conclude that the Maform a linear basis of a Z-subalgebra PQSym of EQSym, which is also a sub-coalgebra
if one defines the coproduct in the usual way.

24

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

Example 5.1.
(142)

M1 M11 = M122 + M121 + M113 .

(143)

M1 M221 = M1332 + M3231 + M2231 + M2214 .

(144)

M12 M21 = M1243 + M1432 + M4231 + M1324 + M3214 + M2134 .

(145)∆M525124 = M525124 ⊗ 1 + 1 ⊗ M525124 .

(146)∆M4131166 = M4131166 ⊗ 1 + M41311 ⊗ M11 + 1 ⊗ M4131166 .

The main interest of the non-commutative and non-cocommutative Hopf algebraof parking functions defined in [22] is that it leads to two algebras of trees. The
authors obtain a cocommutative Hopf algebra of planar binary trees by summingover the distinct permutations of parking functions, and an algebra of planar trees
by summing over hypoplactic classes.
We shall now investigate whether similar constructions can be found for the commutative version PQSym.
5.2. From labelled to unlabelled parking graphs. A first construction, which
can always be done for Hopf algebras of labelled graphs is to build a subalgebra bysumming over labellings. Notice that this subalgebra is the same as the subalgebra
obtained by summing endofunctions graphs over their labellings. Those graphs arealso known as endofunctions (hence considered there as unlabelled graphs) in [3].
The dimension of this subalgebra in degree n is equal to the number of unlabelledparking graphs(147)

1, 1, 3, 7, 19, 47, 130, 343, 951, 2615, 7318, 20491, 57903, 163898, . . .

known as sequence A001372 in [31]. For example, here are the 7 unlabelled parking
graphs of size 3 (to be compared with the 16 parking functions):

The product of two such unlabelled graphs is the concatenation of graphs and thecoproduct of an unlabelled graph is the unshuffle of its connected subgraphs. So thisalgebra is isomorphic to the polynomial algebra on generators indexed by connectedparking graphs.

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

25

5.3. Binary trees and nondecreasing parking functions. One can easily checkthat in PQSym, summing over parking functions having the same reordering does notlead to a subalgebra. However, if we denote by I the subspace of PQSym spannedby the Ma where a is not nondecreasing, I is an ideal and a coideal, and CQSym :=PQSym/I is therefore a commutative Hopf algebra with basis given by the classes
Mπ := Ma labelled by nondecreasing parking functions.
Notice that CQSym is also isomorphic to the image of PQSym in the quotient of
R/J by the relations(148)

xij xkl = 0, for all i < k and j > l.

The dual basis of Mπ is(149)

S π :=X

S a,awhere the sum is taken over all permutations of π.
The dual CQSym ∗ is free over the set S π , where π runs over connected nondecreasing parking functions. So if one denotes by CQSym the Catalan algebra definedin [22], the usual Cartier-Milnor-Moore argument then shows that(150)

CQSym ∼ CQSym ∗ ,CQSym ∼ CQSym∗ .

5.4. From nondecreasing parking functions to rooted forests. Nondecreasing
parking functions correspond to parking graphs of a particular type: namely, rooted
forests with a particular labelling (it corresponds to nondecreasing maps), the root
being given by the loops in each connected component.
Taking sums over the allowed labellings of a given rooted forest, we get that the
X
(151)
MF :=
Mπ ,
supp(π)=F

span a commutative Hopf algebra of rooted forests, which is likely to coincide with
the quotient of the Connes-Kreimer algebra [7] by its coradical filtration [2].
6. Quantum versions
6.1. Quantum quasi-symmetric functions. When several Hopf algebra structures can be defined on the same class of combinatorial objects, it is tempting to try
to interpolate between them. This can be done, for example with compositions: thealgebra of quantum quasi-symmetric functions QSym q [33, 8] interpolates between
quasi-symmetric functions and non-commutative symmetric functions.
However, the natural structure on QSym q is not exactly that of a Hopf algebra but
rather of a twisted Hopf algebra [18].
Recall that the coproduct of QSym(X) amounts to replace X by the ordered sum
X ′ +̇X ′′ of two isomorphic and mutually commuting alphabets. On the other hand,
QSym q can be realized by means of an alphabet of q-commuting letters(152)

xj xi = qxi xj , for j > i.

26

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

Hence, if we define a coproduct on QSym q by
(153)

∆q f (X) = f (X ′ +̇X ′′ ),with X ′ and X ′′ q-commuting with each other, it will be an algebra morphism(154)

QSym q → QSym q (X ′ +̇X ′′ ) ≃ QSym q ⊗χ QSym q

for the twisted product of tensors(155)(a ⊗ b) · (a′ ⊗ b′ ) = χ(b, a′ )(aa′ ⊗ bb′ ),

where
(156)

′

χ(b, a′ ) = q deg(b)·deg(a )for homogeneous elements b and a′ .
It is easily checked that ∆q is actually given by the same formula as the usual
coproduct of QSym, that is
X(157)∆q MI =MH ⊗ MK .
H·K=I

The dual twisted Hopf algebra, denoted by Symq , is isomorphic to Sym as aalgebra. If we denote by S I the dual basis of MI , S I S J = S I·J , and Symq is freely
generated by the S (n) = Sn , whose coproduct isX(158)∆q Sn =
q ij Si ⊗ Sj .
i+j=n

As above, ∆q is an algebra morphism(159)

Symq → Symq ⊗χ Symq ,where χ is again defined by Equation (156).
6.2. Quantum free quasi-symmetric functions. The previous constructions canbe lifted to FQSym. Recall from [8] that φ(Fσ ) = q l(σ) Fc(σ) is an algebra homomorphism FQSym → QSym q , which is in fact induced by the specialization φ(ai ) = xiof the underlying free variables ai to q-commuting variables xi .
The coproduct of FQSym is also defined by(160)∆F(A) = F(A′ +̇A′′ ),where A′ and A′′ are two mutually commuting copies of A [8]. If instead one
sets a′′ a′ = qa′ a′′ , one obtains again a twisted Hopf algebra structure FQSymq on
FQSym, for which φ is a homomorphism. With these definitions at hand, one cansee that the arguments given in [33] to establish the results recalled in Section 6.1
prove in fact the following more general result:
Theorem 6.1. Let A′ and A′′ be q-commuting copies of the ordered alphabet A, i.e.,a′′ a′ = qa′ a′′ for a′ ∈ A′ and a′′ ∈ A′′ . Then, the coproduct(161)∆q f = f (A′ +̇A′′ )COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

27

defines a twisted Hopf algebra structure. It is explictly given in the basis Fσ by
X(162)∆q Fσ =
q inv(α,β) FStd(α) ⊗ FStd(β)α·β=σ

where inv(α, β) is the number of inversions of σ with one element in α and the otherin β.
More precisely, ∆q is an algebra morphism with values in the twisted tensor productof graded algebras FQSym ⊗χ FQSym where (a ⊗ b)(a′ ⊗ b′ ) = χ(b, a′ )(aa′ ⊗ bb′ ) and′χ(b, a′ ) = q deg(b). deg(a ) for homogeneous elements b, a′ .
The map φ : FQSymq → QSym q defined byφ(Fσ ) = q l(σ) Fc(σ)(163)

is a morphism of twisted Hopf algebras.
Example 6.2.
(164) ∆q F2431 = F2431 ⊗ 1 + q 3 F132 ⊗ F1 + q 3 F12 ⊗ F21 + qF1 ⊗ F321 + 1 ⊗ F2431 .
(165) ∆q F3421 = F3421 ⊗ 1 + q 3 F231 ⊗ F1 + q 4 F12 ⊗ F21 + q 2 F1 ⊗ F321 + 1 ⊗ F3421 .
(166)

(167)

∆q F21 = F21 ⊗ 1 + qF1 ⊗ F1 + 1 ⊗ F21 .
(∆q F21 )(∆q F1 ) = (F213 + F231 + F321 ) ⊗ 1 + (F21 + q 2 (F12 + F21 )) ⊗ F1
+F1 ⊗ (q 2 F21 + q(F12 + F21 )) + 1 ⊗ (F213 + F231 + F321 ).

(168)∆q F213 = F213 ⊗ 1 + F21 ⊗ F1 + qF1 ⊗ F12 + 1 ⊗ F213 .

(169)∆q F231 = F231 ⊗ 1 + q 2 F12 ⊗ F1 + qF1 ⊗ F21 + 1 ⊗ F231 .

(170)∆q F321 = F321 ⊗ 1 + q 2 F21 ⊗ F1 + q 2 F1 ⊗ F21 + 1 ⊗ F321 .

Finally, one can also define a one-parameter family of ordinary Hopf algebra structures on FQSym, by restricting formula (162) for ∆q to connected permutations σ,
and requiring that ∆q be an algebra homomorphism. Then, for q = 0, ∆q becomes
cocommutative, and it is easily shown that the resulting Hopf algebra is isomorphic
to SSym.
However, it follows from [8] that for generic q, the Hopf algebras defined in thisway are all isomorphic to FQSym. This suggests to interpret FQSym as a kindof quantum group: it would be the generic element of a quantum deformation of
the enveloping algebra SSym = U(L). Similar considerations apply to various examples, in particular to the Loday-Ronco algebra PBT, whose commutative version

28

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON

obtained in [22] can be quantized in the same way as QSym, by means of q-commuting
variables [23].
There is another way to obtain QSym from FQSym: it is known [8] that QSym
is isomorphic to the image of FQSym(A) in the hypoplactic algebra K [A∗ / ≡H ].
One may then ask whether there exists a q-analogue of the hypoplactic congruenceleading directly to QSym q .
Recall that the hypoplactic congruence can be presented as the bi-sylvester congruence:
bvca ≡ bvac, with a < b ≤ c,cavb ≡ acvb, with a ≤ b < c,(171)

and v ∈ A∗ .
A natural q-analogue, compatible with the above q-commutation is(172)

bvca ≡qH
cavb ≡qH

q bvac, with a < b ≤ c,q acvb, with a ≤ b < c,and v ∈ A∗ . Then, we have
Theorem 6.3. The image of FQSym(A) under the natural projection K hAi →K hAi/ ≡qH is isomorphic to QSym q as an algebra, and also as a twisted Hopf algebra
for the coproduct A → A′ +̇A′′ , A′ and A′′ being q-commuting alphabets.
Moreover, it is known that if one only considers the sylvester congruencecavb ≡S acvb,(173)

the quotient FQSym(A) under the natural projection K hAi → K hAi/ ≡S is isomorphic to the Hopf algebra of planar binary trees of Loday and Ronco [19, 13].
The previous construction provides natural twisted q-analogs of this Hopf algebra.
Indeed, let the q-sylvester congruence ≡qS be(174)

cavb ≡qS

q acvb, with a ≤ b < c.

Then, since this congruence is compatible with the q-commutation, we have
Theorem 6.4. The image of FQSym(A) under the natural projection K hAi →K hAi/ ≡qS is a twisted Hopf algebra, with basis indexed by planar binary trees.

Acknowledgements
This project has been partially supported by EC’s IHRP Programme, grant HPRNCT-2001-00272, “Algebraic Combinatorics in Europe”. The authors would also liketo thank the contributors of the MuPAD project, and especially of the combinat part,for providing the development environment for this research.

COMMUTATIVE COMBINATORIAL HOPF ALGEBRAS

29

References[1] M. Aguiar, N. Bergeron, and F. Sottile, Combinatorial Hopf Algebra and generalized
Dehn-Sommerville relations, preprint ArXiv:math.CO/0310016.
[2] M. Aguiar and F. Sottile, Cocommutative Hopf algebras of permutations and trees, J. Alg.
Comb. 22 (2005), no. 4, 451–470.
[3] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures,
Encyclopedia of Mathematics and its Applications, Cambridge 67, 1998.
[4] N. Bergeron, C. Reutenauer, M. Rosas, and M. Zabrocki, Invariants and coinvariantsof the symmetric group in noncommuting variables, preprint ArXiv:math.CO/0502082.
[5] C. Brouder and A. Frabetti, Renormalization of QED with planar binary trees, Eur. Phys.
J. C, 19 (2001), 715–741.
[6] C. Brouder and R. Oeckl, Quantum groups and quantum field theory: I. The free scalar
field, preprint ArXiv:hep-th/0208118.
[7] A. Connes and D. Kreimer, Hopf algebras, renormalization and noncommutative geometry,Comm. Math. Phys., 199 (1998), 203–242.
[8] G. Duchamp, F. Hivert, and J.-Y. Thibon, Noncommutative symmetric functions VI: freequasi-symmetric functions and related algebras, Internat. J. Alg. Comput. 12 (2002), 671–717.
[9] I.M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. S. Retakh, and J.-Y. Thibon,
Noncommutative symmetric functions, Adv. in Math. 112 (1995), 218–348.
[10] I. Gessel, Noncommutative generalization and q-analog of the Lagrange inversion formula,
Trans. Amer. Math. Soc. 257 (1980), no. 2, 455–482.
[11] R. Grossman and R. G. Larson, Hopf-algebraic structure of families of trees, J. Algebra
126 (1989), n. 1, 184–210.
[12] F. Hivert, Combinatoire des fonctions quasi-symétriques, Thèse de Doctorat, Marne-LaVallée, 1999.
[13] F. Hivert, J.-C. Novelli and J.-Y. Thibon. The algebra of binary search trees, TheoreticalComputer Science, to appear.
[14] F. Hivert, J.-C. Novelli and J.-Y. Thibon. Commutative Hopf algebras of permutations
and trees, preprint ArXiv:math.CO/0502456[15] A. Joyal, Une théorie combinatoire des séries formelles, Adv. Math. 42, (1981), 1–82.
[16] D. Krob and J.-Y. Thibon, Noncommutative symmetric functions IV: Quantum linear groupsand Hecke algebras at q = 0, J. Alg. Comb. 6 (1997), 339–376.
[17] B. Leclerc, T. Scharf and J.-Y. Thibon, Noncommutative cyclic characters of symmetricgroups, Jour. Comb. Theory Ser. A 75 (1996), 55-69.
[18] L. Li and P. Zhang, Twisted Hopf algebras, Ringel-Hall algebras, and Green’s categories, J.
of Algebra 231 (2000), 713–743.
[19] J.-L. Loday and M.O. Ronco, Hopf algebra of the planar binary trees, Adv. Math. 139(1998) n. 2, 293–309.
[20] I.G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford University
Press, 1995.
[21] C. Malvenuto and C. Reutenauer, Duality between quasi-symmetric functions and theSolomon descent algebra, J. Algebra 177 (1995), 967–982.
[22] J.-C. Novelli and J.-Y. Thibon, An algebra of parking functions, FPSAC’04, Vancouver,
2004.
[23] J.-C. Novelli and J.-Y. Thibon, Parking functions and descent algebras, preprint
ArXiv:math.CO/0411387.
[24] J.-C. Novelli and J.-Y. Thibon, Construction de trigèbres dendriformes, C. R. Acad. Sci,
Paris, Sér. I, 342, (2006), 365–369.
[25] J.-C. Novelli, J.-Y. Thibon, and N.M. Thiéry, Algèbres de Hopf de graphes, C. R. Acad.
Sci., Paris, Sér. A, 339, vol. 9, (2004), 607–610.

30

F. HIVERT, J.-C. NOVELLI, AND J.-Y. THIBON[26] J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion, preprint ArXiv:math.CO/0512570.
[27] S. Poirier and C. Reutenauer, Algèbre de Hopf des tableaux, Ann. Sci. Math. Qébec 19(1995), 79–90.
[28] C. Reutenauer, Free Lie algebras, Oxford, 1993.
[29] B. Sagan and M. Rosas, Symmetric functions in noncommuting variables, Trans. Amer.
Math. Soc., to be published.
[30] T. Scharf and J.-Y. Thibon, A Hopf-algebra approach to inner plethysm, Adv. in Math. 104(1994), 30–58.
[31] N.
J.
A.
Sloane,The
On-LineEncyclopediaofInteger
Sequences,
http://www.research.att.com/∼njas/sequences/[32] R. P. Stanley, Enumerative combinatorics, vol. 2, Cambridge University Press, 1999.
[33] J.-Y. Thibon and B.C.V. Ung, Quantum quasi-symmetric functions and Hecke algebras,
Journal of Physics A 29 (1996), 7337–7348.
Institut Gaspard Monge, Université de Marne-la-Vallée, 5 Boulevard Descartes,
Champs-sur-Marne, 77454 Marne-la-Vallée cedex 2, FRANCE
E-mail address, Florent Hivert: hivert@univ-mlv.fr
E-mail address, Jean-Christophe Novelli: novelli@univ-mlv.fr
E-mail address, Jean-Yves Thibon: jyt@univ-mlv.fr