title: Stack-Sorting with Consecutive-Pattern-Avoiding Stacks
authors: Colin Defant Kai Zheng
text: 
  
  ]Stack-Sorting with Consecutive-Pattern-Avoiding Stacks
  [2010]
  
  
  ]Colin Defant
  []Fine Hall, 304 Washington Rd., Princeton, NJ 08544
  cdefant@princeton.edu
  ]Kai Zheng
  []Fine Hall, 304 Washington Rd., Princeton, NJ 08544
  kzheng@princeton.edu
  [
      [
      December 30, 2023
  =====================
  
  
  
  
  We introduce consecutive-pattern-avoiding stack-sorting maps _σ, which are natural generalizations of West's stack-sorting map s and natural analogues of the classical-pattern-avoiding stack-sorting maps s_σ recently introduced by Cerbai, Claesson, and Ferrari. We characterize the patterns σ such that (_σ), the set of permutations that are sortable via the map s∘_σ, is a permutation class, and we enumerate the sets (_σ) for σ∈{123,132,321}. We also study the maps _σ from a dynamical point of view, characterizing the periodic points of _σ for all σ∈ S_3 and computing max_π∈ S_n|_σ^-1(π)| for all σ∈{132,213,231,312}. In addition, we characterize the periodic points of the classical-pattern-avoiding stack-sorting map s_132, and we show that the maximum number of iterations of s_132 needed to send a permutation in S_n to a periodic point is n-1. The paper ends with numerous open problems and conjectures. 
  
  
  
  
  § INTRODUCTION
  
  
  
   §.§ Background
  
  
  Let S_n denote the set of permutations of the set [n]:={1,…,n}, which we write as words in one-line notation. The investigation of pattern avoidance in permutations began in 1968, when Knuth <cit.> introduced a stack-sorting machine and showed that a permutation can be sorted to the identity permutation using this machine if and only if it avoids the pattern 231 (we define pattern containment and avoidance formally below). In his 1990 Ph.D. dissertation, West <cit.> introduced a deterministic variant of Knuth's machine; this variant is a function s:S_n→ S_n. As in Knuth's case, a permutation π∈ S_n satisfies s(π)=123⋯ n if and only if it avoids 231. More recently, Albert, Homberger, Pantone, Shar, and Vatter <cit.> introduced a vast generalization of Knuth's stack-sorting machine by considering 𝒞-machines. Roughly speaking, a 𝒞-machine is a sorting machine that uses a stack whose entries, when read from top to bottom, must have the same relative order as an element of the permutation class 𝒞. Even more recently, Cerbai, Claesson, and Ferrari <cit.> generalized West's stack-sorting map in a similar manner. For each permutation pattern σ, they defined a map s_σ:S_n→ S_n that sends each permutation through a stack in a right-greedy manner, insisting that the contents of the stack must avoid the pattern σ when read from top to bottom. In this more general setup, West's stack-sorting map is just s_21. Although the article <cit.> is quite recent, it has already spawned several subsequent papers <cit.>. 
  
  In this article, we introduce consecutive-pattern-avoiding stack-sorting maps _σ. In order to define the maps s_σ and _σ formally and simultaneously, it is helpful to define more general maps T_𝒜 dependent on sets 𝒜 of permutations. Assume we are given an input permutation π=π_1⋯π_n. Throughout this procedure, we consider the permutation obtained by reading the contents of a vertical stack from top to bottom. If moving the next entry in the input permutation to the top of the stack results in a stack whose contents have the same relative order as any element of 𝒜, then the next entry in the input permutation is placed at the top of the stack (this operation is called a push). Otherwise, the entry at the top of the stack is annexed to the end of the growing output permutation (this operation is called a pop). This procedure stops when the output permutation has length n. We then define T_𝒜(π) to be this output permutation. When 𝒜 is the set of permutations that avoid σ, the map T_𝒜 is s_σ. Our focus in this article is on the case in which 𝒜 is the set of permutations that avoid σ as a consecutive pattern, in which case we write T_𝒜=_σ. 
  
  
  The following diagram portrays the steps involved in sending the permutation 265413 through a consecutive-231-avoiding stack, showing that _231(265413)=653142. 
  
  
  
      < g r a p h i c s >
  
  
    
  Notice that there is one step where the contents of the stack, when read from top to bottom, form the permutation 3142. The permutation 3142 contains the pattern 231 classically (i.e., nonconsecutively), but avoids 231 consecutively, which is why it is allowed to be in the stack. On the other hand, this would not be allowed if we were using a classical-231-avoiding stack. In that case, the steps would proceed as in the following diagram, which shows that s_231(265413)=651432. 
  
  
  
  
      < g r a p h i c s >
  
  
    
  
  
  
  Our newly-defined maps _σ serve as perfectly legitimate generalizations of West's stack-sorting map because _21 is the same as s, which is also the same as s_21 (a permutation avoids the pattern 21 classically if and only if it avoids 21 consecutively). However, when the length of σ is at least 3, the maps _σ and s_σ exhibit different behaviors. 
  
  The decision to consider stacks that avoid consecutive patterns, rather than stacks that avoid classical patterns, is very natural. Indeed, when one actually works through the process of sending a permutation through a classical-21-avoiding stack, one checks at each step whether the next entry in the input permutation is greater than the entry currently sitting at the top of the stack. One does not bother checking if the next entry in the input is greater than all of the entries in the stack because the smallest number in the stack is necessarily the top entry (this is another manifestation of the simple observation that a permutation avoids 21 classically if and only if it avoids 21 consecutively). If σ has length k≥ 3, then when one sends a permutation through a classical-σ-avoiding stack, one must check all of the entries in the stack to see if the addition of the next entry produces an occurrence of the pattern σ. By contrast, when one sends a permutation through a consecutive-σ-avoiding stack, it is only necessary to compare the next entry in the input permutation with the top k-1 entries in the stack. In this way, the mechanics governing the maps _σ are in some sense “closer” to those governing West's stack-sorting map than those of the maps s_σ are.  
  
  Typically, researchers have approached West's stack-sorting map from a “sorting” point of view. The usual questions concern structural and enumerative aspects of t-stack-sortable permutations, which are permutations that get sorted to the identity using at most t iterations of the map s <cit.>. On the other hand, there are now several articles that study the stack-sorting map from a “dynamical” point of view (see <cit.> and the references therein). In this approach, we view the stack-sorting map as an interesting combinatorially-defined function, without caring so much about trying to sort permutations. The typical questions concern the number of preimages of a permutation under s, which is called the fertility of the permutation. The investigation of fertilities of permutations has revealed unexpected patterns and connections with several other aspects of combinatorics <cit.>, 
  
  including a very surprising and useful link with the combinatorics of cumulants in noncommutative probability theory <cit.>. This dynamical approach concerning fertilities has also shed new light on the t-stack-sortable permutations studied from the sorting point of view <cit.>. 
  
  In this paper, we consider the maps _σ from both the sorting point of view and the dynamical point of view. All of the sorting questions we consider are analogues of questions asked about the maps s_σ in <cit.>. On the other hand, our dynamical approach is completely novel in the realm of pattern-avoiding stack-sorting maps (other than s itself). We will also see that there are several dynamical questions that one can ask about the maps _σ that are trivial when σ=21 (i.e., when _σ=s), but which become much more interesting when the length of σ is at least 3. 
  
  
  
   §.§ Outline and Summary of Main Results
  
  
  The articles <cit.> focus primarily on the set (s_σ) of permutations that get sorted to the identity using a σ-avoiding stack followed by a classical-21-avoiding stack. Since the set of permutations that s maps to the identity is the set (231) of 231-avoiding permutations, we have (s_σ)=s_σ^-1((231)). Note that (s_21)=s^-1((231)) consists of the 2-stack-sortable permutations, which have received an enormous amount of attention since their inception in West's dissertation <cit.>. Let us also remark that the articles <cit.> have studied other close variants of these sets; for example, the paper <cit.> explores the sets (s_σ,τ)=s_σ,τ^-1((231)), where s_σ,τ is the map that sends a permutation through a right-greedy stack whose contents avoid both σ and τ (using our earlier notation, s_σ,τ=T_(σ,τ)). In Section <ref>, we define (_σ)=_σ^-1((231)), which can similarly be seen as the set of permutations that get sorted into the identity by a consecutive-σ-avoiding stack followed by a 21-avoiding stack. We will prove that if σ∈ S_k for some k≥ 3, then (_σ) is a permutation class if and only if σ and σ both contain the pattern 231, where σ is the permutation obtained by swapping the first 2 entries in σ; this is a direct analogue of one of the main results from <cit.>. 
  
  The other main results from <cit.> concern the enumeration of the sets (s_123) and (s_321). Extending this work, the article <cit.> focuses on the enumeration of the set (s_132). In Sections <ref> and <ref>, we give analogues of these results by characterizing and enumerating the sets (_123), (_321), and (_132). More precisely, we will see that (_123) is enumerated by the first differences of Motzkin numbers, that (_321) is enumerated by the Motzkin numbers, and that (_132) is enumerated by the Catalan numbers. 
  
  In Section <ref>, we adopt the dynamical point of view and consider the periodic points of the maps _σ, which we view as functions from S_n to S_n for each n≥ 1. It is easy to show that the only periodic point of s:S_n→ S_n is the identity permutation 123⋯ n. By contrast, if the length of σ is at least 3, then _σ has multiple periodic points. We will prove that if σ∈ S_3, then the periodic points of _σ:S_n→ S_n are precisely the permuatations in S_n that avoid σ and its reverse as consecutive patterns.
  
  It is known that the identity permutation 123⋯ n, which has C_n:=1/n+12n n preimages under s, has strictly more preimages under s than every other permutation in S_n (see <cit.>). The analogous results for the maps _σ are more difficult. In Section <ref>, we study preimages under the maps _132 and _312, proving in particular that 
      max_π∈ S_n|_132^-1(π)|=max_π∈ S_n|_312^-1(π)|=n-1⌊n-1/2⌋
   (along the way, we obtain a simple formula for |_132^-1(π)| for all reverse-layered permutations π). In Section <ref>, we prove a similar result for the maps _231 and _213, showing that 
      max_π∈ S_n|_231^-1(π)|=max_π∈ S_n|_213^-1(π)|=2^n-2
   when n≥ 2.
  
  Section <ref> is a little different from the rest of the paper because it focuses on classical-pattern-avoiding stack-sorting maps instead of consecutive-pattern-avoiding stack-sorting maps. The purpose of this section is to prove dynamical results about the maps s_132 and s_312. Such questions have not previously been considered for these maps, and we believe our results open the gate for interesting further developments. Specifically, we prove that the periodic points of s_132 (respectively, s_312) are precisely the permutations that avoid 132 and 231 (respectively, 312 and 213). We also prove the the maximum number of iterations needed for s_132 (respectively, s_312) to send a permutation to one of its periodic points is n-1 (these results are much more difficult than the analogous results for West's stack-sorting map). 
  
  Finally, Section <ref> collects a large number of open problems, conjectures, and other suggestions for future work. 
  
  
  
   §.§ Terminology and Notation
  
  
  Recall that in this article, a permutation is an ordering of the elements of the set [n] for some n. If π is a sequence of n distinct integers, then the standardization of π is the permutation in S_n obtained by replacing the ith-smallest entry in π with i for all i. For example, the standardization of 4829 is 2314. We say two sequences have the same relative order if their standardizations are equal. We say a permutation σ contains a permutation τ as a pattern if there is a (not necessarily consecutive) subsequence of σ that has the same relative order as τ; otherwise, σ avoids τ. We say σ contains τ consecutively if σ has a consecutive subsequence with the same relative order as τ; otherwise, σ avoids the consecutive pattern τ. When we wish to stress that pattern containment (or avoidance) is nonconsecutive, we will sometimes call it classical pattern containment (or avoidance). We refer to the standard references <cit.> for more information about classical and consecutive permutation patterns. 
  
  We denote consecutive patterns by underlining them (or referring to them as consecutive patterns). If τ^(1),τ^(2),… is a (finite or infinite) list of classical or consecutive patterns, then we write _n(τ^(1),τ^(2),…) for the set of permutations in S_n that avoid τ^(1),τ^(2),…. We also write (τ^(1),τ^(2),…)=⋃_n≥ 0_n(τ^(1),τ^(2),…). For example, (231,321) is the set of permutations that avoid 231 and 321, while (321) is the set of permutations that avoid the consecutive pattern 321. If τ is an arbitrary unspecified permutation, then we let (τ) be the set of permutations that consecutively avoid τ. 
  
  Given a permutation σ=σ_1⋯σ_k of length k≥ 2, we let σ=σ_2σ_1σ_3⋯σ_k denote the permutation obtained by swapping the first two entries in σ. We also let (σ)=σ_k⋯σ_1 denote the reverse of σ. If σ∈ S_k, then we write (σ)=(k+1-σ_1)⋯(k+1-σ_k) for the complement of σ. A descent (respectively, ascent) of σ is an index i such that σ_i>σ_i+1 (respectively, σ_i<σ_i+1). An ascending run of σ is a maximal consecutive increasing subsequence of π, while a descending run is a maximal consecutive decreasing subsequence. For example, the ascending runs of 7862351 are 78, 6, 235, and 1, while the descending runs of 7862351 are 7, 862, 3, and 51. We write |τ| for the length of a sequence τ of positive integers.  
  
  
  
   §.§ A Preliminary Lemma
  
  Before we proceed, it will be helpful to record the following lemma, which will allow us to simplify many of our considerations. The proof of this lemma is immediate from the definitions of s_σ and _σ. 
  
  
  If σ∈ S_k for some k≥ 2, then 
      s_(σ)=∘ s_σ∘  and  _(σ)=∘_σ∘.
   
  
  
  
  
  
  
  § WHEN IS (_Σ) A PERMUTATION CLASS?
  
  
  A permutation class is a set 𝒞 of permutations that is closed under classical pattern containment. Said differently, this means that if σ,τ are permutations such that σ contains τ classically and σ∈𝒞, then τ∈𝒞. Equivalently, a set of permutations is a permutation class if and only if it is of the form (τ^(1),τ^(2),…) for some classical patterns τ^(1),τ^(2),…. 
  
  Recall that σ is the permutation obtained by swapping the first two entries in σ. Furthermore, (s_σ)=s_σ^-1((231)) is the set of permutations that get sorted into the identity by the map s∘ s_σ. The following theorem is one of the main results in <cit.>. 
  
  
  Let σ∈ S_k for some k≥ 2. The set (s_σ) is a permutation class if and only if σ=12 or σ contains the pattern 231 classically. 
  
  
  Our goal in this section is to prove the following analogue of Theorem <ref> for the consecutive-pattern-avoiding stack-sorting maps _σ. Recall that (_σ)=_σ^-1((231)) is the set of permutations that get sorted into the identity by the map s∘_σ. 
  
  
  The set (_12) is equal to the permutation class (213), while (_21) is not a permutation class. If σ∈ S_k for some k≥ 3, then the set (_σ) is a permutation class if and only if σ and σ both contain the pattern 231 classically. In this case, (_σ)=(132). 
  
  
  We will prove Theorem <ref> via the following two lemmas. Recall that (σ) denotes the reverse of the permutation σ. 
  
  
  Let σ∈ S_k for some k≥ 3. If σ contains 231 classically, then (_σ) is the set (132,(σ)) of permutations that avoid 132 classically and avoid (σ) consecutively.
  
  
  
  In general, it is immediate from the definition of _σ that _σ(π)=(π) whenever π avoids (σ) consecutively. Indeed, in this case, all of the entries in π enter the stack and then proceed to exit the stack in the reverse of the order in which they entered. It follows that if π avoids (σ) consecutively and avoids 132 classically, then _σ(π)=(π)∈(231). Furthermore, if π contains 132 classically and avoids (σ) consecutively, then _σ(π)=(π) contains 231 classically. This implies that π∉(_σ).
  
  Suppose now that π contains (σ) consecutively, and let i be the minimal index such that π_i⋯π_i+k-1 is a consecutive occurrence of the pattern (σ). Consider sending π through a consecutive-σ-avoiding stack. When π_i+k-1 is about to enter the stack, the top k-1 entries in the stack, read from top to bottom, are π_i+k-2,…,π_i. The entry π_i+k-2 pops out of the stack, and the entry π_i+k-1 enters the stack immediately afterward. Once all of the entries have finally exited the stack, the entries π_i+k-2,π_i+k-1,π_i+k-3,…,π_i will appear in this order in the output permutation _σ(π). However, π_i+k-2π_i+k-1π_i+k-3⋯π_i has the same relative order as σ, which in turn contains 231 classically by hypothesis. This shows that _σ(π)∉(231), so π∉(_σ). 
  
  
  
  If σ∈_k(231) for some k≥ 3, then (_σ) is not a permutation class. 
  
  
  
  We first dispose of the case in which σ=231. A simple computation yields _231(2413)=3142∉(231) and _231(25314)=54132∈(231). This shows that 25314 is in (_231) while 2413 is not. Since 25314 classically contains 2413, it follows that (_231) is not a permutation class. We may now assume σ≠ 231. Because the length of σ is at least 3, we have _σ(132)=231. This shows that 132∉(_σ). 
  
  Let us now assume that σ classically contains 231 but is not equal to 231. One can easily check that _σ((σ))=σ, and we assumed that σ∈(231). This shows that (σ)∈(_σ). Now note that (σ) contains 132 classically and that 132∉(_σ). It follows that (_σ) is not a permutation class in this case.  
  
  Next, assume σ∈(231), σ_1<σ_2, and σ_2>2. These assumptions force σ_1=1 since, otherwise, the entries σ_1,σ_2,1 would form a classical 231 pattern in σ. Let π=σ_k'⋯σ_2'σ_1'σ_2, where σ_i'=σ_i if σ_i<σ_2 and σ_i'=σ_i+1 if σ_i≥σ_2. We will prove that π∈(_σ). Since the entries 2,σ_2',σ_2 form an occurrence of the classical pattern 132 in π and 132∉(_σ), this will imply that (_σ) is not a permutation class. One can easily compute that _σ(π)=σ_2'σ_2σ_1'σ_3'⋯σ_k'. Notice that the permutation σ_2σ_1'σ_3'⋯σ_k' has the same relative order as σ, which avoids 231 classically by hypothesis. Therefore, if _σ(π) contains 231, then the first entry in the occurrence of the 231 pattern must be σ_2'. Since σ_2'=σ_2+1, we can replace σ_2' with σ_2 in this subsequence in order to obtain an occurrence of the pattern 231 in _σ(π) that starts with the entry σ_2. However, this contradicts our earlier observation that σ_2σ_1'σ_3'⋯σ_k' avoids 231. 
  
  For our next case, we assume σ∈(231), σ_1=1, and σ_2=2. Let π=σ_k⋯σ_321(k+1) be the concatenation of (σ) with the entry k+1. Let π'=σ_k⋯σ_32(k+1)1(k+2). The first 3 entries of the permutation _σ(π)=2(k+1)1σ_3⋯σ_k form a 231 pattern, so π∉(_σ). On the other hand, since π' certainly avoids the pattern (σ) consecutively, we have _σ(π')=(π')=(k+2)1(k+1)2σ_3⋯σ_k. The assumption σ∈(231) guarantees that _σ(π')∈(231), so π'∈(_σ). The permutation π' contains π classically, so (_σ) is not a permutation class in this case. 
  
  The final case we need to consider is that in which σ∈(231) and σ_1>σ_2. Notice that the hypothesis σ∈(231) forces σ_2=1 in this case. Let π=σ_k'⋯σ_2'σ_1'2, where σ_2'=1 and σ_i'=σ_i+1 for all i≠ 2. We have _σ(π)=12σ_1'σ_3'⋯σ_k'; note that this permutation avoids 231 because σ avoids 231. Therefore, π∈(_σ). The entries σ_2',σ_1',2 form an occurrence of the pattern 132 in π, and we have seen that 132∉(_σ). Therefore, (_σ) is not a permutation class in this final case. 
  
  
  
  It is straightforward to check that if π∈ S_n for some n≥ 1, then the last entry in _12(π) is 1. It follows that _12(π) avoids 231 if and only if it avoids 12. Using Lemma <ref>, we find that 
      (_12)=_12^-1((231))=_12^-1((12))=(_21^-1(((12))))
   
      =(s^-1((21)))=((231))=(213).
   On the other hand, the set (_21) is not a permutation class because it includes the permutation 35241 but not the permutation 3241. 
  
  Now assume σ∈ S_k for some k≥ 3. If σ and σ both contain 231 classically, then it follows from Lemma <ref> that 
      (_σ)=(132,(σ))=(132).
   If σ∈(231), then Lemma <ref> tells us that (_σ) is not a permutation class. Now assume σ∈(231) and σ∉(231). Note that this implies that σ_1>σ_2>1. Since _σ((σ))=σ, the permutation (σ) is not in (_σ). However, the permutation π=(σ_k+1)⋯(σ_2+1)1(σ_1+1), which contains (σ) classically, is in (_σ). To see this, note that the condition σ_1>σ_2>1 guarantees that π avoids (σ) consecutively. Therefore, _σ(π)=1(σ_1+1)(σ_2+1)⋯(σ_k+1), and this permutation avoids 231 because σ does. Hence, (_σ) is not a permutation class.  
  
  
  
  
  § PERIODIC POINTS
  
  In this section, we prove the following theorem, which completely classifies the periodic points of the consecutive-σ-avoiding stack-sorting map for σ∈ S_3. 
  
  
  Let σ∈ S_3. The periodic points of the map _σ:S_n→ S_n are precisely the permutations in _n(σ,(σ)). When n≥ 2, each of these periodic points has period 2. 
  
  
  Lemma <ref> tells us that for each permutation pattern σ, the maps _σ and _(σ) are topologically conjugate (with the discrete topology), with the complementation map  serving as the topological conjugacy. It follows that if Theorem <ref> holds when σ is some specific pattern τ, then it also holds when σ=(τ). Thus, we really only need to prove the theorem when σ∈{123,132,231}. We first handle the case in which σ∈{132,231}. 
  
  
  
  
  For σ∈{132, 231}, the set of periodic points of the map _σ:S_n→ S_n is the set _n(132,231) of permutations in S_n that avoid 132 and 231 consecutively (these permutations also avoid 132 and 231 classically). When n≥ 2, these points have period 2.
  
  
  
  
  Note that {132,231}={σ,(σ)}. It is clear that if π∈(132, 231), then _σ(π) = (π) ∈(132, 231), so _σ^2(π) = π. Hence, π  is a periodic point of _σ, and the period is 2 if n≥ 2. 
  
  We now prove that every periodic point of _σ:S_n→ S_n is in (132,231). This is trivial if n≤ 2, so we may assume n≥ 3 and induct on n. Given τ∈ S_n, let τ^* be the permutation in S_n-1 obtained by deleting the entry 1 from τ and then decreasing all remaining entries by 1. Observe that if the entries 1 and 2 appear consecutively in τ, then they also appear consecutively in _σ(τ) and that (_σ(τ))^*=_σ(τ^*). Now fix π∈ S_n. By induction, we have _σ^t(π^*)∈(132,231) for all sufficiently large t.  We will prove that if t is sufficiently large, then the entries 1 and 2 appear consecutively in _σ^t(π). It will then follow that (_σ^t(π))^*=_σ^t(π^*)∈(132,231) for all sufficiently large t, which will imply that _σ^t(π)∈(132,231) for all sufficiently large t. 
  
  Let D(τ) denote the number of entries between 1 and 2 in τ (regardless of whether 1 appears before or after 2 in τ). First, note that neither 1 nor 2 will get popped from the stack until after all of the entries of τ have entered the stack because neither 1 nor 2 can trigger the consecutive-σ-avoiding restriction when at the top of the stack. This immediately implies that D(τ) ≤ D(_σ(τ)). We further show that if D(τ)>0, then D(_σ^2(τ))<D(τ), implying that 1 and 2 are consecutive entries in _σ^t(π) for all sufficiently large t. Let {1, 2} = {τ_i, τ_i+c} so that D(π) = c-1, and assume c≥ 2. The consecutive subsequence τ_iτ_i+1⋯τ_i+c of τ contains a consecutive occurrence of either σ or (σ). If it contains a consecutive occurrence of (σ), then when τ_i+c enters the stack, the entries between τ_i and τ_i+c form a strict subset of {τ_i+1,…, τ_i+c-1}. Moreover, these entries are precisely the entries between 1 and 2 in _σ(τ) since neither 1 nor 2 is popped until all entries of τ have entered the stack. This implies that D(_σ(τ)) < D(τ). If there is no consecutive occurrence of (σ) in the consecutive subsequence τ_iτ_i+1⋯τ_i+c of τ, then τ_i+cτ_i+c-1⋯τ_i is a consecutive subsequence of _σ(τ) that contains a consecutive occurrence of (σ), so the previous argument guarantees that D(_σ^2(τ)) < D(_σ(τ))≤ D(τ).
  
  
  
  
  Next, we consider the periodic points of _123 and _321. By complementing, it suffices to just consider _321. To understand this map, it helps to decompose a permutation π by writing π = a_1 ⋯ a_k, where the a_i's are the ascending runs (maximal consecutive increasing subsequences). In addition, let a_i^m be the subsequence of a_i consisting of the entries that are not the first or last entries in a_i, and let a_i^e be the sequence obtained from a_i by deleting a_i^m. If |a_i| is 1 or 2, then a_i^e = a_i and a_i^m is an empty sequence. For example, the ascending runs of 4572136 are a_1 = 457, a_2 = 2, and a_3 = 136, with a_1^e = 47, a_2^e = 2, a_3^e = 16, a_1^m = 5, a_2^m empty, and a_3^m = 3.
  
   
  Keeping the notation above, let π = a_1 ⋯ a_k, where the a_i's are ascending runs. Then _321(π) = a_1^m ⋯ a_k^m (a_1^e ⋯ a_k^e) = a_1^m ⋯ a_k^m (a_k^e) ⋯(a_1^e).
  
  
  When the ascending run a_i enters the consecutive-321-avoiding stack, each entry in a^m is popped immediately after it enters while a_i^e remains in the stack. After all entries have been pushed into the stack, the entries remaining in the stack are popped out in the reverse of the order in which they entered and thus the output is a_1^m ⋯ a_k^m (a_1^e ⋯ a_k^e) =a_1^m ⋯ a_k^m (a_k^e) ⋯(a_1^e).
  
  
  To identify the periodic points of _321, we analyze how the number of peaks and valleys of a permutation π changes as _321 is iteratively applied to π. A peak (respectively, valley) of π = π_1 ⋯π_n is an index i∈{2,…,n-1} such that π_i-1<π_i>π_i+1 (respectively, π_i-1>π_i<π_i+1). If i is a peak (respectively, valley) of π, then the entry π_i is called a peak top (respectively, valley bottom) of π. We let g(π) denote the total number of indices that are either peaks or valleys of π. 
  
   
  Let π = a_1 ⋯ a_k∈ S_n, where a_1,…,a_k are the ascending runs of π. We have g(π) ≤ g(_321(π)). Moreover, if |a_k|≥ 2, then this inequality is an equality if and only if a_1^m ⋯ a_k^m (a_k^e) is a decreasing sequence. If |a_k|=1, then g(π)= g(_321(π)) if and only if a_1^m ⋯ a_k^m (a_k^e) is an increasing sequence. 
  
  
  We specifically show that the peak tops and valley bottoms of π are still peak tops and valley bottoms in _321(π). The key observation is that each peak top (valley bottom) of π is the second (first) entry of a_j^e for some ascending run a_j of length at least 2, and it is not the first or last entry of π.
  
  Suppose the entry π_i is a peak top of π. Then π_i is the last entry of some ascending run a_j of length at least 2. We have a_j^e=π_hπ_i for some π_h<π_i. Similarly, π_i+1 is the first entry of the ascending run a_j+1 and is less than π_i. By Lemma <ref>, the sequence (a_j+1^e)(a_j^e), which itself has π_i+1π_iπ_h as a consecutive subsequence, is a consecutive subsequence of _321(π). Consequently, π_i is still a peak top of _321(π).
  A completely analogous argument shows that every valley bottom of π is also a valley bottom of _321(π), so g(π)≤ g(_321(π)). 
  
  
  For the equality cases, suppose first that a_k has length at least 2. Note that g(π) = g(_321(π)) if and only if no entry in a_1^m ⋯ a_k^m (a_k^e) except for the last entry is a peak top or valley bottom in _321(π). This happens if and only if a_1^m ⋯ a_k^m (a_k^e) is an increasing or decreasing sequence. Since (a_k^e) is a decreasing sequence, it follows that g(π) = g(_321(π)) if and only if a_1^m ⋯ a_k^m (a_k^e) is a decreasing sequence. 
  
  Now suppose a_k has length 1. We again have g(π) = g(_321(π)) if and only if no element in a_1^m ⋯ a_k^m (a_k^e) is a peak top or valley bottom in _321(π). Note that a_1^m ⋯ a_k^m (a_k^e) is part of the consecutive subsequence a_1^m ⋯ a_k^m (a_k^e)(a_k-1^e) in _321(π). Since a_k has length 1, it is a single entry that is less than the entry before it in π; this entry before it is also the entry after it in a_1^m ⋯ a_k^m (a_k^e)(a_k-1^e). Thus, no entry in a_1^m ⋯ a_k^m (a_k^e) is a peak top or valley bottom if and only if a_1^m ⋯ a_k^m (a_k^e) is an increasing sequence. 
  
  
  By the previous lemma, it is clear that if g(π) < g(_321(π)), then π cannot be a periodic point. We make use of this fact when proving the next few results. 
  
   
  Let π = a_1 ⋯ a_k, where the a_i's denote ascending runs. If |a_k|≥ 3 or |a_1|=|a_2|=1, then π is not a periodic point of _321.
  
  
  If |a_k|≥ 3, then a_k^m(a_k^e) is not a decreasing sequence, so g(π) < g(_321(π)) by Lemma <ref>. Hence, π is not a periodic point of _321. If |a_1|=|a_2|=1, then _321(π) is a permutation ending in an ascending run of length at least 3, so it follows from the preceding argument that _321(π) is not a periodic point of _321. Hence, π is not a periodic point in this case either.  
  
  
   
  Let π = a_1 ⋯ a_k∈ S_n for some n≥ 3, where the a_i's denote ascending runs. If |a_1|≥ 3 or |a_k-1|=|a_k|=1, then π is not a periodic point of _321.
  
  
  
  
  Suppose π is a periodic point of _321 and |a_1|≥ 2. Let ℓ be the period of π so that _321^ℓ(π)=π. Let π_1 denote the first entry of π. By Lemma <ref>, we must have g(π)=g(_321^t(π)) for all t≥ 1. By Lemma <ref>, the last two entries of _321(π) form the sequence (a_1^e); in particular, the last ascending run of _321(π) has length 1 and is simply π_1. Since _321(π) ends in an ascending run of length 1 and g(π)=g(_321(π)), Lemma <ref> guarantees that _321^2(π) begins with an ascending run that contains π_1, so _321^2(π)_1 ≤π_1. In fact, the first ascending run of _321^2(π) must actually contain a_1^e, so _321^2(π) is a periodic point of _321 that starts with an ascending run of length at least 2. Moreover, if _321(π) has an ascending run of length at least 3, then the first ascending run of _321^2(π) actually begins with an entry that is smaller than π_1, implying that _321^2(π)_1 < π_1. Repeating this argument shows that (_321^2t(π)_1)_t≥ 1 is a weakly decreasing sequence and is nonconstant if _321^2t-1(π) contains an ascending run of length at least 3 for some t ≥ 1. Since _321^kℓ(π)=π for all integers k≥ 1, it follows that for every t≥ 1, the permutation _321^2t-1(π) does not have an ascending run of length at least 3. This implies that _321^2t(π) = (_321^2t-1(π)) for all t ≥ 1. 
  
  Now consider π_2, the second entry of π. As previously stated, _321(π) ends in (a_1^e), so the second-to-last entry of _321(π) is greater than or equal to π_2. This implies that the second entry of _321^2(π) is greater than or equal to π_2, as _321^2(π) = (_321(π)). Repeating this argument shows that the sequence (_321^2t(π)_2)_t≥ 1 is weakly increasing. As _321^2kℓ(π)=π for all k≥ 1, this sequence must actually be constant. If |a_1|≥ 3, then the second-to-last entry of _321(π), which is also the second entry of _321^2(π), is actually strictly greater than π_2. This is a contradiction. 
  
  Now suppose π is a periodic point and |a_k-1|=|a_k|=1. This means we must have g(π)=g(_321(π)), so it follows from Lemma <ref> that a_1^m⋯ a_k^m(a_k^e) is an increasing sequence. Notice also that the first 3 entries of the sequence (a_k^e)(a_k-1^e)(a_k-2^e) appear in increasing order (we must have k≥ 3 since n≥ 3 and |a_k-1|=|a_k|=1). This shows that _321(π) is a periodic point beginning with an ascending run of length at least 3, which contradicts what we found in the previous two paragraphs. 
  
  
  The following proposition proves Theorem <ref> for σ=321, thereby completing the proof of the entire theorem. Indeed, we already proved the theorem for σ∈{132,213,231,312}, and we can use Lemma <ref> to see that the next proposition implies Theorem <ref> for σ=123 as well. 
  
  
  The set of periodic points of _321:S_n→ S_n is _n(123, 321), the set of permutations in S_n that avoid 123 and 321 consecutively. When n≥ 2, these points have period 2.
  
  
  It is clear that if π∈(123, 321), then _321(π) = (π) ∈(123, 321), so _321^2(π) = π. Hence, π  is a periodic point of _321, and the period is 2 if n≥ 2. 
  
  Suppose that π∉(123, 321); we will show that π is not a periodic point of _321. If π does not contain a consecutive 321 pattern but does contain a consecutive 123 pattern, then _321(π) = (π) contains a consecutive 321, so we may simply assume that π∉(321) (otherwise, the same analysis applies to _321(π)). Suppose instead that π is a periodic point, and let a_1,…,a_k be its ascending runs. Note that we have g(π) = g(_321(π)). Furthermore, the sequence a_1^m⋯ a_k^m is nonempty because π contains a consecutive 321 pattern. It then follows from Lemma <ref> that _321(π) is a periodic point of _321 that begins with the sequence a_1^m ⋯ a_k^m (a_k^e). If |a_k|≥ 2, then a_1^m ⋯ a_k^m (a_k^e) has length at least 3, and Lemma <ref> tells us that this sequence is decreasing.  This implies that the periodic point _321(π) starts with a decreasing sequence of length at least 3, contradicting Corollary <ref>. Hence, we must have |a_k|=1. Consider π_n-1, which is last entry in a_k-1. We must have π_n-1>π_n, so it follows from Lemma <ref> that a_1^m ⋯ a_k^m (a_k^e)π_n-1 is an increasing sequence of length at least 3. This shows that _321(π) is a periodic point whose first ascending run has length at least 3, which contradicts Corollary <ref>. 
  
  
  
  § THE MAPS _132 AND _312
  
  
  In this section, we explore the maps _132 and _312 from both a sorting point of view and a dynamical point of view. We do not have much to say about _312 from a sorting point of view because we were not able to enumerate the set (_312). The initial values of the sequence (|_n(_312)|)_n≥ 0 are 
      1, 1, 2, 5, 15, 50, 179, 675, 2649, 10734;
   this sequence appears to be new.
  
  However, we will be able to characterize and enumerate the permutations in (_132). Specifically, we show that they are in bijection with Dyck paths and are thus enumerated by the Catalan numbers. 
  
  From a dynamical point of view, we will be interested in the number of preimages of permutations under _132 and _312. In this setup, it suffices to focus our attention on _132. Indeed, since 312=(132), Lemma <ref> implies that |_312^-1(π)|=|_132^-1((π))| for all π∈ S_n. Consequently, we will not need to discuss the map _312 directly in this section. 
  
  Let us begin with the set (_132). Recall that a left-to-right minimum of a permutation π=π_1⋯π_n is an entry π_i such that π_i<π_j for all 1≤ j<i. For example, the left-to-right minima of 4572163 are 4, 2, and 1. 
  
  
  Let π = a_1 ⋯ a_k∈ S_n, where the subsequences a_i are the ascending runs of π. For each i, let us write a_i = m_i t_i, where m_i is the first entry of a_i and t_i is the (possibly empty) string obtained by removing m_i from a_i. Then _132(π) ∈(231) if and only if each m_i is a left-to-right minimum of π and the concatenation (t_1)⋯(t_k) is a decreasing sequence. 
  
  
  Let us first assume _132(π)∈(231). We will prove by induction that the entries m_1,…,m_k are all left-to-right minima of π. Since m_1 is the first entry of π, it is trivially a left-to-right minimum. Now consider 1≤ i<k, and suppose that m_1,…,m_i are all left-to-right minima. Suppose by way of contradiction that m_i+1 is not a left-to-right minimum. This implies that if we write t_i = b_1 ⋯ b_j, where j=|t_i|, then j≥ 1 and m_i<m_i+1<b_j. Let ℓ be the smallest index such that b_ℓ > m_i+1. When we send π through the consecutive-132-avoiding stack, the consecutive subsequence a_i will enter the stack consecutively, so (a_i)=b_j⋯ b_1m_i will be at the top of the stack when m_i+1 is next in line to be pushed into the stack. The entries b_j,…,b_ℓ+1 will be popped, and then m_i+1 will be pushed into the stack on top of b_ℓ. Since b_ℓ>m_i+1, the entry m_i+1 will not get popped out of the stack until after all of the entries of π have entered the stack. It follows that m_i+1,b_ℓ,m_i form an occurrence of the classical pattern 231 in _132(π); this is our desired contradiction. It is straightforward to see that _132(a_1 ⋯ a_k) = (t_1) ⋯(t_k) m_k ⋯ m_1, where m_k = 1. Since we are assuming _132(a_1⋯ a_k) avoids 231, the sequence (t_1) ⋯(t_k) must be decreasing. 
  
  For the reverse direction, suppose that the entries m_1,…,m_k are left-to-right minima and that the sequence (t_1) ⋯(t_k) is decreasing. As above, _132(π) = (t_1) ⋯(t_k)m_k ⋯ m_1, which is a decreasing sequence followed by an increasing sequence. Such a permutation necessarily avoids 231.
  
  
  
  The proof of Proposition <ref> yields the somewhat-unexpected fact that if a permutation is in the image of _132 and avoids the pattern 231, then it also avoids 132. 
  
  
   Proposition <ref> tells us that each π∈(_132) is determined by the first entries m_i of its ascending runs as well as the lengths |a_1|,…,|a_k| of its ascending runs. Furthermore, these quantities must satisfy n+1 - m_i ≥ |a_1| + ⋯ + |a_i| for all i. Indeed, the entries in t_1 must be the |a_1|-1 largest elements of [n]∖{m_1,…,m_k}, the entries in t_2 must be the next |a_2|-1 largest elements, and so on. The condition that  n+1 - m_i ≥ |a_1| + ⋯ + |a_i| for all i guarantees that the m_i's are left-to-right minima. 
  
  A Dyck path of semilength n is a word over the alphabet {U,D} that contains n copies of each letter and has the additional property that each of its prefixes contains at least as many occurrences of U as occurrences of D. Let D_n denote the set of Dyck paths of semilength n. It is well known that | D_n|=C_n=1/n+12n n is the nth Catalan number. Given π∈ S_n such that _132(π) ∈(231), write π = a_1 ⋯ a_k and a_i = m_i t_i as in Proposition <ref>. Let Φ(π) be the Dyck path U^m_0-m_1D^|a_1|U^m_1-m_2D^|a_2|⋯ U^m_k-1-m_kD^|a_k|, where we make the convention m_0=n+1. 
  
  
  Let π=589436712, and note that _132(π)=987621345∈(231). We have a_1=589, a_2=4, a_3=367, and a_4=12. The first entries of these ascending runs are m_1=5, m_2=4, m_3=3, and m_4=1. Therefore, Φ(π)=UUUUUDDDUDUDDDUUDD.
  
  
   
  The map Φ:_n(_132)→ D_n is a bijection. Consequently, 
      |_n(_132)|=C_n.
   
  
  
  
  Preserve the notation from above. The total number of occurrences of the letter U in Φ(π) is (m_0-m_1)+⋯+(m_k-1-m_k)=m_0-m_k=(n+1)-1=n, and the total number of occurrences of D is |a_1|+⋯+|a_k|=n. As mentioned above, we have n+1-m_i≥|a_1|+⋯+|a_i| for all i; this guarantees that Φ(π) is indeed a Dyck path of semilength n. Moreover, by the previous discussion, Φ is injective. 
  
  To prove surjectivity, suppose we are given a Dyck path Λ=U^γ_1D^δ_1U^γ_2D^δ_2⋯ U^γ_kD^δ_k for some positive integers γ_1,…,γ_k,δ_1,…,δ_k. Define m_i=n+1-γ_1-⋯-γ_i. Using the fact that Λ is a Dyck path, one can verify that there exists a permutation π∈ S_n with ascending runs a_1,…,a_k satisfying the conditions in Proposition <ref> with a_i=m_it_i and |a_i|=δ_i for all i. This permutation is in _n(_132) and satisfies Φ(π)=Λ.  
  
  
  The next series of results determines the maximum number of preimages of permutations under _132 and _312. As mentioned above, it is only necessary to consider _132.
  
   
  Let π∈ S_n. Suppose there exists an entry i∈[n-1] that occurs before i+1 but not immediately before i+1 in π. Let π' be the permutation obtained by swapping i and i+1 in π. Then,
  
      |_132^-1(π)| ≤ |_132^-1(π')|.
  
  
  
  Suppose _132(τ) = π, and let τ' be the permutation obtained by swapping i and i+1 in τ. We will prove that _132(τ') = π'. To do so, it suffices to show that the sequence of “push” and “pop” operations that is used to send τ through the consecutive-132-avoiding stack is exactly the same as the sequence used to send τ' through the stack. 
  
  When sending τ through the consecutive-132-avoiding stack, the entries i and i+1 are never consecutive entries in the stack. Indeed, if they were, then i would sit on top of i+1 because i appears before i+1 in the output permutation π. However, if i sits on top of i+1, then these two entries will appear consecutively in the output π, contrary to our hypothesis. Now consider the sequences of “push” and “pop” operations that send τ and τ' through the stack. Note that in each sequence, the first two operations are necessarily pushes. Now suppose the first two sequences agree in their first k operations. Suppose further that after the first k operations, the stack-sorting procedure that is being applied to τ (respectively, τ') has b (respectively, b') as the top entry in the stack, has c (respectively, c') as the second-to-top entry in the stack, and has a (respectively, a') as the entry next in line to enter the stack. We show that the next operation is the same as well. 
  
  If none of a, b, and c are i or i+1, then it must be that a = a', b = b', and c = c', so the claim is trivially true. Next, if exactly one of a, b, and c is i or i+1, then abc and a'b'c' have the same relative order, so the claim is true is in this case as well. Finally, suppose exactly two of a,b,c are i or i+1. Because i and i+1 cannot appear consecutively in the stack, we cannot have {b,c}={i,i+1}. If {a,b}={i,i+1}, then one of the two sorting procedures (sorting τ or τ') would have i and i+1 appear consecutively in the stack, which is again impossible. Therefore, it must be that (a, c) = (i, i+1) or (a',c') = (i,i+1). The two cases are symmetric, so we may assume the former. Note that abc cannot have the same relative order as 132 as, otherwise, i and i+1 would end up being consecutive in the stack once b gets popped out and c=i+1 gets pushed in. Thus, the next operation for the τ case is to push a into the stack. Likewise a' = i+1 and c' = i, so a'b'c' cannot have the same relative order as 132. The next operation in the τ' case is therefore to push a' into the stack. By induction, the sequences of operations when sending τ and τ' through the consecutive-132-avoiding stack are identical.
  
  Since the map τ↦τ' is one-to-one, this shows that |_132^-1(π)| ≤ |_132^-1(π')|, as desired.
  
  
   
  For every positive integer n, we have 
  
      max_π∈_n(132,213)|_132^-1(π)| = max_π∈ S_n|_132^-1(π)|.
  
  
  
  Suppose π∈ S_n. If π classically contains an occurrence of either 132 or 213, then there exists some i∈[n-1] such that i and i+1 are not consecutive in π and i occurs before i+1. Lemma <ref> tells us that swapping these entries yields a permutation with at least as many preimages under _132. By repeatedly performing such swaps, we must eventually reach a permutation in _n(132,213) (the sequence of swaps must terminate because each swap decreases the number of inversions in the permutation by 1), and this permutation has at least as many preimages under _132 as π.
  
  
  A permutation in S_n is called reverse-layered if the set of entries in each of its ascending runs forms an interval of consecutive integers. For example, 5674231 is reverse-layered because the sets of entries in its ascending runs are {5,6,7}, {4}, {2,3}, and {1}. It is well known <cit.> that _n(132,213) is precisely the set of reverse-layered permutations in S_n. Note that each reverse-layered permutation is uniquely determined by its set of descents, which we can encode via a word of length n over the alphabet {A,D} that starts with A. More precisely, the reverse-layered permutation π=π_1⋯π_n corresponds to the word b_1⋯ b_n, where b_1=A and for 2≤ j≤ n, we have b_j=A if π_j-1<π_j and b_j=D if π_j-1>π_j. Let d_π(k) denote the number of occurrences of D in the subword b_1⋯ b_k. Let a_π(k) denote the number of occurrences of A in the word b_k+1⋯ b_n that appear to the right of an occurrence of the letter D in b_k+1⋯ b_n. For example, the reverse-layered permutation π=78634512 corresponds to the word AADDAADA. We have 
      (d_π(0),…,d_π(8))=(0,0,0,1,2,2,2,3,3)  and  (a_π(0),…,a_π(8))=(3,3,3,3,1,1,1,0,0).
    Using this notation, we can obtain a nice formula for |_132^-1(π)| when π is reverse-layered. The reader may find it helpful to refer to Example <ref> while reading the following proof. 
  
  
  
   
  Let π∈_n(132,213) be a reverse-layered permutation in S_n, and preserve the definitions of d_π(k) and a_π(k) from above. We have 
  
      |_132^-1(π)| = ∑_k = 0^nd_π(k) + a_π(k)  k.
  
  
  
  
      Let _132,k^-1(π) denote the set of permutations τ∈_132^-1(π) such that when τ is sent through the consecutive-132-avoiding stack, exactly k entries get popped out of the stack before all entries have entered the stack. We will show that 
      |_132,k^-1(π)|=d_π(k) + a_π(k)  k,
   which will complete the proof. Note that |_132,0^-1(π)|=1 because the only element of _132,0^-1(π) is (π). Indeed, _132 does actually send (π) to π because π is reverse-layered (hence, (π) avoids 231). Therefore, we may assume that k≥ 1 in what follows. 
      
      Suppose τ∈_132,k^-1(π). When we send τ through the consecutive-132-avoiding stack, the k entries popped before all entries have entered the stack must be exactly π_1, …, π_k, and they must be popped in that order. The other entries π_k+1,…,π_n get popped out of the stack later in this order, so they must appear in τ in the order π_n,…,π_k+1. Thus, when constructing such a preimage τ, we first insert each entry π_i with 1≤ i≤ k between a pair of entries π_j(i),π_j(i)+1 with k+1≤ j(i)≤ n and then reverse the entire permutation. When we do so, the following conditions must be satisfied:
     
      
          
    * the string π_j(i)π_iπ_j(i)+1 has the same relative order as 132;
          
    * j(1)≥⋯≥ j(k);
          
    * if j(i)=j(i+1), then π_i>π_i+1 and π_i+1π_i is a consecutive subsequence of τ.
      
      The first and third conditions ensure that the entries π_1,…,π_k actually get popped before all entries have entered the stack; the second and third conditions ensure that they are popped in the correct order.
      Moreover, each placement of the entries π_1, …, π_k between consecutive entries in π_k+1⋯π_n such that the three conditions are satisfied yields a unique preimage τ∈_132,k^-1(π). 
      
      To determine the number of valid placements, let π_ℓ be the last entry in the ascending run of π that includes π_k. When we insert the entry π_k between the entries π_j(k),π_j(k)+1, the first condition above guarantees that j(k)≥ℓ+1, so it follows from the second condition that j(1)≥⋯≥ j(k)≥ℓ+1. Thus, for each i∈[k], the possible choices for the index j(i) are precisely the ascents counted by a_π(k).
      To satisfy the third condition, note that we can have j(i)=j(i+1) only if i is a descent of π. In summary, this proves that the number of ways to choose a preimages τ is equal to the number of ways to choose the indices j(1),…,j(k) from among the ascents counted by a_π(k) such that j(1)≥⋯≥ j(k), where the inequality j(i)≥ j(i+1) is actually strict whenever i is an ascent of π.  
      If we decide that there are precisely t descents i such that j(i)=j(i+1), then there are d_π(k)t choices for these descents. There are then kk-t choices for the set {j(1),…,j(k)} of values taken by the indices j(1),…,j(k). These choices uniquely determine j(1),…,j(k).
      Together, this shows that
      
      |_132,k^-1(π)|=∑_t=0^d_π(k)d_π(k) ta_π(k)  k - t = d_π(k) + a_π(k)  k,
  
      where the second equality is due to Vandermonde's Identity. 
  
  
  
  Let us take π to be the permutation 12 13 11 8 9 10 6 7 5 1 2 3 4. Suppose we want to construct a preimage τ∈_132,5^-1(π). The ascents counted by a_π(5) are 7,10,11,12, which correspond to the following blanks: 67 5 1234. Therefore, a_π(5)=4. We need to insert the entries 12,13,11,8,9 into some of these blanks. As an example illustrating the notation from the proof of Theorem <ref>, placing the entry π_2=13 in the blank between the entries π_10=1 and π_11=2 would correspond to setting j(2)=10. The indices in {1,…,5} that are descents of π are 2 and 3 (meaning d_π(5)=2), so the proof of the theorem tells us that we must choose j(1),…,j(5)∈{7,10,11,12} such that j(1)>j(2)≥ j(3)≥ j(4)>j(5). The number of ways to make this choice is 
      ∑_t=0^22 t4 5-t=2+4 5.
   
  For one specific choice, we can take j(1)=12, j(2)=j(3)=j(4)=10, and j(5)=7. This corresponds to inserting the entries into the blanks to produce the permutation 6 9 7 5 1 13 11 8 2 3 12 4. Reversing this permutation produces τ=4 12 3 2 8 11 13 1 5 7 9 6, which is indeed in _132,5^-1(π). 
  
  
   
  Let π = π_1 ⋯π_n∈ S_n∖{123⋯ n}, and let b = b_1 ⋯ b_n be its corresponding word over the alphabet {A,D} as above. Let i be the smallest positive integer such that b_i+1=A, and let a = a_π(i-1). Finally, let π' be the permutation whose corresponding word over {A,D} is the following modification of b: 
  
      b'=AD⋯ DD_i+1b_i+2⋯ b_n     a ≥ i; 
      AD⋯ D_ib_i+2⋯ b_nA     a < i.
  
   Then |_132^-1(π)| ≤ |_132^-1(π')|.
  
  
  
  Suppose a ≥ i. Then b = AD⋯ DA_i+1b_i+2⋯ b_n and b' = AD⋯ DD_i+1b_i+2⋯ b_n, with permutations π and π' corresponding to b and b' respectively. Note that a = a_π(i-1) = ⋯ = a_π(1). Furthermore, d_π(r)=r-1 for all 1≤ r≤ i. By Theorem <ref> and the Hockey Stick Identity, 
  
      |_132^-1(π)|    = 1 + a  1 + ⋯ + a+i-2  i-1 +  ∑_r = i^nd_π(r) + a_π(r)  r
         = 1 + a+i-1  i-1 +  ∑_r = i^nd_π(r) + a_π(r)  r.
  
  It is straightforward to see that d_π(i) = d_π(i+1) and a_π(i) = a_π(i+1), so by Pascal's Identity,
  
      |_132^-1(π)| = 1 + a+i-1  i-1  + d_π(i+1) + a_π(i+1) + 1  i+1+ ∑_r = i+2^nd_π(r) + a_π(r)  r.
  
  
  As for the preimages of π', notice that for r ≥ i + 1, we have d_π'(r) = d_π(r) + 1 and a_π'(r) = a_π(r). Furthermore, we have d_π'(r)=d_π(r)=r-1 and a_π'(r)≥ a_π(r)-1 for all 1≤ r≤ i. Thus, 
  
      |_132^-1(π')| ≥ 1 +    a-1  1 + ⋯ + a+i-3  i-1 +  a+i-2  i
         +d_π(i+1) + a_π(i+1) + 1  i+1 +   ∑_r = i+2^nd_π(r) + a_π(r)  r
      
          = 1 +    a+i-1  i +  d_π(i+1) + a_π(i+1) + 1  i+1 +   ∑_r = i+2^nd_π(r) + a_π(r)  r.
  
  This proves that if a = a_π(i-1) ≥ i, then |_132^-1(π)| ≤ |_132^-1(π')| as desired.
  
  Now suppose a < i so that b =  AD⋯ DA_i+1b_i+2⋯ b_n and b' = AD⋯ D_ib_i+2⋯ b_nA, with permutations π and π' corresponding to b and b' respectively. We may suppose that b_j = D for some j ≥ i+2 as, otherwise, b = b' and the inequality is trivially true. Thus, a_π'(i) = a_π(i) + 1 and  d_π'(i) = d_π(i). It is straightforward to see that d_π'(r) = d_π(r) and a_π'(r) = a_π(r) for 1 ≤ r ≤ i-1. Furthermore, d_π(r) = d_π'(r-1) and a_π(r) ≤ a_π'(r-1) for r ≥ i+2. Observe also that d_π'(n)+a_π'(n)n=d_π'(n)n=0. It follows that,
  
      |_132^-1(π')| - |_132^-1(π)|    = d_π(i) + a_π(i) + 1  i - d_π(i) + a_π(i)  i - d_π(i+1) + a_π(i+1)  i+1
         +∑_r = i+1^n-1d_π'(r) + a_π'(r)   r - ∑_r=i+2^nd_π(r) + a_π(r)  r
         ≥d_π(i) + a_π(i) + 1  i - d_π(i) + a_π(i)  i - d_π(i+1) + a_π(i+1)  i+1
         +∑_r = i+2^n[d_π(r) + a_π(r)   r-1 - d_π(r) + a_π(r)  r].
  
  
  Since a < i by assumption, a_π(r) < a < i < r for all r ≥ i+2. Moreover, d_π(r) < r trivially, so it follows that 2r > d_π(r) + a_π(r) and
  
      d_π(r) + a_π(r)  r-1≥d_π(r) + a_π(r)  r
  
  for all r ≥ i+2. This shows that the summation in the above inequality is nonnegative.
  
  Finally, we also have that d_π(i) = d_π(i+1) = i-1 and a_π(i) = a_π(i+1), so by Pascal's Identity,
  
      |_132^-1(π')| - |_132^-1(π)|    ≥d_π(i) + a_π(i) + 1  i - d_π(i) + a_π(i)  i - d_π(i+1) + a_π(i+1)  i+1
         = i + a_π(i)  i -  i + a_π(i)  i+1≥ 0,
  
  as desired. The last inequality follows from the fact that a_π(i) ≤ a_π(i-1) = a < i.
  
  
  If we start with a permutation π∈(132,213) whose corresponding word over {A,D} is not of the form AD ⋯ D A ⋯ A (i.e., the permutation is not simply a decreasing sequence followed by an increasing sequence), then the previous lemma allows us to alter the permutation and obtain a new permutation π' with at least as many preimages under _132 as π. This is stated in the following corollary. It is well known that a permutation can be written as a decreasing sequence followed by an increasing sequence if and only if it avoids 132 and 231 classically. Therefore, the set of permutations in (132,213) that can be written as a decreasing sequence followed by an increasing sequence is precisely (132,213,231). 
  
   
  For every positive integer n, we have 
  
      max_π∈_n(132,213,231)|_132^-1(π)| = max_π∈ S_n|_132^-1(π)|.
  
  
  
  Let M=max_π∈ S_n|_132^-1(π)|. By Corollary <ref>, there is a permutation π∈_n(132,213) such that |_132^-1(π)|=M. Suppose π contains the pattern 231. We can alter π using Lemma <ref> in order to obtain a new permutation π' with |_132^-1(π)|=M. Let b and b' be the words over {A,D} corresponding to π and π' respectively. Given a word w over {A,D}, let f_1(w) denote the length of the longest consecutive string of D's in w starting in the second position of w, and let f_2(w) be the length of the longest suffix  of w that uses only the letter A. Because π contains 231, it is straightforward to check (using the definition of b' given in the proof of Lemma <ref>) that f_1(b)≤ f_1(b') and f_2(b)≤ f_2(b'), where at least one of these inequalities must be strict. This shows that if we repeatedly use Lemma <ref> to alter permutations, we must eventually reach a permutation τ∈_n(132,213,231) with |_132^-1(τ)|=M. 
  
  
   The maximum number of preimages under _132 or _312 that a permutation in S_n can have is given by
  
      max_π∈ S_n|_132^-1(π)|=max_π∈ S_n|_312^-1(π)|=n-1⌊n-1/2⌋.
  
  
  
  By complementing, it suffices to consider only the map _132. Let M=max_π∈ S_n|_132^-1(π)|. By Corollary <ref>, there exists π∈_n(132,213,231) with |_132^-1(π)|=M. Since π avoids 132, 213, and 231, it must be of the form 
      n(n-1)⋯(n-r+1)123⋯ (n-r).
   The word over {A,D} corresponding to π is AD⋯ D_rA⋯ A_n-r-1. Observe that d_π(k)=min(k-1,r) for all 1≤ k≤ n. Furthermore, we have a_π(k)=n-r-1 if 1≤ k≤ r and a_π(k)=0 if r+1≤ k≤ n. By Theorem <ref> and the Hockey Stick Identity, we have
  
      M=|_132^-1(π)| = 1+n-r-1 1+n-r 2+⋯+n-2 r=n-1  r≤n-1⌊n-1/2⌋.
  
  Moreover, equality is achieved when r = ⌊n-1/2⌋; this completes the proof. 
  
  
  
  
  § THE MAPS _213 AND _231
  
  
  We begin this section with a brief discussion of the sets (_213) and (_231). 
  The initial terms of the sequence (|_n(_213)|)_n≥ 0 are 
      1, 1, 2, 5, 15, 50, 180, 686, 2731, 11254.
   This sequence appears to be new.
  
  On the other hand, the first 10 terms of (|_n(_213)|)_n≥ 0 are 
      1, 1, 2, 6, 21, 79, 311, 1265, 5275, 22431.
   These numbers match the initial terms in the OEIS sequence A033321, which is the binomial transform of Fine's sequence. Fine's sequence (F_k)_k≥ 0 can be defined via its generating function 
      ∑_k≥ 0F_kx^k=1-√(1-4x)/3-√(1-4x).
  
  
  
  For each positive integer n, we have 
      |_n(_231)|=∑_k=0^nnkF_k+1.
   
  
  
  Our main focus in this section will be on the maximum number of preimages a permutation in S_n can have under either _213 or _231.
  
  
  
  
  For every n≥ 2, we have
  
      max_π∈ S_n|_213^-1(π)|=max_π∈ S_n|_231^-1(π)| = 2^n-2.
   
  
  
  
  
  The equality max_π∈ S_n|_213^-1(π)|=max_π∈ S_n|_231^-1(π)| follows directly from Lemma <ref>, so we can focus on the map _231. Now consider the process of sending a permutation τ = τ_1 ⋯τ_n∈ S_n through a consecutive-231-avoiding stack. Say that the entry τ_j is premature if it is popped out of the stack before all of the entries of τ enter the stack. The effect of sending τ through the stack is to shift all of the premature entries to the left while preserving their relative order and reverse the remaining (non-premature) entries.
  More formally, if {τ_j_1, ⋯, τ_j_k} are the premature entries of τ, then _231(τ) = τ_j_1⋯τ_j_k(τ∖{τ_j_1, ⋯, τ_j_k}), where τ∖{τ_j_1, ⋯, τ_j_k} is simply the sequence τ with the terms in {τ_j_1, ⋯, τ_j_k} removed.
  
  Now fix π=π_1⋯π_n∈ S_n, and consider a preimage τ of π under _231. Suppose that τ_j_1,…,τ_j_k are the premature entries of τ (with j_1<⋯<j_k). By the previous paragraph, τ is obtained by inserting the entries π_1,…,π_k into (π_k+1⋯π_n) so that the entry in position j_i of τ is π_i for all i∈[k]. This shows that τ is uniquely determined by specifying π and the set of indices {j_1,…,j_k}. Finally, notice that the first and last entries of a permutation cannot be premature. Therefore, the positions of the premature entries of τ must form a subset of {2, …, n-1}. It follows that |_231^-1(π)|≤ 2^n-2
  
  To complete the proof, it suffices to show that |_231^-1(n (n-1) ⋯ 1)|≥ 2^n-2. For each set J={j_1,…,j_k}⊆{2,…,n-1} (with j_1<⋯<j_k), let τ^J be the permutation obtained by inserting the entries n,n-1,…,n-k+1 into the sequence 123⋯ (n-k) so that for each i∈[k], the entry n+1-i is in position j_i. For example, if n=8 and J={2,3,5}, then τ^J=18726345. It is straightforward to check that _231(τ^J)=n(n-1)⋯ 1 and that τ^J≠τ^J' whenever J≠ J'. Consequently, |_231^-1(n(n-1)⋯ 1)|≥ 2^n-2. 
  
  
  
  
  
  
  § THE MAPS _123 AND _321
  
  
  Our goal in this section is to enumerate the sets (_123) and (_321), thereby proving analogues of two more of the main theorems from <cit.>. Our enumeration of (_321) generalizes to (_k(k-1) ⋯ 1), so we focus on (_k(k-1) ⋯ 1) first instead.
  
  It follows immediately from Lemma <ref> that (_k(k-1) ⋯ 1) = (132, 12⋯ k) for k≥ 3. In Proposition 3.2 of <cit.> it was shown that this set is enumerated by the so-called generalized Motzkin numbers M_k-1,n, which can be defined via the formula 
      M_k-1,n=1/n+1∑_j=0^⌊ n/k⌋(-1)^jn+1j2n-jkn.
   For k= 3,4,5, and 6, these numbers are given by OEIS sequences A001006, A036765, A036766, and A036767 respectively <cit.>.
  
  
  For k≥ 3, the sets _n(_k(k-1) ⋯ 1) = _n(132, 12⋯ k) are enumerated by the generalized Motzkin numbers. More precisely, 
      |_n(_k(k-1)⋯ 1)|=M_k-1,n.
  
  
  
  
  
  The above theorem completes our enumeration of (_k(k-1) ⋯ 1). We remark that when k=3, the generalized Motzkin numbers M_2,n are the same as the classical Motzkin numbers M_n. These numbers will also be related to our enumeration of (_123).
  
    
  The set (_321) is enumerated by the Motzkin numbers. That is, 
  
      |_n(_321)| = M_n.
  
  
  
  The following is a well-known recurrence for the Motzkin numbers.
  
   
  We have M_0 = M_1 = 1 and, for n≥ 2,
  
      M_n = M_n-1 + ∑_i=0^n-2 M_iM_n-2-i.
  
  
  
  
  To begin enumerating (_123), we first classify the set. In order to do this, it is helpful to use the notion of a vincular pattern. We refer the reader to <cit.> for a formal treatment of vincular patterns; we will only need to consider the set (132,3214,4213,4312). This is the set of permutations that avoid 132 and also do not contain any occurrences of the patterns 3214, 4213, or 4312 in which the first 3 entries in the occurrence of the pattern appear consecutively in the permutation. For example, 51324 belongs to this set of permutations because, although 5,3,2,4 form an occurrence of the pattern 4213, the entries 5,3,2 do not appear consecutively in 51324. 
   
  The set (_123) consists of the permutations π = π_1 ⋯π_n, for some positive integer n, that satisfy the following properties:
  
      
    * π∈(132)
      
    * if π_iπ_i+1⋯π_j is a descending run of π of length at least 3, then there are no entries bigger than π_j-1 to the right of π_j-1 in π, and 
      the entries π_i+1,...,π_j-1 are consecutive integers.
  
  Alternatively, (_123)=(132,3214,4213,4312). 
  
  It is straightforward to check that a permutation satisfies the two listed conditions if and only if it is in (132,3214,4213,4312). The proof of the first statement is straightforward once we find an expression for _123(π). Fortunately, this was done in Lemma <ref> for the map _321, so we may use Lemma <ref> to find a similar expression for _123(π) by complementing. Namely, suppose π = d_1 ⋯ d_k, where each d_i is a descending run. We have _123(π) = d_1^m⋯ d_k^m(d_k^e) ⋯(d_1^e), where d_i^m is the subsequence of d_i consisting of the entries that are not the first or last entries in d_i and d_i^e is the sequence obtained from d_i by deleting d_i^m.
  
  To see that all permutations in (_123) must satisfy the two conditions, note first that if abc forms an occurrence of the classical pattern 132 in π and a,b, and c are in the descending runs d_i, d_j, and d_ℓ respectively, then c, the second entry of (d_j^e), and the first entry of (d_i^e) form an occurrence of the classical pattern 231 in _123(π). This shows that (_123)⊆(132). For the first part of the second condition, suppose π_iπ_i+1⋯π_j is a descending run of length at least 3 and that π_ℓ is an entry to the right of π_j that is also the first entry of a different descending run. Then π_j-1π_ℓπ_j is a subsequence of _123(π), and  we certainly have π_j < π_j-1. It follows that if _123(π) ∈(231), then π_ℓ < π_j-1. Hence, no entry to the right of π_j-1 in π is bigger than π_j-1. Finally, the previous two points imply the second part of the second condition. If the entries π_i+1,...,π_j-1 are not consecutive integers, then there is some entry π_i' that is not part of the descending run containing these entries and that satisfies π_i+1 > π_i' > π_j-1. Then either  π_i'π_iπ_i+1 is a 132-subsequence or there is an entry to the right of π_j-1 that is bigger than π_j-1.
  
  To see that every permutation satisfying these conditions is indeed in (_123), again decompose π into its descending runs and write _123(π) =  d_1^m⋯ d_k^m(d_k^e) ⋯(d_1^e). The first condition ensures that (d_k^e) ⋯(d_1^e) does not contain an occurrence of the classical pattern 231. The first part of the second condition ensures that d_1^m⋯ d_k^m is a decreasing sequence, so it also does not contain an occurrence of 231. Finally, the first condition and first part of the second condition ensure that there is no occurrence of the pattern 231 containing entries from both d_1^m⋯ d_k^m and (d_k^e) ⋯(d_1^e). Indeed, suppose abc is an occurrence such a pattern. As d_1^m⋯ d_k^m is a decreasing sequence, the entry a must be in d_1^m⋯ d_k^m while b and c are in  (d_k^e) ⋯(d_1^e). Let i,j,ℓ be the indices such that a is in d_i^m, b is in d_j^e, and c is in d_ℓ^e. Since c appears to the right of b in _123(π), we must have ℓ<j. The first part of the second condition guarantees that j≤ i. However, this implies that cba is an occurrence of the classical pattern 132 in π, which is a contradiction. 
  
  
  
  Before enumerating the permutations in (_123), we need one more lemma that counts permutations avoiding 132 classically and 123 consecutively. We obtain this result via a bijection between (132) and (231). For our purposes, we only need the existence of this bijection and one of its properties. The bijection is described in detail in Lemma 4.1 of <cit.>. 
  
  
  For each n≥ 1, there exists a bijection : _n(132)→_n(231) that preserves the set of descents. That is, an index i is a descent of π if and only if it is a descent of (π).
  
   
  For each n≥ 1, the sets of permutations _n(132, 321), _n(231, 321), and _n(132, 123) are in bijection. Consequently, |_n(132, 321)| = M_n. 
  
  
  Using the previous lemma, we obtain a chain of bijections 
      _n(132, 321)_n(231, 321)_n(132, 123).
  
  By Theorem <ref>,  |_n(132, 321)| = |_n(132, 123)| = M_n. 
  
  
  We need one final lemma before completing the enumeration of (_123).
   
  The number of permutations in _n(_123) beginning with the entry n is M_n-1.
  
  
  We proceed by induction on n, noting first that the lemma is trivial if n ≤ 2. Assume n≥ 3. Suppose π∈_n(_123) starts with the entry n, and let π' be the permutation obtained by deleting the leading entry n from π. It follows from Theorem <ref> that π'∈_n-1(_123) and that π' either starts with the entry n-1 or starts with an ascent. On the other hand, if τ∈_n-1(_123) starts with the entry n-1 or starts with an ascent, then the permutation nτ is in _n(_123). By the induction hypothesis, there are M_n-2 permutations in _n-1(_123) that start with n-1. 
  
  We now need to determine the number of permutations τ∈_n-1(_123) that start with an ascent. Let i∈{2,…,n-1} be such that τ_i=n-1. We may write τ as A(n-1)B, where A does not start with a descent (meaning it either starts with an ascent or consists of a single entry). Since τ must avoid 132 by Theorem <ref>, every entry in A is greater than every entry in B, so the entries in A are n-i+2,…,n-2 and the entries in B are 1, …, n-i+1. Since (n-1)B has length n-i+1 and has the same relative order as (n-i+1)B, the number of possibilities for (n-1)B is the same as the number of possibilities for (n-i+1)B. Now (n-i+1)B can be any element of _n-i+1(_123) that starts with n-i+1, so it follows from the induction hypothesis that the number of possibilities for (n-1)B is M_n-i. Next, for each possible choice of A, we can subtract n-i+1 from each entry of A. Theorem <ref> implies that this operation yields a bijection between the set of possible choices for A and the set of permutations in _i-1(132,321) that do not start with a descent. If i≥ 3, then since A avoids 132 and starts with an ascent, the first two entries of A must be consecutive integers. As a result, removing the first entry and standardizing gives a bijection between permutations in _i-1(132,321) that do not start with a descent and permutations in _i-2(132,321). This implies that there are M_i-2 possibilities for A by Lemma <ref>. If i=2, then it is also certainly true that the number of choices for A is M_i-2=M_0=1. 
  
  Putting this all together and invoking the Motzkin number recurrence in Lemma <ref>, we find that the number of permutations in _n(_123) beginning with n is 
      M_n-2 + ∑_i=2^n-1M_i-2M_n-i = M_n-2 + ∑_i=0^n-3M_iM_n-3-i = M_n-1.
  
  
  
  We can now prove that (_123) is enumerated by the first differences of Motzkin numbers, which form the OEIS sequence A002026 <cit.>.
  
  The permutations in (_123) are counted by the first differences of Motzkin numbers. That is, 
  
      |_n(_123)| = M_n+1 - M_n.
  
  
  
  Let X_i^n denote the set of permutations in _n(_123) in which the ith entry is n. If π∈ X_i^n, then we may write π = AnB, where A has length i-1 and B has length n-i. By Theorem <ref>, AnB avoids the pattern 132, so every entry in A is bigger than every entry in B, meaning that A is a permutation of the numbers n-i+1,…, n-1 and B is a permutation of 1, …, n-i. Moreover, the standardization of A can be an arbitrary element of (132, 321), so the number of possibilities for A is M_i-1 by Corollary <ref>. Meanwhile, the standardization of nB can be an arbitrary permutation in _n-i+1(_123) that starts with n-i+1, so by Lemma <ref>, there are M_n-i possibilities for nB. Thus, |X_i^n| = M_i-1M_n-i, and 
      |_n(_123)| = ∑_i=1^n M_i-1M_n-i =  ∑_i=0^n-1 M_iM_n-1-i = M_n+1 - M_n.
  
  
  
  
  
  § DYNAMICS OF THE MAPS S_132 AND S_312
  
  
  The set (s_132) was the primary focus of the recent article <cit.>, where it was shown that (s_132) is equal to the set of permutations avoiding the classical pattern 2314 as well as a certain mesh pattern. The same article proved that |_n(s_132)|=∑_k=0^n-1n-1kC_k, where C_k denotes the kth Catalan number. In this section, we briefly discuss some dynamical properties of the map s_132 and, by complementation, the map s_312. 
  
  
  The periodic points of the map s_132:S_n→ S_n are precisely the permutations in _n(132,231). The periodic points of the map s_312:S_n→ S_n are precisely the permutations in _n(213,312). When n≥ 2, each of these periodic points has period 2. Furthermore, for every permutation π∈ S_n, we have s_132^n-1(π)∈_n(132,231) and s_312^n-1(π)∈_n(213,312).  
  
  
  
  By Lemma <ref>, it suffices to prove the desired properties of s_132. Note that if we have π∈(132,231), then s_132(π) = (π) ∈(132, 231), so s_132^2(π) = π. Hence, π  is a periodic point of s_132, and the period is 2 if n≥ 2. 
  
  It remains to prove that s_132^n-1(π)∈(132,231) for every π∈ S_n. This is trivial if n=1, so we may assume n≥ 2 and induct on n. Consider sending a permutation τ∈ S_n through a classical-132-avoiding stack. When the entry 1 enters the stack, the entries below it in the stack must appear in increasing order from top to bottom. Furthermore, the entry 1 will not leave the stack until after all entries have entered the stack. This implies that the last ascending run of s_132(τ) begins with the entry 1. Therefore, it suffices to prove that if π∈ S_n is a permutation whose last ascending run begins with 1, then s_132^n-2(π)∈(132,231). We prove this by induction on n, noting first that it is trivial if n=2. Now suppose n≥ 3.   
  
  For each τ∈ S_n, let τ^* be the permutation in S_n-1 obtained by deleting the entry 1 from τ and then decreasing all remaining entries by 1. Observe that if the entries 1 and 2 appear consecutively in τ, then they also appear consecutively in s_132(τ) and that (s_132(τ))^*=s_132(τ^*). By induction, we have s_132^n-2(τ^*)∈(132,231). If the last ascending run of τ begins with 1, then the above analysis of the classical-132-avoiding stack shows that the entries 1 and 2 appear consecutively in s_132(τ). It then follows that the entries 1 and 2 appear consecutively in s_132^n-2(τ) and that (s_132^n-2(τ))^*=s_132^n-2(τ^*)∈(132,231). This implies that s_132^n-2(τ)∈(132,231), as desired. 
  
  
  Whenever one is confronted with a noninvertible finite dynamical system, it is natural to ask for the maximum number of iterations of the map needed to send every point to a periodic point. For example, Knuth <cit.> studied this problem for the classical bubble sort map. For West's stack-sorting map s, permutations requiring close to the maximum number of iterations to get sorted into the identity were studied by West and Claesson–Dukes–Steingrímsson<cit.>. Ungar gave a rather nontrivial argument proving that the maximum number of iterations needed to sort a permutation in S_n using the pop-stack-sorting map is n-1 <cit.>, and the permutations requiring n-1 iterations were investigated further by Asinowski, Banderier, and Hackl <cit.>. Some other papers that have studied similar questions for other finite dynamical systems include 
  
  <cit.>.
  
  Our second result in this section will determine the maximum number of iterations of s_132 (equivalently, s_312) needed to send a permutation to a periodic point. In what follows, we let _132(π) denote the smallest nonnegative integer t such that s_132^t(π)∈(132,231). Note that _132(π) is also the smallest nonnegative integer t such that s_312^t((π))∈(213,312). 
  
  
  For n≥ 3, we have 
      max_π∈ S_n_132(π)=n-1.
   
  
  
  
  Theorem <ref> tells us that max_π∈ S_n_132(π)≤ n-1, so it suffices to find a permutation π∈ S_n such that _132(π)≥ n-1. Let n=3m+r, where r∈{0,1,2}. Let λ_m denote the permutation in S_n-r obtained by taking the skew sum of m copies of the permutation 132. In other words, λ_m=ξ_mξ_m-1⋯ξ_1, where ξ_j denotes the sequence (3j-2)(3j)(3j-1). Let 
      π=λ_m     r=0; 
        nλ_m     r=1; 
        (n-1)nλ_m     r=2.
   We claim that s_132^n-2(π)∉(132,231); that is, _132(π)≥ n-1. For the sake of simplicity, we will prove this in the case r=0; the proofs in the cases r=1 and r=2 are similar. Thus, n=3m and π=λ_m. If n=3, then we are done because s_132(π)=s_132(132)=231∉(132,231). Therefore, we may assume n=3m≥ 6.
  
  It will be helpful to introduce a little more notation. If k≥ 1 is odd (respectively, even), we let V_k denote the permutation in S_3k obtained by listing the odd (respectively, even) numbers in [3k+1] in decreasing order and then listing the even (respectively, odd) numbers in [3k+1] in increasing order. For example, we have V_1=3124, V_2=6421357, and V_3=9 7 5 3 1 2 4 6 8 10. For i∈{0,1,2}, let D_k,m^(i) be the sequence obtained by writing the elements of {3k+2,3k+3,…,3m} that are congruent to i modulo 3 in decreasing order. For example, D_2,5^(0)=15 12 9, D_2,5^(1)=13 10, and D_2,5^(2)=14 11 8. The following two claims can be verified in a straightforward manner using nothing more than the definition of the map s_132; we leave this verification to the reader. 
  
  Claim 1: We have s_132^4(λ_m)=D_1,m^(2)D_1,m^(0)V_1(D_1,m^(1)).
  
  Claim 2: For 1≤ k≤ m-2, we have 
      s_132^3(D_k,m^(2)D_k,m^(0)V_k(D_k,m^(1)))=D_k+1,m^(2)D_k+1,m^(0)V_k+1(D_k+1,m^(1)).
   
  
  These two claims imply that s_132^n-2(π)=s_132^3m-2(λ_m)=D_m-1,m^(2)D_m-1,m^(0)V_m-1(D_m-1,m^(1)). Note that D_m-1,m^(2) consists of the single entry 3m-1. Similarly, D_m-1,m^(0) consists of the single entry 3m. Finally, D_m-1,m^(1) is empty. Thus, s_132^n-2(π)=(3m-1)(3m)V_m-1∉(132,231). 
  
  
  
  
  § FUTURE DIRECTIONS
  
  
  We have initiated the study of the consecutive-pattern-avoiding stack-sorting maps _σ and analyzed them as both dynamical systems and sorting procedures. These maps are generalizations of West's stack-sorting map <cit.> and are variants of the classical-pattern-avoiding stack-sorting maps studied by Cerbai, Claesson, and Ferrari in <cit.>. 
  
  Our main results on _σ as a sorting procedure were the characterization of when (_σ) is a permutation class and the enumeration of (_σ) summarized in the table below.
  
  
  
  
  
  
  
   σ \ n     0     1     2     3     4     5     6     7     8     9     OEIS 
  
   
  
   123     1     1     2     5     12     30     76     196     512     1353     A002006
   [0.1cm] 
   132      1     1     2     5     14     42     132     429     1430     4862     A000108
   [0.1cm]
   213      1     1     2     5     15     50     180     686     2731     11254     unknown 
   [0.1cm]
   231      1     1     2     6     21     79     311     1265     5275     22431     unknown
   [0.1cm]
   312      1     1     2     5     15     50     179     675     2649     10734     unknown 
   [0.1cm]
   321      1     1     2     4     9     21     51     127     323     835     A001006
   [0.1cm]
  
  
  
  
  It would be interesting to have nontrivial information about the asymptotic behavior of the unknown sequences in this table. Recall that we also have Conjecture <ref>, which states that (_231) is enumerated by the binomial transform of Fine's sequence (OEIS sequence A033321). 
  
  From the dynamical point of view, we first proved Theorem <ref>, which characterized the periodic points of _σ for each σ∈ S_3. This theorem has motivated us to formulate the following conjecture, which we have additionally confirmed when k=4 and n≤ 8.
  
  
  Let σ∈ S_k for some k≥ 3. The periodic points of the map _σ:S_n→ S_n are precisely the permutations in _n(σ,(σ)).
  
  
  We then asked for the maximum value of |_σ^-1(π)| for π∈ S_n. The following table summarizes what we know about these values; note that by Lemma <ref>, we only need to consider one pattern from each of the pairs {123,321}, {132,312}, {213,231}. 
  
  
  
   
   σ \ n      1     2     3     4     5     6     7     8     9     OEIS
  
   
  
   123     1     1     2     3     4     7     11     16     26     unknown
   [0.1cm]
   132     1     1     2     3     6     10     20     35     70     A001405
   [0.1cm]
   231     1     1     2     4     8     16     32     64     128     A011782
   [0.1cm]
  
  
  
  
  It would be interesting to have nontrivial estimates for the numbers max_π∈ S_n|_123^-1(π)| appearing in the first row of the above table. 
  
  In Section <ref>, we studied the maximum number of iterations of s_132 (equivalently, s_312) needed to send a permutation to a periodic point. This line of investigation is completely open for the consecutive-pattern-avoiding stack-sorting maps. However, we do have the following conjecture, which we have verified for n≤ 9. Recall that the set of periodic points of _231:S_n→ S_n is _n(132,231)=_n(132,231).
  
  
  Let n≥ 3. We have _231^2n-4(π)∈_n(132,231) for every π∈ S_n. Furthermore, there exists a permutation τ∈ S_n such that _231^2n-5(τ)∉_n(132,231). 
  
  
  In <cit.>, the first author showed that the numbers 3,7,11,15,19,23 are infertility numbers, meaning that there does not exist a permutation π such that |s^-1(π)|∈{3,7,11,15,19,23}. By contrast, we have the following conjecture for the maps _σ with σ∈ S_3. 
  
  
  For every σ∈ S_3 and every positive integer f, there exists a permutation π such that |_σ^-1(π)|=f.  
  
  
  Section <ref> contains the first theorems of a dynamical nature concerning maps of the form s_σ. It would be interesting to have other dynamical results for these maps, including analogues of Theorems <ref> and <ref> for the maps s_σ with σ∈{123,213,231,321}. In Theorems <ref> and <ref>, we proved that every permutation π∈ S_n satisfies s_132^n-1(π)∈(132,231) and that there exists at least one permutation τ∈ S_n such that s_132^n-2(τ)∉(132,231). It would be interesting to obtain nontrivial information about these permutations τ. We also have the following conjecture. If n is odd (respectively, even), let V_n denote the permutation in S_n obtained by listing the odd (respectively, even) elements of [n] in decreasing order and then listing the even (respectively, odd) elements of [n] in increasing order. For example, V_6=642135 and V_7=7531246. 
  
  
  If τ∈ S_n is such that s_132^n-2(τ)∉(132,231), then s_132^n-1(τ)= V_n. 
   
  
  For example, one can check that if τ∈ S_6 is such that s_132^4(τ)∉(132,231), then s_132^5(τ)= V_6=642135. 
  
  Of course, it would also be very natural to consider the maps of the form _σ^(1),…,σ^(r), where _σ^(1),…,σ^(r) is defined using a stack whose contents must consecutively avoid all of the patterns σ^(1),…,σ^(r). It would also be exciting to have results about the maps _σ for patterns σ of length at least 4 (such as progress toward Conjecture <ref>).  
  
  
  
  § ACKNOWLEDGMENTS
  
  This research was conducted as part of the University of Minnesota Duluth Mathematics REU and was supported by NSF-DMS
  Grant 1949884 and NSA Grant H98230-20-1-0009.
  The authors thank Joe Gallian for running the REU program and providing encouragement. We also thank Giulio Cerbai for very helpful discussions. The first author was supported by a Fannie and John Hertz Foundation Fellowship and an NSF Graduate Research Fellowship.
  
  
  
  
  99
  
  Asinowski
  A. Asinowski, C. Banderier, and B. Hackl, Flip-sort and combinatorial aspects of
  pop-stack sorting. arXiv:2003.04912.
  
  AHPSV
  M. Albert, C. Homberger, J. Pantone, N. Shar, and V. Vatter, Generating permutations with restricted containers. J. Combin. Theory Ser. A, 157 (2018).
  
  Baril
  J.-L. Baril, C. Khalil, V. Vajnovszki, Catalan and Schröder permutations sortable by two restricted stacks. arXiv:2004.01812. 
  
  Bentz
  H.-J. Bentz, Proof of the Bulgarian Solitaire conjectures. Ars Combin., 23 (1987), 151–170. 
  
  Berlow
  K. Berlow, Restricted stacks as functions. arXiv:2008.01164.
  
  Bona
  M. Bóna, Combinatorics of permutations. CRC Press, 2012. 
  
  BonaSurvey
  M. Bóna, A survey of stack-sorting disciplines. Electron. J. Combin., 9 (2003).
  
  Bousquet98
  M. Bousquet-Mélou, Multi-statistic enumeration of two-stack sortable permutations. Electron. J. Combin., 5 (1998).
  
  Bousquet
  M. Bousquet-Mélou, Sorted and/or sortable permutations. Discrete Math., 225 (2000), 25–50.
  
  Cerbai3
  G. Cerbai, Sorting Cayley permutations with pattern-avoiding machines. arXiv:2006.05692. 
  
  Cerbai
  G. Cerbai, A. Claesson, and L. Ferrari, Stack sorting with restricted stacks. J. Combin. Theory Ser. A, 173 (2020).
  
  Cerbai2
  G. Cerbai, A. Claesson, L. Ferrari, and E. Steingrímsson, Sorting with pattern-avoiding stacks: the 132-machine. Electron. J. Combin., 27 (2020). 
  
  Claessonn-4
  A. Claesson, M. Dukes, and E. Steingrímsson, Permutations sortable by n-4 passes through a stack. Ann. Combin., 14 (2010), 45–51.  
  
  DefantCatalan
  C. Defant, Catalan intervals and uniquely sorted permutations. J. Combin. Theory Ser. A, 174 (2020).
  
  DefantCounting
  C. Defant, Counting 3-stack-sortable permutations. J. Combin. Theory Ser. A, 172 (2020). 
  
  DefantFertility
  C. Defant, Fertility numbers. J. Comb., 11 (2020), 511–526. 
  
  DefantPreimages
  C. Defant, Preimages under the stack-sorting algorithm. Graphs Combin., 33 (2017), 103–122. 
  
  
  
  
  DefantTroupes
  C. Defant, Troupes, cumulants, and stack-sorting. arXiv:2004.11367. 
  
  DefantEngenMiller
  C. Defant, M. Engen, and J. A. Miller, Stack-sorting, set partitions, and Lassalle's sequence. J. Combin. Theory Ser. A, 175 (2020). 
  
  
  
  
  Elizalde
  S. Elizalde. A survey of consecutive patterns in permutations. In: Recent trends in combinatorics, 601–618. Springer, 2016.
  
  Etienne
  G. Etienne, Tableux de Young et Solitaire Bulgare, J. Combin. Theory Ser. A, 58 (1991), 181–197.
  
  Goulden
  I. Goulden and J. West, Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations, J. Combin. Theory Ser. A, 75 (1996), 220–242.
  
  Griggs
  J. R. Griggs and C.-C. Ho, The cycling of partitions and composition under repeated shifts. Adv.
  Appl. Math., 21 (1998), 205–227.
  
  HeinHuang
  N. Hein and J. Huang, Modular Catalan numbers, European J. Combin., 61 (2017), 197–218.
  
  Hobby
  J. D. Hobby, D. Knuth, Problem 1: Bulgarian Solitaire, In: A Programming and Problem-Solving Seminar, Department of Computer Science, Stanford University, 1983 (December),
  6–13.
  
  Igusa
  K. Igusa, Solution of the Bulgarian solitaire conjecture, Math. Mag., 58 (1985), 259–271.
  
  Kitaev
  S. Kitaev, Patterns in Permutations and Words. Monographs in Theoretical Computer
  Science. Springer, Heidelberg, 2011.
  
  Knuth
  D. E. Knuth, The Art of Computer Programming, Volume I: Fundamental Algorithms.
  Addison-Wesley, 1973.
  
  Knuth2
  D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching. Addison–Wesley, Reading, 2nd ed., 1998.
  
  Linton
  S. Linton, N. Ruškuc, V. Vatter, Permutation Patterns, London Mathematical Society Lecture Note Series, Volume 376. Cambridge University Press, 2010.
  
  Hanna
  H. Mularczyk, Lattice paths and pattern-avoiding uniquely sorted permutations. arXiv:1908.04025.
  
  OEIS
  The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org, 2020.
  
  Maya
  M. Sankar, Further bijections to pattern-avoiding valid hook configurations. To appear in Adv. Appl. Math. 
  
  Steingrimsson
  E. Steingrímsson, Generalized permutation patterns — a short survey. In: Permutation Patterns (2010), S. Linton, N. Rus̆kuc, and V. Vatter (eds.), vol. 376 of London Math.
  Soc. Lecture Note Ser., 137–152. 
  
  Toom
  A. L. Toom, Problem Solution M655. Kvant, 12 (1981), 28–30.  (In Russian.)
  
  Ungar
  P. Ungar, 2N noncollinear points determine at least 2N directions. J. Combin. Theory Ser. A, 33 (1982), 343–347. 
  
  West
  J. West, Permutations with restricted subsequences and stack-sortable permutations, Ph.D. Thesis, MIT, 1990.
  
  Zeilberger
  D. 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.  
  
  
  