COMBINATORICS OF FULLY COMMUTATIVE INVOLUTIONSIN CLASSICAL COXETER GROUPSRICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU
Abstract. An element of a Coxeter group W is fully commutative if any
two of its reduced decompositions are related by a series of transpositions ofadjacent commuting generators. In the present work, we focus on fully commutative involutions, which are characterized in terms of Viennot’s heaps. By
encoding the latter by Dyck-type lattice walks, we enumerate fully commutative involutions according to their length, for all classical finite and affine
Coxeter groups. In the finite cases, we also find explicit expressions for theirgenerating functions with respect to the major index. Finally in affine typeA, we connect our results to Fan–Green’s cell structure of the corresponding
Temperley–Lieb algebra.

Introduction
Let W be a Coxeter group. An element w ∈ W is said to be fully commutative(FC) if any reduced expression for w can be obtained from any other one by transposing adjacent pairs of commuting generators. Fully commutative elements wereextensively studied by Stembridge in a series of papers [18, 19, 20] where, among
others, he classified the Coxeter groups having a finite number of FC elements andenumerated them in each case. It is known that these elements index a basis for the
associated (generalized) Temperley–Lieb algebra ([7, 10]). The growth function ofsuch an algebra can then be obtained by computing the generating function, withrespect to the length, of fully commutative elements in W . This function has beene andcomputed by Barcucci et al [2] in type A, by Hanusa and Jones [12] in type A,
by the present authors [4] in all finite and affine types. A striking fact is that, ineach affine case, the corresponding growth sequence is ultimately periodic.
In the present work we focus on FC involutions for all classical Coxeter groups.
As explained by Stembridge in [20], a FC element w is an involution if and only
if its commutation class R(w) is palindromic, meaning that it includes the mirror
image of some (equivalently, all) of its members. We will reformulate this in termsof heaps and certain Dyck-type lattice walks which encode them.
As a first consequence, we will be able to enumerate, in types A, B, and D, FC
involutions according to the major index. This was recently done by Barnabei etal. [3] for the symmetric group (type A), by using the 321-avoiding characterizationof such elements, the Robinson-Schensted correspondence, and a nice connection to
integer partitions. Our approach in terms of heaps uses neither pattern-avoidance
characterizations nor the Robinson-Schensted correspondence. However, it also
Date: May 14, 2015.
Key words and phrases. Fully commutative elements, involutions, Coxeter groups, generating
functions, lattice walks, heaps, major index, Temperley–Lieb algebra.
1

2

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU

yields a connection to integer partitions through our Dyck-type lattice walks, which,as will be explained, turn out to be in bijection with the ones used in [3]. The
advantage of our point of view is that it naturally extends to types B and D
for which major indices can be defined, whereas the use of Stembridge’s patternavoiding characterizations [20, Theorems 5.1 and 10.1] seems hard to handle. In
type B, our result can for instance be written as follows (see Proposition 2.5):


n
h−1
X
X
X h − 1n,q maj(w) =qh+ibn/2c q
q
FC
i=0
w∈B̄n

h=1

where the square brackets are the so-called q-binomial coefficients, B̄nF C is the setof FC involutions in Bn , and maj is the major index.
As a second consequence of our characterizations of FC involutions, we will also
give the t-weighted generating functions for all types of classical finite and affine
Coxeter group. More precisely, if W̄ F C denotes the subset of FC P
involutions of`(w)
W and ` denotes the Coxeter length, we will define W̄ F C (t) :=w∈W̄ F C t
as the length generating function for FC involutions in W . We will use both ourcharacterization in terms of heaps and the way these are encoded by Dyck-typelattice walks to compute W̄ F C (t) when W is finite or affine. In the affine case,we will also show that the corresponding growth sequences are ultimately periodic,
with periods dividing the values recorded in the following table (see Propositions 3.3
and 3.4):
Affine Type
Periodicity

en−1 (n even)
A
n

en
C
2n + 2en+1
B(2n + 1)(2n + 2)

e n+2
D
2n + 2en−1 is finite.)(if n is odd, the number of fully commutative involutions in A

Finally, as a third consequence of our approach, we will relate our previous
e to Fan–Green’s cells structure of the associatedcharacterization in affine type A
Temperley–Lieb algebra described in [8]. More precisely, we will see how the use ofheaps highlights and simplifies some of their results connected to FC involutions,such as [8, Theorem 3.5.1].
This paper is organized as follows. In Section 1, we recall definitions and basic
results on Coxeter groups, fully commutative involutions, heaps and walks. In
Section 2, we enumerate FC involutions with respect to the major index in classicalfinite types. Section 3 is devoted to the characterization of FC involutions and their
enumeration with respect to the Coxeter length in classical finite and affine types.
Finally, in Section 4, after recalling the cell structure on FC elements defined in [8]e Temperley–Lieb algebra, we show how the use of heaps makes theusing the type A
combinatorics of these cells more explicit.
1. Fully commutative involutions, heaps and walks

1.1. Coxeter groups, length and major index. We refer to [13] for standard
notations and terminology pertaining to general Coxeter groups. A Coxeter system
is a pair (W, S) where W is a group and S ⊂ W is a finite set of generators
for W subject only to relations of the form (st)mst = 1, where mss = 1, andFULLY COMMUTATIVE INVOLUTIONS

3

mst = mts ≥ 2, for s 6= t ∈ S. If st has infinite order we set mst = ∞. These
relations can be rewritten more explicitly as s2 = 1 for all s ∈ S, andsts| {z· ·}·,
| {z· ·}· = tst
mst

mts

where mst < ∞. They are the so-called braid relations. When mst = 2, they aresimply named commutation relations, st = ts.
The Coxeter graph of (W, S) will be denoted by Γ. The irreducible Coxeter
systems corresponding to finite and affine Coxeter groups are completely classified(see [6, 13]), and the Coxeter graphs corresponding to the classical families are
depicted in Figures 1 and 2. Here, and all along this paper, the indexing of theclassical Coxeter graphs is slightly different from the more standard one used in [18]–[20], and [4], but it is more appropriate when one considers both the Coxeter lengthand the major index.
sn+1
4
s1 s2

An−1

sn−1

s1 s2

sn−1 sn

Bn

s1

Dn+1

sn−1
sn

Figure 1. Coxeter graphs for classical irreducible finite types.

s0
sn−1

s1

en−1
A

4

4

4

un s1

sn−1 sn

un s1

en
C

sn−1

sn+1

un+1

sn

un

en+1
B

sn+1
sn−1

s1

sn

e n+2
D

Figure 2. Coxeter graphs for classical irreducible affine types.

For w ∈ W , the length of w, denoted by `(w), is the minimum length l of any
expression w = s1 · · · sl with si ∈ S. These expressions of length `(w) are called
reduced, and we denote by R(w) the set of all reduced expressions of w.
The (right) descent set of an element w ∈ W is defined as follows:
DesR (w) = {s ∈ S | `(ws) < `(w)},and its cardinality is usually called the descent number des(w).
We define the major index of w ∈ W as the sum of the labels of the descents of
w; more preciselyX
maj(w) :=i.
si ∈DesR (w)

It is clear that the major index depends on the indexing of the generating set S
of W . In the case of the symmetric group An−1 , the notion of major index isstandard, and a very famous result states that the major index and the length areequidistributed over An−1 (see [15, 9]). For other Coxeter groups, several definitions
exist. With our previous indexing of the Coxeter graphs, the major index defined
above corresponds to the one already used by Reiner [16], and Steingrı́msson [17]in the type B case.

4

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU

1.2. Fully commutative elements and heaps. In this section, we recall thedefinition of fully commutative elements in Coxeter groups and its relation withthe theory of heaps. We then explain how the subfamily of alternating heaps
corresponding to involutions can be encoded by various classes of Dyck-type lattice
walks.
According to the well known Matsumoto-Tits word property, any expression in
R(w) can be obtained from any other using only braid relations (see for instance [6,Section 3.3]). The notion of full commutativity is a strengthening of this property.
Definition 1.1. An element w is fully commutative if any reduced expression for
w can be obtained from any other by using only commutation relations.
We let S ∗ be the free monoid generated by S. The equivalence classes of thecongruence on S ∗ generated by the commutation relations are usually called commutation classes. We recall from Stembridge in [18, Prop. 2.1] that an elementw ∈ W is FC if, and only if, all its reduced words avoid all factors of the form
sts · · · with length mst ≥ 3.
By definition the set R(w) forms a single commutation class; we will see thatthe concept of heap helps to capture the notion of full commutativity. We use thedefinition as given in [11, p. 20] (see also [14, Definition 2.2]), and we refer to [4]for details of the relation with FC elements.
Definition 1.2 (Heap). Let Γ be a finite graph with vertex set S. A heap on Γ (orof type Γ) is a finite poset (H, ≤), together with a labeling map  : H → Γ, which
satisfies the following conditions:(1) For any vertex s, the subposet Hs := −1 ({s}) is totally ordered, and forany edge {s, t}, the subposet H{s,t} := −1 ({s, t}) is totally ordered.
(2) The ordering on H is the transitive closure of the relations given by all
chains Hs and H{s,t} , i.e. the smallest partial ordering containing thesechains.
Two heaps on Γ are isomorphic if there exists a poset isomorphism between
them which preserves the labels. The size |H| of a heap H is its cardinality. Given
any subset I ⊂ S, we will note HI the subposet induced by all elements of H withlabels in I. In particular H{s} is the chain Hs = s(1) < s(2) < · · · < s(k) wherek = |Hs | is its cardinality. If s, t are two labels such that mst ≥ 3, note that H{s,t}is also a chain.
Fix a word w = s1 · · · sl in S ∗ . Define a partial ordering ≺ of the index set{1, . . . , l} as follows: set i ≺ j if i < j and {si , sj } is an edge of Γ, and extend bytransitivity. We denote by Heap(w) this poset together with  : i 7→ sai . It is easy
to see that this indeed forms a heap as in Definition 1.2.
Proposition 1.3 (Viennot, [21]). Let Γ be a finite graph. The map w → Heap(w)induces a bijection between Γ-commutation classes of words and isomorphism classesof finite heaps on Γ .
As explained in [4], if w is a FC element and w is a reduced word for it, we
can define Heap(w) := Heap(w), and heaps of this form are called FC heaps. In
Figure 3, we consider the Dynkin diagram B7 , and we give two examples of words
with the corresponding FC heaps. In the Hasse diagram of Heap(w), elements withthe same labels are drawn in the same column.

FULLY COMMUTATIVE INVOLUTIONS

w1 = s5 s7 s4 s6 s1 s3 s5 s7 s2 s4 s6 s3 s5 s7 s4

5

w2 = s6 s3 s5 s7 s2 s4 s6 s1 s3 s5 s7 s2 s4 s6 s3 s5 s7 s6

s4
s3
s2
s1

s6
s5
s6

s4
s3

s5

s7

s5

s6

s4

s2
s7

s5

s3

s1

s6

s4

s2

s6

s4

s5

s3

s7

s3

s5
s6

s7
s7
s7

s1 s2 s3 s4 s5 s6 s7

s1 s2 s3 s4 s5 s6 s7

Figure 3. Two heaps on B7 , the one on the right corresponding
to a FC involution.
Let us point out a simple operation on heaps: if (H, ≤, ) is a heap, then its dualis (H, ≥, ), which is the heap with the inverse order, and where the labels are kept
the same. We will say that a heap is self-dual if it is isomorphic to its dual. Then
we have the following result, which is essentially proved in [20].
Lemma 1.4. Let W be a Coxeter group with corresponding Coxeter graph Γ. A
fully commutative element w ∈ W is an involution if and only if Heap(w) is selfdual.
Proof. A FC element w ∈ W is an involution if and only if for a (equivalently,− := s · · · s is also in R(w). This isany) w = si1 · · · sin ∈ R(w), the reverse ←
w
in
i1
←
−
equivalent to Heap(w) = Heap( w), which is by definition the dual of Heap(w). 
1.3. Alternating heaps and self-dual right-peaks. In this section we recall theclassification of the FC involutions in the classical finite Coxeter groups essentiallygiven in [20]. We use a description in terms of heaps derived from [4, §2.5, §4.4],
together with Lemma 1.4.
First, we need to recall a few definitions. We fix mv0 v1 , mv1 v2 , . . . , mvn−1 vn inthe set {3, 4, . . .} ∪ {∞} and we consider the Coxeter system (W, S) corresponding
to the linear Coxeter graph Γn = Γn ((mvi vi+1 )i ) of Figure 4.
mv0 v1 mv1 v2

v0

v1

v2

mvn−1 vn

vn−1

vnFigure 4. The linear Coxeter graph Γn .
Note that this linear diagram contains as special cases the Coxeter diagrams oftypes An−1 , Bn and C̃n .
Definition 1.5. Consider the linear graph Γn , and a heap H on Γn . We say that H
is alternating if for each edge {vi , vi+1 } of Γn , the chain H{vi ,vi+1 } has alternatinglabels vi and vi+1 .
Next, we will need the following families of heaps, which are specific to the types
B and D.

6

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU

Definition 1.6. A self-dual right-peak of type Bn is a heap such that there existsj ∈ {1, . . . , n − 1} satisfying:(a) H{sj ,...,sn } = Heap(sj · · · sn−1 sn sn−1 · · · sj );(b) H{sj−1 ,sj } = sj sj or sj−1 sj sj sj−1 for j > 1, and s1 s1 for j = 1;(c) H{s1 ,...,ṡj } is self-dual alternating, where ṡj means that one sj is deleted.

sj

sn

Figure 5. A self-dual right-peak of type Bn .
The Coxeter diagram of type Dn+1 is not linear. We can nevertheless define selfdual alternating heaps and self-dual right-peaks based on the previous definitions
in type Bn . More precisely, self-dual alternating heaps of type Dn+1 are obtained
from self-dual alternating heaps of type Bn having either zero or an odd number of
elements labeled sn , by replacing these by sn or sn+1 alternatively, or by sn sn+1 if
there was originally exactly one label sn , cf. Figure 6.

s1

s8

(s7 )

s7

(s8 )

s8

(s7 )

s1

s7 s8

Figure 6. Two self-dual alternating heaps of type D8 .
Self-dual right peaks of type Dn+1 are heaps satisfying conditions (b) and (c)above, and such that there exists j ∈ {1, . . . , n − 1} with:(a’) H{sj ,...,sn+1 } = Heap(sj · · · sn−1 sn sn+1 sn−1 · · · sj ).
Remark 1.7. In the above families of right-peaks the index j is uniquely determined; this will be particularly useful for enumerating purposes.
From [4, Theorem 3.10] and Lemma 1.4, we have the following result.
Proposition 1.8 (Classification of FC involutions in classical types). A FC elementw ∈ An−1 is an involution if and only if Heap(w) is a self-dual alternating heap.
Moreover, a FC element w ∈ Bn ( resp. w ∈ Dn+1 ) is an involution if and only
if Heap(w) is either a self-dual alternating heap of type Bn ( resp. Dn+1 ) or aself-dual right-peak of type Bn ( resp. Dn+1 ).

FULLY COMMUTATIVE INVOLUTIONS

7

1.4. Motzkin type lattice walks. Next, we define the lattice walks we will use
in the sequel to compute generating functions for FC involutions.
Definition 1.9 (Walks). A walk of length n is a sequence P = (P0 , P1 , . . . , Pn )of points in N2 with its n steps in the set {(1, 1), (1, −1), (1, 0)}, such that P0 has
abscissa 0 and all horizontal steps (1, 0) can only occur between points on the x-axis.
The set of all walks of length n will be denoted by Gn∗ . The subset of walks
starting at P0 = (0, 0) will be denoted by Q∗n , and the subset of Q∗n ending at
Pn = (n, 0) will be denoted by M∗n . To each family Fn∗ ⊆ Gn∗ corresponds the
subfamily Fn consisting of those walks with no horizontal step, and Fˇn ⊆ Fn
consisting of the ones which hit moreover the x-axis at some point.
The total height
Pn ht of a walk is the sum of the heights of its points: if Pi = (i, hi )then ht(P ) = i=0 hi . To each family Fn∗ ⊆ Gn∗ we associate the series Fn∗ (t) =P
ht(P ), and we define the generating functions in the variable x by
∗ t
P ∈Fn
F ∗ (x) =XFn∗ (t)xn ,F (x) =n≥0X

Fn (t)xn

and F̌ (x) =n≥0XF̌n (t)xn .

n≥0

Notice that M (x) (resp. Q(x)) counts Dyck paths (resp. prefixes of Dyck paths),
taking into account the height. Moreover, the generating function M ∗ (x) can easily
be related to M (x): a path in M∗n can be seen as a concatenation of Dyck paths andhorizontal steps which alternate, remembering that the set of Dyck paths contains
the empty one. Therefore one can write:M ∗ (x) =M (x).
1 − xM (x)(1)

Recall that, setting t = 1, the series M (x) simply becomes the generating function for the famous Catalan numbers, and is therefore equal to the generating
function for 321-avoiding permutations, or equivalently FC elements of type A(see [4, 5, 20]).
Moreover, we have the recursive relation
M (x) = 1 + tx2 M (x)M (tx),(2)

as can be seen by considering the first return to the x-axis, as follows:tM (tx)

=

M (x)

+

We also point out that for all the subfamilies Fn∗ of Gn∗ that will naturally appear
later in our enumerations, there will be some equations of the form (1) relatingF ∗ (x), F (x) and M (x), and recursive relations like (2) for F (x).
1.5. Bijective encoding of alternating heaps. We now define a bijective encoding of self-dual alternating heaps by walks, which will be especially handy tocompute generating functions in the next sections. It is obtained by understanding
how the encoding of heaps defined in [4] restricts to self-dual heaps.

8

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU

Proposition 1.10. Let H be a self-dual alternating heap of type Γn . To eachvertex vi of Γn we associate the point Pi = (i, |Hvi |). We define ϕ(H) as thewalk (P0 , P1 , . . . , Pn ). Then the map H 7→ ϕ(H) is a bijection between self-dual
alternating heaps of type Γn and Gn∗ . The size |H| of the heap is the total height ofϕ(H).
Proof. For any alternating heap H and any i ∈ {0, . . . , n − 1}, we have −1 ≤|Hvi | − |Hvi+1 | ≤ 1. Moreover if H is self-dual and |Hvi | =6 0, then |Hvi | =6|Hvi+1 |. Therefore the map is well defined. Fix (P0 , P1 , . . . , Pn ) ∈ Gn∗ . If thestep Pi = (i, hi ) → Pi+1 = (i + 1, hi+1 ) is equal to (1, 1) (resp. (1, −1)), then we
define a convex chain Ci of length 2hi (resp. 2hi+1 ) as (vi+1 , vi , . . . , vi+1 ) (resp.
(vi , vi+1 , . . . , vi )). If the step Pi → Pi+1 is (1, 0), then hi = hi+1 = 0, and we let
Ci be the empty chain. Next we define H as the transitive closure of the chains
C0 , . . . , Cn−1 . It is acyclic since Γn is linear, so we get a heap H which is uniquely
defined, alternating, and satisfies ϕ(H) = (P0 , P1 , . . . , Pn ). Since hi = |Hvi | theresult follows.
H

u11 s1 s2ϕ(H)s10 s110

11e11 and its associated walk.
Figure 7. The heap of a FC involution in C

Remark 1.11. In the type An−1 case, if we consider alternating FC heaps, since
they have either zero or one occurrence of the labels s1 and sn−1 , we can add an
initial and a final step to the paths obtained through Proposition 1.10, to get abijection with paths in M∗n . Similarly, since alternating FC heaps on Bn are in∗
bijection with paths in Gn−1
starting at height zero or one, we can add an extra
initial step, to obtain a bijection with paths in Q∗n .
2. Enumeration with respect to the major index
Recall the following enumerative expressions for the number of FC involutionsin classical finite types, which were first proved in [20, Section 4].
Proposition 2.1. We have for n ≥ 1nFC|Ān−1 | =
,
bn/2c


n
FC
n
|B̄n | = 2 +
− 1,
bn/2c



n+1

n

2 +
− 1 if n even,



n/2
FC
|D̄n+1 | =




n+1
3

n

− 1 if n odd.
2 +2 (n + 1)/2

(3)
(4)

(5)

FULLY COMMUTATIVE INVOLUTIONS

9The striking observation is that by considering the major index defined in Section 1 we can obtain nice q-analogues for formulas (3)–(5). For type A this analogue
was recently computed by Barnabei et al. in [3], by using the 321-avoiding characterization of FC involutions, the Robinson–Schensted algorithm, and a connection
with integer partitions. A non-bijective proof of this result, using the principal
specialization of Schur functions, has also been given by Stanley, and a third one
has been found by Dahlberg and Sagan (see [3, §6]).
In this section, we show that our different approach in terms of heaps will allow
us to derive this result and extend it to types B and D. In type A, we will shortly
explain in Proposition 2.4 below that our approach and the one of Barnabei et al.
are equivalent, and yield the same connection to integer partitions. In types B andD, we will still use our characterization in terms of heaps and the idea from [3] toconnect walks to integer partitions; here the approach through pattern avoidancein signed permutations seems harder to use.
Before giving our result, we recall a classical property relating q-binomial coefficients and integer partitions. A partition of the integer N is a nonincreasing
sequence λ = (λ1 ≥ · · · ≥ λl > 0) of positive integers whose sum is equal to N ,which we denote by |λ| and call the weight of λ. The integer l is the length of λ,while the λi ’s are called the parts of λ. It will be convenient to use Frobenius notations for partitions. Let j be the rank of a partition λ, namely the largest integer isuch that λi ≥ i: it is also the size of the Durfee square of λ. For 1 ≤ i ≤ j, define
αi = λi − i and βi = λ0i − i. The Frobenius notation for λ is the array
α1 α2 . . . αj.
β1 β2 . . . βj
We have the following classical generating function (see for instance [1]).
Lemma 2.2. The generating function in the variable q, according to the weight,of integer partitions with largest part smaller or equal to k and length smaller or
equal to n − k, is given by the q-binomial coefficient n(1 − q) · · · (1 − q n ).
:=(1 − q) · · · (1 − q k )(1 − q) · · · (1 − q n−k )k q
2.1. Type A. We prove the following result, which can be found in [3].
Proposition 2.3. For any positive integer n, we haveXnmaj(w)q=.
bn/2c qFC

(6)w∈Ān−1

C
Proof. Recall from Proposition 1.8 that each FC involution w ∈ ĀF
n−1 corresponds
bijectively to a self-dual alternating heap H = Heap(w), which is itself in one-to-one
correspondence with a walk in M∗n , thanks to Proposition 1.10 and Remark 1.11.
Note that i ∈ DesR (w) if and only if there exists in the poset H a maximum element
labeled si . In the path encoding this corresponds to a peak (i.e. an ascending step
followed by a descending one) at coordinates (i, |Hsi |). Therefore the position i ofsuch a descent is equal to the number of steps from the origin to this peak.
Fix a walk γ ∈ M∗n and let k be its number of horizontal steps. Note that k and nhave the same parity. Replace the first bk/2c (resp. the last dk/2e) horizontal steps
by descending (resp. ascending) ones. Next replace all descending (resp. ascending)

10

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU

steps by horizontal (resp. vertical) ones, yielding γ̄ in Πn , the set of walks withn horizontal or vertical steps, starting at the origin and ending at (bn/2c, dn/2e).
These operations are invertible, and an example of the bijection γ → γ̄ is provided
in Figure 8.
8

2

10

2

8

10

γ ∈ M∗13(4, 6)(3, 5)(0, 2)γ̄ ∈ Π13
Figure 8. An example of the walk-to-partition bijection.
It is not difficult to see that descents of γ coincide in γ̄ with corner points (formed
by a vertical step followed by a horizontal one). Moreover the position of a descentin γ is given by the sum of the coordinates of the corresponding corner point in γ̄.
Denote by P1 (a1 , b1 ), . . . , Pj (aj , bj ), with bn/2c > a1 > · · · > aj ≥ 0 and dn/2e ≥b1 > · · · > bj > 0 the corner points of γ̄. Summarizing, we haveXX
q maj(w) =q a1 +b1 +···+aj +bj .
(7)
γ̄∈Πn

C
w∈ĀF
n−1

Since any walk γ̄ ∈ Πn is uniquely determined by its corner points, it can beassociated with an integer partition λ defined in Frobenius notation as


a1
a2
...
aj
λγ̄ =
.
b1 − 1 b2 − 1 . . . bj − 1

This is a bijection: for a proof see [3, Theorem 3.4] to which we refer for moredetail. As any such partition has length ≤ dn/2e and greatest part ≤ bn/2c, we
obtain (6) through (7) and Lemma 2.2.

By comparing our resulting bijection with that of [3], we observed a striking
coincidence. Starting from a FC involution w ∈ An−1 , we considered the following
sequence of bijective transformations:w −→ H −→ γ ∈ M∗n ,where H = Heap(w) and γ = ϕ(H) (see Remark 1.11). Barnabei et al. [3] consider
a different sequence of transformations, namely:RSw −→ T −→ β ∈ Qn ,

FULLY COMMUTATIVE INVOLUTIONS

11

where T is the two rows standard tableau obtained by the Robinson–Schensted
correspondence, and β is the classical associated Dyck-path prefix. The following
proposition shows that the two constructions essentially coincide.
Proposition 2.4. The walk β is obtained from γ by replacing in the latter all
horizontal steps by ascending ones.
Proof. If w(i) = i, then w(j) < i for all j < i (equivalently, w(j) > i for all j > i):otherwise w(j) > i > j would be an occurrence of the pattern 321. This shows thatH splits naturally into two heaps corresponding to elements smaller, resp. larger
than i. Moreover H contains elements labeled neither by si−1 nor by si , whichmeans the ith step of γ being a horizontal step. In the RS construction, we alsoeasily see that such a fixed point i will correspond to an up step in β, where β
leaves at abscissa i a certain height for the last time.
Thus the statement of the proposition is proved if we can show that β = γ
whenever w has no fixed points, which we now assume. In this case β and γ are
Dyck paths in Mn , and their construction is illustrated in Figure 9.
w=

1 2 3 4 5 6 7 8 9 10 11 12
3 4 1 2 7 10 5 11 12 6 8 9
RS

9
2

3

1

H=

6

10

7 8

11
12

4 5
45

1
2

3

6

T =

12

1
3

2
4

5 6 8 97 10 11 12

11

78
9

10

γ=β

Figure 9. Two constructions of the same correspondence.
Note that we superimposed a cell on each vertex from the heap H. This is usefulto read off the involution directly, see for instance [21]. More precisely, pick anylabeled edge, say i, on the top side, and follow the corresponding “column” of cells
until the bottom side is reached: the label that can be read off is w(i). By theconstruction of γ from w, it is then clear that its ith step is an up step if and only
if w(i) > i.
On the other hand, the ith step in β is an up step if and only if it appears in the
top row of the tableau T obtained from w. Now one can show by induction that,in the RS insertion algorithm, an entry j < i will bump i from the first row if andonly if j = w(i). Putting things together, the ith step in β is an up step if andonly if w(i) > i. Comparing with the previous paragraph, this shows that β and γ
coincide, and concludes the proof.
12

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU

2.2. Type B. In type B, we have the following generalisation.
Proposition 2.5. For any positive integer n, we have


n
h−1
X
X
X h − 1nmaj(w)
h
q
=
q
+
.
i
bn/2c q
q
FC
i=0

(8)

h=1

w∈B̄n

Proof. By Proposition 1.8, we have to inspect separately self-dual alternating heaps
and right-peaks of type Bn . By definition right-peaks can be split for a j ∈{1, . . . , n − 1} into two heaps H{s1 ,...,ṡj } and H{sj ,...,sn } , and this decompositionis unique by Remark 1.7. These two parts can be bijectively reassembled by associating to the first one a walk in Q∗j ending at height one, and to the second
one a walk starting with a (1, −1)-step, followed by n − j − 1 horizontal steps, andthen gluing these two walks together. This yields a walk in M∗n with less than nhorizontal steps. For instance, the walk associated to the right-peak in Figure 5 is
depicted below.

j=7

We remark that if w ∈ B̄nF C corresponds to a right-peak, then sn 6∈ DesR (w),so by applying the same arguments as in type An−1 , we find that the generating
function for those elements is equal to


n
− 1.
(9)
bn/2c q

The remaining heaps are the self-dual alternating ones, which are by Proposition 1.10 in one-to-one correspondence with walks in Q∗n .
First, replace in these walks all (1, 0) steps by (1, −1) steps. Secondly, replace asin type An−1 all descending (resp. ascending) steps by horizontal (resp. vertical)
ones. We obtain this time a bijection with length n walks with horizontal or verticalsteps, starting at the origin but ending at any height, whose set is denoted by Π0n ,as can be seen on the illustration below.
(7, 5)

2(4, 3)

127

γ 0 ∈ Q∗12

(0, 2)

γ̄ 0 ∈ Π012

As before, if we fix w ∈ B̄nF C , the descents of w correspond in γ̄ 0 ∈ Π0n to corner
points, together with the last point if it ends a vertical step. Denote all thesepoints by P1 (a1 , b1 ), . . . , Pj (aj , bj ); they satisfy a1 > · · · > aj ≥ 0 and b1 > · · · >bj > 0, with the additional condition a1 + b1 ≤ n, and again maj(w) is equal to
a1 + b1 + · · · + aj + bj . As in type A, the corner points define a unique partitionλγ̄ 0 in Frobenius notation, such that a1 + b1 ≤ n.

FULLY COMMUTATIVE INVOLUTIONS

13

Summarizing, alternating FC involutions in Bn are in bijection with such integers
partitions λγ̄ 0 satisfying a1 + b1 ≤ n. If λγ̄ 0 is not empty, note that a1 = λ1 andb1 = l − 1, where l is its length. Set h := a1 + b1 and i := b1 , therefore we have1 ≤ h ≤ n and 0 ≤ i ≤ h − 1. Remove from λγ̄ 0 its first part λ1 and decreaseby one all the remaining parts, therefore giving a partition µ of weight |λγ̄ 0 | − h.
Moreover, µ satisfies the conditions of Lemma 2.2 with n replaced by h − 1 and k
by i, therefore giving the generating functionnh−1
XX h − 1
h
1+
q
,
i
q
i=0
h=1

which concludes the proof.

Thanks to the previous proof, we can refine as follows this result, as was donein [3] for type A.
Corollary 2.6. For any integer 1 ≤ k ≤ n, we have 
n−2k−1h XXX
i+k−1 h+k−1−ihmaj(w)
k2
q
.
q
=q
k−1 q
k−1
q
FC
i=0
h=0

w∈B̄n

des(w)=k

Moreover, when k = 0, this generating function is equal to 1.
Proof. We analyse more precisely the structure of the partition λγ̄ 0 from the previous proof when the FC involution has k descents. Obviously, if k = 0, then thispartition is empty, which yields the result. Otherwise k ≥ 1 is the row length in
the Frobenius notation of λγ̄ 0 , so it corresponds to the size of its Durfee square. We
can define as before the integers h and i, satisfying this time 2k − 1 ≤ h ≤ n andk − 1 ≤ i ≤ h − k, respectively. Moreover, the partition µ obtained from λγ̄ 0 has a
Durfee square of size k − 1, so the desired generating function is equal to

 

n
h−k
X
X
i
h−1−i
h
(k−1)2.
qq
k−1 q k−1 qh=2k−1i=k−1

The result is then obtained by shifting accordingly the indices h and i.



2.3. Type D. Finally, for type D, we have the following result.
Proposition 2.7. For any positive integer n, we have




X
n−1
n+1
q maj(w) = Pn (q) + (q 2n+1 − q n )+,b(n + 1)/2c qb(n − 1)/2c q
FCw∈D̄n+1

where for n even,
Pn (q) :=

n−1
X
h=1

and for n odd,
Pn (q) :=

n−1
X
h=1

q

h


n−1
X n − 1
h−1
1 n,+ q (1 + q)
2
i
i
q
q
i=0

h−1
X
i=0


n−1
X n − 1
h−1
1 n+ q (1 + q)
i
2
i
q
q
i=0

h−1
X
i=0

q

h

(10)

14

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU(n−1)/2

+

X

h=1

q n−h





n−h−1
1
n−1
+ q n (1 + q).
(n − 1)/2 q 2(n − 1)/2 q

Proof. Obviously from their definition, self-dual right-peaks of type Dn+1 are in
bijection with the ones of type Bn , and have no descents at sn , sn+1 , so theirgenerating function is equal to (9).
The alternating involutions containing sn sn+1 are in bijection with walks in Q∗nending at height 1. Among these, the walks having an ascending last step areenumerated by


n−1
2n+1
q
.
b(n − 1)/2c q

Indeed both sn and sn+1 are descents, and the first n − 1 steps form a walk inM∗n−1 so we can use Proposition 2.3.
The generating function for the previous walks having a descending last step can
be computed in the following way: first add an extra descending step to reach thex-axis, thus obtaining a walk in M∗n+1 ending with two descending steps. Note thatneither sn nor sn+1 are descents for the corresponding involutions, so the generating
function is obtained by computing the generating function of all type A walks fromthe origin to (n + 1, 0), to which we must substract the generating function of thewalks having either a peak in position (n, 1) or ending with one horizontal step (seethe figure below).

nType Dn+1=−
Type Ansn−

Type An−2

Type An−1

Again by Proposition 2.3, the result is






n−1
n
n+1
− qn
−
.
b(n − 1)/2c q
bn/2c qb(n + 1)/2c q
By adding the two previous expressions to (9), we get the two last terms in (10)minus 1, therefore we now have to show that the generating function for the remaining alternating elements is equal to Pn (q) + 1. Consider such an element, andlet H be its corresponding heap. If there is no occurrence of sn and sn+1 , thenH is encoded by a walk in M∗n . Otherwise notice that self-duality implies that
|H{sn ,sn+1 } | is odd. Therefore if the first label of H{sn ,sn+1 } is sn (resp. sn+1 ), thenH is in bijection with a walk γ sn (resp. γ sn+1 ) in Q∗n ending at an odd height.
Denote by M∗n (q) the generating function (6) for type An−1 , and Q∗sn (q) thegenerating function for the alternating FC involutions in Bn . Let also Q∗sn+1 (q)be the generating function of alternating FC involutions in Bn but where eachoccurrence of sn is replaced by sn+1 .
We claim that if n is even, then the desired generating function is equal to11M∗n (q) + (Q∗sn (q) − M∗n (q)) + (Q∗sn+1 (q) − M∗n (q)).
(11)
22Recall that Q∗sn (q) counts walks in Q∗n . These walks can be split into three parts:
the ones ending at 0, at an even height ≥ 2, or at an odd height. Then (11) isconsequence of a bijection between these walks ending at an odd height, and thoseFULLY COMMUTATIVE INVOLUTIONS

15

ending at an even ≥ 2 height. This bijection goes as follows: in a walk ending at
an odd height replace the last (1, 0) step (as n is even there is at least one) by a(1, 1) step, and shift accordingly the remaining steps. For the reverse application,change the last (1, 1) step starting from the x-axis into a (1, 0) step. This bijection
preserves the peaks of the walks (and therefore the descents of the associated FC
involutions).
Simplifying (11), we have to compute (Q∗sn (q) + Q∗sn+1 (q))/2, where thanks tothe analysis of the previous type B case,Q∗sn (q) = 1 +

n
X

h=1

qh

h−1
X
i=0


h−1
.
i
q

Notice that in type B, a FC involution has a descent at sn if and only if a1 +b1 = n,with the notations above. Therefore Q∗sn+1 (q) can be computed similarly to Q∗sn (q),except for h = n, in which case the corresponding term has to be multiplied by q.
This yields the desired expression Pn (q) + 1.
If n is odd, our previous bijection between walks ending at odd and even height
does not work anymore, as our walks can have no horizontal step. So after splitting
the walks in Q∗n as before, but where the walks ending at an odd height are separated
between those having or not an horizontal step, we can use the previous bijection
to see that one must therefore replace (11) by
1 ∗1(Q (q) + Q∗sn+1 (q)) + (Qsn (q) + Qsn+1 (q)),
2 sn2where Qsn (q) is the generating function for the walks in Q∗n having no horizontal
step, and Qsn+1 (q) is the same generating function, but where each occurrence ofsn is replaced by sn+1 . Note that all these walks must end at an odd height. To
conclude, it is enough to prove that(n−1)/2

Qsn (q) =

X

h=0

q

n−h



n−h−1
.
(n − 1)/2 q

To see this, consider any of the previous walks, which has, say j, steps of theform (1, 1) leaving definitively a certain height (note that j has to be odd, liken). Transform bijectively the (j − 1)/2 first of these steps in the previous walkto steps (1, −1) and shift accordingly all remaining steps. Remark that peaks
are preserved by this transformation (this is a well known bijection, see [3] andthe references therein). Then transform our walk as in types A and B, to get awalk of length n with paths (1, 0) and (0, 1), starting at the origin and ending at((n − 1)/2, (n + 1)/2). The analysis is now the same as in type A, except that wehave to distinguish whether the last step corresponds to a descent (if it is of theform (0, 1)) or not. To do this, denote by h the distance between the top extremityof the last vertical step and the point ((n − 1)/2, (n + 1)/2), as shown in the figure
below, and then proceed as in type A to relate our walks to integer partitions in a
box.

16

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU
h
dn/2e

n

bn/2c


3. Enumeration with respect to the Coxeter length
3.1. Finite types. Recall from the introduction thatPfor any Coxeter group W ,the length generating function W̄ F C (t) is defined as w∈W̄ F C t`(w) . In the threeclassical finite types these series are polynomials, and we denote their generating
functions by
X
X
X
FC
C
n
D̄n+1
(t)xn ,
B̄nF C (t)xn , and D̄(x) =ĀF
B̄(x) =
Ā(x) =n−1 (t)x ,
n≥0

n≥0

n≥1

where D̄1F C (t) := 1.
Proposition 3.1. We have
M (x)
− 1,
1 − xM (x)Q(x)
x2 t3 M (x)M (tx)B̄(x) =+,
1 − xM (x) 1 − xt2 1 − xM (x)M (x)xt2 M (x)M (tx)Qo (x)++,
D̄(x) = 2
1 − xM (x) 1 − xM (x) 1 − xt2 1 − xM (x)
Ā(x)

=

(12)
(13)
(14)

where Qo (x) denotes the generating function for t-weighted prefixes of Dyck walks
ending at an odd height. Note that the previous generating functions can all be
explicitly computed thanks to (2) and the following functional equations:Q(x)= M (x)(1 + xtQ(tx)),o= xtM (x)M (tx)(1 + xt2 Qo (xt2 )).

Q (x)Proof. From Proposition 1.8, and Proposition 1.10, FC involutions in An−1 are in
one-to-one correspondence with walks in M∗n . This shows (12) by using (1).
From Proposition 1.8, FC involutions in Bn correspond to self-dual heaps which
are either alternating or right-peaks.
As before, in the alternating case, one can use Proposition 1.10 to show that they
are in one-to-one correspondence with walks in Q∗n . Moreover, such a walk can beseen as a collection of pairs (Dyck path, horizontal step), followed by a prefix of a
Dyck path. This is illustrated in Figure 10 and shows thatQ∗ (x) =Q(x),
1 − xM (x)yielding the first term on the right-hand side of (13).

FULLY COMMUTATIVE INVOLUTIONS

1
1−xM (x)

17

Q(x)

...
Figure 10. Decomposition of walks for self-dual alternating heapsof type B.

By definition right-peaks can be split into two parts H{s1 ,...,ṡj } and H{sj ,...,sn } ,and this decomposition is unique by Remark 1.7. The generating function of thesecond part is
x2 t 3,
1 − xt2
while by Proposition 1.10 the first part is in bijection with walks in Q∗n ending atheight 1. The latter can be seen as collections of pairs (Dyck path, horizontal step),
followed by a couple of Dyck walks, the first starting and ending at height 0, andthe second at height 1, as illustrated below.
1
1−xM (x)

M (x)

...

M (qx)x

1

Figure 11. Decomposition of walks for self-dual right-peaks oftype B.
This yields the generating function
xtM (x)M (tx).
1 − xM (x)The second term on the right-hand side of (13) arises as the product of these twogenerating functions, after dividing by xt, which corresponds to the occurrence of
one sj belonging to both parts of our split.
Finally, for the proof of (14), we use the type Dn+1 case of Proposition 1.8.
Starting from a self-dual alternating heap H of type Bn , we have three cases:• if there is no occurrence of sn in H, then Proposition 1.10 and formula (1)give the generating function M (x)/(1 − xM (x)).
• if there is at least one occurrence of sn in H (self-duality implies this number
is odd), we replace Hsn by (sn , sn+1 , . . . , sn ) or (sn+1 , sn , . . . , sn+1 ), givingFCrise to two heaps corresponding to elements of D̄n+1, which are in bijection∗
with walks in Qn ending at odd height. This gives the generating function
2Qo (x)/(1−xM (x)), with the same decomposition as in Figure 10, in whichQ(x) is replaced by Qo (x).

18

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU• if there is exactly one occurrence of sn in H, we must add the generating function for the self-dual FC heaps corresponding to type Dn+1 involutions, by replacing sn by sn sn+1 (= sn+1 sn ). These elements are in
bijection with walks in Q∗n ending at height 1, whose generating function
has already been computed (see Figure 11). Taking into account an extra t due to the occurrence of sn sn+1 , we obtain the generating function
xt2 M (x)M (tx)/(1 − xM (x)).
The generating function of right-peaks of type Dn+1 is the one for type Bn
multiplied by t, and it is equal tox2 t4 M (x)M (tx).
1 − xt2 1 − xM (x)By summing up these four expressions we obtain formula (14) after a few simplifications. Finally the functional equations for Q(x) and Qo (x) can be computed
thanks to classical decompositions of (prefixes of) Dyck walks.

en−1 . In this section, we will give the description of the heaps for3.2. Affine type A
en−1 , and their generating function with respect to the length.
FC involutions in A
en−1 is FC if and only if,
Recall from [4, Proposition 2.1] that an element w in A
in any reduced decomposition of w, the occurrences of si and si+1 alternate for alli ∈ {0, . . . , n − 1}, where we set sn = s0 . This shows that FC heaps for the graphen−1 coincide exactly with alternating heaps (extended to the non-linearof type A
en−1 ).
Coxeter diagram of A
Moreover, from Lemma 1.4, we immediately derive the following description.

en−1 is an involution if and only if Heap(w)Proposition 3.2. A FC element w ∈ A
e
is a self-dual alternating heap of type An−1 .

en−1 by depicting all (alternating) chains
We shall represent heaps of type A
H{si ,si+1 } for i = 0, . . . , n − 1. To be able to represent these chains in a planar
fashion, we duplicate the set of s0 -elements and use one copy for the depiction of
the chain H{s0 ,s1 } and one copy for H{sn−1 ,s0 } . This can be seen in Figure 8, where
we also illustrate the restriction of the bijection with walks from [4] to self-dual
alternating heaps corresponding to involutions.

H ∈ Ã10s0

11

s10 s0H ∈ Ã7
s0

s7 s0

8

Figure 12. Two illustrations of the bijection between self-dualealternating heaps and walks in type A.

FULLY COMMUTATIVE INVOLUTIONS

19

Note that Proposition 3.2 immediately implies finiteness of the set of FC involuen−1 if n is odd, as the corresponding heaps H can not have full support,
tions in A
i.e. there exists necessarily an integer i such that |Hsi | = 0. Indeed, thanks to
self-duality and the alternating condition, one can see that there exists even inthis case an integer i such that |H{si ,si+1 } | = 0. Moreover, we are able to deduce
the following result, where as usual [xn ]F (x) stands for the coefficient of xn in the
power series F (x).
Proposition 3.3. The generating function, with respect to the length, of fully comen−1 , is equal tomutative involutions of type A
2 ∂(xM )tn Ǒn (t)n M (x)(1 + tx
∂x (tx))
+
[x
]
,
n
1−t
1 − xM (x)(15)

where On (t) is the generating function for walks in Gn starting and ending at thesame height. Moreover, if n is odd, (15) is a polynomial, while the corresponding
growth sequence is ultimately periodic with period dividing n, if n is even. Finally,in the latter case, periodicity starts at length 1 + n2 /4.
en−1 correspond to
Proof. From Proposition 3.2, we know that FC involutions in A
self-dual alternating heaps. Next, by using the restriction to self-dual heaps ofthe bijection ϕ0 of [4, Theorem 2.2], we see that these involutions are in one-to-one
correspondence with walks in Gn∗ starting and ending at the same height. Moreover,the length of the corresponding involution is equal to the area below the walk. Suchwalks can be decomposed according to whether they hit the x-axis or not, as canbe seen below.

+>0

The first term in formula (15) corresponds to the walks on the left. For the walks on
the right, the central part is in M∗j (for a j between 0 and n − 2) whose generating
function is given by (1), while the other two parts can be joined to form a path in
Mn−j−2 . The second term in formula (15) is therefore obtained through classicalconsiderations (see for example the proof of [4, Corollary 2.4]).
Next, it is clear that if n is odd, then On (t) = 0, while ultimate periodicity is
obvious from formula (15) if n is even. Finally, in the latter case, the second termin (15) is a polynomial with degree n2 /4, which corresponds to the area of the walkstarting and ending at the origin (having therefore n/2 up steps followed by n/2
down steps), and this finishes the proof.

3.3. Other classical affine types. By using the classification results of [4], it ispossible to compute all the generating functions for FC involutions W̄ F C (t) whene Be and D,e and we
W is affine. Nevertheless, we will only give the results for types C,
leave the exceptional types to the interested reader. In the following result, we givethe general forms of these generating functions, which shows ultimate periodicity

20

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU

of the growth sequence in all cases. Note that the exact beginning of periodicity
could also be computed by our methods.
Denote by Fne , (resp. Fno ) the subfamily of Gn of paths ending at an even (resp.
odd) height. Denote also by Fnee , (resp. Fnoo ) the subfamily of Gn of paths startingand ending at an even (resp. odd) height. Recall that to each one of these families
we associate a generating function as explained in Section 1.5.
Proposition 3.4. The generating functions for fully commutative involutions inen , Ben+1 and D
e n+2 are respectively given by:types C
tn+1 F̌n (t) 2t2n+3++ Rn (t),1 − tn+1
1 − t22t2n+2 F̌no (t) + 2tn+1 F̌ne (t) t2n+4
t4n+2++ Tn (t),+1 − t2n+2
1−t
1 − t2n+1
4t2n+2 F̌noo (t) + 4tn+1 F̌nee (t) 2t2n+6
2t4n+4+++ Un (t),1 − t2n+2
1 − t2
1 − t2n+2

(16)

(17)
(18)

where Rn (t), Tn (t), and Un (t) are polynomials. The corresponding growth sequences
are ultimately periodic, with period dividing 2n + 2, (2n + 1)(2n + 2), and 2n + 2,
respectively.
en correspond
Proof. From [4, Theorem 3.4] and Lemma 1.4, FC involutions in C
to self-dual heaps belonging to five families, among which only two are infinite. It
is therefore enough to focus on these two sets, the first of which being made ofalternating heaps. From Proposition 1.10, such elements correspond to walks in
Gn∗ ; their generating function is given by2
tn+1 F̌n (t)n (1 + txQ(tx))+[x],
1 − tn+1
1 − xM (x)by considering as before the decomposition illustrated below.

1 + txQ(tx)11−xM (x)1 + txQ(tx)+>0Figure 13. Decomposition of walks in Gn∗ .
The elements of the second infinite set are the self-dual zigzags; they are selfdual heaps of the form H = Heap(w) where w is a finite factor of the infinite∞
periodic word (un s1 s2 · · · sn−1 sn sn−1 · · · s2 s1 ) such that |Hsi | ≥ 4 for at least onei ∈ {1, . . . , n−1}. The minimal length is equal to 2n+3, as can be seen in Figure 14,
left. Moreover, there are 2 self-dual heaps for each length 2n + 3 + 2k (with k ≥ 0)
by left-right symmetry, and 0 for other lengths, yielding the generating function
2t2n+3.
1 − t2FULLY COMMUTATIVE INVOLUTIONS

21

Summing these expressions and adding the polynomial generating functions corresponding to self-dual heaps in the three remaining finite families from [4] gives (16).
en+1 , and from [4] and Lemma 1.4, it suffices to
For FC involutions of type Beexamine among type Bn+1 alternating and zigzag heaps which ones are self-dual.
Concerning alternating ones, we perform the following substitution in each selfen : replace the occurrence of (sn , sn , sn , . . .)dual alternating heap H of type C
by (sn , sn+1 , sn , . . .) or (sn+1 , sn , sn+1 , . . .), together with the replacement sn 7→
sn sn+1 = sn+1 sn in the case of exactly one occurrence of sn . The self-duality
condition forces |Hsn | to be either odd, or equal to 0. Therefore the generatingen+1 takes the form
function for self-dual alternating heaps of type B
xt2 Q(x)M (tx)
Q(x)
n
2
n
+
[x
,
]
t
Q(tx)
+
2Q∗o
(t)
−
[x
]
n
1 − xM (x)1 − xM (x)∗where Q∗on (t) is the generating function for walks in Gn ending at odd height. Moreover, the only non-polynomial term in this expression is Q∗on (t). The corresponding
walks can be decomposed as in Figure 13 in which the parity of h has to be taken
into account, and the last term 1 + txQ(tx) has to be replaced by Qo (x). This
yieldst2n+2 F̌no (t) tn+1 F̌ne (t)(1 + txQ(tx))Qo (x)Q∗o++ [xn ].
n (t) =
2n+2
2n+2
1−t
1−t
1 − xM (x)

un
sn+1
sn

un

sn sn+1
un un+1

sn sn+1unsn

un

sn sn+1
un un+1

sn+1

sn sn+1
un

C̃n

B̃n+1

D̃n+2

Figure 14. Some self-dual zigzag heaps.
en+1 is equal to 2n + 4. MoreThe minimal length for self-dual zigzags of type B
over, for any k ≥ 0 there are 2 self-dual heaps for each length 4n + 2 + k(2n + 1):
these are the heaps starting and ending at sn or sn+1 (see Figure 14, middle). For
other lengths there is only 1 such heap, yielding the generating function
t2n+4
t4n+2
+
.
1−t
1 − t2n+1

It is then easy to derive formula (17) by adding the previous generating functions
to the polynomials corresponding to self-dual heaps in the three remaining (finite)families of [4].

22

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU

e n+2 , we again consider the self-dual heaps
Finally, for FC involutions of type Damong alternating and zigzag ones. The alternating self-dual heaps correspond towalks in Gn∗ starting and ending at odd height. Moreover, each such walk gives
rise to 4 FC involutions, according to the choices of un or un+1 , and sn or sn+1 .
Among these walks, only the ones staying above the x-axis correspond to an infinite
number of elements, their generating function is given by:
4t2n+2 F̌noo (t) + 4tn+1 F̌nee (t),1 − t2n+2
as can be seen as before through classical walk decomposition. The minimal lengthfor self-dual zigzags is 2n + 6. For any k ≥ 0, by left-right symmetry there are 4
such elements for each length 4n + 4 + k(2n + 2) (see Figure 14, right), 2 for othereven lengths, and 0 for odd lengths, yielding the generating function
2t4n+42t2n+6+.
2
1−t
1 − t2n+2e
4. Cells for FC elements in type A

This section is not about enumeration, but aims at illustrating how the representation of FC elements as heaps can be useful in other ways.
en−1 ). It is
In [8], Fan and Green study the affine Temperley–Lieb algebra TL(Aen−1 Hecke algebra, and can be defined by generators Es
a quotient of the type Ai
for i ∈ {0, 1, . . . , n − 1} and relations:2Esi = Esi ,Esi Esj Esi = Esi if i = j ± 1 modulo n,
Esi Esj = Esj Esi if i 6= j ± 1 modulo n.

Note that the first relation involves usually an extra parameter α, but this hasen−1 ) has a linear
no incidence on the results we will describe. The algebra TL(Aebasis (Ew ) indexed by FC elements in An−1 : one can define unambiguously Ew =Esi1 · · · Esik where si1 · · · sik is any reduced expression of the FC element w.
Using this algebra, there are natural relations on the set of FC elements.
R

en−1 . One writes w 6 w0 if
Definition 4.1. Let w, w0 be FC elements of type ARR

there exists a FC element x such that Ew0 = Ew Ex , and w ∼ w0 if w 6 w0 andR

w0 6 w.

R

R

Since 6 is a preorder, ∼ is an equivalence relation whose classes are called rightcells. These are analogues of the famous Kazhdan–Lusztig cells which give representations of the Hecke algebras, in the arguably simpler context of the Temperley–Lieben−1 ).
algebra TL(ATheorem 4.2. [8, Theorem 3.5.1] Each right cell contains at most one involution.
Right cells with no involution occur only when n is even.
In the sequel we wish to show how the use of heaps can illustrate this result andmake it more precise. To this aim we first describe in terms of heaps the so-called
reduction of FC elements used in [8].

FULLY COMMUTATIVE INVOLUTIONS

23

en−1 , and si ∈Definition 4.3 (Reduction). Let w be a FC element of type A
DesR (w). Then w can be reduced to wsi if at least one of si−1 , si+1 belongs to
R
DesR (wsi ). We will write w → wsi .
R

Reduction is easy to illustrate on heaps: w → wsi if si labels a maximal elementin Heap(w) and if either si−1 or si+1 labels a maximal element in Heap(wsi ) :=top
Heap(w) \ {stopis the maximal element of the chain Hsi . We refer thei }, where si
reader to Figure 15 for a chain of successive reductions.

Figure 15. Successive reductions.
Reduction is useful to investigate right cells, thanks to the following simple result.
R

R

Lemma 4.4. If w → wsi , then w ∼ wsi . In other words, if w reduces to wsi , thenboth belong to the same right cell.
A FC element w is called irreducible if it can not be reduced to wsi for any i. It
is relatively easy to give a characterization of the heaps of such elements. Recall
that the support of the FC element w is the set of si , i ∈ {0, . . . , n − 1}, which
occur in a reduced decomposition of w.
Proposition 4.5. A FC element w is irreducible if and only if its heap satisfies
top
top
top
top
stop
> stopii+1 < si+2 > si+3 < . . . si+2m−1 < si+2m for all i, m satisfying:• if w has full support, then n is even, m = n/2 and i = 0 or 1,• otherwise {i, i+1, . . . , i+2m} is any maximal (cyclic) interval of the supportof w.
Proof. First it is clear that such elements are indeed irreducible. Suppose w is notof this form. Then (up to a cyclic shift of the indices and a relabeling i 7→ n−i), the> stopand either |Hs2 | = 0 or stop
> stopfollowing situation occurs: one has stop
0
1
1
2 .
R

Therefore w → s0 w and we are done.

For w irreducible, we now define a particular subset of elements in Heap(w): thiswill allow us to connect irreducible heaps with FC involutions.
If the support of w is not full, then we select all maximal elements in the heap.
This is illustrated in Figure 16, left.
Otherwise, n is even by the proposition. Define R0 := s0 s2 · · · sn−2 and R1 :=s1 s3 · · · sn−1 . Then select in Heap(w) the upper ideal isomorphic to the heap of24

RICCARDO BIAGIOLI, FRÉDÉRIC JOUHET, AND PHILIPPE NADEAU

Figure 16. Heaps of irreducible elements.
R R1− R R1− · · · Rδ R1−δ with the maximal number of factors, where , δ ∈ {0, 1}.
Two such examples are illustrated in Figure 16, middle and right, the one in the
middle (resp. right) having an odd (resp. even) number of such factors.
In each case, denote by H top the subset of selected elements and H bottom thecomplement in Heap(w).
Proposition 4.6. [8] Distinct irreducible elements belong to different right cells.
We will not prove this proposition which is arguably the crucial part of theargument in [8]. An immediate consequence is that each right cell contains precisely
one irreducible element.
To obtain Theorem 4.2, we need to relate irreducible elements to involutions.
One easily constructs an irreducible element from a FC involution by reducing it
repeatedly. It can be seen in this case that the process is reversible: given such anirreducible element with heap H, take the dual of H bottom and add it as an upper
ideal to H, as illustrated in Figure 17.

Figure 17. Heaps of FC involutions corresponding to irreducible elements.
Right cells with no involution are now easy to characterize: those are the ones
whose unique irreducible element has full support and a top part H top with an evennumber of factors R0 , R1 : see for example the right heap in Figure 16. Indeed theinverse process does not produce a FC heap in this case.
References[1] G. E. Andrews. The theory of partitions. Addison-Wesley Publishing Co., Reading, Mass.London-Amsterdam, 1976. Encyclopedia of Mathematics and its Applications, Vol. 2.
[2] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani. Some permutations with forbidden
subsequences and their inversion number. Discrete Math., 234(1-3):1–15, 2001.
[3] M. Barnabei, F. Bonetti, S. Elizalde, and M. Silimbani. Descent sets on 321-avoiding involutions and hook decompositions of partitions. To appear in J. Combin. Theory Ser. A,
preprint arXiv:1401.3011, 2014.
[4] R. Biagioli, F. Jouhet, and P. Nadeau. Fully commutative elements in finite and affine
Coxeter groups. To appear in Monatsh. Math., DOI 10.1007/s00605-014-0674-7, preprint
arXiv:1402.2166, 2014.

FULLY COMMUTATIVE INVOLUTIONS

25[5] S. C. Billey, W. Jockusch, and R. P. Stanley. Some combinatorial properties of Schubertpolynomials. J. Algebraic Combin., 2(4):345–374, 1993.
[6] A. Björner and F. Brenti. Combinatorics of Coxeter groups, volume 231 of Graduate Texts
in Mathematics. Springer, New York, 2005.
[7] C. K. Fan. A Hecke algebra quotient and properties of commutative elements of a Weyl group.
PhD thesis, M.I.T., 1995.
[8] C. K. Fan and R. M. Green. On the affine Temperley-Lieb algebras. J. London Math. Soc.
(2), 60(2):366–380, 1999.
[9] D. Foata. On the Netto inversion number of a sequence. Proc. Amer. Math. Soc., 19:236–240,
1968.
[10] J. Graham. Modular representations of Hecke algebras and related algebras. PhD thesis,
University of Sydney, 1995.
[11] R. M. Green. Combinatorics of minuscule representations. Cambridge Tracts in Mathematics.
Cambridge University Press, 2013.
[12] C. R. H. Hanusa and B. C. Jones. The enumeration of fully commutative affine permutations.
European J. Combin., 31(5):1342–1359, 2010.
[13] J. E. Humphreys. Reflection groups and Coxeter groups, volume 29 of Cambridge Studies inAdvanced Mathematics. Cambridge University Press, Cambridge, 1990.
[14] C. Krattenthaler. The theory of heaps and the Cartier Foata monoid. Appendix of the electronic edition of “Problèmes combinatoires de commutation et réarrangements”, 2006.
[15] P. A. MacMahon. Combinatory analysis. Vol. I, II (bound in one volume). Dover Phoenix
Editions. Dover Publications, Inc., Mineola, NY, 2004. Reprint of An introduction to combinatory analysis (1920) and Combinatory analysis. Vol. I, II (1915, 1916).
[16] V. Reiner. Signed permutation statistics. European J. Combin., 14(6):553–567, 1993.
[17] E. Steingrı́msson. Permutation statistics of indexed permutations. European J. Combin.,15(2):187–205, 1994.
[18] J. R. Stembridge. On the fully commutative elements of Coxeter groups. J. Algebraic Combin.,5(4):353–385, 1996.
[19] J. R. Stembridge. Some combinatorial aspects of reduced words in finite Coxeter groups.
Trans. Amer. Math. Soc., 349(4):1285–1332, 1997.
[20] J. R. Stembridge. The enumeration of fully commutative elements of Coxeter groups. J.
Algebraic Combin., 7(3):291–320, 1998.
[21] G. X. Viennot. Heaps of pieces. I. Basic definitions and combinatorial lemmas. In Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985), volume 1234 of Lecture Notes
in Math., pages 321–350. Springer, Berlin, 1986.
Institut Camille Jordan, Université Claude Bernard Lyon 1, 69622 Villeurbanne
Cedex, France
E-mail address: biagioli@math.univ-lyon1.fr
URL: http://math.univ-lyon1.fr/~biagioli
Institut Camille Jordan, Université Claude Bernard Lyon 1, 69622 Villeurbanne
Cedex, France
E-mail address: jouhet@math.univ-lyon1.fr
URL: http://math.univ-lyon1.fr/~jouhet
CNRS, Institut Camille Jordan, Université Claude Bernard Lyon 1, 69622 Villeurbanne Cedex, France
E-mail address: nadeau@math.univ-lyon1.fr
URL: http://math.univ-lyon1.fr/~nadeau