# Extended Abstract for Enumerating Pattern Avoidance for Affine Permutations

Andrew Crites†

Department of Mathematics, University of Washington, Box 354350, Seattle, Washington, 98195-4350

**Abstract.** In this paper we study pattern avoidance for affine permutations. In particular, we show that for a given pattern $p$, there are only finitely many affine permutations in $\tilde{S}_n$ that avoid $p$ if and only if $p$ avoids the pattern 321. We then count the number of affine permutations that avoid a given pattern $p$ for each $p$ in $S_3$, as well as give some conjectures for the patterns in $S_4$. This paper is just an outline; the full version will appear elsewhere.

**Résumé.** Dans cet œuvre, on étudie comment les permutations affines évitent les motifs. Spécifiquement, on peut dire que pour le motif $p$, il existe un nombre limité de permutations affines dans $\tilde{S}_n$ qui évite $p$ si et seulement si $p$ évite le motif 321. Après, on compte le nombre de permutations affines qui évitent le motif $p$ pour chaque $p$ de $S_3$. Puis, on donne des conjectures pour les motifs de $S_4$. Ceci n’est qu’un aperçu; la version complète apparaîtra ailleurs.

**Keywords:** pattern avoidance, affine permutation, generating function, Catalan number

## 1 Introduction

Given a property $Q$, it is a natural question to ask if there is a simple characterization of all permutations with property $Q$. For example, in Lakshmibai and Sandhya (1990) the permutations corresponding to smooth Schubert varieties are exactly the permutations that avoid the two patterns 3412 and 4231. In Tenner (2007) it was shown that the permutations with Boolean order ideals are exactly the ones that avoid the two patterns 321 and 3412. A searchable database listing which classes of permutations avoid certain patterns can be found at Tenner (2009).

Since we know pattern avoidance can be used to describe useful classes of permutations, we might ask if we can enumerate the permutations avoiding a given pattern or set of patterns. For example, in Marcus and Tardos (2004) it was shown that if $S_n(p)$ is the number of permutations in the symmetric group, $S_n$, that avoid the pattern $p$, then there is some constant $c$ such that $S_n(p) \le c^n$. Thus the rate of growth of pattern avoiding permutations is bounded. This result was known as the Stanley-Wilf conjecture, now called the Marcus-Tardos Theorem.

We can express elements of the affine symmetric group, $\tilde{S}_n$, as an infinite sequence of integers, and it is still natural to ask if there exists a subsequence with a given relative order. Thus we can extend the notion of pattern avoidance to these affine permutations and we can try to count how many $\omega \in \tilde{S}_n$ avoid a given pattern.

<footnote>†Andrew Crites acknowledges support from grant DMS-0800978 from the National Science Foundation.</footnote>
For $p \in S_m$, let

$$f_n^p = \# \{ \omega \in \tilde{S}_n : \omega \text{ avoids } p \} \qquad (1)$$

and consider the generating function

$$f^p(t) = \sum_{n=2}^{\infty} f_n^p t^n. \qquad (2)$$

For a given pattern $p$ there could be infinitely many $\omega \in \tilde{S}_n$ that avoid $p$. In this case, the generating function in (2) is not even defined. As a first step towards understanding $f^p(t)$, we will prove the following theorem.

**Theorem 1** Let $p \in S_m$. For any $n \ge 2$ there exist only finitely many $\omega \in \tilde{S}_n$ that avoid $p$ if and only if $p$ avoids the pattern 321.

It is worth noting that 321-avoiding permutations and 321-avoiding affine permutations appear as an interesting class of permutations in their own right. In (Billey et al., 1993, Theorem 2.1) it was shown that a permutation is fully commutative if and only if it is 321-avoiding. This means that every reduced expression for $\omega$ may be obtained from any other reduced expression using only relations of the form $s_i s_j = s_j s_i$ with $|i - j| > 1$. Moreover, a proof that this result can be extended to affine permutations as well appears in (Green, 2002, Theorem 2.7). For a detailed discussion of fully commutative elements in other Coxeter groups, see Stembridge (1996).

Even in the case where there might be infinitely many $\omega \in \tilde{S}_n$ that avoid a pattern $p$, we can always construct the following generating function. Let

$$g_{m,n}^p = \# \{ \omega \in \tilde{S}_n : \omega \text{ avoids } p \text{ and } \ell(\omega) = m \}. \qquad (3)$$

Then set

$$g^p(x, y) = \sum_{n=2}^{\infty} \sum_{m=0}^{\infty} g_{m,n}^p x^m y^n. \qquad (4)$$

Since there are only finitely many elements in $\tilde{S}_n$ of a given length, we always have $g_{m,n}^p < \infty$. The generating function $g^{321}(x, y)$ is computed in (Hanusa and Jones, 2009, Theorem 3.2).

The outline of this abstract is as follows. In Section 2 we will review the definition of the affine symmetric group and list several of its useful properties. In Section 3 we will outline the proof of Theorem 1. Finally, in Section 4 we will give some basic results and conjectures for $f^p(t)$ for the patterns in $S_3$ and $S_4$. The full text of this paper has been submitted for publication and is currently available on the math arXiv:1002.1933.

## 2 Background

For $n \ge 2$, let $\tilde{S}_n$ denote the set of all bijections $\omega : \mathbb{Z} \to \mathbb{Z}$ with $\omega(i + n) = \omega(i) + n$ for all $i \in \mathbb{Z}$ and

$$\sum_{i=1}^{n} \omega(i) = \binom{n+1}{2}. \qquad (5)$$
$\tilde{S}_n$ is called the affine symmetric group, and the elements of $\tilde{S}_n$ are called affine permutations. This definition of affine permutations first appeared in (Lusztig, 1983, §3.6) and was then developed in Shi (1986). Note that $\tilde{S}_n$ also occurs as the affine Weyl group of type $\tilde{A}_{n-1}$.

We can view an affine permutation in its one-line notation as the infinite string of integers

$$ \cdots \omega_{-1} \omega_0 \omega_1 \cdots \omega_n \omega_{n+1} \cdots, $$

where, for simplicity of notation, we write $\omega_i = \omega(i)$. An affine permutation is completely determined by its action on $[n] := \{1, \dots, n\}$. Thus we only need to record the base window $[\omega_1, \dots, \omega_n]$ to capture all of the information about $\omega$. Sometimes, however, it will be useful to write down a larger section of the one-line notation.

Given $i \neq j$ mod $n$, let $t_{ij}$ denote the affine transposition that interchanges $i + mn$ and $j + mn$ for all $m \in \mathbb{Z}$ and leaves all $k$ not congruent to $i$ or $j$ fixed. Since $t_{ij} = t_{i+n,j+n}$ in $\tilde{S}_n$, it suffices to assume $1 \le i \le n$ and $i < j$. Note that if we restrict to the affine permutations with $\{\omega_1, \dots, \omega_n\} = [n]$, then we get a subgroup of $\tilde{S}_n$ isomorphic to $S_n$, the group of permutations of $[n]$. Hence if $1 \le i < j \le n$, the above notion of transposition is the same as for the symmetric group.

Given a permutation $p \in S_k$ and an affine permutation $\omega \in \tilde{S}_n$, we say that $\omega$ contains the pattern $p$ if there is a subsequence of integers $i_1 < \dots < i_k$ such that the subword $\omega_{i_1} \cdots \omega_{i_k}$ of $\omega$ has the same relative order as the elements of $p$. Otherwise, we say that $\omega$ avoids $p$. For example, if $\omega = [8, 1, 3, 5, 4, 0] \in \tilde{S}_6$, then 8,1,5,0 is an occurrence of the pattern 4231 in $\omega$, so that $\omega$ contains $p$. However, $\omega$ avoids the pattern 3412. A pattern can also come from terms outside of the base window $[\omega_1, \dots, \omega_n]$. In the previous example, $\omega$ also has 2,8,6 as an occurrence of the pattern 132. Choosing a subword $\omega_{i_1} \cdots \omega_{i_k}$ with the same relative order as $p$ will be referred to as placing $p$ in $\omega$.

## 2.1 Coxeter Groups

For a general reference on the basics of Coxeter groups, see Björner and Brenti (2005) or Humphreys (1990). Let $S = \{s_1, \dots, s_n\}$ be a finite set, and let $F$ denote the free group consisting of all words of finite length whose letters come from $S$. Here the group operation is concatenation of words, so that the empty word is the identity element. Let $M = (m_{ij})_{i,j=1}^n$ be any symmetric $n \times n$ matrix whose entries come from $\mathbb{Z}_{>0} \cup \{\infty\}$ with 1's on the diagonal and $m_{ij} > 1$ if $i \neq j$. Then let $N$ be the normal subgroup of $F$ generated by the relations

$$ R = \{(s_i s_j)^{m_{ij}} = 1\}_{i,j=1}^n. $$

If $m_{ij} = \infty$, then there is no relationship between $s_i$ and $s_j$. The Coxeter group corresponding to $S$ and $M$ is the quotient group $W = F/N$.

Any $w \in W$ can be written as a product of elements from $S$ in infinitely many ways. Every such word will be called an *expression* for $w$. Any expression of minimal length will be called a *reduced expression*, and the number of letters in such an expression will be denoted $\ell(w)$, the *length* of $w$. Call any element of $S$ a *simple reflection* and any element conjugate to a simple reflection, a *reflection*.

We graphically encode the relations in a Coxeter group via its *Coxeter graph*. This is the labeled graph whose vertices are the elements of $S$. We place an edge between two vertices $s_i$ and $s_j$ if $m_{ij} > 2$ and we label the edge $m_{ij}$ whenever $m_{ij} > 3$. The Coxeter graphs of all the finite Coxeter groups have been classified. See, for example, (Humphreys, 1990, §2).
In (Björner and Brenti, 2005, §8.3) it was shown that $\tilde{S}_n$ is the Coxeter group with generating set $S = \{s_0, s_1, \dots, s_{n-1}\}$, and relations

$$R = \begin{cases} s_i^2 = 1, & \text{if } |i-j| \ge 2, \\ (s_i s_j)^2 = 1, & (s_i s_{i+1})^3 = 1, & \text{for } 0 \le i \le n-1, \end{cases}$$

where all of the subscripts are taken mod $n$. Thus the Coxeter graph for $\tilde{S}_n$ is an $n$-cycle, where every edge is unlabeled.

<figure><img src="image_1.png" /><figcaption>Fig. 1: Coxeter graph for $\tilde{S}_n$.</figcaption></figure>

If $J \subsetneq S$ is a proper subset of $S$, then we call the subgroup of $W$ generated by just the elements of $J$ a parabolic subgroup. Denote this subgroup by $W_J$. In the case of the affine symmetric group we have the following characterization of parabolic subgroups, which follows easily from the fact that when $J = S \setminus \{s_i\}$, $(\tilde{S}_n)_J = \text{Stab}([i, i + n - 1])$ (Björner and Brenti, 2005, Proposition 8.3.4).

**Proposition 2** Let $J = S \setminus \{s_i\}$. Then $\omega \in \tilde{S}_n$ is in the parabolic subgroup $(\tilde{S}_n)_J$ if and only if there exists some integer $i \le j \le i + n - 1$ such that $\omega_j \le \omega_k < \omega_j + n$ for all $i \le k \le i + n - 1$.

## 2.2 Length Function for $\tilde{S}_n$

For $\omega \in \tilde{S}_n$, let $\ell(\omega)$ denote the length of $\omega$ when $\tilde{S}_n$ is viewed as a Coxeter group. Recall that for a non-affine permutation $\pi \in S_n$ we can define an inversion as a pair $(i, j)$ such that $i < j$ and $\pi_i > \pi_j$. For an affine permutation, if $\omega_i > \omega_j$ for some $i < j$, then we also have $\omega_{i+kn} > \omega_{j+kn}$ for all $k \in \mathbb{Z}$. Hence any affine permutation with a single inversion has infinitely many inversions. Thus we standardize each inversion as follows. Define an affine inversion as a pair $(i, j)$ such that $1 \le i \le n$, $i < j$, and $\omega_i > \omega_j$. If we let $\text{Inv}_{\tilde{S}_n}(\omega)$ denote the set of all affine inversions in $\omega$, then $\ell(\omega) = \#\text{Inv}_{\tilde{S}_n}(\omega)$, (Björner and Brenti, 2005, Proposition 8.3.1).

We also have the following characterization of the length of an affine permutation, which will be useful later.

**Theorem 3** (Shi, 1986, Lemma 4.2.2) Let $\omega \in \tilde{S}_n$. Then

$$\ell(\omega) = \sum_{1 \le i < j \le n} \left| \left\lfloor \frac{\omega_j - \omega_i}{n} \right\rfloor \right| = \text{inv}(\omega_1, \dots, \omega_n) + \sum_{1 \le i < j \le n} \left\lfloor \frac{|\omega_j - \omega_i|}{n} \right\rfloor, \quad (6)$$

where $\text{inv}(\omega_1, \dots, \omega_n) = \#\{1 \le i < j \le n : \omega_i > \omega_j\}$.
For $1 \le i \le n$ define $\mathrm{Inv}_i(\omega) = \#\{j \in \mathbb{N} : i < j, \omega_i > \omega_j\}$. Now let $\mathrm{Inv}(\omega) = (\mathrm{Inv}_1(\omega), \dots, \mathrm{Inv}_n(\omega))$, which will be called the *affine inversion table* of $\omega$. In (Björner and Brenti, 1996, Theorem 4.6) it was shown that there is a bijection between $\tilde{S}_n$ and elements of $\mathbb{Z}_{\ge 0}^n$ containing at least one zero entry.

### 3 Outline of Proof of Theorem 1

The Proof of Theorem 1 is broken up into two parts. First, if $p \in S_m$ contains the pattern 321, then we exhibit an infinite family of affine permutations, all of which avoid 321 and hence avoid $p$. Second, if $p$ avoids the pattern 321, then we show that there exists a constant $L$, depending on $p$, such that if $\ell(\omega) > L$, then $\omega$ must contain $p$ as follows. Using the length formula in Theorem 3, if $\ell(\omega)$ is large, then there must be two indices $1 \le i < j \le n$ with $|\omega_i - \omega_j|$ large. Once $|\omega_i - \omega_j|$ is large enough, we then show how to use translates $\omega_{i+rn}$ and $\omega_{j+sn}$ of $\omega_i$ and $\omega_j$ to construct an occurrence of $p$ in $\omega$. Hence if $\omega$ avoids $p$, $\ell(\omega)$ must be bounded above, so that there can be only a finite number of such $\omega$.

The algorithm for constructing an occurrence of $p$ gives the length bound $\ell(\omega) \le (m^{\ell+1} + 2)\binom{n}{2}$, where $p \in S_m$, $\omega \in \tilde{S}_n$ and $\ell$ is the length of the sequence of left-to-right maxima in $p$. In general, this upper bound is much larger than needed. For example, let $p = 3412 \in S_4$. Then our algorithm gives that if $\omega \in \tilde{S}_n$ avoids $p$, then $\ell(\omega) \le 66\binom{n}{2}$. However, we can actually prove a tighter bound $\ell(\omega) \le 3\binom{n}{2}$ for this particular pattern. Thus it would be nice to find an algorithm that gives a tighter upper bound on length.

### 4 Generating Functions for Patterns in $S_3$ and $S_4$

Let $f_n^p$ and $f^p(t)$ be as in (1) and (2) in Section 1. Then by Theorem 1 we have $f_n^{321} = \infty$ for all $n$. However, for all of the other patterns $p \in S_3$ we can still compute $f^p(t)$.

**Theorem 4** Let $f^p(t)$ be as above. Then

$$f^{123}(t) = 0, \qquad (7)$$

$$f^{132}(t) = f^{213}(t) = \sum_{n=2}^{\infty} t^n, \qquad (8)$$

$$f^{231}(t) = f^{312}(t) = \sum_{n=2}^{\infty} \binom{2n-1}{n} t^n. \qquad (9)$$

The only tricky part in the proof of Theorem 4 is Equation 9. The proof involves using the affine inversion table of an affine permutation and some identities amongst the Catalan numbers.

We now look at pattern avoidance for patterns in $S_4$. There are 24 patterns to consider, although for all but three patterns, $f^p(t)$ is easy to compute. First let

$$P = \{1432, 2431, 3214, 3241, 3421, 4132, 4213, 4231, 4312, 4321\}.$$

By Theorem 1, if $p \in P$, then $f_n^p = \infty$, so $f^p(t)$ is not defined.
**Theorem 5** We have

$$f^{1234}(t) = 0, \qquad (10)$$

$$f^{1243}(t) = f^{1324}(t) = f^{2134}(t) = f^{2143}(t) = \sum_{n=2}^{\infty} t^n, \qquad (11)$$

$$f^{1342}(t) = f^{1423}(t) = f^{2314}(t) = f^{3124}(t) = \sum_{n=2}^{\infty} \binom{2n-1}{n} t^n. \qquad (12)$$

Based on some initial calculations, we also have the following conjectures for the remaining three patterns in $S_4$.

**Conjecture 1** The following equalities hold:

$$f_n^{3142} = \sum_{k=0}^{n-1} \frac{(n-k)}{n} \binom{n-1+k}{k} 2^k \qquad (13)$$

$$f_n^{3412} = f_n^{4123} = \frac{1}{3} \sum_{k=0}^{n} \binom{n}{k}^2 \binom{2k}{k}. \qquad (14)$$

Note that (13) is sequence A064062 and (14) is sequence A087457 in Sloane (2009). It is also worth comparing (14) to the number of 3412-avoiding, non-affine permutations given in (Gessel, 1990, §7) as

$$u_3(n) = 2 \sum_{k=0}^{n} \binom{n}{k}^2 \binom{2k}{k} \frac{3k^2 + 2k + 1 - n - 2kn}{(k+1)^2(k+2)(n-k+1)}. \qquad (15)$$

## Acknowledgements

The author would like to thank Brant Jones for inspiring him to ask this question and Sara Billey for all of her guidance and helpful conversations. He is also indebted to Neil Sloane and his team, whose encyclopedia of integer sequences was invaluable for forming the conjectures in this paper.

## References

S. Billey and S. A. Mitchell. Affine partitions and affine Grassmannians. *Electron. J. Combin.*, 16(2): Research Paper 18, 45 pp. (electronic), 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; 3-540-44238-3.

A. Björner and F. Brenti. Affine permutations of type A. *Electron. J. Combin.*, 3(2):Research Paper 18, approx. 35 pp. (electronic), 1996. ISSN 1077-8926. The Foata Festschrift.
I. M. Gessel. Symmetric functions and P-recursiveness. *J. Combin. Theory Ser. A*, 53(2):257–285, 1990.
ISSN 0097-3165. doi: 10.1016/0097-3165(90)90060-A. URL http://dx.doi.org/10.1016/
0097-3165(90)90060-A.

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

C. Hanusa and B. Jones. The enumeration of fully commutative affine permutations. preprint, math.CO/0907.0709v1, July 2009.

J. E. Humphreys. *Reflection groups and Coxeter groups*, volume 29 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1990. ISBN 0-521-37510-X.

D. E. Knuth. *The art of computer programming. Volume 3*. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching, Addison-Wesley Series in Computer Science and Information Processing.

V. Lakshmibai and B. Sandhya. Criterion for smoothness of Schubert varieties in $Sl(n)/B$. *Proc. Indian Acad. Sci. Math. Sci.*, 100(1):45–52, 1990. ISSN 0253-4142.

G. Lusztig. Some examples of square integrable representations of semisimple $p$-adic groups. *Trans. Amer. Math. Soc.*, 277(2):623–653, 1983. ISSN 0002-9947.

A. Marcus and G. Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. *J. Combin. Theory Ser. A*, 107(1):153–160, 2004. ISSN 0097-3165.

J. Y. Shi. *The Kazhdan-Lusztig cells in certain affine Weyl groups*, volume 1179 of *Lecture Notes in Mathematics*. Springer-Verlag, Berlin, 1986. ISBN 3-540-16439-1.

N. J. A. Sloane. Online encyclopedia of integer sequences. http://www.research.att.com/~njas/sequences/, 2009.

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

B. E. Tenner. Pattern avoidance and the Bruhat order. *J. Combin. Theory Ser. A*, 114(5):888–905, 2007. ISSN 0097-3165.

B. E. Tenner. Database of permutation pattern avoidance. http://math.depaul.edu/~bridget/patterns.html, 2009.

J. West. *Permutations with forbidden sequences; and, stack-sortable permutations*. PhD thesis, Massachusetts Institute of Technology, September 1990.