The Enumeration of Fully Commutative Elements of Coxeter Groups.
A Coxeter group element w is fully commutative if any reduced expression for w can be obtained from any other via the interchange of commuting generators. For example, in the symmetric group of degree n, the number of fully commutative elements is the nth Catalan number. The Coxeter groups with finitely many fully commutative elements can be arranged into seven infinite families A_n, B_n, D_n, E_n, F_n, H_n and I_2(m). For each family, we provide explicit generating functions for the number of fully commutative elements and the number of fully commutative involutions; in each case, the generating function is algebraic.
Introduction
A Coxeter group element w is said to be fully commutative if any reduced word for w
can be obtained from any other via the interchange of commuting generators. (More
explicit definitions will be given in Section 1 below.)
For example, in the symmetric group of degree n, the fully commutative elements are
the permutations with no decreasing subsequence of length 3, and they index a basis for
the Temperley-Lieb algebra. The number of such permutations is the nth Catalan number.
In [St1], we classified the irreducible Coxeter groups with finitely many fully commutative
elements. The result is seven infinite families of such groups; namely, An , Bn ,
Dn , En , Fn , Hn and I 2 (m). An equivalent classification was obtained independently by
Graham [G], and in the simply-laced case by Fan [F1]. In this paper, we consider the
problem of enumerating the fully commutative elements of these groups. The main result
(Theorem 2.6) is that for six of the seven infinite families (we omit the trivial dihedral
family I 2 (m)), the generating function for the number of fully commutative elements can
be expressed in terms of three simpler generating functions for certain formal languages
over an alphabet with at most four letters. The languages in question vary from family to
family, but have a uniform description. The resulting generating function one obtains for
each family is algebraic, although in some cases quite complicated. (See (3.7) and (3.11).)
In a general Coxeter group, the fully commutative elements index a basis for a natural
quotient of the corresponding Iwahori-Hecke algebra [G]. (See also [F1] for the simply-
laced case.) For An , this quotient is the Temperley-Lieb algebra. Recently, Fan [F2] has
shown that for types A, B, D, E and (in a sketched proof) F , this quotient is generically
semisimple, and gives recurrences for the dimensions of the irreducible representations.
the question of semisimplicity remains open.) This provides another possible
approach to computing the number of fully commutative elements in these cases; namely,
as the sum of the squares of the dimensions of these representations. Interestingly, Fan also
shows that the sum of these dimensions is the number of fully commutative involutions.
With the above motivation in mind, in Section 4 we consider the problem of enumerating
fully commutative involutions. In this case, we show (Theorem 4.3) that for the six
nontrivial families, the generating function can be expressed in terms of the generating
functions for the palindromic members of the formal languages that occur in the unrestricted
case. Again, each generating function is algebraic, and in some cases, the explicit
form is quite complicated. (See (4.8) and (4.10).)
In Section 5, we provide asymptotic formulas for both the number of fully commutative
elements and the number of fully commutative involutions in each family. In an appendix,
we provide tables of these numbers up through rank 12.
1. Full Commutativity
Throughout this paper, W shall denote a Coxeter group with (finite) generating set S,
Coxeter graph \Gamma, and Coxeter matrix standard reference is [H].
1.1 Words.
For any alphabet A, we use A   to denote the free monoid consisting of all finite-length
words A. The multiplication in A   is concatenation, and on
occasion will be denoted ' \Delta '. Thus (a; b)(b; a) subsequence
of a obtained by selecting terms from a set of consecutive positions is said to be a subword
or factor of a.
For each w 2 W , we define R(w) ae S   to be the set of reduced expressions for w; i.e.,
the set of minimum-length words  such that
For each integer m - 0 and s; t 2 S, we define
and let - denote the congruence on S   generated by the so-called braid relations; namely,
for all s; t 2 S such that m(s; t) ! 1.
It is well-known that for each w 2 W , R(w) consists of a single equivalence class relative
to -. That is, any reduced word for w can be obtained from any other by means of a
sequence of braid relations [B,xIV.1.5].
1.2 Commutativity classes.
Let - denote the congruence on S   generated by the interchange of commuting gener-
ators; i.e., (s; t) - (t; s) for all s; t 2 S such that m(s; 2. The equivalence classes of
this congruence will be referred to as commutativity classes.
Given the heap of s is the partial order of f1; obtained
from the transitive closure of the relations i OE j for all
3. It is easy to see that the isomorphism class of the heap is an invariant of
the commutativity class of s. In fact, although it is not needed here, it can be shown that
only if there is an isomorphism i 7! i 0 of the corresponding heap
orderings with s example, see Proposition 1.2 of [St1].)
In [St1], we defined w 2 W to be fully commutative if R(w) consists of a single commutativity
class; i.e., any reduced word for w can be obtained from any other solely by use of
the braid relations that correspond to commuting generators. It is not hard to show that
.
I (m)54
F
A

Figure

1: The irreducible FC-finite Coxeter groups.
this is equivalent to the property that for all s; t 2 S such that m(s; t) - 3, no member of
R(w) has hs; ti m as a subword, where
It will be convenient to let W FC denote the set of fully commutative members of W .
As mentioned in the introduction, the irreducible FC-finite Coxeter groups (i.e., Coxeter
groups with finitely many fully commutative elements) occur in seven infinite families
denoted An , Bn , Dn , En , Fn , Hn and I 2 (m). The Coxeter graphs of these groups are
displayed in Figure 1. It is interesting to note that there are no "exceptional" groups.
For the dihedral groups, the situation is quite simple. Only the longest element of I 2 (m)
fails to be fully commutative, leaving a total of 2m \Gamma 1 such elements.
Henceforth, we will be concerned only with the groups in the remaining six families.
1.3 Restriction.
For any word s 2 S   and any J ae S, let us define sj J to be the restriction of s to J ;
i.e., the subsequence formed by the terms of s that belong to J . Since the interchange of
adjacent commuting generators in s has either the same effect or no effect in sj J , it follows
that for any commutativity class C, the restriction of C to J is well-defined.
Figure

2: A simple branch.
A family F of subsets of S is complete if for all s 2 S there exists J 2 F such that
and for all s; t 2 S such that m(s; t) - 3 there exists J 2 F such that s; t 2 J .
Proposition 1.1. If F is a complete family of subsets of S, then for all s; s 0 2 S   , we
have
Proof. The necessity of the stated conditions is clear. For sufficiency, suppose that s is
the first term of s. Since s 2 J for some J 2 F , there must also be at least one occurrence
of s in s 0 . We claim that any term t that precedes the first s in s 0 must commute with s.
If not, then we would have sj fs;tg 6- s 0 j fs;tg , contradicting the fact that sj J - s 0 j J for some
J containing fs; tg. Thus we can replace s 0 with some s 00 - s 0 whose first term is s. If
we delete the initial s from s and s 00 , we obtain words that satisfy the same restriction
conditions as s and s 0 . Hence s - s 00 follows by induction with respect to length.
2. The Generic Case
Choose a distinguished generator s 1 2 S, and let denote the
infinite sequence of Coxeter groups in which W i is obtained from W i\Gamma1 by adding a new
generator s i such that m(s commutes with all other generators of W i\Gamma1 .
In the language of [St1], fs is said to form a simple branch in the graph of Wn .
For ng denote the generating set for Wn , and let \Gamma n denote
the corresponding Coxeter graph. (See Figure 2.) It will be convenient also to let S 0 and
denote the corresponding data for the Coxeter group W 0 obtained when s 1 is deleted
from S. Thus
2.1 Spines, branches, and centers.
For any w 2 W FC
n , we define the spine of w, denoted oe(w), to be the pair (l; A), where l
denotes the number of occurrences of s 1 in some (equivalently, every) reduced word for w,
and A is the subset of defined by the property that k 2 A iff there is no
occurrence of s 2 between the kth and (k 1)th occurrences of s 1 in some (equivalently,
reduced word for w. We refer to l as the length of the spine.
Continuing the hypothesis that w is fully commutative, for J ' Sn we let wj J denote
the commutativity class of sj J for any reduced word s 2 R(w). (It follows from the

Figure

3: An F 7 -heap. Figure 4: Center and branch.
discussion in Section 1.3 that this commutativity class is well-defined.) In particular, for
each w 2 W FC
n , we associate the pair
(wj Sn \GammaS
We refer to wj Sn \GammaS 0
and wj S1 as the branch and central portions of w, respectively.
For example, consider the Coxeter group F 7 . We label its generators fu; t; s
in the order they appear in Figure 1, so that fs is a simple branch. The heap of
a typical fully commutative member of F 7 is displayed in Figure 3. Its spine is (5; f1; 4g),
and the heaps of its central and branch portions are displayed in Figure 4.
"branch set") to be the set of all commutativity classes B over the
ng such that
a subword of some member of B, then
a subword of some member of B, then
Furthermore, given a spine oe = (l; A), we define Bn (oe) to be the set of commutativity
Bn such that there are l occurrences of s 1 in every member of B, and
(B3) The kth and (k 1)th occurrences of s 1 occur consecutively in some member of B
if and only if k 2 A.
We claim (see the lemma below) that Bn (oe) contains the branch portions of every fully
commutative w 2 Wn with spine oe. Note also that Bn depends only on n, not W .
Similarly, let us define "central set") to be the set of commutativity classes
C over the alphabet S
(C1) For all s 2 S 1 , no member of C has (s; s) as a subword.
(C2) If hs; ti m is a subword of some member of C, where
occurs at least twice in this subword. (In particular, s
In addition, we say that compatible with the spine every member
of C has l occurrences of s 1 , and
is a subword of some member of C, where
subword includes the kth and (k 1)th occurrences of s 1 for some k 62 A.
denote the set of oe-compatible members of C. We claim (again, see the
lemma below) that C(oe) contains the central portions of every w 2 W FC
n with spine oe.
Note also that C(oe) depends only on (more precisely, on the Coxeter graph \Gamma),
not the length of the branch attached to it.
Lemma 2.1. The mapping w 7! (wj Sn \GammaS defines a bijection
oe
Bn (oe) \Theta CW (oe):
Proof. For all non-commuting pairs s; t 2 Sn , we have fs; tg
so by Proposition 1.1, the commutativity class of any w 2 W FC
(and hence w itself) is
uniquely determined by wj Sn \GammaS 0
and wj S1 . Thus the map is injective.
Now choose an arbitrary fully commutative w 2 Wn with spine
. The defining properties of the spine immediately imply the
validity of (B3). Since consecutive occurrences of any s 2 Sn do not arise in any s 2 R(w),
it follows that for all k - 1, the kth and (k 1)th occurrences of s in s must be separated
by some t 2 Sn such that m(s; t) - 3. For the only possibilities for t
are in Sn holds. For s 2 S 0 , the only possibilities for t are in S 1 , so (C1)
could fail only if some k, the only elements separating the kth and (k +1)th
occurrences of s 1 in s that do not commute with s 1 are one or more occurrences of s 2 . In
that case, we could choose a reduced word for w so that the subword running from the kth
to the (k +1)th occurrences of s 1 forms a reduced word for a fully commutative element of
the parabolic subgroup isomorphic to An generated by fs g. However, it is easy to
show (e.g., Lemma 4.2 of [St1]) that every reduced word for a fully commutative member
of An has at most one occurrence of each "end node" generator. Thus (C1) holds.
Concerning (B2), (C2) and (C3), suppose that (s occurs as a subword of some
member of the commutativity class B. If i ? 1, then every s 2 Sn that does not commute
with s i belongs to Sn \Gamma S 0 . Hence, some reduced word for w must also contain the subword
contradicting the fact that w is fully commutative. Thus (B2) holds. Similarly,
if we suppose that hs; ti m occurs as a subword of some member of C, where
and s; t 2 S 1 , then again we contradict the hypothesis that w is fully commutative unless
is the only member of S 1 that may not commute with some
member of Sn In either case, since hs; ti m cannot be a subword of any s 2 R(w),
it follows that s 1 occurs at least twice in hs; ti m (proving (C2)), and between two such
occurrences of s 1 , say the kth and (k + 1)th, there must be an occurrence of s 2 in s. By
definition, this means k 62 A, so (C3) holds. Thus B 2 Bn (oe) and C 2 CW (oe).
Finally, it remains to be shown that the map is surjective. For this, let be a
spine, and choose commutativity classes B 2 Bn (oe) and C 2 CW (oe). Select representatives
is a singleton,
and this singleton appears the same number of times in s B and s C (namely, l times), it
follows that there is a word s 2 S
whose restrictions to Sn \Gamma S 0 and S 1 are s B and s C ,
respectively. We claim that s is a reduced word for some w 2 W FC
n , and hence w 7! (B; C).
To prove the claim, first consider the possibility that for some s 2 Sn , (s; s) occurs as
a subword of some member of the commutativity class of s. In that case, depending on
whether s 2 S 1 , the same would be true of either B or C, contradicting (B1) or (C1).
Next consider the possibility that hs; ti m occurs as a subword of some word s 0 in the
commutativity class of s, where 3. We must have either s; t 2 Sn \Gamma S 0 or
hence the same subword appears in some member of B or C, respectively.
In the former case, (B2) requires that 3. However the restriction of s 0
to S 1 would then have consecutive occurrences of s 1 , contradicting (C1). In the latter
case, (C2) and (C3) require that s t, and that the subword hs; ti m includes
the kth and (k 1)th occurrences of s 1 in s 0 for some k 62 A. It follows that s 2 does not
occur between these two instances of s 1 in s 0 , and thus they appear consecutively in the
restriction of s 0 to Sn \Gamma S 0 , contradicting (B3). Hence the claim follows.
The above lemma splits the enumeration of the fully commutative parts of the Coxeter
groups into two subproblems. The first subproblem, which is universal
for all Coxeter groups, is to determine the number of branch commutativity classes with
spine oe; i.e., the cardinality of Bn (oe) for all integers n - 0 and all oe. The second subprob-
lem, which needs only to be done once for each series Wn , is to determine the number of
central commutativity classes with spine oe; i.e., the cardinality of CW (oe).
s
A
ss
s

Figure

5.
2.2 Spinal analysis.
The possible spines that arise in the FC-finite Coxeter groups are severely limited. To
make this claim more precise, suppose that is one of the six nontrivial
families of FC-finite Coxeter groups (i.e., A, B, D, E, F , or H). The Coxeter graph of W
can then be chosen from one of the six in Figure 5. For convenience, we have used s as
the label for the distinguished generator previously denoted s 1 .
Lemma 2.2. If C 2 CW is compatible with the spine is one of the
Coxeter groups in Figure 5, then A ' f1; l \Gamma 1g.
Proof. Let s 2 S   be a representative of C, and towards a contradiction, let us suppose
that A includes some k such that 1. Note that it follows that the kth and
1)th occurrences of s in s are neither the first nor the last such occurrences.
For the H-graph, property (C1) implies that the occurrences of s and t alternate in s.
Hence, the kth and (k 1)th occurrences of s appear in the middle of a subword of the
form (s; t; s; t; s; t; s). In particular, these two occurrences of s participate in a subword of
s of the form (t; s; t; s; contradicting (C3).
For the F -graph, property (C1) implies that any two occurrences of s must be separated
by at least one t. On the other hand, the subword between two occurrences of s must be
a reduced word for some fully commutative member of the subgroup generated by ft; ug
(property (C2)), so the occurrences of s and t must alternate, and in the restriction of
s to fs; tg, the kth and (k 1)th occurrences of s appear in the middle of a subword of
the form (s; t; s; t; s; t; s). By (C3), these two occurrences of s cannot participate in an
occurrence of (t; s; t; s) or (s; t; s; t) in s. Hence, the two occurrences of t surrounding the
occurrence of s must be separated by an occurrence of u.
However in that case, (u; t; u) is a subword of some member of the commutativity class
of s, contradicting (C2).
For the E-graph, at least one of t and t 0 must appear between any two occurrences
of s (otherwise (C1) is violated), and both t and t 0 must appear between the kth and
1)th occurrences of s, by (C2). On the other hand, property (C3) also implies that
the subword (strictly) between the 2)th occurrences of s in s must be
a reduced word for some fully commutative member of W , a Coxeter group isomorphic
to A 4 . In particular, this implies that t 0 can appear at most once, and t at most twice, in
this subword. Since we have already accounted for at least four occurrences of t and t 0 ,
we have a contradiction.
This completes the proof, since the remaining three graphs are subgraphs of the preceding
ones.
2.3 Branch enumeration.
The previous lemma shows that for the FC-finite Coxeter groups, we need to solve the
branch enumeration problem (i.e., determine the cardinality of Bn (oe)) only for the spines
1g. For this, we first introduce the notation
for the number of (n+ sequences. That is, B n;l is the number of orderings of
votes for two candidates so that the winning candidate never trails the losing candidate,
with the final tally being n l votes to n \Gamma l votes. (For example, see [C, x1.8].) This
quantity is also the number of standard Young tableaux of shape (n
Lemma 2.3. For integers n; l - 0, we have
Proof. For
n;l denote the cardinality of Bn (oe) for
respectively. In the case oe = (l; ?), the defining properties (B1) and (B3)
for membership of B in Bn (oe) can be replaced with
member of B has (s
It follows that for 1 l, the kth and (k 1)th occurrence of s 1 in any member of B
must be separated by exactly one s 2 , and the total number of occurrences of s 2 must be
according to whether the first and last occurrences of s 1 are preceded (resp.,
followed) by an s 2 . Furthermore, the restriction of B to fs ng is a commutativity
class with no subwords of the form (s possibly
shifting indices (i i), we thus obtain any one of the members of
l 0 denotes the number of occurrences of s 2 . Accounting for the four possible ways that s 1
and s 2 can be interlaced (or two, if l = 0), we obtain the recurrence
n\Gamma1;l +B (0)
On the other hand, it is easy to show that B n;l satisfies the same recurrence and initial
. (In fact, one can obtain a bijection with ballot sequences by
noting that the terms of the recurrence correspond to specifying the last two votes.)
By word reversal, the cases corresponding to are clearly
equivalent, so we restrict our attention to the former. Properties (B1) and (B3) imply
that the restriction of any B in Bn (oe) to fs must then take the form
where each ' ' represents an optional occurrence of s 2 . We declare the left side of B to be
open if the above restriction has the form (s there is no s 3 separating
the first two occurrences of s 2 . Otherwise, the left side is closed.
Case I. The left side is open. In this case, if we restrict B to fs (and shift
indices), we obtain any one of the members of according
to whether there is an occurrence of s 2 following the last s 1 . (If l = 2, then there is no
choice: l is the only possibility.)
Case II. The left side is closed. In this case, if we delete the first occurrence of s 1
from B, we obtain any one of the commutativity classes in Bn (l \Gamma
The above analysis yields the recurrence
2:
It is easy to verify that the claimed formula for B (1)
n;l satisfies the same recurrence and the
proper initial conditions.
For the restriction of any B in Bn (oe) to fs takes the form
where again each ' ' represents an optional occurrence of s 2 . In the special case l = 3,
this becomes deleting one of the occurrences of s 1 , we obtain any one
of the commutativity classes in Bn (2; f1g).
Assuming l - 4, we now have not only the possibility that the left side of B is open (as
in the case but the right side may be open as well, mutatis mutandis.
Case I. The left and right sides of B are both open. In this case, if we restrict B to
ng (and shift indices), we obtain any one of the members of
Case II. Exactly one of the left or right sides of B is open. Assuming it is the left
side that is open, if we restrict B to fs ng (and shift indices), we obtain any one of
the members of according to whether there is an
occurrence of s 2 following the last s 1 .
Case III. The left and right sides of B are both closed. In this case, if we delete the
first and last s 1 from B, we obtain any one of the members of Bn (l \Gamma 2; ?).
The above analysis yields B (2)
n;2 and the recurrence
for Once again, it is routine to verify that the claimed formula for B (2)
n;l satisfies the
same recurrence and initial conditions.
Remark 2.4. The union of Bn (l; ?) for all l - 0 is the set of commutativity classes
corresponding to the fully commutative members of the Coxeter group Bn whose reduced
words do not contain the subword In the language of [St2], these are the "fully
commutative top elements" of Bn ; in the language of [F1], these are the "commutative
elements" of the Weyl group Cn .
Let R(x) denote the generating series for the Catalan numbers. That is,
Note that xR(x) 1. The following is a standard application of the Lagrange
of [GJ]). We include below a combinatorial proof.
Lemma 2.5. We have
Proof. A ballot sequence in which A defeats B by 2l votes can be factored uniquely
by cutting the sequence after the last moment when candidate B trails
by i votes, 1. The first part consists of a ballot sequence for a tie vote,
and all remaining parts begin with a vote for A, followed by a ballot sequence for a tie.
After deleting the 2l votes for A at the beginnings of these parts, we obtain an ordered
1)-tuple of ballot sequences for ties, for which the generating series is R(x) 2l+1 .
2.4 The generic generating function.
To enumerate the fully commutative elements of the family
remains is the "central" enumeration problem; i.e., determining the cardinalities of CW (oe)
for all spines oe of the form described in Lemma 2.2. Setting aside the details of this
problem until Section 3, let us define
and let C i denote the generating series defined by
l-0
l-3
l-3
Although these quantities depend on W , we prefer to leave this dependence implicit.
Theorem 2.6. If W is one of the six Coxeter groups displayed in Figure 5, we have
Proof. Successive applications of Lemmas 2.1, 2.2, and 2.3 yield
oe
l-0
l-3
l-3
n;l
l-0
l-3
c l;1
l-3
c l;2
Using Lemma 2.5 to simplify the corresponding generating function, 1 we obtain
l-0
l-3
c l;1
l-3
c l;2
It should be noted that when \Gamma1, the coefficient of c l;2
in (2.1) is zero. Thus the range of
summation for this portion of the generating function can be extended to n - \Gamma1.
Bearing in mind that R(x) is routine to verify that this agrees with
the claimed expression.
Remark 2.7. As we shall see in the next section, for each series Wn the generating
functions C i (x) are rational, so the above result implies that the generating series for
belongs to the algebraic function field
3. Enumerating the Central Parts
In this section, we determine the cardinalities of the central sets for each
of the six Coxeter groups W displayed in Figure 5. (The reader may wish to review the
labeling of the generators in these cases, and recall that the distinguished generator s 1
has been given the alias s.) We subsequently apply Theorem 2.6, obtaining the generating
function for the number of fully commutative elements in Wn .
3.1 The A-series.
In this case, s is a singleton generator, so there is only one commutativity class of each
length. It follows easily from the defining properties that the only central commutativity
classes are those of (s) and ( ) (the empty word). These are compatible only with the
spines respectively. Thus we have
and Theorem 2.6 implies
Extracting the coefficient of x n , we obtain
a result first proved in [BJS, x2].
3.2 The B-series.
In this case, we have and the defining properties imply that the central
commutativity classes are singletons in which the occurrences of s and t alternate. It
follows that c l;0 is simply the number of alternating fs; tg-words in which s occurs l times;
namely, 4 (if l ? Also, the only alternating fs; tg-word that is compatible
with a spine (l; A) with A 6= ? is (s; t; s), which is compatible with (2; f1g). Thus we have
4x
After some simplifications, Theorem 2.6 yields
Extracting the coefficient of x
a result first proved in [St2,x5].
3.3 The D-series.
In this case, a set of representatives for the central commutativity classes consist of the
subwords of (s; t; s; t
Of these, only (s; t; t compatible with a spine (l; A) with A 6= ?; the remainder are
compatible only with (l; ?) for some l. Among the subwords of (s; t; s; t
number with l occurrences of s is 8 (if l - 2), 7 (if l = 1), or 3 (if l = 0). Thus we have
and after some simplifications, Theorem 2.6 implies
Extracting the coefficient of x n\Gamma2 , we obtain
a result obtained previously in [F1] and [St2,x10].
3.4 The H-series.
As in the B-series, the central commutativity classes are the singletons formed by each
of the alternating fs; tg-words. In particular, the value of C 0 (x) is identical to its B-series
version. The words that are compatible with spines of the form (l; f1g) are those that
begin with s (and have at least two occurrences of s), and (t; s; t; s); thus c
3. The words compatible with spines of the form f1; l \Gamma 1g are those
that both begin and end with s and have at least four occurrences of s; i.e., c
4. Thus we have
After some simplifications, Theorem 2.6 yields
Extracting the coefficient of x
3: (3.4)
3.5 The F -series.
In this case, we can select a canonical representative s 2 S   from each central commutativity
class by insisting that whenever s and u are adjacent in s, u precedes s. Any such
word has a unique factorization l each being
words consisting of an initial s followed by a ft; ug-word. In fact, given our conventions,
we must have
with allowed only if We also cannot have (s; t; u) preceded by (u), (t; u),
or (s; t; u); otherwise, some member of the commutativity class of s contains the forbidden
subword (u; t; u). Conversely, any word meeting these specifications is the canonical
representative of some central commutativity class. The language formed by these words
therefore consists of
together with the exceptional cases f(u); (t; u); (u; s); (t; u; s)g. Hence
Turning now to C 1 (x), note that the central commutativity classes that are compatible
with a spine of the form (l; f1g) are those for which the first two occurrences of s do not
participate in an occurrence of the subwords (s; t; s; t), or (t; s; t; s). If s occurs three or
more times, this requires ( ) to be the first factor in (3.5), followed by an occurrence of
(s; t; u; s; t). Hence, the canonical representatives compatible with (l; f1g) consist of
and four additional cases with l = 2: f(s; t; s); (u; s; t; s); (s; t; s; u); (t; u; s; t; s)g. It follows
that c
l-3
c l;1 x
To determine C 2 (x), note first that (s; t; u; s; t; s) is the unique canonical representative
compatible with the spine (3; f1; 2g). For the spines (l; f1; l \Gamma 1g) with l - 4, compatibility
requires (s) to be the last factor in (3.6), and it must be preceded by (s; t; u; s; t). Hence
l-3
c l;2 x
After simplifying the generating function provided by Theorem 2.6, we obtain
While it is unlikely that there is a simple closed formula for
is interesting to note
that the Fibonacci numbers f n satisfy
f 2n x
f 3n x
so when the coefficient of x n\Gamma2 is extracted in (3.7), we obtain
3.6 The E-series.
We claim that there is a unique member of each central commutativity class (in fact,
any commutativity class in S   ) with the property that (s; u), do not occur
as subwords. To see this, note first that the set of left members of these pairs is disjoint
from the set of right members. Secondly, these pairs are precisely the set of commuting
generators of W . Hence, for any pair of words that differ by the interchange of two
adjacent commuting generators, one member of the pair can be viewed as a "reduction"
of the other, in the sense that the set of positions where u and t occur are farther to
the left. Furthermore, since the set of instances of the forbidden pairs in any given word
are pairwise disjoint, it follows by induction that any sequence of reductions eventually
terminates with the same word, proving the claim.
Let L denote the formal language over the alphabet S formed by the canonical representatives
(in the sense defined above) of the central commutativity classes. Given any formal
language K over S, we will write K(x) for the generating function obtained by assigning
the weight x l to each s 2 K for which s occurs l times. Note that by this convention, we
have
Any word s 2 S   has a unique factorization
l each being words consisting of an initial s followed by a ft; t 0 ; ug-word. For
membership in L, every subword of s not containing s must be a member of
the set of canonical representative for the fully commutative members of the subgroup
generated by ft; t 0 ; ug. When s is prepended to these words, only six remain canonical:
Thus we have
For each e 2 E, let L e
denote the set of s 2 L for which the initial factor s 0 is e. If
or deletion of the initial s in s yields a member
of L e
for some e 2 f(t); (t; conversely. In terms of generating
functions, we have
Similarly, deletion of s from the second position defines a bijection from L (u) \Gamma f(u); (u; s)g
to so we have
Combining these two decompositions, we obtain
Now consider the language and the refinements K i
consisting of those nonvoid members of K whose initial factor is a i . Since the result of
appending a to any s 2 L remains in L if and only if s does not already end in s,
it follows that L ( g. Similarly, we have
so (3.8) can be rewritten in the form
For the commutativity classes of
a 2 a 3 ; a 3 a 4 a 3 ; a i a
each have representatives in which one or more of the subwords (t; s;
and (t; u; t) appear, and hence cannot be central. Conversely, as a subset of fa
membership in K is characterized by avoidance of the subwords listed above. It follows
that K
Solving this recursive description of the languages K i (essentially a computation in the
ring of formal power series in noncommuting variables a
a 4 a 3 ; a 2 a 4 a 3 a 4 g   \Delta f( ); a 2 ; a 2 a 4 a 3 a 5 g. Thus
and hence (3.9) implies
The central commutativity classes compatible with spines of the form (l; f1g) are those
for which the first two occurrences of s do not participate in an occurrence of the subwords
These correspond to the members of L for which the first occurrence
of one of the factors a i is either a 5 or a 6 , followed by at least one more occurrence of
. If a 5 is the first factor, the possibilities are limited to f( ); (u); (t; u)ga 5 a 1 ,
since a 5 can be followed only by a 1 . If the first factor is a 6 , then the choices consist of
the members of K 6 f( ); a 1 g other than a 6 , since no nonvoid member of E can precede a 6 .
Hence, the language of canonical representatives compatible with the spines (l; f1g) is
In particular, (s; t; t are the
members compatible with the spine (2; f1g), so c 5. Hence, using the decomposition
of K 6 determined above, we obtain
The canonical representatives of the central commutativity classes compatible with
spines of the form (l; must have a factorization in which there are at least three
occurrences of the words a i , the first and penultimate of these being a 5 or a 6 . Since a 6
cannot be preceded by any of the factors a i , a 5 must be the penultimate factor. Since
a 5 can be followed only by a 1 , the first factor must therefore be a 6 , there is no non-void
member of E preceding a 6 , and the last factor must be a 1 . From the above decompositions
of K 6 and K
that the language formed by the members of L that start with
a 6 and terminate with a 5 a 1 is
a 6 \Delta fa 2 a 4 ; a 2 a 4 a 3 ; a 2 a 4 a 3 a 4 g   \Delta a 2 a 4 a 3 a 5 a
and therefore
Combining our expressions for C i the generating function provided by
Theorem 2.6 can be simplified to the form
4. Fully Commutative Involutions
We will say that a commutativity class C is palindromic if it includes the reverse of
some (equivalently, all) of its members. A fully commutative w 2 W is an involution if
and only if R(w) is palindromic.
In the following, we will adopt the convention that if X is a set of commutativity classes,
then -
X denotes the set of palindromic members of X. Similarly, -
W and -
W FC shall denote
the set of involutions in W and W FC , respectively.
4.1 The generic generating function.
Consider the enumeration of fully commutative involutions in a series of Coxeter groups
of the type considered in Section 2. It is clear that w 2 W FC
n is an involution
if and only if its branch and central portions are palindromic. Thus by Lemma 2.1,
determining the cardinality of W FC
n can be split into two subproblems: enumerating -
Bn (oe)
(the palindromic branch classes) and -
CW (oe) (the palindromic central classes).
For integers n; l - 0, we define -
e.
Lemma 4.1. We have
Bn (l; ?)
Bn (l; f1g)
Proof. Following the proof of Lemma 2.3, for
n;l denote the cardinality
of -
Bn (oe) for respectively. Recall that the occurrences
of s 1 and s 2 must be interlaced in any representative of B 2 Bn (l; ?), and that when we
restrict B to fs ng (and shift indices), we obtain a member of
denotes the number of occurrences of s 2 . To be palindromic, it is therefore necessary and
sufficient that the fs ng-restriction of B is palindromic, and that l
(or 0, if l = 0). This yields the recurrence
It is easy to verify that -
satisfies the same recurrence and initial conditions.
For spines of the form oe = (l; f1g), it is clear that there can be no palindromic classes
since for l ? 2, there must be an occurrence of s 2 between the last two
occurrences of s 1 , but not for the first two. Assuming l = 2, the bijection provided in the
proof of Lemma 2.3 preserves palindromicity, and thus proves the recurrence
It is routine to check that the claimed formula for -
n;2 satisfies the same recurrence and
initial conditions.
For the left and right sides of any palindromic B 2 Bn (oe) must be
both open or both closed, in the sense defined in the proof of Lemma 2.3. Furthermore, a
branch class with this property is palindromic if and only if its restriction to fs ng
is palindromic, so the bijection provided in Lemma 2.3 for this case yields
and -
n;2 . Once again, it is routine to check that the claimed formula for -
n;l
satisfies the same recurrence and initial conditions.
Lemma 4.2. We have
Proof. We have
We can interpret F l;j (x) as the generating function for sequences of votes in an election
in which A defeats B by l votes. Such sequences can be uniquely factored by cutting
the sequence after the last moment when B trails A by i votes, 1. The
first factor consists of an arbitrary sequence for a tie vote, which has generating function
1=
and the remaining l factors each consist of a vote for A, followed by a
"ballot sequence" for a tie vote (cf. Section 2.3), which has generating function xR(x 2 ).
Turning now to the palindromic central commutativity classes, let us define
and associated generating functions
l-0
l-3
Theorem 4.3. If W is one of the Coxeter groups displayed in Figure 5, then
Proof. As noted previously, w 2 W FC is an involution if and only if the central and
branch portions of w are palindromic. Successive applications of Lemmas 2.1, 2.2, and 4.1
therefore yield
oe
Bn (oe)
l-0
l-3
n;l
l-0
l-3
The corresponding generating function thus takes the form
l-0
l-3
-c l;2
using Lemma 4.2.
As we shall see below, both -
are rational, so the generating series for
belongs to the algebraic function field Q(x; R(x 2
4.2 The A-series.
In this case, we have -
since there are only two central
commutativity classes (namely, those of ( ) and (s)), and both are palindromic. Hence
A FC
Either by extracting the coefficient of x n , or more directly from (4.1), we obtain
A FC
4.3 The B-series.
In this case, the central commutativity classes are singletons in which the occurrences
of s and t alternate. For each l - 0, there are two such words that are palindromic and
have l occurrences of s. Among these, (s; t; s) is the only one that is compatible with a
spine (l; A) with A 6= ?. Hence -
Theorem 4.3 implies
Extracting the coefficient of x
dn=2e
4.4 The D-series.
In this case, the palindromic central classes are represented by the odd-length subwords
of (s; t; s; t middle term is t or t 0 , together with ( ), (s), (t; t 0 ), and
In particular, leaving aside (s; t; t there are exactly four such words with l
occurrences of s for each even l - 0, so we have
Also -
is the only representative compatible with a spine of
the form (l; with A 6= ?. After simplifying the expression in Theorem 4.3, we obtain
Extracting the coefficient of x n\Gamma2 yields
(n+1)=2
4.5 The H-series.
The palindromic central classes in this case are the same as those for the B-series; the
only difference is that those corresponding to hs; ti 7 are now compatible with
spines of the form (l; f1; l \Gamma 1g) for l - 4. Thus we have
The generating function provided by Theorem 4.3 is therefore
and hence fi fi -
4.6 The F -series.
Recall that in Section 3.5, we selected a set of canonical representatives for the central
commutativity classes by forbidding the subword (s; u). If s is one such representative,
let s   denote the canonical representative obtained by reversing s and then reversing each
offending (s; u)-subword.
If s is the canonical representative of a palindromic class (i.e.,
else s has a unique factorization fitting one of the forms
a
where a is itself a canonical representative for some central commutativity class. Con-
versely, any canonical representative ending in (s) can be uniquely factored into one of
the two forms a \Delta (s) or a \Delta (u; s), and the corresponding word obtained by appending a
remains central. Similarly, any canonical representative ending with (t) but not (u; t) or
factored into the form a \Delta (t), remains central when a   is appended.
Now from (3.5), the language of canonical representatives ending in (s) consists of the
exceptional set f(u; s); (t; u; s)g, together with
and the language of representatives ending with (t) but not (u; t) or (u; s; t) is
Including the exceptional cases ( ) and (s), this yields
The unique palindromic classes compatible with the spines (2; f1g) and (3; f1; 2g) are
represented by (s; t; s) and (s; t; u; s; t; s). For the spines
recall from Section 3.5 that a canonical representative compatible with oe must begin with
(s; t; u; s; t) and end with (t; u; s; t; s). Selecting the portions of (4.6) and (4.7) that begin
with (s; t; u; s; t) yields the languages
so we have
Simplification of the generating series provided by Theorem 4.3 yields
F FC
The coefficients can be expressed in terms of the Fibonacci numbers as follows:
F FC
F FC
4.7 The E-series.
In Section 3.6, we selected a canonical representative s for each central commutativity
class. As in the previous section, we let s   denote the canonical representative for the
commutativity class of the reverse of s.
If s 2 S   is a representative of any palindromic commutativity class, then the set of
generators appearing an odd number of times in s must commute pairwise. Indeed, the
"middle" occurrence of one generator would otherwise precede the "middle" occurrence
of some other generator in every member of the commutativity class. Aside from the
exceptional cases ( ), (u), and (which cannot be followed and preceded by the same
member of S and remain central), it follows that every central palindromic class has a
unique representative fitting one of the forms
a   (t) a; a
where a is the canonical representative of some central commutativity class. However,
we cannot assert that the above representatives are themselves canonical; for example,
if then a   (u; t 0 ) a is a representative of a central palindromic class, but the
canonical representative of this class is (t; u; s; t
For the representatives whose middle factor is
s must be the first term of a, assuming that a is nonvoid. Furthermore, if we prepend
an initial s (or s; t, in the case of (u; t 0 )), the resulting words (s; t) a, (s;
and (s; t; u; t 0 ) a are (in the notation of Section 3.6) members of the formal languages
respectively. Conversely, any member
of these languages arises in this fashion.
For a representative whose middle factor is (u; s), if we prepend (s; t; t 0 ) to (u; s) a,
we obtain a member of a central commutativity class whose canonical representative is
hence a member of K 6 f(); (s)g. Conversely, any member of K 6 f(); (s)g
other than a way.
Collecting the contributions of the five types of palindromic central classes, along with
the exceptional cases f( ); (u); (s)g, we obtain
For the spine there is a unique oe-compatible central class that is palin-
dromic; namely, the class of (s; t; t 0 ; s). For the spines oe of the form (l; f1; l \Gamma 1g), recall
from (3.10) that the canonical representatives of the oe-compatible classes all begin with
a 6 a 2 a 4 and end with a 3 a 5 a 1 . It follows that for a palindromic central class represented
by a word of the form (4.9) to be compatible with oe, it is necessary and sufficient that a
end with a 3 a 5 a 1 . Using the decompositions obtained in Section 3.6, we find that
a 4 a 3 ; a 2 a 4 a 3 a 4 g   \Delta a 2 a 4 a 3 a 5 ;
a 4 a 3 ; a 2 a 4 a 3 a 4 g   \Delta a 2 a 4 a 3 a 5 ;
a 6 \Delta fa 2 a 4 ; a 2 a 4 a 3 ; a 2 a 4 a 3 a 4 g   \Delta a 2 a 4 a 3 a 5
are the respective portions of K 2 , K 4 , and K 6 that end with a 3 a 5 ; there are no such words
in K 5 . It follows that
The generating function provided by Theorem 4.3 can be simplified to the form
5. Asymptotics
Given the lack of simple expressions for the number of fully commutative members of
En and Fn , it is natural to consider asymptotic formulas.
Theorem 5.1. We have
(a)
1:466 is the real root of x
(b)
1:618 is the largest root of x
Proof. Consider the generating function
Theorem 2.6.
In the case of Fn , we see from (3.7) that the singularities of G(x) consist of a branch cut
at together with simple poles at and the zeroes of
. The latter are (respectively) f1=fl; \Gammafl g,
5)=2 denotes the golden ratio. The smallest of these (in absolute value)
is
0:236, a zero of In particular, since 1=fl 3 ! 1=4, the asymptotic
behavior of
fi fi is governed by the local behavior of G(x) at specifically,
since there is a simple pole at
using (3.7), together with the relations
In the case of En , we see from (3.11) that the singularities of G(x) consist of a branch
cut at together with simple poles at and the zeroes of
These polynomials are related by the fact
that if ff is any zero of is the minimal polynomial of
is the minimal polynomial of ff=(1+ ff) 2 . (The fact that
such a simple relationship exists is not coincidental; see Remark 5.3 below.) The smallest
of the nine zeroes of these polynomials (in absolute value) is
0:682 is the real zero of Equivalently, we have
1=ff is the real root of x 1=4, the asymptotic behavior of
is once again governed by the local behavior of G(x) near a simple pole. In this case, we
obtain
using (3.11) and the fact that
Remark 5.2. For the sake of completeness, it is natural also to consider the asymptotic
number of fully commutative elements in An , Bn , Dn , and Hn . Given the explicit formulas
(3.1), (3.2), (3.3), and (3.4), it is easily established that
using Stirling's formula. In each of these cases, the dominant singularity in the corresponding
generating function is the branch cut at
Remark 5.3. If ff is a pole of f(x), then ff=(1 + ff) is a pole of f(x=(1 \Gamma x)) and
ff=(1+ff) 2 is a pole (of some branch) of f(R(x) \Gamma 1). On the other hand, from Theorem 2.6,
we see that aside from the branch cut at a pole at the singularities
of
are limited to those of C 2 (x), C
Thus, unless there is unexpected cancellation, for each pole ff
of C 2 (x), there will be a triple of poles at ff=(1 in G(x).
Now consider the asymptotic enumeration of fully commutative involutions. Again,
given the explicit formulas (4.2), (4.3), (4.4), and (4.5), it is routine to show that
A FC
In the following, fi and fl retain their meanings from Theorem 5.1.
Theorem 5.4. We have
(a)
(b)
(c)
F FC
(d)
F FC
Proof. Consider the generating series -
Theorem 4.3.
In the case of Fn , we see from (4.8) that the singularities of -
G(x) consist of branch cuts
at together with simple poles at (the zeroes of
(the zeroes of In absolute value, the
smallest of these occur at that the asymptotic
behavior of
F FC
fi fi is determined by the local behavior of -
G(x) at
specifically, we have
F FC
F FC
Using (4.8) and the fact that Q(fl \Gamma3=2
and a similar calculation (details omitted) yields
In the case of En , we see from (4.10) that the singularities of -
G(x) consist of branch
cuts at together with simple poles at
and the square roots of
the zeroes of Continuing the notation from the
proof of Theorem 5.1, the poles occurring closest to the origin are at
2). Thus we have
Using (4.10) and the fact that Q(ffi 1=2
and a similar calculation can be used to determine c \Gamma ; we omit the details.


Appendix


An Bn Dn En Fn Hn
9 16796 53481 29171 44199 153584 182720

Table

1: The number of fully commutative elements. 2
An Bn Dn En Fn Hn
9 252 637 381 443 968 1014

Table

2: The number of fully commutative involutions.
2 The parenthetical entries correspond to cases in which the group in question is either reducible or
isomorphic to a group listed elsewhere.



--R

Some combinatorial properties of Schubert polynomials
"Groupes et Alg'ebres de Lie, Chp. IV-VI,"
"Advanced Combinatorics,"
"A Hecke Algebra Quotient and Properties of Commutative Elements of a Weyl Group,"
Structure of a Hecke algebra quotient
"Combinatorial Enumeration,"
"Modular Representations of Hecke Algebras and Related Algebras,"
"Reflection Groups and Coxeter Groups,"
On the fully commutative elements of Coxeter groups
Some combinatorial aspects of reduced words in finite Coxeter groups
--TR

--CTR
Sara C. Billey , Gregory S. Warrington, Kazhdan-Lusztig Polynomials for 321-Hexagon-Avoiding Permutations, Journal of Algebraic Combinatorics: An International Journal, v.13 n.2, p.111-136, March 2001
coxeter group;braid relation;reduced word