Reduced word manipulation: patterns and enumeration

Abstract

We develop the technique of reduced word manipulation to give a range of results concerning reduced words and permutations more generally. We prove a broad connection between pattern containment and reduced words, which specializes to our previous work for vexillary permutations. We also analyze general tilings of Elnitsky’s polygon and demonstrate that these are closely related to the patterns in a permutation. Building on previous work for commutation classes, we show that reduced word enumeration is monotonically increasing with respect to pattern containment. Finally, we give several applications of this work. We show that a permutation and a pattern have equally many reduced words if and only if they have the same length (equivalently, the same number of 21-patterns) and that they have equally many commutation classes if and only if they have the same number of 321-patterns. We also apply our techniques to enumeration problems of pattern avoidance and give a bijection between 132-avoiding permutations of a given length and partitions of that same size, as well as refinements of these data and a connection to the Catalan numbers.

1 Introduction

The reduced words of a permutation w are strings of positive integers that describe the ways to write w as a product of adjacent transpositions. These data have connections to Coxeter groups of other types and an influence on the structure of various objects related to permutations. Additionally, the Bruhat order on the symmetric group can be defined in terms of reduced words, and thus they are key to understanding the structure of this important poset (see, for example, [11, 13,14,15, 22, 30] for progress on elucidating this architecture and that of related objects).

In [29], we revealed a powerful relationship between reduced words and permutation patterns in the case of a vexillary permutation. That result had a range of algebraic, topological, and enumerative applications, addressing questions about commutation classes of reduced words, tilings of certain families of polygons, and the topological structure of a family of algebraic objects. In the present work, we expand the manipulative techniques on reduced words that we debuted in [29]. This will enable us to show that the main result of [29] is a special case of a broader phenomenon. Moreover, we employ these methods and that general phenomenon to give enumerative results about reduced words and commutation classes of permutations and the patterns that contain them, extending Stanley’s analysis of reduced word enumeration in [26] and our own work in [29, 30].

There are many ways to represent permutations, including reduced words and one-line notation. The latter is the most natural presentation for questions about patterns, a concept that gained broad attention after work of Simion and Schmidt [23], and that has since become popular in many guises (see, for example, Kitaev’s text [16] and the various special journal issues devoted to the topic, including [24]). The first hint of a direct connection between reduced words and permutation patterns appeared in [5], where Billey, Jockusch, and Stanley proved that 321-avoidance was equivalent to avoiding $i(i\pm 1)i$ factors in reduced words. We gave a broader relationship between reduced words and permutation patterns in [29], showing that a permutation p is vexillary if and only if, roughly speaking, reduced words of p can appear as isolated factors in reduced words of w, for all w containing p. That result had a number of applications, notably involving tilings of the polygon X(w), whose rhombic tilings were shown to be in bijection with commutation classes of reduced words of w by Elnitsky [12].

The “manipulation” in the title of this paper refers to the techniques we employ in this work. More precisely, our approach to analyzing features of a permutation (and its reduced words) will often include shortening it via a sequence of targeted position and value swaps, where these swaps correspond to right and left multiplication (respectively) by adjacent transpositions. This technique can be highly revealing about the reduced words of a permutation, as we shall see in subsequent sections, and can expose enumerative phenomena that have been hitherto unrecognized.

In Sect. 2 of this paper, we discuss terminology and symbols relevant to this work, including examples of the basic objects under examination here. Section 3 introduces the main manipulative techniques we apply to reduced words and gives the first main result of these efforts in Theorem 3.9. That theorem gives the broad relationship described earlier, between containment of a p-pattern and the influence of p’s reduced words on the reduced words of the larger permutation. The next two sections of the paper are concerned with applications of Theorem 3.9 and, more generally, with the manipulative techniques used in the proof of that result. To be precise, Sect. 4 shows how pattern containment influences the tiling of a particular polygon used in the study of Coxeter groups, with the culminating result given in Corollary 4.18. In Sect. 5, we apply our manipulative techniques to enumerative questions about commutation classes of permutations and to the number of reduced words of a permutation as they relate to those of its patterns. Each of these quantities is monotonically increasing with respect to pattern containment (Proposition 5.2; Theorem 5.3), and we can describe exactly when equality occurs in each case (Theorems 5.5, 5.7). We also show how our methods can be employed to enumeration problems of pattern avoidance and demonstrate this by giving a bijection between 132-avoiding permutations of length $\ell$ and partitions of $\ell$ (Theorem 5.15). This bijection has additional implications, related to the number of restricted partitions and to the Catalan numbers (Corollaries 5.17, 5.20).

2 Definitions and notation

We are concerned with the symmetric group, also known as the finite Coxeter group of type A. In this section, we introduce the relevant definitions and notation, and additional background on these objects can be found in the literature, such as in [7, 19].

We write ${\mathfrak S}_n$ for the symmetric group on $\{1,\ldots ,n\}$, and a permutation $w \in {\mathfrak S}_n$ is represented in one-line notation as the word $w = w(1)w(2)\cdots w(n)$.

The adjacent transpositions in ${\mathfrak S}_n$ are $\{\sigma _i: 1 \le i < n\}$, where $\sigma _i$ transposes i and $i+1$ and fixes all other letters. These involutions generate ${\mathfrak S}_n$ and obey the Coxeter relations

$$\begin{aligned}&\sigma _i\sigma _j = \sigma _j\sigma _i \qquad \qquad \qquad \,\,\, \text { if } |i-j| > 1, \text { and} \end{aligned}$$

(1)

$$\begin{aligned}&\sigma _i\sigma _{i+1}\sigma _i = \sigma _{i+1}\sigma _i\sigma _{i+1} \quad \text { for } 1 \le i \le n-2. \end{aligned}$$

(2)

The relation in Eq. (1) is a commutation, and the relation in Eq. (2) is a braid. Because $\{\sigma _i: 1 \le i < n\}$ generates ${\mathfrak S}_n$, each $w \in {\mathfrak S}_n$ can be written as a product of adjacent transpositions, where we view permutations as maps and thus $\sigma _iv$ transposes the positions of the values i and $i+1$ in v, whereas $v\sigma _i$ transposes the values in positions i and $i+1$ in v.

Definition 2.1

If $w = \sigma _{i_1} \cdots \sigma _{i_{\ell }}$ for $\ell$ minimal, then $\ell = \ell (w)$ is the length of w, the product

$$\begin{aligned} \sigma _{i_1} \cdots \sigma _{i_{\ell }} \end{aligned}$$

is a reduced decomposition of w, and the string

$$\begin{aligned} \mathsf{i_1\cdots i_{\ell }} \end{aligned}$$

is a reduced word of w. The set of all reduced words of w is denoted R(w).

We will use sans-serif typeface for reduced words, thus distinguishing them from permutations in one-line notation.

Note that length can be calculated by counting inversions: $\ell (w) = \big |\{i<j : w(i) > w(j)\}\big |$.

Reduced decompositions and reduced words are in obvious bijection with each other, and the terms “commutation” and “braid” transfer to the context of reduced words in the natural way.

Example 2.2

Consider $3241 \in {\mathfrak S}_4$. Its reduced decompositions are $\sigma _2\sigma _1\sigma _2\sigma _3$, $\sigma _1\sigma _2\sigma _1\sigma _3$, and $\sigma _1\sigma _2\sigma _3\sigma _1$, and thus

$$\begin{aligned} R(3241) = \{\mathsf{2123}, \mathsf{1213}, \mathsf{1231}\}. \end{aligned}$$

The first two elements of R(3241) differ by a braid, while the latter two elements differ by a commutation.

Reduced words are strings, and we will sometimes view them as nothing more than that.

Definition 2.3

A factor in a string is a consecutive substring. Shifting a string by x means adding a fixed value x to each symbol in the string. When specificity is not needed, we will suppress the expression “by x”.

A permutation in one-line notation is itself a string, and we will have use for the following concept.

Definition 2.4

Two strings, whose letters are drawn from a totally ordered set, are isomorphic if their symbols appear in the same relative order. We use $\approx$ to denote this (equivalence) relation.

Example 2.5

$42135 \approx 82(-4)\pi \sqrt{95}$.

The notion of isomorphic strings is central to the definition of permutation patterns.

Definition 2.6

Fix $p \in {\mathfrak S}_k$. A permutation w contains a p -pattern, denoted $p \prec w$, if $p \approx w(i_1)\cdots w(i_k)$ for some $i_1< \cdots < i_k$. This $w(i_1)\cdots w(i_k)$ is an occurrence of p, and we may denote $w(i_j)$ by $\langle p(j) \rangle$. If w does not contain a p-pattern, then w avoids p or is p -avoiding, denoted $p \not \prec w$. For a set of patterns P, write

Pattern containment depends on there being at least one occurrence of the pattern, but the (positive) multiplicity of occurrences is unimportant.

Example 2.7

The permutation 42135 contains the pattern 213, and it does so in five ways: $425 \approx 415 \approx 435 \approx 213 \approx 215$. The permutation 45132 is 213-avoiding, so $213\not \prec 45132$.

Theorem 3.9 of this article gives a potential relationship between elements of R(p) and elements of R(w) when $p \prec w$. That result, which will specialize to the main result of [29], involves an object that is most easily described as a set of the “barred” patterns introduced by West in [32].

Definition 2.8

A barred pattern $\overline{p}$ is a permutation p in which some letters are decorated by bars. A permutation w contains $\overline{p}$, denoted $\overline{p} \prec w$, if w has an occurrence of the undecorated portion of $\overline{p}$ that is not also part of a larger p-pattern.

Example 2.9

Let $w = 42135$ and $\overline{p} = 3\overline{2}14$. Thus $3\overline{2}14 \prec 42135$ because $\langle 213 \rangle = 213$ is not part of any 3214-pattern in w. We could not have drawn this conclusion from $\langle 213 \rangle = 415$, because of $\langle 3214 \rangle = 4215$ in w.

Note that barred patterns can also be expressed in the more general language of mesh patterns, as introduced in [9].

Our work in [29] gave a new definition of vexillary permutations. The feature of non-vexillary permutations that caused trouble was that a 2143-pattern could be “spread out,” both in position and value by inserting a letter between the 1 and the 4 to yield the permutation 21354. Let us capture this phenomenon more precisely.

Definition 2.10

Fix $p \in {\mathfrak S}_k$. A barred pattern $\overline{q}$ is a spread of p if its undecorated portion is isomorphic to p itself and if $q \in {\mathfrak S}_{k+1}$ is obtained by inserting a letter (barred in $\overline{q}$) to transform a 2143-pattern in p into a 21354 pattern. In the degenerate case, when p avoids 2143, the only spread of p is p itself. Write $p^+$ for the set of spreads of p.

Note that a permutation may have more than one spread.

Example 2.11

$251364^+ = \{261\overline{3}475, 2614\overline{3}75, 261\overline{4}375, 2613\overline{4}75\}$.

3 Influence of patterns on reduced words

The main result of [29] was a relationship between containing a pattern p and implications for one’s reduced words in terms of the reduced words of p. That relationship, presented here as Corollary 4.1, held if and only if p was vexillary; that is, if and only if p avoided 2143. Vexillary permutations were introduced independently by Lascoux and Schützenberger [18] and by Stanley [26]. There are several equivalent definitions of vexillary, such as 2143-avoidance, the one given in the main result of [29], and others as discussed in [19].

In Theorem 3.9 below, we establish that elements of R(p) appear as particular factors in elements of R(w) if and only if . Moreover, these factors should not be unduly influenced by their prefix or suffix, as expressed in the following definitions.

Definition 3.1

Fix $w \in {\mathfrak S}_n$ and consider $\mathsf{s} \in R(w)$, where $\mathsf{s} = \mathsf{abc}$ is the concatenation of three (possibly empty) strings with $\mathsf{a} \in R(u)$ and $\mathsf{c} \in R(v)$. The factor $\mathsf{b}$ is isolated on $[m,m']$ in $\mathsf{s}$ if there are integers $m \le r \le t \le m'$ such that

• (1) the smallest letter appearing in $\mathsf{b}$ is r and the largest letter appearing in $\mathsf{b}$ is t,

• (2) $\ell (u \sigma _i)> \ell (u)$ and $\ell (\sigma _i v) > \ell (v)$ for all $i \in [r,t]$, and

• (3) there are two particular increasing patterns in each of u and v:

  • (a) in u, an increasing sequence of length $r-m+1$ ends in position r, and an increasing sequence of length $m' - t + 1$ begins in position $t+1$, and

  • (b) in v, an increasing sequence of length $r-m+1$ ends with the value r, and an increasing sequence of length $m'-t+1$ begins with the value $t+1$.

While the concept of a factor is relatively common, isolation is unusual enough—and important enough in the context of this work—to merit some examples.

Example 3.2

Consider the reduced word $\mathsf{s} = \mathsf{12325} \in \mathsf{R(243165)}$.

• (a) Define the factor $\mathsf{b} = \mathsf{2}$ so that $\mathsf{a} = \mathsf{1}$ and $\mathsf{c} = \mathsf{325}$. Thus $r = t = 2$. This $\mathsf{b}$ is not isolated on [1, 2] in $\mathsf{s}$ because, in the language of Definition 3.1, $u = 213456$ and $\ell (u\sigma _1) < \ell (u)$.

• (b) Now define the factor $\mathsf{b} = \mathsf{2}$ so that $\mathsf{a} = \mathsf{123}$ and $\mathsf{c} = \mathsf{5}$. Thus $r = t = 2$. This $\mathsf{b}$ is isolated on [1, 2] in $\mathsf{s}$ because $u = 234156$ and $v = 123465$, and both $\ell (u\sigma _i) > \ell (u)$ and $\ell (\sigma _iv) > \ell (v)$ for all $i \in [1,2]$.

Note that Definition 3.1 fixes a mistake in [29], in which it was inadvertently assumed that patterns would not begin or end with fixed points. In the language of Definition 3.1 above, we would have $m = r$ and $m' = t$ for such a situation, and so requirement (3) of the definition would be trivial. It should be noted that the applications of the main result of [29] are unaffected by this correction, and many of them do not even involve patterns with initial or concluding fixed points. Also, if we were to think of permutations as actions on ${\mathbb {Z}}$ that involve only finitely many elements, then requirement (3) of Definition 3.1 would again be trivial, because there would be increasing sequences of infinite length beginning or ending with any position or value.

Example 3.3

• (a) Consider the reduced word $\mathsf{23} \in \mathsf{R(13425)}$. Let $\mathsf{b} = 3$, $\mathsf{a} = 2$, and $\mathsf{c} = \emptyset$. Thus $r = t = 3$. Consider $m = 2$ and $m' = 4$. In the language of Definition 3.1, $u = 13245$ and $v = 12345$. First note that $\ell (u\sigma _3) > \ell (u)$ and $\ell (\sigma _3v) > \ell (v)$. Also, u has an increasing sequence of length $r-m+1 = 2$ ending in position $r = 3$ (the sequence 12), and an increasing sequence of length $m' - t + 1 = 2$ beginning in position $t + 1 = 4$ (the sequence 45). Similarly, v has the necessary increasing sequences. Thus this $\mathsf{b}$ is isolated on [2, 4] in $\mathsf{23}$.

• (b) In contrast, consider the reduced word $\mathsf{234} \in \mathsf{R(13452)}$. Again let $\mathsf{b} = 3$ and $\mathsf{a} = 2$, and so we now have $\mathsf{c} = 4$. Again $r = t = 3$, and we continue to consider $m = 2$ and $m' = 4$. In the language of Definition 3.1, $u = 13245$ and $v = 12354$. As before, $\ell (u\sigma _3) > \ell (u)$ and $\ell (\sigma _3v) > \ell (v)$, and although u has the required increasing sequences, the permutation v does not; specifically, it has no increasing sequence whose minimum value is $t + 1 = 4$. Thus this $\mathsf{b}$ is not isolated on [2, 4] in $\mathsf{234}$.

In our usage, the range $[m,m']$ of Definition 3.1 will be predetermined, as described below.

Definition 3.4

Fix $p \in {\mathfrak S}_k$. A reduced word for p that has been shifted by x is isolated in some $\mathsf{s}$ if it is isolated on $[x+1,x+k-1]$ in $\mathsf{s}$.

The importance of isolation arises from the following result, which describes when pattern containment might be affected by products of adjacent transpositions.

Lemma 3.5

Fix permutations p and w for which w has a p-pattern occupying positions P and using values V. If $\{i, i+1\}\not \subseteq V$, then

$$\begin{aligned} p \prec \sigma _iw. \end{aligned}$$

If $\{j, j+1\}\not \subseteq P$, then

$$\begin{aligned} p \prec w\sigma _j. \end{aligned}$$

Proof

If $\{i, i+1\}\not \subseteq V$, then $\sigma _iw$, which transposes the positions of the values i and $i+1$ in w, has a p-pattern occupying positions P. If $\{j, j+1\}\not \subseteq P$, then $w\sigma _j$, which transposes the values in positions j and $j+1$ in w, has a p-pattern using values V. $\square$

The following example demonstrates necessity of the hypotheses in Lemma 3.5.

Example 3.6

Consider $231 \prec 4231$, for which $P = \{2,3,4\}$ and $V = \{1,2,3\}$. The permutation

$$\begin{aligned} \sigma _3(4231) = 3241 \end{aligned}$$

has a 231-pattern in occupying positions P, and

$$\begin{aligned} (4231)\sigma _1 = 2431 \end{aligned}$$

has a 231-pattern using values V. On the other hand, the following permutations are all 231-avoiding:

$$\begin{aligned} \sigma _1(4231)= & {} 4132,\\ \sigma _2(4231)= & {} 4321,\\ (4231)\sigma _2= & {} 4321,\\ (4231)\sigma _3= & {} 4213. \end{aligned}$$

The influence of isolation in Lemma 3.5 will be important to the proof of Theorem 3.9. Indeed, that argument will be constructive and will involve manipulation of the permutation w via the following mechanism.

Corollary 3.7

Fix permutations p and w and suppose that elements of R(p) appear as shifted isolated factors in elements of R(w). Then $p \prec w$. Moreover, if w has a p-pattern in positions P and using values V, then for $\{i, i+1\}\not \subseteq V$ and $\{j, j+1\}\not \subseteq P$,

• elements of R(p) appear as shifted isolated factors in elements of $R(\sigma _iw)$, and

• elements of R(p) appear as shifted isolated factors in elements of $R(w\sigma _j)$.

Proof

This can be proved by induction on $\ell (w) - \ell (p)$. $\square$

The next lemma gives the basis of the inductive argument in the proof of Theorem 3.9.

Lemma 3.8

Suppose there is an occurrence of p in w that either occupies consecutive positions or uses consecutive values. Then elements of R(p) appear as shifted isolated factors in elements of R(w).

Proof

Suppose that $p \in {\mathfrak S}_k$ and $\langle p \rangle$ occupies positions $\{x+1,\ldots , x+k\}$ of w. Let $w'$ be the permutation obtained by writing the letters of $\langle p \rangle$ in increasing order and leaving all other letters fixed. Thus $\ell (w') = \ell (w) - \ell (p)$. Consider any $\mathsf{s} \in R(p)$ and $\mathsf{t} \in R(w')$, and let $\mathsf{s'}$ be the shift of $\mathsf{s}$ by x. Then the word $\mathsf{ts'}$ represents a product of adjacent transpositions that produces w. This word has length $\ell (w') + \ell (p) = \ell (w)$, so $\mathsf{ts'} \in R(w)$, as desired. If $\mathsf{s'}$ were not isolated in $\mathsf{ts'}$, then w would not have a p-pattern in positions $\{x+1,\ldots , x+k\}$. Thus $\mathsf{s'}$ must be isolated.

The case of $\langle p \rangle$ using consecutive values is analogous, with the shifted reduced word of p occurring as a factor on the left side in the reduced word of w. $\square$

We are now ready for the main result of this section. Its proof is inductive, measured by how far the occurrences of p are from satisfying the hypothesis of Lemma 3.8. When , the proof constructs an element of R(w) that contains an isolated shift of any R(p) element as a factor.

Theorem 3.9

Elements of R(p) appear as shifted isolated factors in elements of R(w) if and only if .

Proof

Fix $p \in {\mathfrak S}_k$.

First suppose that elements of R(p) appear as shifted isolated factors in elements of R(w). Then, by Corollary 3.7, we have $p \prec w$. Let $\mathsf{abc} \in R(w)$ be such a reduced word, where $\mathsf{b}$ is a shifted element of R(p) that is isolated in $\mathsf{abc}$. Then $\mathsf{b} \in R(p')$, where

$$\begin{aligned} p'(i) = {\left\{ \begin{array}{ll} p(i-x) + x &{} \text {if } i \in [x+1,x+k] \text { and}\\ i &{} \text {otherwise,} \end{array}\right. } \end{aligned}$$

for some x. The letters of $\mathsf{a}$ act on $p'$ by lengthening the permutation via transpositions of consecutive values. Because $\mathsf{b}$ is isolated and $\mathsf{a}$ is reduced, this procedure never transposes two values that are both in the pattern occurrence. Similarly, the reduced word $\mathsf{c}$ acts on that resulting permutation by lengthening it via transpositions of consecutive positions, never transposing two positions that are both in the pattern occurrence. The conclusion of these actions yields the permutation w. Consider any 2143-pattern in p. The “lengthening” requirement of both $\mathsf{a}$ and $\mathsf{c}$ makes it impossible to move some $y \in (\langle 2 \rangle , \langle 3 \rangle )$ into the middle of a 2143-pattern in p unless it is swapping positions with some other $y' \in (\langle 2 \rangle ,\langle 3 \rangle )$. Thus the only such values in w must have been in p itself, and so .

For the remainder of the proof, suppose that . We will induct on a statistic $\mathsf{gap}$ defined as follows. For a given $\langle p \rangle$ in w, let

$$\begin{aligned} \mathsf{gap_{pos}}(\langle p \rangle ,w) = \Big (w^{-1}\big (\langle p(k) \rangle \big ) - w^{-1}\big (\langle p(1) \rangle \big )\Big ) - (k-1) \end{aligned}$$

measure any excessive positional span of $\langle p \rangle$ in w, and

$$\begin{aligned} \mathsf{gap_{val}}(\langle p \rangle ,w) = \big (\langle k \rangle - \langle 1 \rangle \big ) - (k-1) \end{aligned}$$

measure any excessive value span. Both are nonnegative, and $\mathsf{gap_{pos}}(\langle p \rangle ,w) = 0$ if and only if $\langle p \rangle$ appears in consecutive positions of w, while $\mathsf{gap_{val}}(\langle p \rangle ,w) = 0$ if and only if $\langle p \rangle$ uses consecutive values in w. Now set

$$\begin{aligned} \mathsf{gap}(p,w) = \min _{\langle p \rangle \text { in } w} \Big \{ \mathsf{gap_{pos}}(\langle p \rangle ,w) + \mathsf{gap_{val}}(\langle p \rangle ,w)\Big \}. \end{aligned}$$

If $\mathsf{gap}(p,w) = 0$, then some $\langle p \rangle$ appears in consecutive positions in w and with consecutive values. By Lemma 3.8, then, the result holds.

Assume, inductively, that the result holds for all with $\mathsf{gap}(q,v) < \mathsf{gap}(p,w)$. Fix an occurrence $\langle p \rangle$ in w for which $\mathsf{gap}(p,w) = \mathsf{gap_{pos}}(\langle p \rangle ,w) + \mathsf{gap_{val}}(\langle p \rangle ,w)$.

Call each $\langle p(i) \rangle$ a pattern entry. Call $x \not \in \langle p \rangle$ a position gap if it appears between $\langle p(1) \rangle$ and $\langle p(k) \rangle$ in the one-line notation of w, and a value gap if $\langle 1 \rangle< x < \langle k\rangle$. If either $\mathsf{gap_{pos}}(\langle p \rangle ,w)$ or $\mathsf{gap_{val}}(\langle p \rangle ,w)$ is 0 then we can apply Lemma 3.8 and be done, so assume that both are positive. Fix x to be the minimal position gap.

If x is less than all pattern entries appearing to its left, then multiply w on the right by adjacent transpositions to produce $w'$ in which x has been shifted to the left of the p-pattern, and the rest of the one-line notation is unchanged. This $w'$ contains an occurrence of p having the same values as $\langle p \rangle$ in w, but its positional span is one less than that of $\langle p \rangle$ in w. Thus $\mathsf{gap}(p,w') < \mathsf{gap}(p,w)$, and, because we never transposed two pattern entries in a single move, the result follows from the inductive hypothesis and Corollary 3.7.

If x is greater than all pattern entries appearing to its right, then in fact all position gaps are greater than those pattern entries. Multiply w on the right by adjacent transpositions to produce $w'$ in which the rightmost position gap has been shifted to the right of the p-pattern. Again, then, $\mathsf{gap}(p,w') < \mathsf{gap}(p,w)$, and the result follows from the inductive hypothesis and Corollary 3.7.

It remains to address when the following two situations occur simultaneously: a pattern entry less than x appears to the left of x in w, and a pattern entry greater than x appears to the right of x in w. Note that this implies existence of some m for which $\langle m \rangle< x < \langle m+1 \rangle$.

Suppose that the pattern entries that are both less than x and to its left appear in increasing order in w. The following procedure, which we call ($\dagger$), acts on a particular p-pattern and position gap in a permutation, and loops as necessary. Note that it never transposes two pattern entries in a single move.

• If $y = \langle m \rangle$ is to the left of x in w (necessarily the rightmost smaller pattern entry appearing to the left of x), then multiply w on the right by adjacent transpositions to produce $w'$ in which x has been shifted leftward until it abuts y. Each multiplication removes an inversion, shortening the permutation at each step. Moreover, the values of $\langle p \rangle$ still form a p-pattern in $w'$, as do the values of $\langle p \rangle$ with the exception of now using x instead of y. If y had been the leftmost pattern entry in w, then the revalued p-pattern has fewer position gaps than $\langle p \rangle$ had in w, so the result follows from the inductive hypothesis and Corollary 3.7. Otherwise, iterate ($\dagger$) using this new p-pattern in $w'$ and the position gap $y < x$.

• If $y = \langle m \rangle$ is to the right of x in w, then multiply w on the left by elements of $\{\sigma _i : y \le i < x\}$ to produce $w'$ in which $\{y, y + 1, \ldots , x\}$ appear in increasing order and no other letters have moved. By definition of x and m, this $w'$ contains a p-pattern in the same positions as $\langle p \rangle$ in w, and the only value that differs is some $y' > y$ now acting as “m” in the pattern. If $\mathsf{gap}(p,w') < \mathsf{gap}(p,w)$, then the result follows from the inductive hypothesis and Corollary 3.7. Otherwise, because the number of position gaps and value gaps have not changed with this revalued p-pattern, the measure $\mathsf{gap}(p,w')$ is obtained on it. Now iterate ($\dagger$) using this new p-pattern in $w'$ and the position gap $y < x$, which necessarily appears no further to the right in $w'$ than x had appeared in w.

When all pattern entries that are both greater than x and to its right form an increasing sequence in w, the argument is similar to ($\dagger$), with one additional step. Let $x'$ be the maximal position gap that does not appear to the left of x. Because $x' \ge x$, we in fact have that all pattern entries that are both greater than $x'$ and to its right appear in increasing order in w. Apply a procedure to $x'$ and its rightward larger pattern entries, analogous to the previous argument for x and its leftward smaller pattern entries.

We have now addressed all scenarios except one: when neither x’s leftward smaller pattern entries nor its rightward larger pattern entries forms an increasing sequence; that is,

$$\begin{aligned} w = \cdots \langle p(a) \rangle \cdots \langle p(b) \rangle \cdots x \cdots \langle p(c) \rangle \cdots \langle p(d)\rangle \cdots , \end{aligned}$$

for some

$$\begin{aligned} \langle p(b) \rangle< \langle p(a) \rangle< x< \langle p(d) \rangle < \langle p(c)\rangle . \end{aligned}$$

But this means exactly that , which is a contradiction. $\square$

There are two things in particular to observe about Theorem 3.9. First, if and $\mathsf{abc} \in R(w)$ with $\mathsf{b}$ a shifted isolated reduced word of p, then in fact we can replace $\mathsf{b}$ by that same shift of any reduced word of p. Second, the proof of Theorem 3.9 is constructive; that is, if then the proof produces reduced words of w that contain shifted reduced words of p as isolated factors.

4 Combinatorial influence of patterns on reduced words

One immediately corollary to Theorem 3.9 recovers the main result of [29].

Corollary 4.1

([29, Theorem 3.8]) A permutation p is vexillary if and only if for every $w \succ p$, elements of R(p) appear as shifted isolated factors in elements of R(w).

Proof

Combine Theorem 3.9 with the fact that p is vexillary if and only if $p^+ = \{p\}$.

$\square$

Theorem 3.9 also has applications for other objects, defined on a particular partition of the reduced words of a permutation.

Definition 4.2

Fix a permutation w and define a relation $\sim$ on the set R(w) such that $\mathsf{s} \sim \mathsf{t}$ if and only if $\mathsf{s}$ and $\mathsf{t}$ differ by a sequence of commutations. This $\sim$ is an equivalence relation, and the classes it defines are the commutation classes of w, denoted C(w).

Example 2.2

(continued). Observe that $\mathsf{1213} \sim \mathsf{1231}$. Thus the commutation classes of $3241 \in {\mathfrak S}_4$ are $\{\mathsf{2123}\}$ and $\{\mathsf{1213}, \mathsf{1231}\}$, and $|C(3241)| = 2$.

The commutation classes of a permutation do not take braids into account, but we can interpret the influence of those moves by means of a graph defined on commutation classes.

Definition 4.3

The graph of commutation classes (or, simply, “graph” for our purposes) of a permutation w has vertex set C(w), and an edge between classes when representatives of those classes differ by a braid move.

Example 4.4

Because the reduced words $\mathsf{2123}$ and $\mathsf{1213}$ differ by a braid move, we have

The sum of the letters in a reduced word is constant within a commutation class, and braid moves change the parity of this sum. Therefore, the graph G(w) is bipartite. It is also connected (see, for example, [12]).

In fact, we can say more about G(w) in light of Theorem 3.9.

Corollary 4.5

If , then G(p) is a subgraph of G(w).

Despite the natural definition of the classes C(w), they are not especially well understood. For example, we cannot yet enumerate $|C(n(n-1)\cdots 21)|$. In [12], Elnitsky defined a polygon X(w) whose rhombic tilings are in bijection with elements of C(w). This gives another perspective for working with commutation classes and can be quite fruitful. Indeed, we used Elnitsky’s polygon in [29] to show that pattern containment affects the number of these classes.

Proposition 4.6

([29, Theorem 5.10]) If $p \prec w$ then $|C(p)| \le |C(w)|$.

We now define Elnitsky’s polygon, and refer the reader to [12] for more details.

Definition 4.7

Fix a permutation $w \in {\mathfrak S}_n$. Elnitsky’s polygon, denoted X(w), is an equilateral 2n-gon in which the sides are labeled $1, \ldots , n, w(n), \ldots , w(1)$ in counterclockwise order from the top, the left half (labeled $1, \ldots , n$) is convex, and sides are parallel if and only if they have the same label. Any polygon of this form is an Elnitsky polygon.

Note that Elnitsky polygons permit a type of degeneracy when w has fixed points, in which circumstance the left and right borders of the polygon may coincide for one or more edges. Similarly, the left and right borders may intersect in a vertex if $\{w(1),\ldots ,w(r)\} = \{1,\ldots ,r\}$ for $w \in {\mathfrak S}_n$ and some $r < n$.

The specific angles in X(w) are unimportant. One could also replace the equilateral requirement by a rule that all parallel sides be congruent, but this adds no complexity to the object or the tilings of it that we will consider.

Example 4.8

Elnitsky looked at rhombic tilings of X(w).

Definition 4.9

Fix a permutation w. Let T(w) be the set of rhombic tilings of X(w) where all edges are congruent and parallel to edges of X(w).

Fig. 1

The two ways to tile a sub-hexagon in Elnitsky’s polygon

Define a graph with vertex set T(w) and an edge between two tilings if they differ only in the tiling of a single sub-hexagon, as in Fig. 1. Elnitsky proved in [12] that this graph is in bijection with the graph G(w) of commutation classes. In particular, this means that T(w) is in bijection with C(w). The details of Elnitsky’s bijection are useful to this work, and we review them here. Note that this is a slight variation of Elnitsky’s original bijection.

Proposition 4.10

([12, Theorem 2.2]) Fix $w \in {\mathfrak S}_n$ and $T \in T(w)$. Label the rhombi in T by $1, 2, \ldots$ from right to left, always labeling a rhombus that shares two edges with the rightmost border of X(w) or with tiles that have already been labeled. Use this labeling to create a string $\mathsf{s_{\ell (w)} \cdots s_2s_1}$, where $\mathsf{s_i = j}$ if the edges of tile i are $j\hbox {th}$ and $(j+1)$st in a path of length n from the topmost to the bottommost vertex in X(w). The map $T \rightarrow \mathsf{s_{\ell (w)} \cdots s_2s_1}$ gives a bijection between T(w) and C(w) because a given T produced all reduced words within a single commutation class of w.

Example 4.11

Elnitsky’s bijection for $3241 \in {\mathfrak S}_4$ is

because of $T_1$’s unique labeling

corresponding to $\{\mathsf{2123}\}$, and the two possible labelings of $T_2$

corresponding to $\{\mathsf{1213}, \mathsf{1231}\}$.

The breadth of Theorem 3.9 enables us to use more generic tiles in Elnitsky’s polygon.

Definition 4.12

Fix a permutation w and tile X(w) by other Elnitsky polygons, always oriented so that the lefthand path from the highest to the lowest vertex is convex. Let $T^*(w)$ be the set of such tilings, called paw tilings of X(w), and call each tile in $T \in T^*(w)$ a paw.

Note that $T(w) \subseteq T^*(w)$ because each rhombus is an X(21)-paw.

Example 4.13

Figure 2 gives an element of $T^*(352641)$. It has two X(21)-paws, one X(312)-paw, and one X(3421)-paw. All tile edges have been labeled for clarity.

Fig. 2

A paw tiling of X(352641), described in Example 4.13

In any tiling of X(w), the edges of a tile refer to its parallel edges along the border of X(w).

The procedure described in Elnitsky’s bijection (Proposition 4.10) builds a reduced word in a single direction. More precisely, labeling rhombi from the righthand side of X(w) corresponds to multiplying w on the right by adjacent transpositions (equivalently, reducing the length of w by swapping adjacent positions). Recall the algorithm laid out in the proof of Theorem 3.9. Whenever possible, the statistic $\mathsf{gap}(p,w)$ was reduced by means of position swaps (that is, right multiplication by adjacent transpositions). This was done intentionally, to match the rightward favoritism of Elnitsky’s bijection. However, there were two scenarios in the proof of Theorem 3.9 that required value swaps (that is, left multiplication). These were, using the terminology of that proof, the second bullet point of the loop $(\dagger )$, and its analogue when the leftward smaller pattern entries to x have a descent, but the rightward larger ones do not.

Definition 4.14

Suppose that $p \prec w$, and let S be a set of values forming a p-pattern in w. Call (p, w) a value-stable pair if $w = w'v$ for some permutations $w'$ and v such that

• $\ell (w) = \ell (w') + \ell (v)$ and

• a p-pattern occurs in consecutive positions of $w'$, and the set of values forming that pattern in $w'$ is S.

The p-pattern formed by S is the value-stable occurrence of the pair.

Note that requiring (p, w) to be value-stable is more restrictive than requiring that .

Example 4.15

• The pair (352641, 3421) is value-stable because $352641 = (352164)(123564)$. The value-stable occurrence that appears consecutively in 352164, which is also present in 352641, is 3521.

• The pair (241365, 21354) is not value-stable.

Using Elnitsky’s bijection, Theorem 3.9 has an immediate implication for the paw tilings in the context of value-stable pairs.

Corollary 4.16

If (p, w) is value-stable, then there is a paw tiling of X(w) that contains an X(p)-paw.

Fig. 3

Tiling X(321) with an X(312)-paw and a rhombus

Unfortunately, the converse to Corollary 4.16 is false. For example, there is a paw tiling of the convex hexagon X(321) that contains an X(312)-paw, as shown in Fig. 3. To understand when the converse to Corollary 4.16 might be true, we need a notion of “isolation” for paws.

Definition 4.17

Consider a permutation w and an X(p)-paw in some $T \in T^*(w)$. Let $S \subseteq T^*(w)$ be the paw tilings containing this particular X(p)-paw in this particular position, and tiling the rest of X(w) by rhombi. If no element of S has a rhombus sharing two edges with the righthand side of the X(p)-paw, then the X(p)-paw is isolated in T.

Observe that an $X(k\cdots 21)$-paw is necessarily isolated because no rhombus can share two edges with its convex righthand side.

Example 4.3

(continued). The X(3421)-paw in Fig. 2 is isolated, but the X(312)-paw is not because of its potential (in fact, required) adjacency to the rhombus with edges $\{1,4\}$.

The factor isolation described in Theorem 3.9 reveals, now, a biconditional analogue to Corollary 4.16. In other words, Corollary 4.18 describes exactly when we can fit an isolated X(p)-paw into a paw tiling of X(w).

Corollary 4.18

There is a paw tiling of X(w) containing an isolated X(p)-paw if and only if the pair (p, w) is value-stable. Moreover, the edges of this isolated X(p)-paw are $\{i_1,\ldots ,i_k\}$ if and only if $\{i_1,\ldots ,i_k\}$ form a value-stable occurrence of p in w.

Because the permutation $k\cdots 21$ is vexillary, and because $X(k\cdots 21)$ is a convex 2k-gon, we used Corollary 4.1 to study zonotopal tilings of X(w) in [29]; that is, tilings by convex paws. In particular, there is a zonotopal tiling of X(w) containing a 2k-gon with sides labeled $i_1< \cdots < i_k$ if and only if $i_k \cdots i_1$ form a $(k\cdots 21)$-pattern in w [29, Theorem 6.4]. Theorem 3.9 and Corollary 4.18 here now allow us to generalize that result completely.

5 Enumerative applications

We now turn our attention and techniques to enumerative questions. In particular, we give applications of this work in two directions—an analysis of the influence of permutation patterns on |R(w)| and |C(w)|, and a sampling of how it can be applied to enumerative questions about pattern avoidance. That latter discussion gives an elegant bijection between partitions and a class of pattern avoiding permutations, as well as a refinement of the Catalan numbers. Moreover, and perhaps most interestingly, it demonstrates how our work here can give a new framework for analyzing problems of pattern avoidance enumeration.

5.1 Enumerative influence of patterns on reduced words

In [26], Stanley showed that |R(w)| is a linear combination of the number of standard Young tableaux of certain shapes. For example, if w is vexillary, then |R(w)| is equal to the number of standard Young tableaux of a single shape $\lambda (w)$. In [6], Billey and Pawlowski defined further classes of permutations based on how many shapes have nonzero coefficients in the sum. While these collections R(w) can be enumerated, it is often complicated to do so. Moreover, the results do not give any indication of how |R(p)| and |R(w)| might be related (if at all) when $p \prec w$, whereas Theorem 3.9 suggests that indeed some relationship is likely. Similarly, as mentioned earlier in this article, the number |C(w)| of commutation classes of a permutation is very poorly understood outside of a few special cases.

In this section, we look at both |R(w)| and |C(w)| from the perspective of pattern avoidance. We will show that they are both monotonically increasing with respect to pattern containment, and we will completely characterize the $p\prec w$ for which equality is maintained, in each case.

Certainly Theorem 3.9 implies the following result.

Corollary 5.1

If then $|R(p)| \le |R(w)|$.

We can actually strengthen Corollary 5.1 to a property about any $p \prec w$, regardless of whether w contains all of $p^+$.

Consider the following algorithm, which we defined in [29].

This MONO gives an injection $T(p) \hookrightarrow T(w)$, yielding the following result.

Proposition 5.2

([29, Theorem 5.10]) If $p \prec w$ then $|C(p)| \le |C(w)|$.

In fact, an analogous property holds for reduced words.

Theorem 5.3

If $p \prec w$ then $|R(p)| \le |R(w)|$.

Proof

Suppose $p \prec w$ and fix a tiling $T \in T(p)$, with $T' \in T(w)$ a corresponding tiling from MONO. This T describes a commutation class of reduced words that arise from labeling T, and such a labeling depends on choices about the order in which commuting tiles are labeled via Elnitsky’s procedure. Consider one such labeling of T. It induces a labeling on the tiles of $T'$ via MONO, where any collection of rhombi in $T'$ that come from a single (or empty, as in Step 1 of the algorithm) tile in T are labeled consecutively via Elnitsky’s procedure. This gives an injection $R(p) \hookrightarrow R(w)$, and thus $R(p) \le R(w)$. $\square$

Figure 4 gives an example of the injection described in the proof of Theorem 5.3.

Fig. 4

Demonstration of the injection $R(52143) \hookrightarrow R(6213574)$, as indicated by tile labels. Thick borders in X(6213574) bound the images of the rhombi from the tiling of X(52143), and dashed edges give a (in fact, the only for each setting in this example) rhombic tiling of the induced paw

Having established that the numbers of both reduced words and of commutation classes are monotonically increasing with respect to pattern containment, it is natural to wonder when equality is maintained in either case, and if any criteria exist for that to occur. In fact, we can describe such conditions for each statistic, determining precisely which $p \prec w$ preserve the number of reduced words (respectively, commutation classes), and which do not. We prelude those results with a simple proposition.

Proposition 5.4

$|R(w)| = 1$ if and only if, for fixed $\varepsilon \in \{\pm 1\}$ and some $m \le m'$,

$$\begin{aligned} w(i) = {\left\{ \begin{array}{ll} i &{} \text {if } i \not \in [m,m'] \text {, and}\\ i+\varepsilon &{} \text {otherwise, taking values cyclically in } [m,m']. \end{array}\right. } \end{aligned}$$

Proof

The only reduced words that support no commutations or braids are words of the form

$$\begin{aligned} \mathsf{m(m+1)(m+2)\cdots (m'-1)} \end{aligned}$$

or

$$\begin{aligned} \mathsf{(m'-1)(m'-2)(m'-3)\cdots m} \end{aligned}$$

for some $m \le m'$. $\square$

Note that if $m = m'$ in Proposition 5.4, then the reduced word is empty and the permutation w is the identity.

We can now completely characterize the conditions on $p \prec w$ for which |R(p)| is equal to |R(w)|. The theorem only addresses the case when these sets have more than one element, since Proposition 5.4 has already described what must occur when they both have size 1.

Theorem 5.5

Suppose $p \prec w$. Then $|R(p)| = |R(w)| > 1$ if and only if $\ell (p) = \ell (w)$.

Proof

Suppose throughout the proof that $p \prec w$, and fix an occurrence $\langle p \rangle$ of p in w

Suppose $\ell (p) = \ell (w)$. Then every inversion in w is an inversion in this $\langle p \rangle$, and thus w fixes all letters not in $\langle p \rangle$. Define $x_1 \le y_1< x_2 \le y_2 < \cdots$ and $P_1, P_2, \ldots$ so that $\langle p \rangle = P_1P_2 \cdots$, where $P_i$ uses the letters $[x_i,y_i]$. Then elements of R(w) are words on

$$\begin{aligned} \bigcup _i [\mathsf{x_i},\mathsf{y_i}), \end{aligned}$$

and we have a bijection $R(w) \rightarrow R(p)$ defined letter-wise by

$$\begin{aligned} \mathsf{j} \mapsto {\left\{ \begin{array}{ll} \mathsf{j - x_i + 1}&\text {if } x_i \le j < y_i. \end{array}\right. } \end{aligned}$$

Thus $|R(p)| = |R(w)|$.

Now consider $|R(p)| = |R(w)| > 1$. Suppose $\ell (p) < \ell (w)$. Then there is an inversion with values $x>y$ such that, without loss of generality, the value x is not part of $\langle p \rangle$. Choose the positions of this inversion to be as close together as possible, so that everything appearing between x and y in w is both greater than x and part of $\langle p \rangle$. That is,

$$\begin{aligned} w = A x B y C, \end{aligned}$$

where $B \subseteq \langle p \rangle$ and $x < b$ for all $b \in B$. Because $|R(p)| = |R(w)|$, if we multiply w on the right by adjacent transpositions to remove inversions, then any resulting $w'$ in which x is immediately to the left of y can contain no other descents. In particular, this is true for

$$\begin{aligned} w' = AxyBC. \end{aligned}$$

Thus Ax is an increasing sequence of values, as is yBC. Combining this with the relationship between x and B means that, in fact,

$$\begin{aligned} AxBC \end{aligned}$$

is an increasing sequence of values. Thus w has the form of one of the permutations described in Proposition 5.4, contradicting the fact that $|R(w)| > 1$. Therefore, we must in fact have that $\ell (p) = \ell (w)$. $\square$

Theorem 5.5 says that any complexity to w besides its containment of p will introduce additional reduced words. To clarify the practicality of this result, we offer the following corollary.

Corollary 5.6

Suppose $p \prec w$. Then $|R(p)| = |R(w)| > 1$ if and only if w has a p-pattern that can be partitioned as $\langle p \rangle = P_1P_2 \cdots$, where all letters of $P_i$ are less than all letters of $P_{i+1}$ for all i, and all letters not in this $\langle p \rangle$ are fixed by w.

Just as reduced word enumeration was shown to be monotonic in Theorem 5.3 and further refined in Theorem 5.5, we can also refine the commutation class monotonicity from Proposition 5.2. Whereas Theorem 5.3 showed that enumeration of 21-patterns is the crux to equality of |R(p)| and |R(w)|, the analogous result for |C(p)| and |C(w)| will rely on enumeration of 321-patterns.

Theorem 5.7

Suppose $p \prec w$. Then $|C(p)| = |C(w)|$ if and only if the permutations p and w contain the same number of 321-patterns.

Proof

Suppose throughout the proof that $p \prec w$, and fix an occurrence $\langle p \rangle$ of p in w.

Suppose that p and w contain the same number of 321-patterns, so every 321-pattern in w is part of this $\langle p \rangle$. We want to show that the MONO algorithm is both surjective and a function. Consider some $T \in T(p)$. Because 321-patterns in w occur within $\langle p \rangle$, each X(q)-paw that MONO produces from a rhombus in T has q avoiding 321. Thus these paws each have exactly one rhombic tiling. Similarly, in Step 1 of MONO, the permutation $w_{\ell (p)}$ must also be 321-avoiding, and thus $|T(w_{\ell (p)})| = 1$. Therefore, MONO is a function; that is, it maps $T \in T(p)$ to a single, well-defined $T' \in T(w)$. Now consider $U' \in T(w)$. If $p = e$ then w is 321-avoiding and has only one commutation class, so certainly $|C(p)| = |C(w)|$. Otherwise, there is an i such that $\langle p(i)\rangle > \langle p(i+1) \rangle$. Moreover, because w has no more 321-patterns than p has, the segment from $\langle p(i)\rangle$ to $\langle p(i+1) \rangle$ in the one-line notation of w is 321-avoiding. Thus the paw created by this segment has a unique rhombic tiling, which must be what we see in $U'$. Let $w'$ be the permutation obtained by rewriting this segment in increasing order, so $X(w')$ is X(w) without that paw, and let $p' = p\sigma _i$, so $X(p')$ is what remains after positioning a rhombus with edges $\{p(i),p(i+1)\}$ along the rightmost border of X(p). Iterating this procedure with $p'$ and $w'$ yields a unique tiling $U \in T(p)$ such that MONO produces $U'$ from U. Thus MONO is surjective, and so we do indeed have $|C(p)| = |C(w)|$.

Fig. 5

Two tilings of the $\{x,y,z\}$ sub-hexagon that must appear in element of T(w), as described in the proof of Theorem 5.7

Now consider $|C(p)| = |C(w)|$. Suppose that $x> y > z$ is a 321-pattern in w. By Corollary 4.18, there are elements of T(w) that are identical except for the tiling of a sub-hexagon with edges $\{x,y,z\}$, as depicted in Fig. 5. Consider $T' \in T(w)$. For some $T \in T(p)$ to produce this particular $\{x,y,z\}$ sub-hexagon unambiguously via MONO, there is an i such that, as defined by the algorithm,

$$\begin{aligned} w_i = \cdots \ \langle p_i(j)\rangle \ \cdots \ x \ \cdots \ y \ \cdots \ \langle p_i(j+1)\rangle \ z \ \cdots , \end{aligned}$$

where $p_i(j) > p_j(j+1)$, and

$$\begin{aligned} w_{i+1} = \cdots \ y \ x \ z \ \cdots . \end{aligned}$$

To obtain this $w_{i+1}$, we must have that x and y are the two largest elements in the segment $\langle p_i(j)\rangle \cdots x \cdots y \cdots \langle p_i(j+1)\rangle$ of $w_i$. For MONO to be a function, this segment must avoid 321. Therefore, $y \not > \langle p_i(j+1)\rangle$. Moreover, because x and y are maximal in this segment, we have $y \not < \langle p_i(j+1)\rangle$. Thus $y = \langle p_i(j+1)\rangle$. Because $\langle p_i(j) \rangle > p_j(j+1) = y$, and x is the largest value in the segment, we must in fact have $x = \langle p_i(j) \rangle$. Therefore, x and y are both values in $\langle p \rangle$. A similar argument for the hexagon tiling in $U'$ shows that z must be part of $\langle p \rangle$ as well. Therefore, every 321-pattern in w is also a 321-pattern in $\langle p \rangle$, and so p and w have equally many 321-patterns. $\square$

Both Theorems 5.5 and 5.7 can be stated in terms of patterns in p and w: Theorem 5.5 requires equally many 21-patterns, and Theorem 5.7 requires equally many 321-patterns. This suggests that patterns may play an even deeper, “meta,” role in structural aspects of the symmetric group. Additionally, note that this equinumerable requirement is somewhat orthogonal to typical forays into pattern containment and avoidance, where one only cares about whether a pattern occurs, and not how often it does so.

5.2 Enumeration of 132-avoiding permutations by length

Permutation patterns appear throughout combinatorics, typically in theorem statements of two varieties: characterization results (such as Corollary 4.1, because “vexillary” is equivalent to 2143-avoiding) and enumerative results. This latter class has received several decades of consistent attention (see, for example, [4, 8, 17, 23, 25]).

Definition 5.8

Fix a permutation p. Let

$$\begin{aligned} {\mathfrak {S}}_n(p) = \{w \in {\mathfrak {S}}_n : w \text { avoids } p\}. \end{aligned}$$

There is great interest in understanding $|{\mathfrak {S}}_n(p)|$ for different p. For example, it is well known and has been proved in many contexts, that

$$\begin{aligned} p \in {\mathfrak {S}}_3 \Longrightarrow |{\mathfrak {S}}_n(p)| = C_n, \end{aligned}$$

(3)

where

is the $n\hbox {th}$ Catalan number. For more information about Catalan numbers, including their enumeration of ${\mathfrak {S}}_3$ pattern avoidance, the reader is encouraged to read [28] and entry A000108 of [21].

This section will show that partitions and a collection of pattern avoiding permutations are in bijection with each other and thus are equinumerous. Parts of size 0 are typically suppressed in partition enumeration—otherwise there would be infinitely many partitions of a given size. Similarly, it will be useful in the upcoming enumeration of pattern avoidance by length to suppress a certain kind of fixed point in our enumeration of pattern avoidance.

To motivate our convention, consider permutations $v \in {\mathfrak {S}}_n$ and $v' \in {\mathfrak {S}}_{n+1}$ defined by

$$\begin{aligned} v'(x) = {\left\{ \begin{array}{ll} v(x) &{} \text { if } x \le n, \text { and}\\ n+1 &{} \text { if } x = n+1. \end{array}\right. } \end{aligned}$$

If $p \in {\mathfrak {S}}_k$ with $p(k) \ne k$, then $v \in {\mathfrak {S}}_n(p)$ if and only if $v' \in {\mathfrak {S}}_{n+1}(p)$. Moreover, $\ell (v) = \ell (v')$ and $R(v) = R(v')$. In other words, in the context of enumerating p-avoidance by length, the permutations v and $v'$ are essentially the same. When $p(1) \ne 1$, a similar statement can be made about $v \in {\mathfrak {S}}_n$ and $v' \in {\mathfrak {S}}_{n+1}$ defined by

$$\begin{aligned} v'(x) = {\left\{ \begin{array}{ll} 1 &{} \text { if } x = 1, \text { and}\\ v(x-1) &{} \text { if } x > 1. \end{array}\right. } \end{aligned}$$

Thus, to enumerate pattern avoidance by length, we define a set that sidesteps this overcounting.

Definition 5.9

For $p \in {\mathfrak {S}}_k$, set

$$\begin{aligned} {\mathfrak {S}}(p) = \bigcup \limits _n\left\{ w \in {\mathfrak {S}}_n : \begin{array}{l} w \text { avoids } p,\\ w(n) \ne n \text { if } p(k) \ne k, \text { and}\\ w(1) \ne 1 \text { if } p(1) \ne 1 \end{array}\right\} . \end{aligned}$$

In the applications of this section, we focus on 132-avoidance. However, other patterns are similarly susceptible to our techniques and results, and we will conclude the paper with a brief indication of how that might proceed.

The pattern $132 \in {\mathfrak {S}}_3$ appears in both an enumerative result (as described in (3)) and a characterization result (entry P0003 of [31]).

Theorem 5.10

([19, 20]) A permutation is 132-avoiding if and only if it is dominant.

For information about the significance of dominant permutations, the reader is referred to [19, 20]. In this paper, we will show an enumerative connection between dominant permutations and partitions. In fact this is not the only relationship between these two objects, since a permutation is dominant if and only if its Lehmer code is non-increasing (see, for example, [1] and [27]).

To facilitate our enumeration below, we highlight a crucial aspect of 132-avoidance that arises from Theorem 3.9.

Remark 5.11

The permutation 132 has one reduced word: $R(132) = \{\mathsf{2 }\}$. Moreover, because $132^+ = \{132\}$, Definition 3.1 and Theorem 3.9 imply that w contains a 132-pattern if and only if w has a reduced word $\mathsf{axc}$ for some letter x, such that $\mathsf{a} \in \mathsf{R(u)}$ and $\mathsf{c} \in \mathsf{R(v)}$, where $\ell (us_{x-1}) > \ell (u)$ and $\ell (s_{x-1}v) > \ell (v)$.

We now use the techniques and results of this paper to analyze 132-avoiding permutations of a given length, and we show— bijectively—that these are enumerated by the partition numbers [21, A000041]. The theory of integer partitions is a highly active area of combinatorial research, treated, for example, in the texts [2, 3] and in a spectacular number of papers.

Definition 5.12

Let ${\mathfrak {p}}(n) = \big |\{\lambda \vdash n\}\big |$.

For example, ${\mathfrak {p}}(4) = 5$ because there are five partitions of 4. Drawn as Young diagrams anchored at the upper-left corners, these are as follows.

In order to study pattern avoidance by length, we consider the following sets, the collection of which partitions ${\mathfrak {S}}(p)$.

Definition 5.13

Fix a permutation p and let

$$\begin{aligned} \mathfrak {S}(p;\ell ) = {\mathfrak {S}}(p) \cap \{w : \ell (w) = \ell \}. \end{aligned}$$

Example 5.14

• (a) Some of these sets are finite: $\mathfrak {S}(132;4) = \{23451, 51234, 4213, 3241, 3412\}$.

• (b) Others are infinite:

  $$\begin{aligned} \mathfrak {S}(321;3) = \{2341, 4123, 3142, 2413, 23154,21453,31254,21534, \ldots \}. \end{aligned}$$

We conclude this paper with an application of Theorem 3.9. Theorem 5.15 below gives a direct connection between partitions and 132-avoiding permutations and recovers a result (proved by other means) of Claesson, Jelínek, and Steingrímsson [10, Proposition 11]. Next, we refine Theorem 5.15 to give a bijective relationship between restricted partitions and 132-avoiding permutations with prescribed first letters. Finally, we use this to give a connection to Catalan numbers in Corollary 5.20, writing those values as sums of quantities of 132-avoiding permutations.

In light of the multitude and breadth of open problems in the study of pattern avoidance enumeration, it seems highly likely that our techniques can provide new insight into this high-interest field.

Theorem 5.15

For any integer $\ell \ge 0$,

$$\begin{aligned} |\mathfrak {S}(132;\ell )| = {\mathfrak {p}}(\ell ). \end{aligned}$$

The statement of this result is quite elegant in its simplicity, and its connection between two objects of such significant interest. Moreover, its bijective proof has a variety of implications. Before giving that proof, we discuss a few of those consequences.

We begin by introducing notation used in [27].

Definition 5.16

Let ${\mathfrak {p}}_k(n)$ be the number of partitions of n into exactly k parts.

The bijection given below in the proof of Theorem 5.15 has the following implication for the number of these restricted partitions.

Corollary 5.17

${\mathfrak {p}}_k(\ell ) = \Big | \mathfrak {S}(132;\ell ) \cap \{w : w(1) = k+1\}\Big |$.

Note the connection between these results and [27, Exercise 1.125]. The binary sequences in that setting describe vertical and horizontal steps around the southeast edge of a partition, the inversions in such a sequence are in bijection with the squares of the shape, and the number of $1\hbox {s}$ refers to the height (or width, depending on convention) of the shape. Thus, in light of our results here, these strings can also describe classes of 132-avoiding permutations.

Another way to refine the result of Theorem 5.15 involves the following sets.

Definition 5.18

Partition $\mathfrak {S}(p;\ell )$ by defining

$$\begin{aligned} \mathfrak {S}(p;\ell , d) = \mathfrak {S}(p;\ell ) \cap \{w : \text {elements of } R(w) \text { have }d\text { distinct letters}\}. \end{aligned}$$

Example 5.19

• (a) $\mathfrak {S}(132;4,3) = \{4213, 3241, 3412\}$, whereas $\mathfrak {S}(132;4,4) = \{23451, 51234\}$.

• (b) $\mathfrak {S}(321;3,2) = \emptyset$ and $\mathfrak {S}(321;3,3) = \mathfrak {S}(321;3)$.

The bijection in the proof of Theorem 5.15 shows that

$$\begin{aligned} \big |\mathfrak {S}(132;\ell ,d)\big | = \big |\{\lambda \vdash \ell : \lambda \text { fits inside the staircase shape } \delta _{d+1} \text { but not inside } \delta _d\}\big |. \end{aligned}$$

These values for small $\ell$ and d are given in Table 1 and were obtained using Sage.

Table 1 The values $\big |\mathfrak {S}(132;\ell ,d)\big |$ for $0 \le \ell , d \le 11$

Because the sets $\mathfrak {S}(132;\ell ,d)$ partition $\mathfrak {S}(132;\ell )$, we have

$$\begin{aligned} \big |\mathfrak {S}(132;\ell )\big | = \sum _{d=0}^{\ell } \big | \mathfrak {S}(132;\ell ,d)\big |. \end{aligned}$$

Moreover, we know from (3) that the Catalan numbers can be refined by this statistic $\big |\mathfrak {S}(132;\ell ,d)\big |$.

Corollary 5.20

In other words, $C_n$ is the sum of all values weakly northwest of the entry and $d = n-1$ in the extension of Table 1.

Example 5.21

We conclude this section with the proof of Theorem 5.15. We divide the argument into a sequence of lemmas in order to highlight the features of the bijection involved in the proof of the theorem.

Throughout our arguments, we consider partitions to be tableaux with a particular filling.

Definition 5.22

The antidiagonal filling of a partition $\lambda$ is defined so that all squares along the highest antidiagonal (that is, southwest to northeast) are labeled 1, all squares along the next highest antidiagonal are labeled 2, and so on. Equivalently, if the rows are indexed from top to bottom and the columns are indexed from left to right, then the square in row r and column c is labeled $r+c-1$.

An example of this filling appears in Fig. 6.

Fig. 6

Antidiagonal filling of the partition $(7,4,4,2,1)\vdash 18$

Definition 5.23

For any partition $\lambda$ with the antidiagonal filling, its reading word, denoted $\mathsf{{read}}(\lambda )$, is obtained by concatenating the entries of the rows of $\lambda$, from bottom to top, and from left to right within each row.

Continuing the example depicted in Fig. 6,

$$\begin{aligned} \mathsf{{read}}\,(7,4,4,2,1)= \mathsf{5453456234512} \mathsf{34567}. \end{aligned}$$

Lemma 5.24

For any partition $\lambda$ with the antidiagonal filling, the word $\mathsf{{read}}(\lambda )$ is reduced.

Proof

To be unreduced, we must be able to apply commutation and braid moves to this word to obtain a new word with either xx or, without loss of generality, $x(x-1)x(x-1)$ as factors. Antidiagonal fillings impose strict rules on $\mathsf{{read}}(\lambda )$. In particular, any two appearances of x in $\mathsf{{read}}(\lambda )$ are separated by an appearance of $x-1$. Neither x can pass over this $x-1$ to reach the other, so we cannot encounter an xx factor. Similarly, we cannot see $\cdots x \cdots x-1 \cdots x \cdots x-1 \cdots$ without $x-2$ appearing between the two copies of $x-1$, and thus the factor $x(x-1)x(x-1)$ does not arise either. $\square$

Lemma 5.24 means that $\mathsf{{read}}(\lambda )$ defines a permutation. Moreover, the length of this permutation is equal to the size of $\lambda$, because it is equal to the number of letters in $\mathsf{{read}}(\lambda )$.

Definition 5.25

Write $\pi (\lambda )$ for the permutation for which $\mathsf{{read}}(\lambda )$ is a reduced word.

Continuing our example, $\mathsf{{read}}(\lambda ) \in R(65472381)$. Thus $\pi (7,4,4,2,1) = 65472381 \in {\mathfrak {S}}_8$. Note that this permutation is 132-avoiding.

Lemma 5.26

The map $\lambda \mapsto \pi (\lambda )$ is injective.

Proof

Let $\lambda$ be a partition having k parts, and $k\hbox {th}$ part of size i. Suppose that $\pi (\lambda ) = \pi (\lambda ')$. By construction, the permutation $\pi (\lambda )$ sends 1 to $k+1$. Thus, $\lambda$ and $\lambda '$ must have the same number of rows. If $\lambda \ne \lambda '$, then it suffices to assume that their bottom rows have different lengths, say i and $i'$, respectively, where $i<i'$. By definition of the filling and construction of the permutation, the leftmost values in the one-line notation of $\pi (\lambda )$ are $(k+1)(k+2)\cdots (k+i)$. Moreover, the next value, the image of $i+1$, must be less than $k+1$. The leftmost values in the one-line notation of $\pi (\lambda )$ are $(k+1)(k+2)\cdots (k+i')$. Since $i' > i$, this is a contradiction. Therefore, $\lambda = \lambda '$. $\square$

We now show the connection between 132-patterns and the permutations $\{\pi (\lambda )\}$.

Lemma 5.27

${\mathfrak {S}}(132) = \{\pi (\lambda )\}$.

Proof

Fix $w \in {\mathfrak {S}}(132)$ and let $\mathsf{s} \in \mathsf{R(w)}$ be its lexicographically greatest reduced word. View $\mathsf{s}$ as the concatenation of maximally long factors of consecutively increasing values:

$$\begin{aligned} \mathsf{\big (x_1 (x_1+1) (x_1+2) \cdots (x_1 + i_1)\big )\big (x_2 (x_2+1) (x_2+2) \cdots (x_2 + i_2)\big ) \cdots }. \end{aligned}$$

Suppose that $x_{j'+1} = x_{j'} - 1$ for all $j' < j$, and consider $x_{j+1}$. The word is reduced, so $x_{j+1} \ne x_j+i_j$. Also, $i_j$ is maximal, so $x_{j+1} \ne x_j+i_j+1$. If $x_{j+1} > x_j+s_j+1$, then $\mathsf{s}$ would not be maximal because $x_{j+1}$ and $x_j+i_j$ could commute. Similarly, if $x_{j+1} \in [x_j,x_j+i_j-1]$, then commutation moves to slide $x_{j+1}$ leftward and a braid move to change $x_{j+1}(x_{j+1}+1)x_{j+1}$ into $(x_{j+1}+1)x_j(x_{j+1}+1)$ would again contradict the maximality of $\mathsf{s}$. Thus $x_{j+1} < x_j$. Define u and v as in Definition 3.1, so that $u\sigma _{x_j}v = w$. The choice of j means that $\ell (u\sigma _{x_j-1}) > \ell (u)$. To be 132-avoiding, the letter $x_j$ cannot be isolated on $[x_j-1,x_j]$ (see Remark 5.11). Thus, $\ell (\sigma _{x_j-1}v) < \ell (v)$. Because $\mathsf{s}$ is lexicographically maximal, $x_{j+1} = x_j-1$ for all j.

Suppose that $i_j < i_{j-1}$. Obtain $\mathsf{s'}$ from $\mathsf{s}$ by sliding the factor $(x_{j-1}+i_j+1)\cdots (x_{j-1}+i_{j-1})$ to the right of $x_j+i_j = x_{j-1}-1+i_j$ via a sequence of commutations. In $\mathsf{s'}$, the letter $x_{j-1}+i_j+1$ is isolated on $[x_{j-1}+i_j,x_{j-1}+i_j+1]$, meaning that $w \not \in {\mathfrak {S}}(132)$ – a contradiction. Finally, if a non-empty $\mathsf{s}$ has minimal letter $m > 1$, then any appearance of m would be isolated on $[m-1,m]$. Thus, by the previous discussion, $x_J = 1$ for the maximal value of J. The word $\mathsf{s}$ as described is exactly $\mathsf{{read}}(i_J+1, i_{J-1}+1, \ldots , i_1+1)$. Thus ${\mathfrak {S}}(132) \subseteq \{\pi (\lambda )\}$.

For the reverse inclusion, first suppose that $\lambda = (\ell )$ has only one part. Then $\mathsf{{read}}(\lambda ) = \mathsf{12\cdots \ell }$ and $\pi (\lambda ) = 234\cdots \ell (\ell +1)1$, which is certainly 132-avoiding. Suppose, inductively, that for any partition $\mu$ having fewer than k parts, the permutation $\pi (\mu )$ is 132-avoiding. Let $\lambda$ be a partition having k parts and kth part of size i. Let $\mu$ be the partition obtained from $\lambda$ by removing the last part. By construction, $\pi (\lambda ) = u\cdot \pi (\mu )$, where $u = \sigma _{k} \sigma _{k+1}\cdots \sigma _{k+i-1}$. The leftmost values in the one-line notation of $\pi (\lambda )$ are $(k+1)(k+2)\cdots (k+i)$. The only inversions in $\pi (\lambda )$ that do not appear in $\pi (\mu )$ arise because k now appears to the right of the values $\{k+1,k+2,\ldots , k+i\}$. For $\pi (\lambda )$ to introduce a 132-pattern, then, we would need $\langle 32\rangle = (k+j)k$ for some $j \in [1,i]$. However, no value less than k appears to the left of this $k+j$, so there can be no such 132-pattern. Hence $\pi (\lambda ) \in {\mathfrak {S}}(132)$ and so $\{\pi (\lambda )\} \subseteq {\mathfrak {S}}(132)$. $\square$

We are now ready to prove the main result of this section.

Proof of Theorem 5.15

Lemmas 5.24 and 5.26 give a bijective correspondence between partitions and a particular class $\{\pi (\lambda )\}$ of permutations. Lemma 5.27 shows that this class is exactly ${\mathfrak {S}}(132)$. Therefore, we have a bijection between partitions and elements of ${\mathfrak {S}}(132)$, and, more precisely, between partitions of $\ell$ and elements of ${\mathfrak {S}}(132;\ell )$. $\square$

By the symmetry of their reduced words, this section’s manipulations and enumerative results about 132-avoidance can be recast in terms of 213-avoidance. However, despite expression (3), we cannot replace 132 there by any other element of ${\mathfrak {S}}_3$ in those statements. Our techniques would still apply for those other patterns, but the details—and the enumerations—would differ. In the final section of this paper, we give a glimpse of how this would work, and state enumerative results about 231-avoidance.

6 Final remarks

It is clear from this work that reduced word manipulation is ripe for application in many settings. Here we have focused only on the symmetric group, but the technique could certainly be employed in other Coxeter groups and to other structural questions. The breadth of applications we have encountered so far is highly promising, and we are optimistic that these methods will continue to yield fruitful results.

For example, if one were to enumerate 231-avoiding permutations (that is, stack-sortable permutations, [17]) by length, one would be looking for factors $x(x+1)$ to be unisolated on $[x,x+1]$. This means, among other things, that if the letters x and $x+1$ each appear only once in a reduced word, then their relative order is forced: They would have to appear as $\mathsf{(x+1)}\cdots \mathsf{x}$. On the other hand, if x and y each appear only once in a reduced word and $|x-y| > 1$, then their relative order does not matter. This produces the following enumerations of 231-avoiding permutations in ${\mathfrak {S}}_n$ by length.