# The enumeration of fully commutative affine permutations

Christopher R. H. Hanusa<fnref n="1" />†and Brant C. Jones<fnref n="2" />‡

**Abstract.** We give a generating function for the fully commutative affine permutations enumerated by rank and Coxeter length, extending formulas due to Stembridge and Barcucci–Del Lungo–Pergola–Pinzani. For fixed rank, the length generating functions have coefficients that are periodic with period dividing the rank. In the course of proving these formulas, we obtain results that elucidate the structure of the fully commutative affine permutations. This is a summary of the results; the full version appears elsewhere.

**Résumé.** Nous présentons une fonction génératrice qui énumère les permutations affines totalement commutatives par leur rang et par leur longueur de Coxeter, généralisant les formules dues à Stembridge et à Barcucci–Del Lungo–Pergola–Pinzani. Pour un rang précis, les fonctions génératrices ont des coefficients qui sont périodiques de période divisant leur rang. Nous obtenons des résultats qui expliquent la structure des permutations affines totalement commutatives. L’article dessous est un aperçu des résultats; la version complète apparaît ailleurs.

**Keywords:** affine Coxeter group, abacus diagram, window notation, complete notation, fully commutative

## 1 Introduction

Let $W$ be a Coxeter group. An element $w$ of $W$ is fully commutative if any reduced expression for $w$ can be obtained from any other using only commutation relations among the generators. For example, if $W$ is simply laced then the fully commutative elements of $W$ are those with no $s_i s_j s_i$ factor in any reduced expression, where $s_i$ and $s_j$ are any noncommuting generators.

The fully commutative elements form an interesting class of Coxeter group elements with many special properties. Stembridge (1996) classified the Coxeter groups having finitely many fully commutative elements, and subsequently enumerated these elements in Stembridge (1998). The type $A$ fully commutative elements were enumerated by Coxeter length by Barcucci et al. (2001), obtaining a $q$-analogue of the Catalan numbers. Our main result in Theorem 3.2 is an analogue of this result for the affine symmetric group.

In Section 2, we introduce the necessary definitions and background information. In Section 3, we enumerate the fully commutative affine permutations by decomposing them into several subsets. The

<footnote n="1">¹Department of Mathematics, Queens College (CUNY), NY, USA</footnote>

<footnote n="2">²Department of Mathematics and Statistics, James Madison University, Harrisonburg, VA, USA</footnote>

<footnote>†The first author received support from PSC-CUNY grant</footnote>

<footnote>‡The second author received support from NSF grant DMS-0636297.</footnote>
formula that we obtain turns out to involve a ratio of $q$-Bessel functions as described in Barcucci et al. (1998) arising as the solution obtained by Bousquet-Mélou (1996) of a certain recurrence relation on the generating function. A similar phenomenon occurred in Barcucci et al. (2001), and our work can be viewed as a description of how to lift this formula to the affine case. It turns out that the only additional ingredients that we need for our formula are certain sums and products of $q$-binomial coefficients.

In Section 4, we prove that for fixed rank, the coefficients of the length generating functions are periodic with period dividing the rank. This result gives another way to determine the generating functions by computing the finite initial sequence of coefficients until the periodicity takes over. We mention some further questions in Section 5.

We thank the anonymous referees whose comments have improved the readability of this manuscript.

## 2 Background

In this section, we introduce the affine symmetric group, abacus diagrams for minimal length coset representatives, and $q$-binomial coefficients.

### 2.1 The affine symmetric group

We view the symmetric group $S_n$ as the Coxeter group of type $A$ with generating set $S = \{s_1, \dots, s_{n-1}\}$ and relations of the form $s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}$ together with $s_i s_j = s_j s_i$ for $|i-j| \ge 2$ and $s_i^2 = 1$. We denote $\cup_{n \ge 1} S_n$ by $S_\infty$ and call $n(w)$ the minimal rank $n$ of $w \in S_n \subset S_\infty$. The affine symmetric group $\tilde{S}_n$ is also a Coxeter group; it is generated by $\tilde{S} = S \cup \{s_0\}$ with the same relations as in the symmetric group together with $s_0^2 = 1$, $s_{n-1}s_0 s_{n-1} = s_0 s_{n-1} s_0$, $s_0 s_1 s_0 = s_1 s_0 s_1$, and $s_0 s_j = s_j s_0$ for $2 \le j \le n-2$.

Recall that the products of generators from $S$ or $\tilde{S}$ with a minimal number of factors are called reduced expressions, and $\ell(w)$ is the length of such an expression for an (affine) permutation $w$. Given an (affine) permutation $w$, we represent reduced expressions for $w$ in sans serif font, say $w = w_1 w_2 \cdots w_p$ where each $w_i \in S$ or $\tilde{S}$. We call any expression of the form $s_i s_{i \pm 1} s_i$ a short braid, where the indices $i, i \pm 1$ are taken mod $n$ if we are working in $\tilde{S}_n$. We say that $s_i$ is a left descent for $w \in \tilde{S}_n$ if $\ell(s_i w) < \ell(w)$ and we say that $s_i$ is a right descent for $w \in \tilde{S}_n$ if $\ell(\tilde{w}s_i) < \ell(w)$.

As in Stembridge (1996), we define an equivalence relation on the set of reduced expressions for an (affine) permutation by saying that two reduced expressions are in the same commutativity class if one can be obtained from the other by a sequence of commuting moves of the form $s_i s_j \mapsto s_j s_i$ where $|i-j| \ge 2$. If the reduced expressions for a permutation $w$ form a single commutativity class, then we say $w$ is fully commutative.

We also refer to elements in the symmetric group by the one-line notation $w = [w_1 w_2 \cdots w_n]$, where $w$ is the bijection mapping $i$ to $w_i$. Then the generators $s_i$ are the adjacent transpositions interchanging the entries $i$ and $i+1$ in the one-line notation. Let $w = [w_1 \cdots w_n]$, and suppose that $p = [p_1 \cdots p_k]$ is another permutation in $S_k$ for $k \le n$. We say $w$ contains the permutation pattern $p$ or $w$ contains $p$ as a one-line pattern whenever there exists a subsequence $1 \le i_1 < i_2 < \cdots < i_k \le n$ such that

$$w_{i_a} < w_{i_b} \text{ if and only if } p_a < p_b$$

for all $1 \le a < b \le k$. We call $(i_1, i_2, \dots, i_k)$ the pattern instance. For example, [53241] contains the pattern [321] in several ways, including the subsequence 541. If $w$ does not contain the pattern $p$, we say that $w$ avoids $p$.
The affine symmetric group $\tilde{S}_n$ is realized as the group of bijections $w : \mathbb{Z} \to \mathbb{Z}$ satisfying $w(i + n) = w(i) + n$ and $\sum_{i=1}^{n} w(i) = \sum_{i=1}^{n} i = \binom{n+1}{2}$. (See for example Chapter 8 of Björner and Brenti (2005)) We call the infinite sequence

$$ (..., w(-1), w(0), w(1), w(2), \dots, w(n), w(n+1), \dots) $$

the complete notation for $w$ and

$$ [w(1), w(2), \dots, w(n)] $$

the base window for $w$. By definition, the entries of the base window determine $w$ and its complete notation. Moreover, the entries of the base window can be any set of integers that are normalized to sum to $\binom{n+1}{2}$ and such that the entries form a permutation of the residue classes in $\mathbb{Z}/(n\mathbb{Z})$ when reduced mod $n$. That is, no two entries of the base window have the same residue mod $n$. With these considerations in mind, we will represent an affine permutation using an abacus diagram together with a finite permutation.

To describe this, observe that $S_n$ acts on the base window by permuting the entries, which induces an action of $S_n$ on $\mathbb{Z}$. In this action, the Coxeter generator $s_i$ simultaneously interchanges $w(i + kn)$ with $w(i + 1 + kn)$ for all $k \in \mathbb{Z}$. Moreover, the affine generator $s_0$ interchanges all $w(kn)$ with $w(kn + 1)$. Hence, $S_n$ is a parabolic subgroup of $\tilde{S}_n$. We form the parabolic quotient

$$ \tilde{S}_n/S_n = \{w \in \tilde{S}_n : \ell(\text{ws}_i) > \ell(w) \text{ for all } s_i \text{ where } 1 \le i \le n-1\}. $$

By a standard result in the theory of Coxeter groups, this set gives a unique representative of minimal length from each coset $wS_n$ of $\tilde{S}_n$. For more on this construction, see (Björner and Brenti, 2005, Section 2.4). In our case, the base window of the minimal length coset representative of an element is obtained by ordering the entries that appear in the base window increasingly. This construction implies that, as sets, the affine symmetric group can be identified with the set $(\tilde{S}_n/S_n) \times S_n$. The minimal length coset representative determines which entries appear in the base window, and the finite permutation orders these entries in the base window.

We say that $w$ has a descent at $i$ whenever $w(i) > w(i + 1)$. Note that if $w$ has a descent at $i$, then $s_{(i \text{ mod } n)}$ is a right descent in the usual Coxeter theoretic sense that $\ell(\text{ws}_i) < \ell(w)$.

## 2.2 Abacus diagrams

The abacus diagrams of James and Kerber (1981) give a combinatorial model for the minimal length coset representatives in $\tilde{S}_n/S_n$. Other combinatorial models and references for these are given in Berg et al. (2009).

An abacus diagram is a diagram containing $n$ columns labeled 1, 2, ..., $n$, called runners. The horizontal rows are called levels and runner $i$ contains entries labeled by $rn + i$ on each level $r$ where $-\infty < r < \infty$. We draw the abacus so that each runner is vertical, oriented with $-\infty$ at the top and $\infty$ at the bottom, with runner 1 in the leftmost position, increasing to runner $n$ in the rightmost position. Entries in the abacus diagram may be circled; such circled elements are called beads. Entries that are not circled are called gaps. The linear ordering of the entries given by the labels $rn + i$ is called the reading order of the abacus which corresponds to scanning left to right, top to bottom.

We associate an abacus to each minimal length coset representative $w \in \tilde{S}_n/S_n$ by drawing beads down to level $w_i$ in runner $i$ for each $1 \le i \le n$ where $\{w_1, w_2, \dots, w_n\}$ is the set of integers in the base window of $w$, with no two having the same residue mod $n$. Since the entries $w_i$ sum to $\binom{n+1}{2}$, we call the
abacus constructed in this way balanced. It follows from the construction that the Coxeter length of the minimal length coset representative can be determined from the abacus.

**Proposition 2.1** Let $w \in \tilde{S}_n/S_n$ and form the abacus for $w$ as described above. Let $m_i$ denote the number of gaps preceding the lowest bead of runner $i$ in reading order, for each $1 \le i \le n$. Then, the Coxeter length $\ell(w)$ is $\sum_{i=1}^n m_i$.

**Proof:** This result is part of the folklore of the subject. One proof can be obtained by combining Propositions 3.2.5 and 3.2.8 of Berg et al. (2009). $\square$

**Example 2.2** The affine permutation $\tilde{w} = [-1, -4, 14, 1]$ is identified with the pair $(w^0, w)$ where $w$ is the finite permutation $s_1s_3 = [2143]$ which sorts the elements of the minimal length coset representative $w^0 = [-4, -1, 1, 14]$. Note that the entries of $w^0$ sum to $\binom{5}{2} = 10$. The abacus of $w^0$ is shown below.

<figure><img src="image_1.png" /></figure>

From the abacus, we see that $w^0$ has Coxeter length $1+10+0+0=11$. For example, the ten gaps preceding the lowest bead in runner 2 are 13, 12, 11, 9, 8, 7, 5, 4, 3, and 0. Hence, $\tilde{w}$ has length $\ell(w^0) + \ell(w) = 13$.

In this work, we are primarily concerned with the fully commutative affine permutations. Green (2002) has given a criterion for these in terms of the complete notation for $w$. His result is a generalization of a theorem from Billey et al. (1993) which states that $w \in S_n$ is fully commutative if and only if $w$ avoids [321] as a permutation pattern.

**Theorem 2.3** Green (2002) Let $w \in \tilde{S}_n$. Then, $w$ is fully commutative if and only if there do not exist integers $i < j < k$ such that $w(i) > w(j) > w(k)$.

Observe that even though the entries in the base window of a minimal length coset representative are sorted, the element may not be fully commutative by Theorem 2.3. For example, if we write the element $w^0 = [-4, -1, 1, 14]$ in complete notation

$$w^0 = (..., -8, -5, -3, \mathbf{10}, -4, -1, \mathbf{1}, 14, \mathbf{0}, 3, 5, 18, \dots)$$

we obtain a [321]-instance as indicated in boldface.

In order to more easily exploit this phenomenon, we slightly modify the construction of the abacus. Observe that the length formula in Proposition 2.1 depends only on the relative positions of the beads in the abacus, and is unchanged if we shift every bead in the abacus exactly $k$ positions to the right in
reading order. Moreover, each time we shift the beads one unit to the right, we change the sum of the entries occurring on the lowest bead in each runner by exactly $n$. In fact, this shifting corresponds to shifting the base window inside the complete notation. Therefore, we may define an abacus in which all of the beads are shifted so that position $n + 1$ becomes the first gap in reading order. We call such abaci *normalized*. Although the entries of the lowest beads in each runner will no longer sum to $\binom{n+1}{2}$, we can reverse the shifting to recover the balanced abacus. Hence, this process is a bijection on abaci, and we may assume from now on that our abaci are normalized.

**Proposition 2.4** Let A be a normalized abacus for $w^0 \in \tilde{S}_n/S_n$, and suppose the last bead occurs at entry $i$. Then, $w^0$ is fully commutative if and only if the lowest beads on runners of A occur only in positions that are a subset of $\{1, 2, \dots, n\} \cup \{i - n + 1, i - n + 2, \dots, i\}$.

We distinguish between two types of fully commutative elements through the position of the last bead in its normalized abacus A. If the last bead occurs in a position $i > 2n$, then we call the element a long element. Otherwise, the last bead occurs in a position $n \le i \le 2n$, and we call the element a short element. As evidenced in Section 3, the long fully commutative elements have a nice structure that allows for an elegant enumeration; the short elements lack this structure.

## 2.3 q-analogs of binomial coefficients

Calculations involving $q$-analogs of combinatorial objects often involve $q$-analogs of counting functions. Define $(a, q)_n = (1-a)(1-aq)\cdots(1-aq^{n-1})$ and $(q)_n = (q, q)_n$. The $q$-binomial coefficient $\begin{bmatrix} n \\ k \end{bmatrix}_q$ (also called the Gaussian polynomial) is a $q$-analog of the binomial coefficient $\binom{n}{k}$. To calculate a $q$-binomial coefficient directly, we use the formula

$$ \begin{bmatrix} n \\ k \end{bmatrix}_q = \frac{(1-q^n)(1-q^{n-1})\cdots(1-q^{n-k+1})}{(1-q^k)(1-q^{k-1})\cdots(1-q^1)} = \frac{(q)_n}{(q)_k(q)_{n-k}}. \quad (1) $$

Just as with ordinary binomial coefficients, $q$-binomial coefficients have multiple combinatorial interpretations and satisfy many identities, a few of which are highlighted below.

**Interpretation 1** (Stanley, 1997, Proposition 1.3.17) Let $M$ be the multiset $M = \{1^k, 2^{n-k}\}$. For an ordering $\pi$ of the $n$ elements of $M$, the number of inversions of $\pi$, denoted $\text{inv}(\pi)$, is the number of instances of two entries $i$ and $j$ such that $i < j$ and $\pi(i) > \pi(j)$. Then $\begin{bmatrix} n \\ k \end{bmatrix}_q = \sum_{\pi} q^{\text{inv}(\pi)}$.

**Interpretation 2** Let $\begin{bmatrix} n \\ k \end{bmatrix}$ be the set of subsets of $[n] = \{1, 2, \dots, n\}$ of size $k$. Given $\mathcal{R} = \{r_1, \dots, r_k\} \in \begin{bmatrix} n \\ k \end{bmatrix}$, define $|\mathcal{R}| = \sum_{j=1}^k (r_j - j)$. Then $\begin{bmatrix} n \\ k \end{bmatrix}_q = \sum_{\mathcal{R} \in \begin{bmatrix} n \end{bmatrix}} q^{|\mathcal{R}|}$.

Interpretation 1 is used most frequently in this article. Interpretation 2 is used in Section 3.1 when counting long fully commutative elements.

# 3 Decomposition and enumeration of fully commutative elements

Let $S_n^{FC}$ denote the set of fully commutative permutations in $S_n$. In the following result, Barcucci et al. enumerate these elements by Coxeter length.
**Theorem 3.1** Barcucci et al. (2001) Let $C(x, q) = \sum_{n \ge 0} \sum_{w \in S_n^{FC}} x^n q^{\ell(w)}$. Then,

$$C(x, q) = \frac{\sum_{n \ge 0} (-1)^n x^{n+1} q^{\frac{(n(n+3))/2}{(x, q)_{n+1}(q, q)_n}}}{\sum_{n \ge 0} (-1)^n x^n q^{\frac{(n(n+1))/2}{(x, q)_n(q, q)_n}}$$

We enumerate the fully commutative elements $\tilde{w} \in \tilde{S}_n$ by identifying each as the product of its minimal length coset representative $w^0 \in \tilde{S}_n/S_n$ and a finite permutation $w \in S_n$ as described in Section 2.2. Recall that we decompose the set of fully commutative elements into long and short elements. The elements with a short abacus structure break down into those where certain entries intertwine and those in which there is no intertwining. When we assemble these cases, we obtain our main theorem.

**Theorem 3.2** Let $\tilde{S}_n^{FC}$ denote the set of fully commutative affine permutations in $\tilde{S}_n$, and let $G(x, q) = \sum_{n \ge 0} \sum_{w \in \tilde{S}_n^{FC}} x^n q^{\ell(w)}$, where $\ell(w)$ denotes the Coxeter length of $w$. Then,

$$G(x, q) = \left( \sum_{n \ge 0} \frac{x^n q^n}{1 - q^n} \sum_{k=1}^{n-1} \begin{bmatrix} n \\ k \end{bmatrix}_q^2 \right) + C(x, q) + \left( \sum_{R, L \ge 1} q^{R+L-1} \begin{bmatrix} L+R-2 \\ L-1 \end{bmatrix}_q S(x, q) \right),$$

where $C(x, q)$ is given by Theorem 3.1, and the component parts of $S(x, q) = S_I(x, q) + S_0(x, q) + S_1(x, q) + S_2(x, q)$ are given in Lemmas 3.8, 3.9, 3.10, and 3.11, respectively.

The first summand of $G(x, q)$ counts the long elements, while the remaining summands count the short elements. This theorem will be proved in Section 3.3 below.

## 3.1 Long elements

In this section, we enumerate the long elements. Recall that the last bead in the normalized abacus for these elements occurs in position $> 2n$.

**Lemma 3.3** For fixed $n \ge 0$, we have

$$\sum_{w \in \tilde{S}_n^{FC} \text{ such that } w \text{ is long}} q^{\ell(w)} = \frac{q^n}{1-q^n} \sum_{k=1}^{n-1} \begin{bmatrix} n \\ k \end{bmatrix}_q^2.$$

**Proof:** Fix a long fully commutative element, and define the set of long runners $\mathcal{R}$ of its normalized abacus $A$ to be the set of runners $\{r_1, \dots, r_k\} \subset [n] \setminus \{1\}$ in which there exists a bead in position $n + r_j$ for $1 \le j \le k$. We will enumerate the long fully commutative elements by conditioning on $k = |\mathcal{R}|$, the size of the set of long runners of its normalized abacus. Note that by Proposition 2.4, all subsets $\mathcal{R} \subset [n] \setminus \{1\}$ are indeed the set of long runners for some fully commutative element.

For a fixed $\mathcal{R}$, there is an infinite family of abaci $\{A_i^R\}_{i \ge 1}$, each having beads in positions $n + r_j$ for $r_j \in \mathcal{R}$, together with $i$ additional beads that are placed sequentially in the long runners in positions larger than $2n$.

By Proposition 2.1, the Coxeter length of the minimal length coset representative $w^0 \in \tilde{S}_n/S_n$ having $A_i^R$ as its abacus is $i(n-k) + \sum_{j=1}^k (r_j - j)$. In addition, $w^0$ has base window $[aa \cdots abb \cdots b]$, where the
(n-k) numbers a are all at most n, and the k numbers b are all at least n + 2. The finite permutations w that can be applied to this standard window may not invert any of the larger numbers (b's) without creating a [321]-pattern with n + 1 in the window following the standard window. Similarly, none of the a's can be inverted. All that remains is to intersperse the a's and the b's, keeping track of how many transpositions are used. This contributes exactly $\begin{bmatrix} n \\ k \end{bmatrix}_q$ to the Coxeter length, by Interpretation 1 of $\begin{bmatrix} n \\ k \end{bmatrix}_q$.

Algebraic simplification and application of Interpretation 2 gives the result. $\square$

## 3.2 Short elements

The normalized abacus of every short fully commutative element has a particular structure. There must be a gap in position n + 1, and for runners 2 ≤ i ≤ n, the lowest bead is either in position i or n + i. In the following arguments, we will assign a status to each runner, depending on the position of the lowest bead in that runner.

**Definition 3.4** An R-entry is a bead lying in some position > n. Let n + j be the position of the last R-entry, or set j = n if there are no R-entries; an M-entry is a lowest bead lying in position i where j + 1 ≤ i ≤ n. Note that it is possible that there do not exist any M-entries. The L-entries are the remaining lowest beads in position i for i ≤ j. This assigns a status left, middle, or right to each entry of the base window, depending on the position of the lowest bead in the corresponding runner. We will call an abacus containing L L-entries, M M-entries, and R R-entries an (L)(M)(R) abacus.

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** The three (3)(1)(2) abaci and Coxeter length of their corresponding minimal length coset representatives.</figcaption></figure>

**Example 3.5** Figure 1 shows the three (3)(1)(2) abaci. In each case, 6 is the unique M-entry and 11 is an R-entry. In the first abacus, the L-entries are {1, 3, 4} and the R-entries are {8, 11}.

The rationale for this assignment is that in the base window of a fully commutative element, not of type (n)(0)(0), neither the L-entries nor the R-entries can have a descent amongst themselves, respectively. To see this, consider the contrary where two R-entries have a descent. These two entries, along with the n+1 entry in the window following the standard window, form a [321]-instance. Similarly, the last R-entry in the window previous to the standard window together with two L-entries that have a descent in the standard window would form a [321]-instance.

When the normalized abacus of a short fully commutative element has no R-entries (and therefore no M-entries), the base window for its minimal length coset representative is [12...n]. That is, the fully commutative elements of $\tilde{S}_n$ having this abacus are in one-to-one correspondence with fully commutative elements of finite $S_n$. These elements have been enumerated in Theorem 3.1.

From now on, we only concern ourselves with (L)(M)(R) abaci where R > 0. Proposition 3.6 proves that it is solely the parameters L, M, and R that determine the set of finite permutations that we can apply
to the minimal length coset representative, and not the exact abacus. In Proposition 3.7 we determine the cumulative contribution to the Coxeter length of the minimal length coset representative from all $(L)(M)(R)$ abaci for fixed $L, M$, and $R$.

**Proposition 3.6** Let $w_1^0, w_2^0 \in \tilde{S}_n/S_n$, each corresponding to an $(L)(M)(R)$ abacus for the same $L, M$, and $R$ with $R > 0$. For any finite permutation $w \in S_n$, $w_1^0 w$ is fully commutative in $\tilde{S}_n$ if and only if $w_2^0 w$ is fully commutative in $\tilde{S}_n$.

**Proposition 3.7** Let $L, M$ and $R > 0$ be fixed. Then, we have

$$ \sum_w q^{\ell(w)} = q^{L+R-1} \begin{bmatrix} L+R-2 \\ L-1 \end{bmatrix}_q. $$

where the sum on the left is over all minimal length coset representatives $w$ having an $(L)(M)(R)$ abacus.

**Proof:** Every $(L)(M)(R)$ abacus contains beads in all positions through $n$ and in position $2n - M$ as well as gaps in position $n + 1$ and all positions starting with $2n - M + 1$. Depending on the positions of the $L-1$ remaining gaps (and $R-1$ remaining beads), the Coxeter length of the minimal length coset representative changes as illustrated by example in Figure 1.

The minimal length coset representative corresponding to an $(L)(M)(R)$ abacus having beads in positions $i$ for $n+2 \le i \le n+R$ together with a bead at position $2n-M$, and gaps in positions $i$ for $n+R+1 \le i \le 2n-M-1$ has Coxeter length $L+R-1$. Notice that every time we move a bead from one of the positions between $n+2$ and $2n-M-1$ into a gap in the position directly to its right, the Coxeter length increases by exactly one. In essence, we are intertwining one sequence of length $L-1$ and one sequence of length $R-1$ and keeping track of the number of inversions we apply. By $q$-binomial Interpretation 1, the contribution to the Coxeter length of the minimal length coset representatives corresponding to the $(L)(M)(R)$ abaci is $q^{L+R-1} \begin{bmatrix} L+R-2 \\ L-1 \end{bmatrix}_q$. $\square$

For the remaining arguments, we ignore the exact entries in the base window and simply fix both some positive number $L$ of L-entries and some positive number $R$ of R-entries, and then enumerate the permutations $w \in S_n$ that we can apply to a minimal length coset representative $w^0$ with base window of the form $[L \cdots LM \cdots MR \cdots R]$. In Theorem 3.2, we sum the contributions over all possible values of $L$ and $R$.

### 3.2.1 Short elements with intertwining

One possibility is that after $w \in S_n$ is applied to our minimal length coset representative $w^0$ with base window of the form $[L \cdots LM \cdots MR \cdots R]$, an R-entry lies to the left of an L-entry. In this case, we say that $w$ is *intertwining*, the L-entries are *intertwining* with the R-entries, and that the interval between the leftmost R and the rightmost L inclusive is the *intertwining zone*.

**Lemma 3.8** Fix $L$ and $R > 0$. Then, we have $S_I(x, q) = \sum_w x^{n(w)} q^{\ell(w)} =$

$$ \sum_{M \ge 0} x^{L+M+R} \sum_{\rho=0}^{R-1} \sum_{\lambda=0}^{L-1} \sum_{\mu=0}^{M} q^Q \begin{bmatrix} M \\ \mu \end{bmatrix}_q \begin{bmatrix} L-\lambda-1+\mu \\ \mu \end{bmatrix}_q \begin{bmatrix} \lambda+\rho \\ \lambda \end{bmatrix}_q \begin{bmatrix} M-\mu+R-\rho-1 \\ M-\mu \end{bmatrix}_q, $$

where the sum on the left is over all $w \in S_\infty$ that are *intertwining* and apply to a short $(L)(M)(R)$ abacus for some $M$, and $Q = (\lambda+1)(\mu+1) + (\rho+1)(M-\mu+1) - 1$.
### 3.2.2 Short elements without intertwining

If the L-entries and R-entries are not intertwined, there may be M-entries lying between the rightmost L and the leftmost R. There can be no descents in the M-entries to the left of the rightmost L nor to the right of the leftmost R by the same reasoning as above. However, multiple descents may now occur among the M-entries. We enumerate these short elements without intertwining by conditioning on the number of descents that occur among the M-entries. Lemmas 3.9, 3.10, and 3.11 enumerate the short elements in which there are zero, one, or two or more descents among the M-entries, respectively.

**Lemma 3.9** Fix L and R > 0. Then, we have

$$S_0(x, q) = \sum_w x^{n(w)} q^{\ell(w)} = \sum_{M \ge 0} x^{L+M+R} \sum_{\mu=0}^{M} q^{\mu} \begin{bmatrix} L-1+\mu \\ \mu \end{bmatrix}_q \begin{bmatrix} R+M-\mu \\ M-\mu \end{bmatrix}_q,$$

where the sum on the left is over all $w \in S_\infty$ that are not intertwining, have no descents among the M-entries, and apply to a short $(L)(M)(R)$ abacus for some M.

**Proof:** Let $\mu$ be the number of M-entries lying to the left of the rightmost L. Then, the $\mu$ M-entries can be intertwined with the remaining $(L-1)$ L-entries, and the remaining $(M-\mu)$ M-entries can be intertwined with the R R-entries.

We compute the Coxeter length offset by counting the inversions among the entries in the base window in the minimal length configuration of this type. In this case, there are simply $\mu$ M-entries that are inverted with the rightmost L. Summing over all valid values of $\mu$ gives the formula. $\square$

A similar method of proof applies to the following Lemma.

**Lemma 3.10** Fix L and R > 0. Then, we have

$$S_1(x, q) = \sum_w x^{n(w)} q^{\ell(w)} = \sum_{M \ge 0} x^{L+M+R} \sum_{\mu=1}^{M-1} \begin{pmatrix} [M] \\ [\mu] \end{pmatrix}_q - 1 \begin{bmatrix} L+\mu \\ \mu \end{bmatrix}_q \begin{bmatrix} R+M-\mu \\ M-\mu \end{bmatrix}_q,$$

where the sum on the left is over all $w \in S_\infty$ that are not intertwining, have exactly one descent among the M-entries, and apply to a short $(L)(M)(R)$ abacus for some M.

The proof of our next result, relies on Lemma 2.3 of Bousquet-Mélou (1996) which solves certain functional recurrences.

**Lemma 3.11** Fix L and R > 0. Then, we have

$$S_2(x, q) = \sum_w x^{n(w)} q^{\ell(w)} = x^{L+R} \sum_{i,j \ge 1} \begin{bmatrix} L+i \\ L \end{bmatrix}_q \begin{bmatrix} R+j \\ R \end{bmatrix}_q d_{i,j}(x,q),$$

where the sum on the left is over all $w \in S_\infty$ that are not intertwining, have at least two descents among the M-entries, and apply to a short $(L)(M)(R)$ abacus for some M. Here, $d_{i,j}(x,q)$ is the coefficient of $z^i s^j$ in the generating function that satisfies the functional equation

$$D(x, q, z, s) = \frac{\sum_{n \ge 0} x^{n+1} \sum_{i=1}^{n-1} \begin{bmatrix} n \\ i \end{bmatrix}_q - 1}{(1 - q s)(1 - x s)} z^i ((qs) - (qs)^{n-i}) + \frac{xqs(D(x, q, z, 1) - D(x, q, z, qs))}{(1 - q s)(1 - x s)}$$

A nonrecursive form for $D(x, q, z, 1)$ is obtained in the proof of Lemma 3.11.
### 3.3 Proof of the main theorem

**Proof of Theorem 3.2:** Partition the set of fully commutative elements $\tilde{w}$ into long elements and short elements. The long elements in $\tilde{S}_n$ are enumerated by Lemma 3.3; we must sum over all $n$.

Each short element $\tilde{w}$ has a normalized abacus of type $(L)(M)(R)$ for some $L, M$, and $R$. When this abacus is of type $(n)(0)(0)$ for some $n$, the base window for the corresponding minimal length coset representative is $[12 \dots n]$. These elements $\tilde{w} \in \tilde{S}_n^{FC}$ are therefore in one-to-one correspondence with elements of $S_n^{FC}$. Therefore, the generating function $C(x, q)$ enumerates these elements for all $n$.

The elements that remain to be enumerated are short elements with normalized abacus of type $(L)(M)(R)$ for $R > 0$. We enumerate these elements by grouping these elements into families based on the values of $L, M$, and $R$. Decompose each element $\tilde{w}$ into the product of its minimal length coset representative $w^0$ and a finite permutation $w$. Proposition 3.6 proves that for two minimal length coset representatives $w_1^0$ and $w_2^0$ of the same abacus type, the set of finite permutations $w$ that multiply to form a fully commutative element is the same. Proposition 3.7 proves that in an $(L)(M)(R)$-family of fully commutative elements, the contribution to the length from the minimal length coset representatives is $q^{L+R-1} [L+R-2]_q$. What remains to be determined is the generating function for the contributions of the finite permutations $w$.

In an $(L)(M)(R)$-family of fully commutative elements, the finite permutations $w$ might intermingle the $L$ entries and the $R$ entries of the base window in which case there is at most one descent among the $M$ entries at a prescribed position; the contribution of such $w$ is given by $S_I$ in Lemma 3.8. Otherwise, there is no intermingling and the finite permutations $w$ may induce zero, one, or two or more descents among the $M$ entries; these cases are enumerated by generating functions $S_0, S_1$, and $S_2$ in Lemmas 3.9, 3.10, and 3.11, respectively. In each of these lemmas, the values for $L$ and $R$ are held constant as $M$ varies. Summing the product of the contributions of the minimal length coset representatives and the finite permutations over all possible values of $L$ and $R$ completes the enumeration. $\square$

## 4 Numerical Conclusions

Theorem 3.2 allows us to determine the length generating function $f_n(q)$ for the fully commutative elements of $\tilde{S}_n$ as $n$ varies. The first few series $f_n(q)$ are presented below.

$$f_3(q) = 1 + 3q + 6q^2 + 6q^3 + 6q^4 + \dots$$

$$f_4(q) = 1 + 4q + 10q^2 + 16q^3 + 18q^4 + 16q^5 + 18q^6 + \dots$$

$$f_5(q) = 1 + 5q + 15q^2 + 30q^3 + 45q^4 + 50q^5 + 50q^6 + 50q^7 + 50q^8 + 50q^9 + \dots$$

$$f_6(q) = 1 + 6q + 21q^2 + 50q^3 + 90q^4 + 126q^5 + 146q^6 + 150q^7 + 156q^8 + 152q^9 + 156q^{10} + 150q^{11} + 158q^{12} + 150q^{13} + 156q^{14} + 152q^{15} + \dots$$

$$f_7(q) = 1 + 7q + 28q^2 + 77q^3 + 161q^4 + 266q^5 + 364q^6 + 427q^7 + 462q^8 + 483q^9 + 490q^{10} + 490q^{11} + 490q^{12} + 490q^{13} + 490q^{14} + 490q^{15} + \dots$$

$$f_8(q) = 1 + 8q + 36q^2 + 112q^3 + 266q^4 + 504q^5 + 792q^6 + 1064q^7 + 1274q^8 + 1416q^9 + 1520q^{10} + 1568q^{11} + 1602q^{12} + 1600q^{13} + 1616q^{14} + 1600q^{15} + 1618q^{16} + 1600q^{17} + 1616q^{18} + 1600q^{19} + 1618q^{20} + \dots$$

$$f_9(q) = 1 + 9q + 45q^2 + 156q^3 + 414q^4 + 882q^5 + 1563q^6 + 2367q^7 + 3159q^8 + 3831q^9 + 4365q^{10} + 4770q^{11} + 5046q^{12} + 5220q^{13} + 5319q^{14} + 5370q^{15} + 5391q^{16} + 5400q^{17} + 5406q^{18} + 5400q^{19} + 5400q^{20} + 5406q^{21} + 5400q^{22} + 5400q^{23} + \dots$$
One remarkable quality of these series is their periodicity, given by the bold-faced terms. This behavior is explained by the following corollary to Lemma 3.3.

**Corollary 4.1** The coefficients $a_i$ of $f_n(q) = \sum_{w \in \tilde{S}_{FC}^n} q^{\ell(w)} = \sum_{i \ge 0} a_i q^i$ are periodic with period $m|n$ for sufficiently large $i$. When $n = p$ is prime, the period $m$ is 1 and in this case there are precisely

$$ \frac{1}{p} \left( \binom{2p}{p} - 2 \right) $$

fully commutative elements of length $i$ in $\tilde{S}_p$, when $i$ is sufficiently large.

**Proof:** For a given $n$, the number of short fully commutative elements is finite. The formula for long elements in Lemma 3.3 is a polynomial divided by $1 - q^n$. Hence, the coefficients of this generating function satisfy $a_{i+n} = a_i$, by a fundamental result on rational generating functions.

When $n$ is prime, the formula in Lemma 3.3 can be shown to be a polynomial divided by $1 - q$. $\square$

The distinction between long and short elements allows us to enumerate the fully-commutative elements efficiently. In some respects, this division is not the most natural in that the periodicity of the above series begins before there exist no more short elements. Experimentally, it appears that the periodicity begins at $1 + \lfloor (n-1)/2 \rfloor \lfloor (n-1)/2 \rfloor$; whereas, we can prove that the longest short element has length $2 \lfloor n/2 \rfloor \lfloor n/2 \rfloor$. We can bound the Coxeter length of finite fully commutative permutations.

**Proposition 4.2** Let $w \in \tilde{S}_n^{FC}$ be a short element. Then $\ell(w) \le 2 \lfloor n/2 \rfloor \lfloor n/2 \rfloor$. In addition, there exists $a w \in \tilde{S}_n^{FC}$ with length $2 \lfloor n/2 \rfloor \lfloor n/2 \rfloor$.

Corollary 4.1 and Proposition 4.2 give another way to compute the series $f_n(q)$, without invoking Theorem 3.2. Using a computer program, one needs simply to count the fully-commutative elements of $\tilde{S}_n$ of length up to $n + 2 \lfloor n/2 \rfloor \lfloor n/2 \rfloor$.

# 5 Further questions

In this work, we have studied the length generating function for the fully commutative affine permutations. It would be interesting to explore the ramifications of the periodic structure of these elements in terms of the affine Temperley-Lieb algebra. Also, all of our work should have natural extensions to the other Coxeter groups. In fact, we know of no analogue of Barcucci et al. (2001) enumerating the fully commutative elements by length for finite types beyond type A. It is a natural open problem to establish the periodicity of the length generating functions for the other affine types. It would also be interesting to determine the analogues for other types of the q-binomial coefficients and q-Bessel functions that played prominent roles in our enumerative formulas.

Finally, it remains an open problem to prove that the periodicity of the length generating function coefficients for fixed rank begins at length $1 + \lfloor (n-1)/2 \rfloor \lfloor (n-1)/2 \rfloor$, as indicated by the data. By examining the structure of the heap diagrams associated to the fully commutative affine permutations, we have discovered some plausible reasoning indicating this tighter bound, but a proof remains elusive.
References

E. Barcucci, A. Del Lungo, J. M. Fédou, and R. Pinzani. Steep polyominoes, $q$-Motzkin numbers and $q$-Bessel functions. *Discrete Math.*, 189(1-3):21–42, 1998. ISSN 0012-365X.

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. ISSN 0012-365X.

C. Berg, B. C. Jones, and M. Vazirani. A bijection on core partitions and a parabolic quotient of the affine symmetric group. *J. Combin. Theory Ser. A*, 116(8):1344–1360, 2009.

S. Billey, W. Jockusch, and R. P. Stanley. Some combinatorial properties of Schubert polynomials. *J. Algebraic Combin.*, 2(4):345–374, 1993. ISSN 0925-9899.

A. Björner and F. Brenti. *Combinatorics of Coxeter groups*, volume 231 of *Graduate Texts in Mathematics*. Springer, New York, 2005. ISBN 978-3540-442387.

M. Bousquet-Mélou. A method for the enumeration of various classes of column-convex polygons. *Discrete Math.*, 154(1-3):1–25, 1996. ISSN 0012-365X.

R. M. Green. On 321-avoiding permutations in affine Weyl groups. *J. Algebraic Combin.*, 15(3):241–252, 2002. ISSN 0925-9899.

G. D. James and A. Kerber. *The representation theory of the symmetric group*, volume 16 of *Encyclopedia of Mathematics and its Applications*. Addison-Wesley Publishing Co., Reading, Mass., 1981. ISBN 0-201-13515-9. With a foreword by P. M. Cohn, With an introduction by Gilbert de B. Robinson.

R. P. Stanley. *Enumerative combinatorics. Vol. 1*, volume 49 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1997. ISBN 0-521-55309-1; 0-521-66351-2. With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original.

J. R. Stembridge. On the fully commutative elements of Coxeter groups. *J. Algebraic Combin.*, 5(4):353–385, 1996. ISSN 0925-9899.

J. R. Stembridge. The enumeration of fully commutative elements of Coxeter groups. *J. Algebraic Combin.*, 7(3):291–320, 1998. ISSN 0925-9899.