Séminaire Lotharingien de Combinatoire 67 (2012), Article B67d

DESCRIBING WEST-3-STACK-SORTABLE PERMUTATIONS WITH PERMUTATION PATTERNS

HENNING ÚLFARSSON

Abstract. We describe a new method for finding patterns in permutations that produce a given pattern after the permutation has been passed once through a stack. We use this method to describe West-3-stack-sortable permutations, that is, permutations that are sorted by three passes through a stack. We also show how the method can be applied to the bubble-sort operator. The method requires the use of mesh patterns, introduced by Brändén and Claesson (2011), as well as a new type of generalized pattern we call a decorated pattern.

Contents

1. Introduction

2. Generalized permutation patterns 2 3. Finding preimages of patterns 7 4. Describing West-3-stack sortable permutations 11 5. Open problems 18 References 19

1. Introduction

A permutation is a one-to-one correspondence from a finite set {1, …, n} to itself. Permutations will be written in one-line notation, so the permutation 2314 maps 1 to 2, 2 to 3 and so on. The number of letters in a permutation will be called its length and the set of all permutations of length n is denoted S_{n}. The identity permutation 12 ⋯ n will be denoted id_{n}, or just id if n is understood from the context, or irrelevant. For integers a < b we use ⟦a, b⟧ to denote the set {a, a + 1, …, b}.

In the 1970’s Knuth [12] initiated the study of sorting and pattern avoidance in permutations. He considered the problem of sorting a permutation by passing it through a stack. A stack is a structure that can store elements from a permutation. We can push onto the top of the stack and elements are popped out to the output. Consider trying to sort the permutation 231 by a stack, as shown in Figure 1.

Key words and phrases. Patterns, Permutations, Sorting.

2 3 1 3 1 2 3 1 2 1 3 2 2 3 1 1 3 2 3 1 2

Figure 1. Trying, and failing, to sort 231 with a stack. The figure is read from right to left

Note that we always want the elements in the stack to be increasing, from the top, since otherwise it would be impossible for the output to be sorted. We failed to sort the permutation in one pass through the stack and therefore say that it is not stack-sortable. Knuth [12] showed that a permutation is stack-sortable if and only if it avoids 231 as a pattern. We will reprove this below in Theorem 3.1. Several variations on Knuth’s original problem have been considered, such as changing the way the stack operates, and/or adding more sorting devices, see Bóna [5] for a survey. In this paper we will consider two variations: repeatedly passing a permutation through a stack and the so-called bubblesort operator. We introduce a new method for finding patterns in a permutation that will cause these sorting devices to output a given pattern. If the given pattern we want to be outputted is a classical pattern (defined below) we show that the mesh patterns introduced by Brändén and Claesson [7] suffice, but if the given pattern is itself a mesh pattern we will need to introduce a new kind of generalized pattern we call a decorated pattern.

In the next section we review some literature on generalized permutation patterns and introduce a new generalization.

2. Generalized permutation patterns

A standardization of a list of numbers is another list of the same length such that the smallest letter in the original list has been replaced with 1, the second smallest with 2, and so on. The standardization of 5371 is 3241. A classical (permutation) pattern is a permutation p in S_{k}. A permutation π in S_{n} contains, or has an occurrence of, the pattern p if there are indices 1 ≤ i_{1} < ⋯ < i_{k} ≤ n such that the standardization of π(i_{1}) ⋯ π(i_{k}) equals the pattern p. If a permutation does not contain a pattern p we say that it avoids the pattern p. The permutation π = 526413 contains the pattern p = 132, and has three occurrences of it, given by the subsequences 264, 263 and 243. We can draw the graph of the permutation by graphing the coordinates (i, π(i)) on a grid. For example the permutation π above is shown in Figure 2 where we have additionally circled the occurrences of the pattern p.

Figure 2. The permutation 526413 and three occurrences of the pattern 132

The same permutation avoids the pattern 123, since we can not find an increasing subsequence of length three in it.

Classical patterns form the base of a hierarchy of generalizations, shown in Figure 3.

classical vincular bivincular 1-barred more barred barred mesh interval Bruhat-restr. marked mesh McGovern decorated mon. grid classes

grid classes

Figure 3. The hierarchy of generalizations of classical patterns

We will describe in detail the mesh, marked mesh and decorated patterns, as well as barred patterns, as these will be the generalizations we need. We describe the others briefly below and give references for them.

2.1. Mesh patterns and barred patterns. Mesh patterns were introduced in [7]. We review them via an example. The mesh pattern

(⋆)

occurs in a permutation if we can find the underlying classical pattern 132 positioned in such a way that the shaded regions are not occupied by other entries in the permutation. Consider the permutation 526413. From above we know that the classical pattern has three occurrences in this permutation. In Figure 4 one can see that just one of these satisfies the additional requirement that there be no additional entries in the shaded region “between and to the left of the 3 and the 2”.

Another way of writing a mesh pattern is to give the underlying classical pattern, followed by the set of shaded boxes, labelled by their lower left corner (the left-most box in the bottom-most row being (0, 0)). The mesh pattern we considered here is (132, {(0, 2), (1, 2), (2, 2)}) and any classical pattern p can be written as the mesh pattern (p, ∅).

Figure 4. The permutation 526413 and one occurrence of the mesh pattern (⋆) above

\begin{matrix}(0,0) \\ (0,2) \\ (1,2) \\ (2,2) \end{matrix}

Figure 5. The mesh pattern (132, {(0, 2), (1, 2), (2, 2)})

Describing the simple permutations with mesh patterns. Recall that an interval in a permutation is a set of entries that is consecutive in positions and values. An interval is trivial if consists of one letter, or is the entire permutation. The elements 4653 form a nontrivial interval in the permutation 28465317.

A permutation without nontrivial intervals is called simple. Simple permutations have been shown to be useful in the study of classical pattern classes, see e.g., Albert and Atkinson [1] and Brignall [8].

Notice that the left-most, right-most, highest and lowest elements (hereafter called the boundary elements) in the interval 4653 form an occurrence of the mesh pattern

.

This leads to the following proposition.

Proposition 2.1. A permutation is simple if and only if it avoids each of the patterns below, as well as their images under symmetries of the square.

Proof. A permutation is not simple if and only if it has a non-trivial interval, and any interval must have boundary elements satisfying one of the mesh patterns above, or their images under symmetries of the square. The element in the patterns that is not one of the boundary elements is added to ensure that the interval is not the entire permutation, and thus trivial. □

Barred patterns were introduced by West [17]. A barred pattern is a classical pattern with bars over some of the entries. Such a pattern is contained in a permutation if the standardization of the unbarred entries is contained in the permutation in such a way that they are not part of an occurrence of the whole barred pattern. This is best explained by considering examples. The barred pattern 3¯5241 does not occur in the permutation 416352, since there is only one occurrence of the classical pattern we get from the unbarred entries, in the subsequence 4352, and this occurrence is part of an occurrence of 35241. The permutation 5264173 does contain this barred pattern, in the subsequence 5473, since that is an occurrence of 3241 that is not part of an occurrence of 35241. In [7] it was shown that any barred pattern with one barred entry is a mesh pattern. The barred pattern we discussed here is in fact the mesh pattern

.

This explains the edge from barred patterns with one bar (“1-barred”) to mesh patterns (“mesh”) in Figure 3.

2.2. Marked mesh patterns. Marked mesh patterns were introduced by the author in [15] and used in joint work with Woo in [16] in the characterization of local complete intersection Schubert varieties. They give finer control over whether a certain region in a permutation is allowed to contain elements, and if so, how many. Again we just give an example. Consider the marked mesh pattern below.

The meaning of the 1 in the region containing boxes (1, 0), (1, 1), (2, 0) and (2, 1) is that this region must contain at least one entry. In Figure 6 we see that there is exactly one occurrence of this mesh pattern in the permutation 526413.

Figure 6. The permutation 526413 and one occurrence of a marked mesh pattern

Marked mesh patterns will be useful below when we need to add elements into an existing pattern to ensure other elements are popped out of a particular sorting device.

2.3. Decorated patterns. Below we will need even finer control over what is allowed inside a particular region in a pattern. We will need to control whether the entries in the region avoid a particular pattern. Consider for example the decorated pattern

.

The decorated region in the middle signifies that an occurrence of this pattern should be an occurrence of the underlying classical pattern 21 that additionally does not have entries in the region that contain the pattern 12 – or equivalently – whatever is in that region must be in descending order, from left to right. In Figure 7 there is an occurrence of the decorated pattern on the left and on the right we have an occurrence of the classical pattern 21 that does not satisfy the requirements of the decorated region.

Figure 7. The permutation 526413 and one occurrences of a decorated pattern

Below we state the formal definition of a decorated pattern.

Definition 2.2. A decorated pattern (p, C) of length k consists of a classical pattern p of length k and a collection C which contains pairs (C, q) where C is a subset of the square ⟦0, k⟧×⟦0, k⟧ and q is some pattern, possibly another decorated pattern. An occurrence of (p, C) in a permutation π is a subset ω of the diagram G(π) = {(i, π(i)) | 1 ≤ i ≤ n} such that there are order-preserving injections α, β : ⟦1, k⟧ → ⟦1, n⟧ satisfying two conditions:

(1) ω = {(α(i), β(j)) : (i, j) ∈ G(p)}.

(2) Let R_{ij} = ⟦α(i) + 1, α(i + 1) − 1⟧×⟦β(j) + 1, β(j + 1) − 1⟧, with α(0) = 0 = β(0) and α(k + 1) = n + 1 = β(k + 1). For each pair (C, q) we let C′ = ⋃_{(i,j)∈C} R_{ij} and require that

C′ ∩ G(π) avoids q.

More bars in more places. We noted above that any barred pattern with just one barred entry can be translated into a mesh pattern. If there is more than one bar on entries that are adjacent in the pattern, this is no longer true. But we can still translate these types of barred patterns into decorated patterns. For example the barred pattern 1¯2¯34 is equivalent to the decorated pattern

.

There are other barred patterns, such as ¯13¯24, that can not be expressed as decorated patterns.

2.4. Other generalizations. Vincular patterns, sometimes called dashed patterns, were defined by Babson and Steingrímsson [4]. They are mesh patterns where shaded regions must be vertical strips. Bivincular patterns were defined by Bousquet-Mélou, Claesson, Dukes and Kitaev [6]. They are mesh patterns where shaded regions can be either vertical or horizontal strips.

Bruhat-restricted patterns and interval patterns were defined by Yong and Woo in [18] and [19], and have applications to the study of singularities of Schubert varieties. In [15] the author showed that interval patterns are a special case of mesh patterns. McGovern [13] showed that classical patterns, with the extra restriction that occurrences must be a union of cycles, have applications to geometry as well. It is shown in [15] that this generalization is subsumed by marked mesh patterns.

Profile classes were introduced in Murphy and Vatter [14], and later called monotone grid classes in Huczynska and Vatter [11]. It is not hard to show that a permutation is a member of a particular monotone grid class if and only if it contains one pattern from a finite list of decorated patterns.

3. Finding preimages of patterns

In this section we define a method for describing patterns that are guaranteed to produce a given pattern in a permutation after it is sorted by a stack or with the bubble-sort operator.

3.1. The stack-sort operator. For a permutation π we denote by S(π) the image of π after it is passed once through a stack. Recall that a permutation is stack-sortable if and only if S(π) = id, the identity permutation. Another way to state this is that a permutation π in S_{n} is stack-sortable if and only if S(π) ∈ Av_{n}(21), where Av_{n}(21) is the set of permutations of length n that avoid 21. Of course Av_{n}(21) = {id} but framing the question like this leads to a generalization: given a pattern p, what conditions need to be put on π such that S(π) ∈ Av_{n}(p). Equivalently, we can ask for a description of S^{−1}(Av_{n}(p)).

Below we call permutations such that S^{k}(π) = id, West-k-stack-sortable permutations, since West considered this generalization from the case of one stack first. Note that for k > 1 these permutations are different from the k-stack-sortable permutations, which are the permutations that can be sorted by using k stacks in series without the requirement that the permutation completely passes through one stack at a time. For example, the permutation 2341 is not West-2-stack-sortable, but if we put the entries 2, 3, 4 onto the first stack, pass 1 all the way to the end, and then use the second stack to sort 2, 3, 4 we end up with 1234. So 2341 is 2-stack-sortable. See also Open Problem (4) in Section 5 below.

The basic idea behind the method we are about to describe is that S(π) has an occurrence of a pattern p of length k if and only if the k elements making up this occurrence were present in π as some kind of pattern before we sorted. This is of course a complete tautology but will get us pretty far. We start by showing how this idea allows us to describe stack-sortable permutations, as well as West-2-stack sortable permutations.

Stack-sortable permutations. We know that π is not sorted by the stack if and only if S(π) contains the classical pattern 21. Therefore consider a particular occurrence of this pattern in S(π). Before sorting, the elements in this occurrence must have been an occurrence the pattern

21 =

in π. In order to remain in this order the element corresponding to 2 must be popped off the stack by a larger element before the element corresponding to 1 enters. Thus the box (1, 2) must be occupied by at least one element and we have an occurrence of the marked mesh pattern

1

which is equivalent to the classical pattern . We have therefore reproven Knuth’s

result.

Theorem 3.1 (Knuth [12]). A permutation π is stack-sortable, i.e., S(π) = id, if and only if it avoids the pattern 231.

West-2-stack-sortable permutations. We can similarly reprove West’s result on West-2-stack sortable permutations, i.e., permutations π such that S^{2}(π) = id. By Knuth’s result we know that π will be sorted by two passes through the stack if and only if S(π) avoids the pattern 231. An occurrence of 231 must have been either of the patterns

,

in π. Consider the pattern on the left. In order for the elements to stay in this order as they pass through the stack we must have an element in the box (2, 3) in order to pop the element corresponding to 3 out of the stack before the smallest element enters. Now, the opposite happens for the pattern on the right. The 3 must stay on the stack until 2 enters, so there can be no elements in the box (1, 3) and then both 2 and 3 must leave the stack before 1 enters. Thus the patterns above become the marked mesh patterns

1  , _{1}  .

These are more naturally written as

, .

The pattern on the right is equivalent to the pattern , in the sense that a permu-

tation either contains both patterns or avoids both, by a lemma of Hilmarsson, Jónsdóttir, Sigurðardóttir, Viðarsdóttir and Úlfarsson [10]. For these two patterns it is also easy to see directly that they are equivalent. As mentioned above this pattern is another representation of the barred pattern 3¯5241. Thus we have re-derived West’s result.

Theorem 3.2 (West [17]). A permutation π is West-2-stack-sortable, i.e., S^{2}(π) = id, if and only if it avoids the patterns 2341 and 3¯5241.

Recall that an inversion in a permutation is an occurrence of the classical pattern 21, while a non-inversion is an occurrence of 12. We now describe how given a classical pattern p the method can be used to find a set of marked mesh patterns P such that

S^{−1}(Av(p)) = Av(P).

There are two things to consider when choosing what classical patterns to start from.

(1) If two elements in p are part of an inversion, they must also be part of an inversion in all patterns in P.

(2) If two elements in p are part of a non-inversion, they can either be a non-inversion or an inversion in the patterns in P.

We now consider which shadings or markings must be added.

(1) If a > b form an inversion in a particular pattern p′ in P and are supposed to come out of the stack as an inversion, then there must be another element c > a that pops the a out before b is pushed onto the stack, thus maintaining the inversion. If such an element is present in p′ we need not do anything. If there is no such element we need to mark the region above a and between a and b with a “1”.

(2) If a > b is an inversion in p′ that must become a non-inversion in p, then we must make sure a stays on the stack until b arrives, and in order to do that we must shade all the boxes above a and between a and b. In particular there can be no other elements of p′ in this shaded region. If a < b is a non-inversion in p′ then it will still be a non-inversion in p after sorting.

This suffices to generate the set of marked mesh patterns P from a classical pattern p. We will see later that if we start with a mesh pattern p then it will be more difficult to find the set P and we will be forced to use the decorated patterns we introduced above.

3.2. The bubble-sort operator. The bubble-sort operator is a very inefficient way of sorting a permutation. It works on adjacent locations in a permutation and if the left element is larger than the right one, they are swapped. For example, one pass of bubblesort on the permutation 52134 produces 21345, since the 5 will travel from the front to the back. As another example, bubble-sorting 521634 produces 215346. A slight modification of the method described above works equally well for this operator. Let B(π) denote the output of one pass of bubble-sort on π. Consider for example permutations π such that B(π) = id. We see that B(π) contains the pattern 21 if and only if π contains

.

To make sure that these elements stay in this order, we either need a large element in front of the 2, which would mean the 2 would never be moved; or we need a large element in between the 2 and the 1 that will stop the 2 from moving past 1. We arrive at the marked mesh pattern

1 .

This pattern is equivalent to the two classical patterns 231 and 321. Albert, Atkinson, Bouvel, Claesson and Dukes [3] first made this result explicit, that B(π) = id if and only if π avoids 231 and 321. In the same paper the authors show that for any classical pattern p with at least three left-to-right maxima, the third of which is not the final symbol of p, the set B^{−1}(Av(p)) is not a classical pattern class, i.e., not described by classical patterns. We consider the smallest example of such a pattern, p = 1243.

Proposition 3.3.

B^{−1}(Av(1243)) = Av ( _{1}  , _{1}  , _{1}  , _{1}  ) .

Remark. Note that all the patterns can be expanded to mesh patterns, but we would then have eight patterns instead of the four above.

Proof of Proposition 3.3. It is easy to see that the underlying classical patterns are the only ones that are possible. Showing that the additional shadings and/or markings are necessary is similar for all of the patterns, so we just consider the third one. The 2 must move past the 1, which is achieved by adding the shading above it. The 4 must not move past the 3 so there must either be a large element in front of it, implying that it will never move, or between it and the 3, implying that it will not move past the 3. □

4. Describing West-3-stack sortable permutations

We now move on to the case of West-3-stack sortable permutations, i.e., permutations π such that S^{3}(π) = id. By West’s result, stated in Theorem 3.2, we know that π will be sorted by three passes through the stack if and only if S(π) avoids the two patterns

W_{1} =  , W_{2} =  .

We will use the same method as we did above, but when we consider the pattern on the right, the shaded box will cause some complications and the decorated patterns introduced above will be necessary. We therefore consider the pattern on the left first.

Lemma 4.1. Let π be a permutation. An occurrence of W_{1} in S(π) comes from exactly one of the patterns below in π.

I_{1} =  , I_{2} =  , I_{3} =  ,

I_{4} =  , I_{5} =

Remark. It is easy to see that the patterns 231, W_{1}, I_{1} are part of a family, whose k-th member prohibits a permutation containing it from being West-k-stack sortable.

Proof of Lemma 4.1. The element 5 in all the patterns is added in to pop all the large elements out before the 1 is pushed on the stack. It is easy to see that the underlying classical patterns in the lemma, without the 5, are the only possible candidates for producing an occurrence of W_{1} in S(π). Since proving that a particular shading must be applied to each of the patterns is similar, we only consider I_{5}. This pattern comes from the elements

in the pattern W_{1} having been arranged in the pattern in π. In order for the

elements to come out in the order we want, the 4 must stay on the stack until both 3 and 2 have been pushed onto the stack. Also, 3 must remain on the stack until 2 arrives. We must therefore shade boxes (1, 3), (1, 4), (2, 2), (2, 3) and (2, 4). Finally, the elements 2, 3 and 4, must leave the stack before 1 arrives, so we must add an extra element, the 5, in between 4 and 1. □

We now consider the pattern W_{2}, but without the shading.

Lemma 4.2. Let π be a permutation. An occurrence of in S(π) comes from

exactly one of the patterns below in π.

j_{1} = _{1}  , j_{2} =  , j_{3} = _{1}

Proof. As in the proof of Lemma 4.1, the 5 is added in to pop out the large elements and it is easy to see that only the classical patterns underlying j_{1}, j_{2}andj_{3} (without the 5) could possibly produce an occurrence of 3241 in S(π).

(1) For the classical pattern underlying j_{1} to become 3241 in S(π) there must be an element in the marked region that pops the 3 out of the stack.

(2) Boxes (2, 4) and (2, 5) in the classical pattern underlying j_{2} must be shaded to ensure that 3 stays on the stack until 2 is put on the stack.

(3) The pattern j_{3} comes from the elements in the pattern W_{2} having been arranged

in the pattern in π. In order for the elements to come out in the order

we want, the 4 must stay on the stack until 2 arrives and this explains the shaded boxes in j_{3}. Now the 3 must be popped out before the 2 arrives and that explains the marking in box (2, 3). □

We must now consider under which additional conditions the patterns j_{1}, j_{2} and j_{3} in the lemma will cause the correct shading in the pattern W_{2}. We express these conditions in the following lemma and two propositions.

Lemma 4.3. An occurrence of j_{3} in a permutation π will become an occurrence of W_{2} in S(π).

We leave the proof to the reader. We rename the pattern J_{3} and note that it can also be expanded into a mesh pattern.

J_{3} = _{1} =

Proposition 4.4. An occurrence of j_{2} in a permutation π will become an occurrence of W_{2} in S(π) if and only if it is part of one of the patterns below, where the elements that have been added to the pattern j_{2} are circled.

J_{2,1} =  , J_{2,2} =  , J_{2,3} =  ,

J_{2,4} =  , J_{2,5} =  , J_{2,6} =  ,

J_{2,7} =  , J_{2,8} =  , J_{2,9} =  ,

J_{2,10} =  , J_{2,11} =  , J_{2,12} =  .

Proof. To ensure that there are no elements in the shaded box in W_{2} we must look at the element that pops 3 in j_{2}. There are four different possibilities.

j_{2,1} =  , j_{2,2} =  , j_{2,3} =  ,

j_{2,4} =  .

We explain the shadings and the decoration of the pattern j_{2,2} as the others are similar. For this pattern, the size of the element that popped the 3 from the stack was in-between the 4 and the 5. Since this was the element that popped the 3 there can be no elements in boxes (1, 3), …, (1, 6). The boxes (2, 5) and (2, 6) can not contain an element, since this would pop out the element we just added (the 5 in j_{2,2}) and this element would land in the shaded box in W_{2}. Now consider the decorated box (2, 4). It can contain elements, but none of them are allowed to leave the stack prior to the 4 being pushed on, since any one of them would then land in the shaded box in W_{2}. Any elements in this region must then be in descending order, or equivalently, avoid the pattern 12.

We also need to make sure that there elements that arrived on the stack prior to 3 are not popped out and into the shaded region in W_{2}. We do the patterns in order of difficulty, which happens to be the reverse order.

(1) Consider the pattern j_{2,4}. No additional shadings are necessary, and we rename this pattern J_{2,12} for future reference.

(2) Consider the pattern j_{2,3}. If there are elements in boxes (0, 4) and (0, 5) that are still on the stack when 3 is pushed on they will be popped by the 6 and will land in the shaded region in W_{2}. We must therefore have these boxes empty, or an element in box (0, 6) that pops everything out before 3 is pushed on. We get the two patterns

J_{2,10} =  , J_{2,11} =  .

(3) Consider the pattern j_{2,2}. If there are elements in box (0, 4) that are still on the stack when 3 is put on they will be popped by the 5 and will land in the shaded region W_{2}. We must therefore have this box empty, or an element in box (0, 5) or (0, 6) that pops everything out before 3 is pushed on. We get the three patterns

J_{2,7} =  , J_{2,8} =  , J_{2,9} =  .

(4) Consider the pattern j_{2,1}. If there are elements in boxes (0, 5) and (0, 6) then they must not be popped by the elements in the decorated region (boxes (2, 6) and (2, 7)). We must therefore consider three cases:

• The decorated region is empty: in this case we do not need to worry about anything prior to 3 and get the pattern

J_{2,1} = .

• The upper box of the decorated region is empty, but not the lower box: we choose the top-most element in the lower box and add it to the pattern.

We can now handle this pattern the same way we handled the pattern j_{2,2} above and get three patterns.

J_{2,2} =  , J_{2,3} =  , J_{2,4} =

• The upper box of the decorated region is not empty: we choose the top-most element and add it to the pattern.

We can again handle this pattern the same way we handled the pattern j_{2,2} above and get two patterns.

J_{2,5} =  , J_{2,6} =  □

We now consider the last pattern, j_{1}, and which conditions must be imposed on it in order to get W_{2} after sorting.

Proposition 4.5. An occurrence of j_{1} in a permutation π will become an occurrence of W_{2} in S(π) if and only if it is part of one of the patterns below, where the elements that have been added to the pattern j_{1} are circled.

J_{1,1} =  , J_{1,2} =  , J_{1,3} =  ,

J_{1,4} =  , J_{1,5} =  , J_{1,6} =  ,

J_{1,7} =  , J_{1,8} =  , J_{1,9} =  ,

J_{1,10} =  , J_{1,11} =  .

Proof. To ensure that there are no elements in the shaded box in W_{2} we must look at the element that pops 3 in j_{1}. There are three different possibilities.

j_{1,1} =  , j_{1,2} =  , j_{1,3} =  .

We also need to make sure that elements that arrived on the stack prior to 3 are not popped out and into the shaded region in W_{2}. The derivation of the patterns in the proposition is identical to the proof of Proposition 4.4. □

Put together, Lemmas 4.1 and 4.3, with Propositions 4.4 and 4.5, produce a list of 29 patterns describing permutations that are not West-3-stack sortable. We can simplify this list considerably as follows: since the patterns J_{1,1}, …, J_{1,6} all imply containment of I_{1} we can remove them. Similarly J_{2,12} removes J_{1,7}, …, J_{1,9}; I_{1} removes J_{2,1}, …, J_{2,6}; I_{2} removes J_{2,7}, …, J_{2,9}, and I_{4} removes J_{3}.

We are left with the fact that a permutation is West-3-stack-sortable if and only if it avoids the patterns

I_{1} =  , I_{2} =  , I_{3} =  , I_{4} =  ,

I_{5} =  , J_{2,12} =  ,

J_{1,10} =  , J_{2,10} =  ,

J_{1,11} =  , J_{2,11} =  .

If the decorated region in J_{2,10} contains an element in the lower box then it will produce an occurrence of I_{5}. The same is true of J_{2,11}. We can therefore replace these patterns with

J_{2,10} =  , J_{2,11} =  .

(keeping the names of the patterns unchanged). The pattern J_{1,10} can be simplified as well. The lower box in the decorated region can contain at most one element, since otherwise we would have an occurrence of I_{2}. We begin by replacing it with

,

and notice that the second pattern above implies containment of J_{2,10}. We therefore replace J_{1,10} with the first pattern.

The pattern J_{1,11} can be simplified in the same way. The lower box in the decorated region can contain at most one element, since otherwise we would have an occurrence of I_{2}. We begin by replacing it with

,

and notice that the second pattern above implies containment of J_{2,11}. We therefore replace J_{1,11} with the first pattern.

We have therefore proven the following.

Theorem 4.6. A permutation π is West-3-stack-sortable, i.e., S^{3}(π) = id, if and only if it avoids the decorated patterns

I_{1} =  , I_{2} =  , I_{3} =  , I_{4} =  ,

I_{5} =  , J_{2,12} =  ,

J_{1,10} =  , J_{2,10} =  ,

J_{1,11} =  , J_{2,11} =  .

5. Open problems

Above we only had use for decorated patterns where the entries in certain boxes needed to avoid a particular pattern. One might guess that in some situations it could be useful to require the entries to contain a particular pattern instead. Furthermore, one could go as far as assigning a set X_{(i,j)} to the entries in box (i, j) and then placing restrictions on those sets, such as X_{(1,1)} = ∅, #X_{(2,3)} ≥ 2, X_{(0,1)} avoids 123, X_{(3,2)} ∪ X_{(3,3)} contains the pattern 21 etc. For a concrete example, note that a fixed point is an occurrence of the pattern (1, #X_{(0,1)} = #X_{(1,0)}).

We end with some open problems related to the above.

(1) The number of West-2-stack-sortable permutations was conjectured by West [17] to be 2(3n)!/((n + 1)!(2n + 1)!). This conjecture was proven by Zeilberger [20]. Later Dulucq, Gire and West [9] found these permutations to be in bijection with rooted non-separable planar maps. The enumeration of West-3-stack-sortable permutations is still completely open.

(2) One might hope the method we described above for finding a set of patterns P such that S^{−1}(Av(p)) = Av(P) could be turned into an algorithm. This is definitely feasible for classical patterns p, but might be difficult for mesh patterns p.

(3) Our method was shown to work as well with the bubble-sort operator. Hopefully it can be applied to other similar sorting operators.

(4) We noted in subsection 3.1 that there is another set of permutations called the 2stack-sortable permutations. It is known that classical patterns suffice to describe this set but it is not known which classical patterns. See Albert, Atkinson and Linton [2] for recent work on this.

The author hopes to pursue each of the open problems mentioned above in future work.

Acknowledgements. The author would like to thank Anders Claesson for suggesting the problem of describing West-3-stack-sortable permutations, as well as for help with testing Theorem 4.6 with a computer. The author would also like to thank Christian Krattenthaler and an anonymous referee for detailed comments. The author is supported by grant no. 090038013 from the Icelandic Research Fund.

References

1. Michael H. Albert and Mike D. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005), 1–15.

2. Michael H. Albert, Mike D. Atkinson, and Steve Linton, Permutations generated by stacks and deques, Ann. Comb. 14 (2010), 3–16.

3. Michael H. Albert, Mike D. Atkinson, Mathilde Bouvel, Anders Claesson, and Mark Dukes, On the inverse image of pattern classes under bubble sort, Journal of Combinatorics 2 (2011), 231–243.

4. Eric Babson and Einar Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Art. B44b, 18 pp.

5. Miklós Bóna, A survey of stack-sorting disciplines, Electron. J. Combin. 9(2) (2002/03), Art. 1, 16 pp., Permutation patterns (Otago, 2003).

6. Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations, J. Combin. Theory Ser. A 117 (2010), 884–909.

7. Petter Brändén and Anders Claesson, Mesh patterns and the expansion of permutation statistics as sums of permutation patterns, Electron. J. Combin. 18(2) (2011), Art. #P5, 14 pp.

8. Robert Brignall, A survey of simple permutations, Permutation patterns, London Math. Soc. Lecture Note Series, vol. 376, Cambridge Univ. Press, Cambridge, 2010, pp. 41–65.

9. Serge Dulucq, Sophie Gire, and Julian West, Permutations with forbidden subsequences and nonseparable planar maps, Discrete Math. 153 (1996), 85–103.

10. Ísak Hilmarsson, Ingibjörg Jónsdóttir, Steinunn Sigurðardóttir, Sigríður Viðarsdóttir, and Henning Úlfarsson, Wilf-classification of mesh patterns of short length, in preparation, 2011.

11. Sophie Huczynska and Vincent Vatter, Grid classes and the Fibonacci dichotomy for restricted permutations, Electron. J. Combin. 13(1) (2006), Research Paper 54, 14 pp.

12. Donald E. Knuth, The art of computer programming, second ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975, Volume 1: Fundamental algorithms, Addison-Wesley Series in Computer Science and Information Processing.

13. William M. McGovern, Closures of K-orbits in the flag variety for SU^{∗}(2n), Represent. Theory 15 (2011), 568–573.

14. Maximillian M. Murphy and Vincent R. Vatter, Profile classes and partial well-order for permutations, Electron. J. Combin. 9(2) (2002/03), Research Article 17, 30 pp. Permutation patterns (Otago, 2003).

15. Henning Úlfarsson, A unification of permutation patterns related to Schubert varieties, Pure Math. Appl. 22 (2011), 273–296.

16. Henning Úlfarsson and Alexander Woo, Which Schubert varieties are local complete intersections?, Proceedings of the 24th Int. Conference on Formal Power Series and Algebraic Combinatorics, Nagoya, 2012 (to appear).

17. Julian West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D. thesis, MIT, 1990.

18. Alexander Woo and Alexander Yong, When is a Schubert variety Gorenstein?, Adv. Math. 207 (2006), 205–220.

19. , Governing singularities of Schubert varieties, J. Algebra 320 (2008), 495–520.

20. Doron Zeilberger, A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!), Discrete Math. 102 (1992), 85–93.

School of Computer Science, Reykjavík University, Menntavegi 1, 101 Reykjavík, Iceland

  E-mail address: henningu@ru.is