# On a conjecture on pattern-avoiding machines

Christopher Bao  C. Bao, The Davidson Academy, Reno, NV, 89507
<EMAIL_ADDRESS>,  Giulio Cerbai  G. Cerbai, University of Iceland,
Iceland<EMAIL_ADDRESS>,  Yunseo Choi  Y. Choi, Harvard University, Cambridge,
MA, 02138<EMAIL_ADDRESS>,  Katelyn Gan  K. Gan, Sage Hill School,
Newport Beach, CA, 92657<EMAIL_ADDRESS>and  Owen Zhang  O. Zhang,
Interlake High School, Bellevue, WA, 98008<EMAIL_ADDRESS>
###### Abstract.

Let $s$ be West’s stack-sorting map, and let $s_{T}$ be the generalized stack-
sorting map, where instead of being required to increase, the stack avoids
subpermutations that are order-isomorphic to any permutation in the set $T$.
In 2020, Cerbai, Claesson, and Ferrari introduced the $\sigma$-machine $s\circ
s_{\sigma}$ as a generalization of West’s $2$-stack-sorting-map $s\circ s$. As
a further generalization, in 2021, Baril, Cerbai, Khalil, and Vajnovski
introduced the $(\sigma,\tau)$-machine $s\circ s_{\sigma,\tau}$ and enumerated
$|\mathrm{Sort}_{n}(\sigma,\tau)|$—the number of permutations in $S_{n}$ that
are mapped to the identity by the $(\sigma,\tau)$-machine—for six pairs of
length $3$ permutations $(\sigma,\tau)$. In this work, we settle a conjecture
by Baril, Cerbai, Khalil, and Vajnovski on the only remaining pair of length
$3$ patterns $(\sigma,\tau)=(132,321)$ for which
$|\mathrm{Sort}_{n}(\sigma,\tau)|$ appears in the OEIS. In addition, we
enumerate $|\mathrm{Sort}_{n}(123,321)|$, which does not appear in the OEIS,
but has a simple closed form.

##  1\. Introduction

In 1990, Julian West [16] introduced the stack-sorting map $s$, a
deterministic variation of Knuth’s [12] stack-sorting machine. In West’s
stack-sorting map $s$, the input permutation is sent through a stack in a
right-greedy manner such that the stack is increasing from top to bottom (see
for example, Figure 1).

4213$\rightarrow$

2134$\rightarrow$

1342$\rightarrow$

3421$\rightarrow$

3421$\rightarrow$

3412$\rightarrow$

4312$\rightarrow$

4123$\rightarrow$

1234

Figure 1. West’s stack-sorting map $s$ on $x=4213$.

Since then, the stack-sorting map $s$ has been generalized to $s_{\sigma}$ for
permutations $\sigma$ [7]. Like $s$, the map $s_{\sigma}$ sends a permutation
through a stack in a right-greedy manner. However, instead of insisting that
the stack increases (i.e., avoids subsequences that are order-isomorphic to
$21$ when as usual, is read from top to bottom), we insist that the stack
avoids subsequences that are order-isomorphic to $\sigma$. Soon after, Berlow
[2] extended $s_{\sigma}$ to stacks that must avoid all of the patterns in a
given set. In the same year, Defant and Zheng [11] extended $s_{\sigma}$ to
vincular patterns.

West’s stack-sorting map $s$ derives its name from the easily verifiable
result that for any $x\in S_{n}$, the permutation $s^{n-1}(x)$ is _sorted_
(i.e., is the identity permutation). Naturally, one of the most classical
questions on the stack-sorting map concerns the characterization of _$1$
-stack-sortable_ permutations—the permutations $x\in S_{n}$ for which $s(x)$
is sorted. Knuth [12] was the first to answer this question; he showed that
$s(x)$ is sorted if and only if $x$ avoids subsequences that are order-
isomorphic to $231$ and enumerated the number of such permutations in $S_{n}$
to be $n^{\text{th}}$ Catalan number $\frac{1}{n+1}\binom{2n}{n}$.

With the question on the permutations that get sorted after passing through
one stack settled, it is then natural to ask about the permutations that are
sorted after passing through multiple stacks in a series. A notable example is
_West’s $2$-stack-sorting-map_ $s\circ s$. In 1990, West [16] characterized
the $2$-stack-sortable permutations—the permutations that are sorted after
passing through West’s $2$-stack-sorting-map—using barred patterns and
conjectured that the number of $2$-stack-sortable permutations in $S_{n}$ is
$\frac{2}{(n+1)(2n+1)}\binom{3n}{n}$. Two years later in 1992, Zeilberger [17]
affirmed West’s conjecture. Later, Cerbai [6] generalized some of the results
on West’s $2$-stack-sorting map to Cayley permutations. Only recently in 2020,
Defant presented a polynomial time algorithm [10] that counts the number of
permutations that are sorted after passing through a series of three stacks.

To better understand the permutations that are sortable under stacks in
series, Cerbai, Claesson, and Ferrari [7] introduced the $\sigma$-machine
$s\circ s_{\sigma}$ in 2020. It is then natural to ask about the permutations
that get sorted after passing through the $\sigma-$machine once. Therefore,
let $\mathrm{Sort}_{n}(\sigma)$ denote the set of permutations in $S_{n}$ that
are sorted after a single pass through the $\sigma$-machine. Equivalently, due
to Knuth’s characterization of $1$-stack sortable permutations,
$\mathrm{Sort}_{n}(\sigma)$ is the set of permutations $x$ where
$s_{\sigma}(x)$ avoids $231$. The most notable enumerations of the sequence
$|\mathrm{Sort}_{n}(\sigma)|$ are by Cerbai, Claesson, and Ferrari [7] and by
Cerbai, Claesson, Ferrari, and Steingrímsson [8] in a subsequent work (see
Table 1).

$\sigma$ | Reference | OEIS entry for $|\mathrm{Sort}_{n}(\sigma)|$
---|---|---
123 | Section 5 of [7] | A294790
132 | Corollary 4.17 of [8] | A007317
321 | Section 4 of [7] | A011782
Table 1. Enumeration of $|\mathrm{Sort}_{n}(\sigma)|$, for patterns $\sigma$
of length three.

In 2021, Baril, Cerbai, Khalil, and Vajnovszki [1] introduced the
$(\sigma,\tau)$-machine $s\circ s_{\sigma,\tau}$ as a further generalization
of the $\sigma$-machine. For example, Figure 2 illustrates that $x=2314$ is
sent to $3124$ after passing through the $(132,321)$-machine.

231413232121$\rightarrow$

314132321212$\rightarrow$

141323212123$\rightarrow$

141323212123$\rightarrow$

413232121213$\rightarrow$

132321212143$\rightarrow$

132321212134$\rightarrow$

132321212341$\rightarrow$

132321213412$\rightarrow$

132321214123$\rightarrow$

132321214123$\rightarrow$

132321211243$\rightarrow$

132321212413$\rightarrow$

132321212431$\rightarrow$

132321214231$\rightarrow$

132321214312$\rightarrow$

132321213124

Figure 2. The $(132,321)$-machine on $x=2314$.

As an analog of $\mathrm{Sort}_{n}(\sigma)$, let
$\mathrm{Sort}_{n}(\sigma,\tau)$ consist of the permutations in $S_{n}$ that
are sorted after an iteration through the $(\sigma,\tau)$-machine.
Permutations in $\mathrm{Sort}_{n}(\sigma,\tau)$ are said to be
_$(\sigma,\tau)$ -sortable_. Baril, Cerbai, Khalil, and Vajnovszki [1]
enumerated $|\mathrm{Sort}_{n}(\sigma,\tau)|$ for several pairs of length $3$
patterns $(\sigma,\tau)$ (see Table 2) and observed through numerical
computation that the only remaining pair of length $3$ permutations
$(\sigma,\tau)$ for which $|\mathrm{Sort}_{n}(\sigma,\tau)|$ may belong to the
OEIS [14] is $(\sigma,\tau)=(132,321)$. As our first main result, in Section 3
we settle Baril, Cerbai, Khalil, and Vajnovszki’s conjecture that
$|\mathrm{Sort}_{n}(132,321)|$ is enumerated by A102407 (see Conjecture 1 of
[1]).

$(\sigma,\tau)$ | Reference | Sequence $|\mathrm{Sort}_{n}(\sigma,\tau)|$ | OEIS
---|---|---|---
123,213
132,312
231,321 | Theorem 4.2 of [1] | Catalan numbers | A000108
123,132 | Corollary 5.3 of [1] | Catalan numbers | A000108
123,231 | Corollary 3.2 of [1] | Large Schröder numbers | A006318
123,312 | Section 6 of [1] | Binomial Transform of Catalan numbers | A007317
132,321 | Theorem 1.1 | 1, 2, 4, 10, 26, 72, 206, 606,$\dots$ | A102407
123,321 | Theorem 1.2 |  $2^{n-1}$ for $n\leq 3$ and $7\cdot 2^{n-4}$ for $n\geq 4$ |
Table 2. Enumerations of $|\mathrm{Sort}_{n}(\sigma,\tau)|$.

######  Theorem 1.1.

The sequence $|\mathrm{Sort}_{n}(132,321)|$ is the OEIS A102407 [14].

To prove Theorem 1.1, we first characterize $\mathrm{Sort}_{n}(132,321)$ by
avoidance of two (generalized) patterns of length three. We then use a
bijection first discovered by West to map $\mathrm{Sort}_{n}(132,321)$ to a
set that we are able to enumerate directly. A more geometrical approach that
involves a bijection with Dyck paths avoiding the subword $dudu$ is also
illustrated in Section 3.1.

Furthermore, in Section 4, we enumerate $\mathrm{Sort}_{n}(123,321)$. This
sequence does not belong to the OEIS [14] but has a simple closed form for
$n\geq 4$.

######  Theorem 1.2.

The sequence $|\mathrm{Sort}_{n}(123,321)|$ is the sequence $7\cdot 2^{n-4}$
for $n\geq 4.$

We end the paper with some suggestions for future work.

##  2\. Preliminaries

Let $[n]=\\{1,2,\dots,n\\}$. A _permutation_ of length $n$ is a bijective map
$x:[n]\to[n]$. Let $S_{n}$ be the set of permutations of length $n$. We denote
a permutation $x\in S_{n}$ by the string $x=x_{1}x_{2}\dots x_{n}$, where
$x_{i}=x(i)$. Let $\mathrm{ind}_{x}(i)=x^{-1}(i)$ be the index such that
$x_{\mathrm{ind}_{x}(i)}=i$. For example, $\mathrm{ind}_{12534}(5)=3$. If
$i<j$ (respectively, $i>j$), we say that $x_{i}$ _appears to the left of
(resp. to the right of)_ $x_{j}$ in $x$. An entry $x_{i}$ is a _left-to-right
minimum_ (briefly, ltr minimum) of $x$ if $x_{i}$ is smaller than each entry
that appears to its left. Furthermore, we let $x_{[i,j]}$ denote the
subsequence $x_{i}x_{i+1}\dots x_{j}$, and we let $\\{x_{[i,j]}\\}$ be the set
$\\{x_{i},x_{i+1},\dots,x_{j}\\}$. For $k\geq 1$, we also let
$x+k=(x_{1}+k)(x_{2}+k)\dots(x_{n}+k)$ denote the string obtained by adding
$k$ to each entry of $x$. As an example to illustrate the above definitions,
let $x=524613$. The ltr-minima of $x$ are $5$, $2$, and $1$. For $i=2$ and
$j=5$, we have $x_{[i,j]}=2461$ and $\\{x_{[i,j]}\\}=\\{2,4,6,1\\}$. Finally,
we have $x+3=857946$.

A short introduction to permutation patterns can be found in Bevan’s note [3].
Let us recall some notions that will be used in this paper. Given two
permutations $x\in S_{n}$ and $y\in S_{m}$, with $m\leq n$, we say that $x$
_contains_ the pattern $y$ if there exists some $c(1)<c(2)<\dots<c(m)$ such
that the subsequence $z=x_{c(1)}x_{c(2)}\dots x_{c(m)}$ is order-isomorphic to
$y$. If so, we say that $z$ is an _occurrence_ of $y$ in $x$. If $x$ does not
contain the pattern $y$, then $x$ _avoids_ $y$. Let $\mathrm{Av}_{n}(y)$
denote the set of permutations of length $n$ that avoid $y$. Similarly, for a
set of patterns $T$ we let $\mathrm{Av}_{n}(T)$ be the set of permutations in
$S_{n}$ avoiding all the patterns in $T$. Bivincular patterns [4] are obtained
by allowing constraints of adjacency on positions and values. Mesh patterns
generalize both classical and bivincular patterns in the following sense. A
_mesh pattern_ [5] is a pair $(y,R)$, where $y\in S_{m}$ is a permutation and
$R\subseteq\left[0,m\right]\times\left[0,m\right]$ is a set of pairs of
integers. Each pair in $R$ determines the lower left corners of unit squares
which specify forbidden regions in the plot of permutations. An occurrence of
the mesh pattern $(y,R)$ in the permutation $x$ is an occurrence of the
classical pattern $y$ such that no other points of $x$ occur in the forbidden
regions specified by $R$. For the rest of this paper, we shall denote by
$123^{\star}$ and $132^{\star}$ the bivincular patterns depicted–as mesh
patterns–in Figure 3. For example, an occurrence of $123^{\star}$ in a
permutation $x$ is a classical occurrence $x_{c(1)}x_{c(2)}x_{c(3)}$ of $123$
such that $c(3)=c(2)+1$ and $x_{c(3)}=x_{c(2)}+1$.

$123^{\star}\;=\;\leavevmode\hbox to46.1pt{\vbox
to46.1pt{\pgfpicture\makeatletter\hbox{\hskip 0.28856pt\lower-0.28856pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{
}{0.0}{1.0}{0.0pt}{0.0pt}{ \lxSVG@closescope
}{0}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{22.76186pt}{0.0pt}\pgfsys@moveto{22.76186pt}{0.0pt}\pgfsys@lineto{22.76186pt}{45.52371pt}\pgfsys@lineto{34.14278pt}{45.52371pt}\pgfsys@lineto{34.14278pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14278pt}{45.52371pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{0.0pt}{22.76186pt}\pgfsys@moveto{0.0pt}{22.76186pt}\pgfsys@lineto{0.0pt}{34.14278pt}\pgfsys@lineto{45.52371pt}{34.14278pt}\pgfsys@lineto{45.52371pt}{22.76186pt}\pgfsys@closepath\pgfsys@moveto{45.52371pt}{34.14278pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}{}{ {}{}{}{}{ }{
}{ }{ }{ }{ }{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.01144pt}{0.01144pt}\pgfsys@moveto{0.01144pt}{11.38092pt}\pgfsys@lineto{45.51225pt}{11.38092pt}\pgfsys@moveto{0.01144pt}{22.76186pt}\pgfsys@lineto{45.51225pt}{22.76186pt}\pgfsys@moveto{0.01144pt}{34.14278pt}\pgfsys@lineto{45.51225pt}{34.14278pt}\pgfsys@moveto{11.38092pt}{0.01144pt}\pgfsys@lineto{11.38092pt}{45.51225pt}\pgfsys@moveto{22.76186pt}{0.01144pt}\pgfsys@lineto{22.76186pt}{45.51225pt}\pgfsys@moveto{34.14278pt}{0.01144pt}\pgfsys@lineto{34.14278pt}{45.51225pt}\pgfsys@moveto{45.51225pt}{45.51225pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{11.38092pt}{11.38092pt}\pgfsys@moveto{13.78088pt}{11.38092pt}\pgfsys@curveto{13.78088pt}{12.70639pt}{12.70639pt}{13.78088pt}{11.38092pt}{13.78088pt}\pgfsys@curveto{10.05545pt}{13.78088pt}{8.98096pt}{12.70639pt}{8.98096pt}{11.38092pt}\pgfsys@curveto{8.98096pt}{10.05545pt}{10.05545pt}{8.98096pt}{11.38092pt}{8.98096pt}\pgfsys@curveto{12.70639pt}{8.98096pt}{13.78088pt}{10.05545pt}{13.78088pt}{11.38092pt}\pgfsys@closepath\pgfsys@moveto{11.38092pt}{11.38092pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{22.76186pt}{22.76186pt}\pgfsys@moveto{25.16182pt}{22.76186pt}\pgfsys@curveto{25.16182pt}{24.08733pt}{24.08733pt}{25.16182pt}{22.76186pt}{25.16182pt}\pgfsys@curveto{21.43639pt}{25.16182pt}{20.3619pt}{24.08733pt}{20.3619pt}{22.76186pt}\pgfsys@curveto{20.3619pt}{21.43639pt}{21.43639pt}{20.3619pt}{22.76186pt}{20.3619pt}\pgfsys@curveto{24.08733pt}{20.3619pt}{25.16182pt}{21.43639pt}{25.16182pt}{22.76186pt}\pgfsys@closepath\pgfsys@moveto{22.76186pt}{22.76186pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{34.14278pt}{34.14278pt}\pgfsys@moveto{36.54274pt}{34.14278pt}\pgfsys@curveto{36.54274pt}{35.46825pt}{35.46825pt}{36.54274pt}{34.14278pt}{36.54274pt}\pgfsys@curveto{32.8173pt}{36.54274pt}{31.74281pt}{35.46825pt}{31.74281pt}{34.14278pt}\pgfsys@curveto{31.74281pt}{32.8173pt}{32.8173pt}{31.74281pt}{34.14278pt}{31.74281pt}\pgfsys@curveto{35.46825pt}{31.74281pt}{36.54274pt}{32.8173pt}{36.54274pt}{34.14278pt}\pgfsys@closepath\pgfsys@moveto{34.14278pt}{34.14278pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\qquad
132^{\star}\;=\;\leavevmode\hbox to46.1pt{\vbox
to46.1pt{\pgfpicture\makeatletter\hbox{\hskip 0.28856pt\lower-0.28856pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{22.76186pt}{0.0pt}\pgfsys@moveto{22.76186pt}{0.0pt}\pgfsys@lineto{22.76186pt}{45.52371pt}\pgfsys@lineto{34.14278pt}{45.52371pt}\pgfsys@lineto{34.14278pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14278pt}{45.52371pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{0.0pt}{22.76186pt}\pgfsys@moveto{0.0pt}{22.76186pt}\pgfsys@lineto{0.0pt}{34.14278pt}\pgfsys@lineto{45.52371pt}{34.14278pt}\pgfsys@lineto{45.52371pt}{22.76186pt}\pgfsys@closepath\pgfsys@moveto{45.52371pt}{34.14278pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}{}{ {}{}{}{}{ }{
}{ }{ }{ }{ }{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.01144pt}{0.01144pt}\pgfsys@moveto{0.01144pt}{11.38092pt}\pgfsys@lineto{45.51225pt}{11.38092pt}\pgfsys@moveto{0.01144pt}{22.76186pt}\pgfsys@lineto{45.51225pt}{22.76186pt}\pgfsys@moveto{0.01144pt}{34.14278pt}\pgfsys@lineto{45.51225pt}{34.14278pt}\pgfsys@moveto{11.38092pt}{0.01144pt}\pgfsys@lineto{11.38092pt}{45.51225pt}\pgfsys@moveto{22.76186pt}{0.01144pt}\pgfsys@lineto{22.76186pt}{45.51225pt}\pgfsys@moveto{34.14278pt}{0.01144pt}\pgfsys@lineto{34.14278pt}{45.51225pt}\pgfsys@moveto{45.51225pt}{45.51225pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{11.38092pt}{11.38092pt}\pgfsys@moveto{13.78088pt}{11.38092pt}\pgfsys@curveto{13.78088pt}{12.70639pt}{12.70639pt}{13.78088pt}{11.38092pt}{13.78088pt}\pgfsys@curveto{10.05545pt}{13.78088pt}{8.98096pt}{12.70639pt}{8.98096pt}{11.38092pt}\pgfsys@curveto{8.98096pt}{10.05545pt}{10.05545pt}{8.98096pt}{11.38092pt}{8.98096pt}\pgfsys@curveto{12.70639pt}{8.98096pt}{13.78088pt}{10.05545pt}{13.78088pt}{11.38092pt}\pgfsys@closepath\pgfsys@moveto{11.38092pt}{11.38092pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{22.76186pt}{34.14278pt}\pgfsys@moveto{25.16182pt}{34.14278pt}\pgfsys@curveto{25.16182pt}{35.46825pt}{24.08733pt}{36.54274pt}{22.76186pt}{36.54274pt}\pgfsys@curveto{21.43639pt}{36.54274pt}{20.3619pt}{35.46825pt}{20.3619pt}{34.14278pt}\pgfsys@curveto{20.3619pt}{32.8173pt}{21.43639pt}{31.74281pt}{22.76186pt}{31.74281pt}\pgfsys@curveto{24.08733pt}{31.74281pt}{25.16182pt}{32.8173pt}{25.16182pt}{34.14278pt}\pgfsys@closepath\pgfsys@moveto{22.76186pt}{34.14278pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{34.14278pt}{22.76186pt}\pgfsys@moveto{36.54274pt}{22.76186pt}\pgfsys@curveto{36.54274pt}{24.08733pt}{35.46825pt}{25.16182pt}{34.14278pt}{25.16182pt}\pgfsys@curveto{32.8173pt}{25.16182pt}{31.74281pt}{24.08733pt}{31.74281pt}{22.76186pt}\pgfsys@curveto{31.74281pt}{21.43639pt}{32.8173pt}{20.3619pt}{34.14278pt}{20.3619pt}\pgfsys@curveto{35.46825pt}{20.3619pt}{36.54274pt}{21.43639pt}{36.54274pt}{22.76186pt}\pgfsys@closepath\pgfsys@moveto{34.14278pt}{22.76186pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ Figure 3. Bivincular
patterns $123^{\star}$ and $132^{\star}$.

Lastly, we cite Knuth’s [12] lemma on the characterization of 1-stack-sortable
permutations.

######  Lemma 2.1 (Knuth [12]).

A permutation $x$ is 1-stack-sortable if and only if $x$ avoids $231$.

###  2.1. West’s Bijection

In 1995, West [15] presented a new bijection between $\mathrm{Av}_{n}(132)$
and $\mathrm{Av}_{n}(123)$. Let $x=x_{1}x_{2}\dots x_{n-1}\in S_{n-1}$. For
$1\leq i\leq n$, denote by $x^{i}$ the permutation $x_{1}x_{2}\dots
x_{i-1}nx_{i}\dots x_{n-1}$ obtained by inserting $n$ in the $i$th _site_ of
$x$ (i.e. the position immediately before $x_{i}$, for $i=1,\dots,n-1$, or at
the end, if $i=n$). Given a pattern $y$, define the $i$th site of $x$ to be
_active_ with respect to $y$ if $x^{i}$ avoids $y$. For example, if $x=45231$,
then $i\in\\{1,3,5,6\\}$ are active with respect to $y=132$, but
$i\in\\{2,4\\}$ are not since both $x^{2}=465231$ and $x^{4}=452631$ contain
$132$. Now, let $\mathrm{small}_{k}(x)$ denote the subsequence of the smallest
$k$ numbers in $x$. Given a pattern $y$, let $\mathrm{Ac}_{j}(x;y)$ denote the
set of active sites in $\mathrm{small}_{|x|+1-j}(x)$ with respect to the
pattern $y$. Note that $\mathrm{Ac}_{1}(x;y)$ is equal to the number of active
sites of $x$ with respect to $y$. For example,
$|\mathrm{Ac}_{1}(45231;132)|=|\mathrm{Ac}_{2}(45231;132)|=4$, because the set
of active sites with respect to $132$ pattern for $x=45231$ is $\\{1,3,5,6\\}$
and for $\mathrm{small}_{4}(x)=4231$ is $\\{1,2,4,5\\}$. The _signature_ of
$x$ with respect to $y$ is the word

$\mathfrak{S}(x;y)=|\mathrm{Ac}_{1}(x;y)|\cdot|\mathrm{Ac}_{2}(x;y)|\dots|\mathrm{Ac}_{n-1}(x;y)|,$

where $\cdot$ denotes concatenation. For example,
$\mathfrak{S}(45231;132)=44332$. In addition, for a set of permutations $T$,
let $\mathfrak{S}(T;y):=\\{\mathfrak{S}(x;y)\mid x\in T\\}$. West[15] showed
that permutations in $\mathrm{Av}(123)$, as well as permutations in
$\mathrm{Av}(132)$, are uniquely determined by their signature. Furthermore,
he showed that
$\mathfrak{S}(\mathrm{Av}_{n}(132);132)=\mathfrak{S}(\mathrm{Av}_{n}(123);123)$.
This naturally induces a bijection between $\mathrm{Av}_{n}(132)$ and
$\mathrm{Av}_{n}(123)$. For example, $x=45231$ is the only
$x\in\mathrm{Av}_{5}(132)$ such that $\mathfrak{S}(x;132)=44332,$ and
$y=42153$ is the only $y\in\mathrm{Av}_{5}(123)$ such that
$\mathfrak{S}(y;123)=44332$.

##  3\. The $(132,321)$-machine

This section is devoted to the $(132,321)$-machine. First we prove that
$\mathrm{Sort}_{n}(132,321)=\mathrm{Av}_{n}(123,132^{\star})$. Then we show
that West’s bijection maps $\mathrm{Av}_{n}(123,132^{\star})$ to
$\mathrm{Av}_{n}(132,123^{\star})$. Finally, we enumerate
$\mathrm{Sort}_{n}(132,321)$ by providing a generating function for
$\mathrm{Av}_{n}(132,123^{\star})$. We end the section by sketching a
bijection between $\mathrm{Sort}_{n}(132,321)$ and the set of Dyck paths of
semilength $n$ that avoid $dudu$ as a factor.

Let us begin by establishing a property that all ltr minima of the input
permutation must satisfy.

######  Lemma 3.1.

If $x_{i}$ is a ltr minimum of $x$ and
$\mathrm{ind}_{s_{132,321}(x)}(x_{i})<\mathrm{ind}_{s_{132,321}(x)}(x_{j})$,
then $j<i$.

###### Proof.

Because $x_{i}$ is a ltr minimum and the stack must avoid the $132$ pattern,
the stack must be increasing from top to bottom right after $x_{i}$ enters the
stack. Now, because $z_{2}>z_{3}$ in any $132$ or $321$ pattern $z$ and the
numbers below $x_{i}$ in the stack are increasing, $x_{i}$ can only leave the
stack after every number has entered or left the stack. Therefore, if $x_{j}$
appears to the right of $x_{i}$ in $s_{132,321}(x)$, then $x_{j}$ must have
been in the stack when $x_{i}$ entered the stack. Thus, $j<i$. ∎

Next, we show that any permutation in $\mathrm{Sort}_{n}(132,321)$ must avoid
the $123$ pattern.

######  Proposition 3.2.

If $x\in\mathrm{Sort}_{n}(132,321)$, then $x\in\mathrm{Av}_{n}(123)$.

###### Proof.

Suppose otherwise. Let $x_{i}x_{j}x_{k}$ be the lexicographically smallest
$123$ pattern of $x$ so that $x_{i}$ is a ltr minimum. By Lemma 3.1, $x_{i}$
must be in the stack when $x_{k}$ enters the stack. Now, $x_{j}$ must leave
the stack before $x_{k}$ enters the stack, because $x_{k}x_{j}x_{i}$ is a
$321$ pattern. As a result, $x_{j}$ must appear to left of $x_{k}$ in
$s_{132,321}(x)$. Furthermore, by Lemma 3.1, $x_{i}$ must appear to the right
of $x_{j}$ and $x_{k}$ in $s_{132,321}(x)$. Thus, $x_{j}x_{k}x_{i}$ is a $231$
pattern in $s_{132,321}(x)$—a contradiction to
$x\in\mathrm{Sort}_{n}(132,321)$ by Lemma 2.1. ∎

Due to Proposition 3.2, the behavior of the $(132,321)$-stack on any
$(132,321)$-sortable permutation is equivalent to the behavior of a
$132$-stack. Therefore,

$\mathrm{Sort}_{n}(132,321)=\mathrm{Sort}_{n}(132)\cap\mathrm{Av}(123).$

The next proposition shows that any permutation in
$\mathrm{Sort}_{n}(132,321)$ must avoid the $132^{\star}$ pattern.

######  Proposition 3.3.

If $x\in\mathrm{Sort}_{n}(132,321)$, then $x\in\mathrm{Av}_{n}(132^{\star})$.

###### Proof.

Suppose otherwise. Let $x_{i}x_{j}x_{j+1}$ be the lexicographically smallest
$132^{\star}$ pattern of $x$ so that $x_{i}$ is a ltr minimum. Now, suppose
that $x_{j}$ has just entered the stack. Because $x_{j}=x_{j+1}+1$, if
$x_{j+1}$ entering the stack introduces a $132$ or $321$ pattern to the stack,
then $x_{j+1}$ and $x_{j}$ must both be a part of the pattern. However, in a
$132$ pattern $z$, it must be that $z_{2}-z_{1}\geq 2$ and in a $321$ pattern
$z$, it must be that $z_{2}<z_{1}$. Yet, $x_{j}-x_{j+1}=1$, and so the
entrance of $x_{j+1}$ into the stack cannot introduce a $132$ or $321$
pattern. Therefore, $x_{j+1}$ must be to the left of $x_{j}$ in
$s_{132,321}(x)$. In addition, by Lemma 3.1, $x_{i}$ must be to the right of
$x_{j}$ and $x_{j+1}$ in $s_{132,321}(x)$. Thus, $x_{j+1}x_{j}x_{i}$ is a
$231$ pattern in $s_{132,321}(x)$—a contradiction to
$x\in\mathrm{Sort}_{n}(132,321)$ by Lemma 2.1. ∎

We shall prove that the conditions of Lemmas 3.2 and 3.3 are sufficient for a
permutation to be in $\mathrm{Sort}_{n}(132,321)$. First, a simple lemma.

######  Lemma 3.4.

If $x_{i}$ is not a ltr minimum of $x\in\mathrm{Av}_{n}(123)$ and $i<j$, then
$x_{i}>x_{j}$.

###### Proof.

Suppose otherwise. Because $x_{i}$ is not a ltr minimum, there exists $x_{k}$
such that $x_{k}<x_{i}$ and $k<i$. Thus, $x_{k}x_{i}x_{j}$ is a $123$ pattern
in $x$—a contradiction. ∎

Next, we prove a property that all $x\in\mathrm{Av}_{n}(123,132^{\star})$ must
satisfy.

######  Lemma 3.5.

If $x_{i}$ is not a ltr minimum of $x\in\mathrm{Av}_{n}(123,132^{\star})$,
then

$\mathrm{ind}_{s_{132,321}(x)}(x_{i})<\mathrm{ind}_{s_{132,321}(x)}(x_{i+1}).$

###### Proof.

First, suppose that $x_{i+1}$ is a ltr minimum. Then because $x_{i}$ is not a
ltr minimum, there must be some ltr minimum $x_{j}$ such that $x_{j}<x_{i}$
and $j<i$. Now, by Lemma 3.1, $x_{j}$ must be in the stack when $x_{i+1}$
enters the stack. Then because $x_{i+1}$ is a ltr minimum, the subsequence
$x_{i+1}x_{i}x_{j}$ must be a $132$ pattern. Therefore, $x_{i}$ must leave the
stack before $x_{i+1}$ enters the stack.

Next, suppose that $x_{i+1}$ is not a ltr minimum. First, because $x_{i}$ is
not a ltr minimum, $x_{i}>x_{i+1}$ by Lemma 3.4. In addition, there is some
ltr minimum $x_{k}$ such that $x_{k}<x_{i+1}$ and $k<i$. Furthermore,
$x_{i}>x_{i+1}+1$, because otherwise, $x_{k}x_{i}x_{i+1}$ is a $132^{\star}$
pattern. Now, if $x_{i+1}+1$ appears to the right of $x_{i+1}$, then
$x_{k}x_{i+1}\cdot(x_{i+1}+1)$ is a $123$ pattern. Thus, by Lemma 3.4,
$x_{i+1}+1$ must be a ltr minimum, and by Lemma 3.1, $x_{i+1}+1$ must be in
the stack when $x_{i+1}$ enters the stack. Now, $x_{i}$ and $x_{i+1}+1$ cannot
both be in the stack when $x_{i+1}$ enters the stack, because
$x_{i+1}x_{i}\cdot(x_{i+1}+1)$ is a $132$ pattern. Thus, $x_{i}$ must leave
the stack before $x_{i+1}$ enters the stack. ∎

######  Proposition 3.6.

If $x\in\mathrm{Av}_{n}(123,132^{\star})$, then
$x\in\mathrm{Sort}_{n}(132,321).$

###### Proof.

By Lemma 3.1, any ltr minimum $x_{i}$ must remain in the stack until every
other number has entered the stack. By Lemma 3.5, any $x_{i}$ that is not a
ltr minimum of $x$ must leave the stack before $x_{i+1}$ enters the stack.
Therefore, any ltr minimum of $x$ must appear to the right of any number that
is not a ltr minimum of $x$ in $s_{132,321}(x)$. Now, because the ltr minima
of $x$ must decreasing from the left to right, by Lemma 3.1, the ltr minima of
$x$ must appear in $s_{132,321}(x)$ in increasing order. Furthermore, by
Lemmas 3.4 and 3.5, the numbers that are not ltr minima of $x$ must appear in
$s_{132,321}(x)$ in decreasing order. Thus, $s_{132,321}(x)$ must avoid the
$231$ pattern and by Lemma 2.1, must be in $\mathrm{Sort}_{n}(132,321)$. ∎

Now, we collate propositions 3.2, 3.3, and 3.6.

######  Theorem 3.7.

For all $n$, it holds that
$\mathrm{Sort}_{n}(132,321)=\mathrm{Av}_{n}(123,132^{\star})$.

Our next goal is to show that West’s bijection maps
$\mathrm{Av}_{n}(123,132^{\star})$ to $\mathrm{Av}_{n}(132,123^{\star})$.
Recall from Section 2.1 that permutations in $\mathrm{Av}_{n}(123)$, as well
as in $\mathrm{Av}(132)$, are uniquely determined by their signature. West’s
bijection then follows from the equality between the corresponding sets of
signatures

$\mathfrak{S}(\mathrm{Av}_{n}(123),123)=\mathfrak{S}(\mathrm{Av}_{n}(132),132).$

We wish to prove that any permutation $x\in\mathrm{Av}_{n}(123)$ contains
$132^{\star}$ if and only if there exists some $1\leq i\leq n-2$ such that

$\mathfrak{S}(x;123)_{i}=\mathfrak{S}(x;123)_{i+1}\leq\mathfrak{S}(x;123)_{i+2}.$

The desired result follows from the fact that the same property holds when we
replace the pattern $123$ with $132$ and the pattern $132^{\star}$ with
$123^{\star}$.

Let us take care of $\mathrm{Av}_{n}(123,132^{\star})$ first. To start, we
show that removing the maximum of a permutation preserves the property of
avoiding both patterns.

######  Lemma 3.8.

If $x\in\mathrm{Av}_{n}(123,132^{\star})$, then
$\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123,132^{\star})$.

###### Proof.

It is clear that $\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123)$. Suppose
that $\mathrm{small}_{n-1}(x)\not\in\mathrm{Av}_{n-1}(132^{\star})$. Then
$x_{j}x_{\mathrm{ind_{x}(n)}-1}x_{\mathrm{ind_{x}(n)}+1}$ must be a
$132^{\star}$ pattern in $\mathrm{small}_{n-1}(x)$, because
$x\in\mathrm{Av}_{n}(132^{\star})$. However, then
$x_{j}x_{\mathrm{ind}_{x}(n)-1}\cdot n$ is a $123$ pattern in $x$—a
contradiction to $x\in\mathrm{Av}_{n}(123,132^{\star})$. ∎

Now, let $x\in\mathrm{Av}_{n}(123)$. It is easy to see that the set of active
sites $\mathrm{Ac}_{1}(x;123)$ of $x$ with respect to $123$ forms an interval.
The entry $x_{|\mathrm{Ac}_{1}(x;123)|}$ preceding the leftmost site that is
not active can be characterized as follows.

######  Lemma 3.9.

Let $x\in\mathrm{Av}_{n}(123)$ and suppose that $x$ is not the decreasing
permutation $n(n-1)\dots 1$. Then
$x_{|\mathrm{Ac}_{1}(x;123)|}=\max\\{x_{i}\mid x_{i}+i\neq n+1\\}.$

###### Proof.

We induct on $n.$ The statement is vacuously true for $n=1.$ First, suppose
that $x_{1}\neq n$. Clearly, $x^{j}\in\mathrm{Av}_{n}(123)$ for $1\leq
j\leq\mathrm{ind}_{x}(n),$ since if $(x^{j})_{a}\cdot(x^{j})_{b}\cdot(n+1)$ is
a $123$ pattern in $x^{j},$ then $x_{a}x_{b}n$ is a $123$ pattern in $x$.
Conversely, if $j>\mathrm{ind}_{x}(n)$, then $x^{j}_{1}\cdot n\cdot(n+1)$ is a
$123$ pattern in $x^{j},$ and so $j\not\in\mathrm{Ac}_{1}(x;123)$. Hence,
$\mathrm{Ac}_{1}(x;123)=\\{1,2,\cdots,\mathrm{ind}_{x}(n)\\}$ and
$x_{|\mathrm{Ac}_{1}(x;123)|}=\max\\{x_{i}\mid x_{i}+i\neq n+1\\}=n$.

Now, suppose that $x_{1}=n$. Then $\mathrm{Ac}_{1}(x;123)=\\{j\mid
j-1\in\mathrm{Ac}_{2}(x;123)\\}\cup\\{1\\}$, because no $123$ pattern in
$x^{j}$ for $1\leq j\leq n+1$ begins with $n$ or $n+1$. Thus,
$|\mathrm{Ac}_{1}(x;123)|=|\mathrm{Ac}_{2}(x;123)|+1$, and the statement of
the lemma follows by the inductive hypothesis. ∎

######  Proposition 3.10.

If $x\in\mathrm{Av}_{n}(123)$ and
$|\mathrm{Ac}_{i}(x;123)|=\mathfrak{|}\mathrm{Ac}_{i+1}(x;123)|\leq|\mathrm{Ac}_{i+2}(x;123)|$
for some $1\leq i\leq n-2$, then $x\not\in\mathrm{Av}_{n}(132^{\star}).$

###### Proof.

We induct on $n$; it is easy to see that the statement holds for $n\leq 3$.
Now, because
$\mathfrak{S}_{n}(x;123)=|\mathrm{Ac}_{1}(x;123)|\cdot\mathfrak{S}_{n}(\mathrm{small}_{n-1}(x;123))$,
if $n\geq 4$ and $2\leq i\leq n-2$, then by Lemma 3.8 and the inductive
hypothesis, $x\not\in\mathrm{Av}_{n}(132^{\star})$. Thus, assume $i=1$.

Next, if $x_{1}=n$, then $|\mathrm{Ac}_{1}(x;123)|=|\mathrm{Ac}_{2}(x;123)|+1$
by Lemma 3.9. Similarly, if $x_{1}=n-1$, then
$|\mathrm{Ac}_{2}(x;123)|=|\mathrm{Ac}_{3}(x;123)|+1$ by Lemma 3.9 on
$\mathrm{small}_{n-1}(x)$. Thus, $x_{1}\leq n-2$.

Now, $n$ appears to the left of $n-1$ in $x$, because
$x\in\mathrm{Av}_{n}(123)$ and $x_{1}\leq n-2$. But if $n\cdot(n-1)$ is not a
substring of $x$, then by Lemma 3.9 and $x_{1}\leq n-2$,

$\displaystyle|\mathrm{Ac}_{1}(x;123)|=\mathrm{ind}_{x}(n)<\mathrm{ind}_{\mathrm{small}_{n-1}(x)}(n-1)=|\mathrm{Ac}_{2}(x;123)|.$

Thus, $x\not\in\mathrm{Av}_{n}(132^{\star})$, because $x_{1}\cdot n\cdot(n-1)$
form a $132^{\star}$ pattern in $x$. ∎

The converse of Proposition 3.10 is also true, as we show below.

######  Proposition 3.11.

If $x\in\mathrm{Av}_{n}(123)\setminus\mathrm{Av}_{n}(132^{\star})$, then for
some $1\leq i\leq n-2$, it holds that
$|\mathrm{Ac}_{i}(x;123)|=|\mathrm{Ac}_{i+1}(x;123)|\leq|\mathrm{Ac}_{i+2}(x;123)|$.

###### Proof.

We induct on $n$; the statement holds for $n\leq 3,$ because
$\mathfrak{S}_{n}(132;123)=222.$ Now, suppose for the sake of contradiction
that $n\geq 4$ and that there is no $1\leq i\leq n-3$ such that
$|\mathrm{Ac}_{i}(x;123)|=\mathfrak{|}\mathrm{Ac}_{i+1}(x;123)|\leq|\mathrm{Ac}_{i+2}(x;123)|.$
Then, since
$\mathfrak{S}_{n}(x;123)=|\mathrm{Ac}_{1}(x;123)|\cdot\mathfrak{S}_{n}(\mathrm{small}_{n-1}(x);123),$
we have that $\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(132^{\star})$ from
the inductive hypothesis. Now,
$x\in\mathrm{Av}_{n}(123)\setminus\mathrm{Av}_{n}(132^{\star})$, but
$\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n}(132^{\star})$, and so
$\mathrm{ind}_{x}(n)=\mathrm{ind}_{x}(n-1)-1>1$.

Now, $|\mathrm{Ac}_{1}(x;123)|=\mathrm{ind}_{x}(n)$ from Lemma 3.9. Similarly,
$|\mathrm{Ac}_{2}(x;123)|=\mathrm{ind}_{\mathrm{small}_{n-1}(x)}(n-1)=\mathrm{ind}_{x}(n)$
from Lemma 3.9 on $\mathrm{small}_{n-1}(x)$. Therefore,
$|\mathrm{Ac}_{1}(x;123)|=|\mathrm{Ac}_{2}(x;123)|$. Now, because
$x\in\mathrm{Av}_{n}(123)$, the substring $x_{[1,\mathrm{ind}_{x}(n)-1]}$ must
be decreasing. Thus, for all $1\leq j\leq\mathrm{ind}_{x}(n)-1$, it must be
that $x_{j}+j\leq n-1$. Therefore, for each $1\leq
j\leq\mathrm{ind}_{x}(n)-1$, if $x_{j}+j\neq n-1$, then $x_{j}\leq n-2-j$.
Thus, $n-2-j+\mathrm{ind}_{x}(n-2-j)\neq n-1$ and by Lemma 3.9,
$|\mathrm{Ac}_{3}(x;123)|\neq j$. Thus,
$|\mathrm{Ac}_{3}(x;123)|\geq|\mathrm{Ac}_{1}(x;123)|=|\mathrm{Ac}_{2}(x;123)|$.
∎

Now, propositions 3.10 and 3.11 characterize
$\mathrm{Av}_{n}(123,132^{\star})$.

######  Theorem 3.12.

For $x\in\mathrm{Av}_{n}(123)$, there exists some $1\leq i\leq n-2$ such that
$\mathfrak{S}_{n}(x;123)_{i}=\mathfrak{S}_{n}(x;123)_{i+1}\leq\mathfrak{S}_{n}(x;123)_{i+2}$
if and only if $x\not\in\mathrm{Av}_{n}(132^{\star})$.

Let us now turn our attention to $\mathrm{Av}_{n}(132,123^{\star})$. We shall
replicate the approach used for $\mathrm{Av}_{n}(123,132^{\star})$ to obtain
an analogous characterization of permutations in $\mathrm{Av}_{n}(132)$ that
contain $123^{\star}$.

######  Lemma 3.13.

If $x\in\mathrm{Av}_{n}(132,123^{\star})$, then
$\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(132,123^{\star})$.

###### Proof.

It is clear that $\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(132)$. It thus
suffices to show that
$\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123^{\star})$. Suppose otherwise.
Because $x\in\mathrm{Av}_{n}(123^{\star})$, the $123^{\star}$ pattern in
$\mathrm{small}_{n-1}(x)$ must be
$\mathrm{small}_{n-1}(x)_{j}\mathrm{small}_{n-1}(x)_{\mathrm{ind}_{x}(n)-1}\mathrm{small}_{n-1}(x)_{\mathrm{ind}_{x}(n)}$
for some $j<\mathrm{ind}_{x}(n)-1$. However, then $x_{j}\cdot
n\cdot\mathrm{small}_{n-1}(x)_{\mathrm{ind}_{x}(n)}$ is a $132$ pattern in
$x$—a contradiction to $x\in\mathrm{Av}_{n}(123,132^{\star})$. ∎

Given $x\in\mathrm{Av}_{n}(132)$, we express $\mathrm{Ac}_{1}(x;132)$ in terms
of $\mathrm{Ac}_{2}(x;132)$.

######  Lemma 3.14.

If $x\in\mathrm{Av}_{n}(132)$, then

$\mathrm{Ac}_{1}(x;132)=\\{i\mid
i-1\in\mathrm{Ac}_{2}(x;132)\cap[\mathrm{ind}_{x}(n),n]\\}\cup\\{1\\}.$

###### Proof.

It is clear that $i\in\mathrm{Ac}_{1}(x;132)$ if and only if
$\\{x_{[1,i-1]}\\}=[n-i+2,n]$. Thus, if $i\leq\mathrm{ind}_{x}(n)$, then
$i\in\mathrm{Ac}_{1}(x;132)$ if and only if $i=1$. But, if
$\mathrm{ind}_{x}(n)+1\leq i$, then $\\{x_{[1,i-1]}\\}=[n-i+2,n]$ if and only
if $\\{\mathrm{small}(x)_{[1,i-2]}\\}=[n-i+2,n-1]$ if and only if
$i-1\in\mathrm{Ac}_{2}(x;132)$. ∎

The following results are the analogs of Proposition 3.10 and Proposition 3.15
for the $132$ pattern.

######  Proposition 3.15.

If $x\in\mathrm{Av}_{n}(132)$ and
$|\mathrm{Ac}_{i}(x;132)|=|\mathrm{Ac}_{i+1}(x;132)|\leq|\mathrm{Ac}_{i+2}(x;132)|$
for some $1\leq i\leq n-2$, then $x\not\in\mathrm{Av}_{n}(123^{\star}).$

###### Proof.

We induct on $n$; it is easy to see that the statement holds for $n\leq 3$.
Now, because
$\mathfrak{S}_{n}(x;132)=|\mathrm{Ac}_{1}(x;132)|\cdot\mathfrak{S}_{n}(\mathrm{small}_{n-1}(x;132))$,
if $n\geq 4$ and $2\leq i\leq n-2$, then by Lemma 3.13 and the inductive
hypothesis, $x\not\in\mathrm{Av}_{n}(123^{\star})$. Thus, assume $i=1$.

Now, if $x_{1}=n,$ then by Lemma 3.14,
$|\mathrm{Ac}_{1}(x;132)|=|\mathrm{Ac}_{2}(x;132)|+1$. Similarly, if
$x_{1}=n-1,$ then $|\mathrm{Ac}_{2}(x;132)|=|\mathrm{Ac}_{3}(x;132)|+1$ by
Lemma 3.14 on $\mathrm{small}_{n-1}(x)$. Thus, $x_{1}\leq n-2.$ Now, $n$
appears to the right of $n-1$ in $x$, because $x\in\mathrm{Av}_{n}(132)$ and
$x_{1}\leq n-2$. Furthermore, $x\in\mathrm{Av}_{n}(132)$ implies that
$\\{x_{[1,\mathrm{ind}_{x}(n-1)]}\\}=[n-\mathrm{ind}_{x}(n-1),n-1]$ and
$\\{x_{[1,\mathrm{ind}_{x}(n)]}\\}=[n-\mathrm{ind}_{x}(n),n]$. Thus, if
$(n-1)\cdot n$ is not a substring of $x,$ then
$\\{\mathrm{ind}_{x}(n-1)+1,\mathrm{ind}_{x}(n)\\}\in\mathrm{Ac}_{2}(x;132)$,
from which it follows that
$\mathrm{Ac}_{1}(x;132)\leq\mathrm{Ac}_{2}(x;132)-1$ by Lemma 3.14. Thus,
$x\notin\mathrm{Av}_{n}(123^{\star}),$ because $x_{1}\cdot(n-1)\cdot n$ is a
$123^{\star}$ pattern of $x.$ ∎

######  Proposition 3.16.

If $x\in\mathrm{Av}_{n}(132)\setminus\mathrm{Av}_{n}(123^{\star})$, then for
some $1\leq i\leq n-2$, it holds that
$|\mathrm{Ac}_{i}(x;132)|=\mathfrak{|}\mathrm{Ac}_{i+1}(x;132)|\leq|\mathrm{Ac}_{i+2}(x;132)|$.

###### Proof.

We induct on $n$; the statement holds for $n\leq 3,$ because
$\mathfrak{S}_{n}(123;132)=222.$ Now, suppose that $n\geq 4$ and suppose for
the sake of contradiction that there is no $i$ such that
$|\mathrm{Ac}_{i}(x;132)|=\mathfrak{|}\mathrm{Ac}_{i+1}(x;132)|\leq|\mathrm{Ac}_{i+2}(x;132)|.$
Then, since
$\mathfrak{S}_{n}(x;132)=|\mathrm{Ac}_{1}(x;132)|\cdot\mathfrak{S}_{n}(\mathrm{small}_{n-1}(x);132),$
we have that $\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123^{\star})$ from
the inductive hypothesis. Now,
$x\in\mathrm{Av}_{n}(132)\setminus\mathrm{Av}_{n}(123^{\star})$ but
$\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n}(123^{\star})$, and so
$\mathrm{ind}_{x}(n-1)=\mathrm{ind}_{x}(n)-1>1$.

Now, because $\mathrm{ind}_{x}(n-1)=\mathrm{ind}_{x}(n)-1$, it holds that
$\mathrm{Ac}_{2}(x;132)\setminus[\mathrm{ind}_{x}(n),n]=\\{1\\}$. Therefore,
$|\mathrm{Ac}_{1}(x;132)|=|\\{i\mid
i-1\in\mathrm{Ac}_{2}(x;132)\cap[\mathrm{ind}_{x}(n),n]\\}|+1=|\mathrm{Ac}_{2}(x;132)|$
by Lemma 3.14. Furthermore, because $\mathrm{ind}_{x}(n-1)>1$, it follows from
Lemma 3.14 that $|\mathrm{Ac}_{2}(x;132)|=|\\{i\mid
i-1\in\mathrm{Ac}_{3}(x;132)\cap[\mathrm{ind}_{x}(n-1),n-1]\\}\cup\\{1\\}|\leq|\mathrm{Ac}_{3}(x;132)|$.
Now,
$|\mathrm{Ac}_{1}(x;123)|=|\mathrm{Ac}_{2}(x;123)|\leq|\mathrm{Ac}_{3}(x;123)|$—a
contradiction as sought. ∎

Once again, we obtain a characterization of
$\mathrm{Av}_{n}(132,123^{\star})$.

######  Theorem 3.17.

For $x\in\mathrm{Av}_{n}(132)$, there exists some $1\leq i\leq n-2$ such that
$\mathfrak{S}_{n}(x;132)_{i}=\mathfrak{S}_{n}(x;132)_{i+1}\leq\mathfrak{S}_{n}(x;132)_{i+2}$
if and only if $x\not\in\mathrm{Av}_{n}(123^{\star})$.

As an immediate corollary of Theorem 3.12 and Theorem 3.17, West’s bijection
maps $\mathrm{Av}_{n}(123,132^{\star})$ to $\mathrm{Av}_{n}(132,123^{\star})$.
We state this in the following theorem.

######  Theorem 3.18.

West’s bijection [15] bijects $\mathrm{Av}_{n}(123,132^{\star})$ and
$\mathrm{Av}_{n}(132,123^{\star})$. Therefore,

$|\mathrm{Av}_{n}(123,132^{\star})|=|\mathrm{Av}_{n}(132,123^{\star})|.$

We are now able to give a generating function for the sequence
$|\mathrm{Av}_{n}(132,123^{\star})|$. Let

$f_{n}=|\\{x\in\mathrm{Av}_{n}(132)\mid\mathrm{ind}_{x}(n)-1=\mathrm{ind}_{x}(n-1)>1,\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123^{\star})\\}|,$

and let $g_{n}=|\mathrm{Av}_{n}(132,123^{\star})|$.

######  Lemma 3.19.

For all $n\geq 2$, it holds that $f_{n}=g_{n-1}-g_{n-2}$.

###### Proof.

It is straightforward from the definitions of $f_{n}$ and $g_{n}$ that

$\displaystyle f_{n}$
$\displaystyle=|\\{x\in\mathrm{Av}_{n}(132)\mid\mathrm{ind}_{x}(n)-1=\mathrm{ind}_{x}(n-1),\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123^{\star})\\}|$
$\displaystyle\hskip 56.9055pt-|\\{x\in\mathrm{Av}_{n}(132)\mid
x_{1}=n-1,x_{2}=n,\mathrm{small}_{n-2}(x)\in\mathrm{Av}_{n-2}(123^{\star})\\}|$
$\displaystyle=|\\{x\in\mathrm{Av}_{n-1}(132)\mid
x\in\mathrm{Av}_{n-1}(123^{\star})\\}|-|\\{x\in\mathrm{Av}_{n-2}(132)\mid
x\in\mathrm{Av}_{n-2}(123^{\star})\\}|$
$\displaystyle=|\mathrm{Av}_{n-1}(132,123^{\star})|-|\mathrm{Av}_{n-2}(132,123^{\star})|=g_{n-1}-g_{n-2}.\qed$

Next, we give another recursive relation between $f_{n}$ and $g_{n}$.

######  Lemma 3.20.

For $n\geq 2$, it holds that $g_{n-1}g_{0}+g_{n-2}g_{1}+\dots
g_{0}g_{n-1}=g_{n}+f_{n}$.

###### Proof.

For each $x\in\mathrm{Av}_{n}(132)$ such that
$\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123^{\star})$, either
$x\in\mathrm{Av}_{n}(123^{\star})$ or
$\mathrm{ind}_{x}(n)-1=\mathrm{ind}_{x}(n-1)>1$. Thus,

$f_{n}+g_{n}=|\\{x\in\mathrm{Av}_{n}(132)\mid\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123^{\star})\\}|.$

At the same time, for each $0\leq i\leq n-1$,

$\displaystyle g_{i}g_{n-1-i}$
$\displaystyle=|\\{x_{[1,i]}+(i+1-n)\in\mathrm{Av}_{i}(132)\mid
x_{[1,i]}+(i+1-n)\in\mathrm{Av}_{i}(123^{\star})\\}|$ $\displaystyle\hskip
99.58464pt\cdot|\\{x_{[i+2,n]}\in\mathrm{Av}_{n-1-i}(132)\mid
x_{[i+2,n]}\in\mathrm{Av}_{n-1-i}(123^{\star})\\}|$
$\displaystyle=|\\{x\in\mathrm{Av}_{n}(132)\mid\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123^{\star}),x_{i+1}=n\\}|.$

Therefore,
$\sum_{i=0}^{n-1}g_{i}g_{n-1-i}=|\\{x\in\mathrm{Av}_{n}(132)\mid\mathrm{small}_{n-1}(x)\in\mathrm{Av}_{n-1}(123^{\star})\\}|=f_{n}+g_{n}$.
∎

The main result of this section, Theorem 1.1, follows immediately.

###### Proof of Theorem 1.1.

By Theorems 3.7 and 3.18,
$|\mathrm{Sort}_{n}(132,321)|=|\mathrm{Av}_{n}(123,132^{\star})|=|\mathrm{Av}_{n}(132,123^{\star})|$.
Now, let $G(z)=\sum_{n\geq 0}g_{n}z^{n}$. By Lemmas 3.19 and 3.20,

$g_{n}+g_{n-1}-g_{n-2}=\sum_{i=0}^{n-1}g_{i}g_{n-1-i},$

from which

$\displaystyle G(z)-z-1+z(G(z)-1)-z^{2}G(z)$ $\displaystyle=zG(z)^{2}-z$
$\displaystyle\iff\ zG(z)^{2}+(z^{2}-z-1)G(z)+z+1$ $\displaystyle=0.$

Thus,

$\frac{(1+z-z^{2})-\sqrt{1-2z-5z^{2}-2z^{3}+z^{4}}}{2z}$

is the generating function for
$g_{n}=|\mathrm{Av}_{n}(132,123^{\star})|=|\mathrm{Sort}_{n}(132,321)|$. The
statement of the theorem now follows from OEIS A102407 [14]. ∎

###  3.1. A bijection with pattern-avoiding Dyck paths

The OEIS A102407 [14] counts the set of Dyck paths of semilength $n$ that do
not contain the word $dudu$ as a factor. We give an alternative proof of
Theorem 1.1 by showing that $\mathrm{Av}_{n}(123,132^{\star})$ is in bijection
with the set of Dyck paths of semilength $n$ that do not contain the word
$dudu$ as a factor. We sketch the construction below and leave the details to
the reader.

A _Dyck path_ is a path in the discrete plane $\mathbb{Z}\times\mathbb{Z}$
starting at the origin, ending on the $x$-axis, never falling below the
$x$-axis and using two kinds of steps—up steps $u=(1,1)$ and down steps
$d=(1,-1)$. The _semilength_ of a Dyck path is the total number of its up
steps, which is also the number of its down steps.

The _ltr-min decomposition_ of a permutation $x$ with ltr minima
$m_{1},m_{2},\dots,m_{k}$ is

$x=m_{1}B_{1}m_{2}B_{2}\cdots m_{k}B_{k},$

where $B_{j}$ contains the entries between two ltr minima $m_{j}$ and
$m_{j+1}$ for $1\leq j\leq k-1$, and $B_{k}$ contains the entries to the right
of $m_{k}$. The ltr-minima decomposition of $x$ induces a _grid decomposition_
[8] of $x$, in which

$H_{i}=\left\\{y\in\\{1,2,\ldots,n\\}:m_{i}<y<m_{i-1}\right\\}$

is the $i$-th _horizontal strip_ of $x$ (note, $m_{0}=+\infty$), and $B_{j}$
is the $j$-th _vertical strip_ of $x$. For any two indices $i,j$, the _cell_
of indices $i,j$ of $x$ is $C_{i,j}=H_{i}\cap B_{j}$. It is clear that
$C_{i,j}=\emptyset$ if $i>j$. The grid decomposition of
$x=8\,11\,6\,10\,4\,9\,7\,5\,3\,1\,2$ is depicted in Figure 4. We first prove
that each cell of a $123$-avoiding permutation $x$ contains at most one number
if and only if $x$ is also $132^{\star}$-avoiding.

######  Proposition 3.21.

If $x\in\mathrm{Av}_{n}(123)$, then $x\in\mathrm{Av}_{n}(132^{\star})$ if and
only if $|C_{i,j}|\leq 1$ for all $i,j$.

###### Proof.

Suppose that $|C_{i,j}|\geq 2$. We prove that $x$ contains $132^{\star}$.
First, the numbers in $B_{j}$ must all be greater than $m_{j}$ and appear in
decreasing order in $x$, because $x\in\mathrm{Av}_{n}(123)$. Therefore, the
two leftmost entries of $x$ that are in $C_{i,j}$, say $x_{\ell}$ and
$x_{\ell+1}$, must be adjacent in $x$. Similarly, once again since
$x\in\mathrm{Av}(123)$, the numbers in $H_{i}$ must appear in decreasing
order, and thus, $x_{\ell}=x_{\ell+1}+1$. As a result,
$m_{i}x_{\ell}x_{\ell+1}$ is an occurrence of $132^{\star}$ in $x$.

Conversely, if $x_{k}x_{\ell}x_{\ell+1}$ is an occurrence of $132^{\star}$,
then neither $x_{\ell}$ nor $x_{\ell+1}$ can be an ltr minimum of $x$, and
thus, $x_{\ell}$ and $x_{\ell+1}$ are in the same cell. ∎

As a result, the grid decomposition of a $(123,132^{\star})$-avoiding
permutation satisfies the following two properties:

  * •

Each cell $C_{i,j}$ contains at most one point;

  * •

If a cell $C_{i,j}$ is not empty, then all the cells located strictly
northeast of $C_{i,j}$ (i.e. all the cells $C_{u,v}$, with $u<i$ and $v>j$)
are empty.

$C_{3,4}$$B_{1}$$B_{2}$$B_{3}$$B_{4}$$B_{5}$$H_{1}$$H_{2}$$H_{3}$$H_{4}$$H_{5}$$m_{1}$$m_{2}$$m_{3}$$m_{4}$$m_{5}$

11109876543210

Figure 4. On the left, the grid decomposition of
$x=8\,11\,6\,10\,4\,9\,7\,5\,3\,1\,2$. On the right, the corresponding Dyck
path (rotated clockwise).

Rotem [9, 13] bijected $321$-avoiding permutations with Dyck paths. The Rotem
bijection can be reformulated for $123$-avoiding permutations by composing the
original map with the complement as follows. Let $x\in\mathrm{Av}_{n}(123)$.
Then construct a sequence $b=b_{1}b_{2}\dots b_{n}$ by letting $b_{1}=n$, and
for $i\geq 2$,

$b_{i}=\begin{cases}b_{i-1}&\text{if $x_{i}$ is a ltr minimum of $x$;}\\\
x_{i}-1&\text{otherwise}.\end{cases}$

For example, the sequence arising from the permutation of Figure 4

$x=8\cdot 11\cdot 6\cdot 10\cdot 4\cdot 9\cdot 7\cdot 5\cdot 3\cdot 1\cdot
2\quad\text{is}\quad b=11\cdot 10\cdot 10\cdot 9\cdot 9\cdot 8\cdot 6\cdot
4\cdot 4\cdot 4\cdot 1.$

Then represent the sequence $b$ as a bar diagram by drawing a horizontal step
of length one starting at $(i-1,b_{i})$, for $i=1,\dots,n$, and then
connecting the ending point of each step with the starting point of the
following one. The bar diagram of $b$ is illustrated in Figure 4. Finally,
rotate the bar diagram counterclockwise to arrive at a Dyck path. For example,
the Dyck path associated with $b$ in Figure 4 is
$udu^{2}du^{2}dud^{2}ud^{2}u^{3}d^{3}ud$.

Now, let $x\in\mathrm{Av}_{n}(123)$, and let $P$ be the Dyck path associated
with $x$ via the reformulated Rotem bijection. Note that $P$ contains $dudu$
as a factor if and only if, in the grid decomposition of $x$, the points
corresponding to the up steps in the occurrence of $dudu$ lie in the same
cell; instead of giving a formal proof of this fact, we refer the reader to
Figure 5. By Proposition 3.21, this is in turn equivalent an occurrence of
$132^{\star}$ in $x$. In other words, Rotem bijection maps
$(123,132^{\star})$-avoiding permutations to Dyck paths that do not contain
$dudu$ as a factor; the desired bijection between $\mathrm{Sort}_{n}(132,321)$
and Dyck paths avoiding $dudu$ now follows immediately from Theorem 3.7.

$\pi_{\ell}$$\pi_{\ell+1}$$\iff$$\begin{cases}\pi_{\ell}=\pi_{\ell+1}+1;\\\
\pi_{\ell}\text{ is not a ltr
minimum}.\end{cases}$$\iff$$m_{i}$$\pi_{\ell}$$\pi_{\ell+1}$ Figure 5. An
occurrence of $dudu$ in (the bar diagram of) a Dyck path corresponds to an
occurrence of $132^{\star}$ in the associated permutation.

##  4\. The $(123,321)$-machine

In this section, we enumerate the set $\mathrm{Sort}_{n}(123,321)$ of
permutations sorted by the $(123,321)$-machine. A direct computation shows
that the sequence $|\mathrm{Sort}_{n}(123,321)|$, $n\geq 1$, starts with
$1,2,4,7$. Our goal is to prove that, for $n\geq 5$, this sequence obeys the
simple recursion

$|\mathrm{Sort}_{n}(123,321)|=2|\mathrm{Sort}_{n-1}(123,321)|.$

We start by proving that $(123,321)$-sortable permutations avoid $123$.

######  Proposition 4.1.

If $x\in\mathrm{Sort}_{n}(123,321),$ then $x\in\mathrm{Av}_{n}(123)$.

###### Proof.

Suppose otherwise. Let $x_{i}x_{j}x_{k}$ be the lexicographically smallest
occurrence of $123$ in $x$. Note that $x_{i}$ is a ltr minimum. Now, if
$x_{i}$ is in the stack when $x_{k}$ enters the stack, $x_{j}x_{k}x_{i}$ is a
$231$ pattern in $\mathrm{s}_{123,321}(x)$, because $x_{k}x_{j}x_{i}$ is a
$321$ pattern. Thus, by Lemma 2.1, $x_{i}$ must leave the stack before $x_{k}$
enters the stack.

Now, because $x_{i}$ is a ltr minimum, the stack below $x_{i}$ must be
decreasing, since the stack is $123$-avoiding. But the stack must also be
$321$-avoiding, so there can be at most two numbers below $x_{i}$ in the
stack. Therefore, for $x_{i}$ to leave the stack before $x_{k}$ enters the
stack, either $\min\\{x_{[i+1,k]}\\}<x_{i}$, or the stack below $x_{i}$ reads
$x_{b}x_{c}$ and $\max\\{x_{[i+1,k]}\\}>x_{b}$. In the first case,
$x_{i}x_{k}\cdot\min\\{x_{[i+1,k]}\\}$ is a $231$ pattern in $s_{123,321}(x)$,
and in the second case, $x_{b}\cdot\max\\{x_{[i+1,k]}\\}\cdot x_{c}$ is a
$231$ pattern in $s_{123,321}(x)$. Hence, by Lemma 2.1,
$x\in\mathrm{Av}_{n}(123).$ ∎

In analogy with what observed after Proposition 3.2, we have

$\mathrm{Sort}_{n}(132,321)=\mathrm{Sort}_{n}(132)\cap\mathrm{Av}(123).$

The following two results show that if $x\in\mathrm{Sort}_{n}(123,321)$, then
$x_{1}\geq n-1$ and $x_{n}\leq 2$.

######  Lemma 4.2.

If $x\in\mathrm{Sort}_{n}(123,321),$ then $x_{1}\in\\{n-1,n\\}$.

###### Proof.

Suppose otherwise. By Proposition 4.1, either $x_{2}=n$ or $x_{2}<x_{1}$. If
$x_{2}=n$, then $s_{123,321}(x)_{[n-1,n]}=n\cdot x_{1}$. Therefore,
$(n-1)\cdot n\cdot x_{1}$ is a $231$ pattern in $s_{123,321}(x)$, and
$x\not\in\mathrm{Sort}_{n}(123,321)$ by Lemma 2.1. Thus, $x_{2}<x_{1}$, and as
a result, the stack must only contain $x_{1}$ when $1$ enters the stack. Then
because $x_{1}$ and $1$ do not exit the stack until the input permutation is
empty, $s_{123,321}(x)_{[n-1,n]}=1\cdot x_{1}$. Furthermore,
$s_{123,321}(x)_{1}=n$, because otherwise, $s_{123,321}(x)_{1}\cdot n\cdot 1$
is a $231$ pattern in $s_{123,321}(x)$, and
$x\not\in\mathrm{Sort}_{n}(123,321)$ by Lemma 2.1. Now, immediately after $n$
leaves the stack, $x_{\mathrm{ind}_{x}(n)-1}$ must leave the stack, because
$n$ cannot be part of a $321$ or $123$ pattern after the next number in the
input permutation enters the stack. By Proposition 4.1,
$x_{\mathrm{ind}_{x}(n)-1}\neq n-1$. Thus,
$x_{\mathrm{ind}_{x}(n)-1}\cdot(n-1)\cdot 1$ is a $231$ pattern in
$s_{123,321}(x)$—a contradiction by Lemma 2.1. ∎

######  Lemma 4.3.

If $x\in\mathrm{Sort}_{n}(123,321)$, then $x_{n}\in\\{1,2\\}$.

###### Proof.

Suppose otherwise. By Lemma 4.2, $x_{1}\in\\{n-1,n\\}$, and so either
$x_{2}<x_{1}$, or $x_{[1,2]}=(n-1)\cdot n$. If $x_{2}<x_{1}$, then the stack
must only contain $x_{1}$ when $1$ enters the stack. Otherwise, the stack
reads $n\cdot(n-1)$ when $1$ enters the stack. In either case, $1$ cannot
leave the stack until the input permutation is empty, and so $1$ appears to
the right of both $2$ and $x_{n}$ in $s_{123,321}(x)$. Now, $2$ must leave the
stack before $x_{n}$ enters the stack, because $x_{n}\cdot 2\cdot 1$ is a
$321$ pattern. Thus, $2\cdot x_{n}\cdot 1$ is a $231$ pattern in
$s_{123,321}(x)$—a contradiction by Lemma 2.1. ∎

The positions of $1$ and $2$ play an important role in our characterization of
$(123,321)$-sortable permutations. From now on, assume $n\geq 5$. First we
show that $n$ appears to the left of $1$ and $2$ in any
$x\in\mathrm{Sort}_{n}(123,321)$. A consequence is that $2\cdot 1$ must appear
as a substring in the output $s_{123,321}(x)$ of the $(123,321)$-stack.

######  Lemma 4.4.

If $x\in\mathrm{Sort}_{n}(123,321)$, then
$\mathrm{ind}_{x}(n)<\min(\mathrm{ind}_{x}(1),\mathrm{ind}_{x}(2))$.

###### Proof.

By Lemma 4.2, $x_{1}\geq n-1$. If $x_{1}=n$, then the claim is immediate.
Thus, suppose that $x_{1}=n-1$. By Lemma 4.3, $x_{n}\in\\{1,2\\}$. Now, for
the sake of contradiction, suppose that
$\mathrm{ind}_{x}(n)>\mathrm{ind}_{x}(3-x_{n})$. Then the stack must only
contain $n-1$ when $3-x_{n}$ enters the stack and must read
$(3-x_{n})\cdot(n-1)$ when $n$ enters the stack. Then
$n\cdot(3-x_{n})\cdot(n-1)$ cannot leave the stack until the input permutation
is empty. Thus, $3\cdot n\cdot(3-x_{n})$ is a $231$ pattern in
$s_{123,321}(x)$—a contradiction by Lemma 2.1. ∎

######  Lemma 4.5.

If $x\in\mathrm{Sort}_{n}(123,321)$, then
$\mathrm{ind}_{s_{123,321}(x)}(2)=\mathrm{ind}_{s_{123,321}(x)}(1)-1$.

###### Proof.

By Lemmas 4.2 and 4.3, $x_{1}\in\\{n-1,n\\}$, and $x_{n}\in\\{1,2\\}$.
Therefore, just after $3-x_{n}$ enters the stack, the stack reads
$(3-x_{n})\cdot x_{1}$ or $(3-x_{n})\cdot n\cdot(n-1)$, and $3-x_{n}$ must
remain in the stack until $x_{[1,n-1]}$ has entered the stack. Furthermore,
from Lemma 4.4, $n$ cannot be above $3-x_{n}$ in the stack. Now, if $x_{n}=1$,
then $3-x_{n}=2$ must be the last number that leaves the stack before $1$
enters the stack; after which, $x_{n}=1$ must leave the stack, because the
input permutation is empty. If $x_{n}=2$, then $x_{n}=2$ must be right above
$3-x_{n}=1$ when $x_{n}=2$ enters the stack; after which, $x_{n}=2$ and
$3-x_{n}=1$ must exit the stack in that order, because the input permutation
is empty. ∎

For the rest of this section, given a permutation $x\in S_{n}$ of length two
or more, define $\mathrm{swap}(x)$ as the permutations obtained from $x$ by
interchanging $1$ and $2$. Furthermore, for $1\leq i\leq n+1$, let
$\mathrm{inc}_{i}(x)$ be the permutation obtained by inserting $1$ in the
$i$-th site of $x$, and suitably rescaling the other entries. More formally,
let

$\mathrm{inc}_{i}(x)=x^{\prime}_{1}\dots x^{\prime}_{i-1}1x^{\prime}_{i}\dots
x^{\prime}_{n},$

where $x^{\prime}_{j}=x_{j}+1$. For example, $\mathrm{inc}_{2}(12543)=213654$.
It follows from the proof of Lemma 4.5 that if $n\geq 5$, then $\mathrm{swap}$
preserves $s_{123,321}(x)$ for $x\in\mathrm{Sort}_{n}(123,321)$.

######  Corollary 4.6.

If $x\in\mathrm{Sort}_{n}(123,321)$, then
$s_{123,321}(x)=s_{123,321}(\mathrm{swap}(x))$.

To complete our description of $\mathrm{Sort}_{n}(123,321)$, we shall prove
that a permutation $x$ is $(123,321)$-sortable if and only if
$\mathrm{inc}_{n+1}(x)$ is.

######  Proposition 4.7.

It holds that $x\in\mathrm{Sort}_{n}(123,321)$ if and only if
$\mathrm{inc}_{n+1}(x)\in\mathrm{Sort}_{n+1}(123,321)$.

###### Proof.

First, suppose that $x\in\mathrm{Sort}_{n}(123,321)$. Then by Lemma 2.1,
$s_{123,321}(x)\in\mathrm{Av}_{n}(231)$. Now, by Lemma 4.5,
$s_{123,321}(\mathrm{inc}_{n+1}(x))=\mathrm{inc}_{\mathrm{ind}_{x}(1)+1}(s_{123,321}(x))$.
Thus, $s_{123,321}(\mathrm{inc}_{n+1}(x))\in\mathrm{Av}_{n+1}(231)$, and so
$s_{123,321}(\mathrm{inc}_{n+1}(x))\in\mathrm{Sort}_{n+1}(123,321)$ by Lemma
2.1.

Now, suppose that $x\not\in\mathrm{Sort}_{n}(123,321)$. Then by Lemma 2.1,
$s_{123,321}(x)\not\in\mathrm{Av}_{n}(231)$. Now,
$s_{123,321}(\mathrm{inc}_{n+1}(x))\not\in\mathrm{Av}_{n}(231)$, for
$s_{123,321}(x)+1$ is a substring of $s_{123,321}(\mathrm{inc}_{n+1}(x))$.
Thus, $s_{123,321}(\mathrm{inc}_{n+1}(x))\not\in\mathrm{Sort}_{n+1}(123,321)$
by Lemma 2.1. ∎

Finally, we use Lemmas 4.3, 4.6, and 4.7 to prove Theorem 1.2.

###### Proof of Theorem 1.2.

It is easy to check that the theorem statement holds for $n=4$. Now, by
Corollary 4.6, $x\rightarrow\mathrm{swap}(x)$ bijects
$\mathrm{Sort}_{n}(123,321)$ to itself for $n\geq 5$. Thus,
$|\mathrm{Sort}_{n}(123,321)|=2|\\{x\in\mathrm{Sort}_{n}(123,321)\mid
x_{n}=1\\}|$ by Lemma 4.3 for $n\geq 5$. Also, by Proposition 4.7,
$x\rightarrow\mathrm{inc}_{n+1}(x)$ bijects $\mathrm{Sort}_{n}(123,321)$ to
$\\{x\in\mathrm{Sort}_{n+1}(123,321)\mid x_{n}=1\\}$ for $n\geq 5$. Thus,
$|\mathrm{Sort}_{n}(123,321)|=2|\mathrm{Sort}_{n-1}(123,321)|$ for $n\geq 5$
as sought. ∎

##  5\. Future Directions

In addition to the statement of Theorem 1.1, Baril, Cerbai, Khalil, and
Vajnovski [1] conjectured that
$|\mathrm{Sort}_{n}(132,213)|=|\mathrm{Sort}_{n}(213,312)|$ for all $n\geq 1$;
the conjecture remains open. Here, we refine their conjecture.

######  Conjecture 5.1.

For any $n$ and $1\leq i\leq n$, we have the equidistributions

$\displaystyle|\\{x\in\mathrm{Sort}_{n}(132,213)\mid x_{1}=i\\}|$
$\displaystyle=|\\{x\in\mathrm{Sort}_{n}(213,312)\mid x_{1}=i\\}|$ and
$\displaystyle|\\{x\in\mathrm{Sort}_{n}(132,213)\mid x_{i}=n\\}|$
$\displaystyle=|\\{x\in\mathrm{Sort}_{n}(213,312)\mid x_{i}=n\\}|.$

## References

  * [1] J. L. Baril, G. Cerbai, C. Khalil and V. Vajnovszki  “Catalan and Schröder permutations sortable by two restricted stacks”  In _Inform. Process. Lett._ 171, 2021, pp. 106138
  * [2] K. Berlow  “Restricted stacks as functions”  In _Discrete Math._ 344, 2021, pp. 112571
  * [3] D. Bevan  “Permutation patterns: basic definitions and notations”  In _arXiv e-prints, arXiv:1506.06673_ , 2015
  * [4] M. Bousquet-Mélou, A. Claesson, M. Dukes and S. Kitaev  “(2+2)-free posets, ascent sequences and pattern avoiding permutations”  In _Journal of Combinatorial Theory, Series A_ 117, 2010, pp. 884–909
  * [5] P. Brändén and A. Claesson  “Mesh Patterns and the expansion of permutation statistics as sums of permutation patterns”  In _The Electronic Journal of Combinatorics_ 18, 2011, pp. 14
  * [6] G. Cerbai  “Sorting Cayley permutations with pattern-avoiding machines”  In _Australas. J. Combin._ 80, 2021, pp. 322341
  * [7] G. Cerbai, A. Claesson and L. Ferrari  “Stack sorting with restricted stacks”  In _J. of Combin. Theory. Series A_ 173, 2020, pp. 105230
  * [8] G. Cerbai, A. Claesson, L. Ferrari and E. Steingrímsson  “Sorting with pattern-avoiding stacks: the 132-machine”  In _Electron. J. Combin._ 27, 2020, pp. P3.32
  * [9] Anders Claesson and Sergey Kitaev  “Classification of bijections between 321- and 132-avoiding permutations”  In _Sém. Lothar. Combin._ 60, 2008, pp. Art. B60d, 30
  * [10] C. Defant  “3-Stack-Sortable permutations and beyond”  In _S´em. Lothar. Combin._ 85, 2021
  * [11] C. Defant and K. Zheng  “Stack-sorting with consecutive-pattern-avoiding stacks”  In _Adv. in Appl. Math._ 128, 2021, pp. 102192
  * [12] D. E. Knuth  “The Art of Computer Programming”  Pearson Education, 1997
  * [13] D. Rotem  “On a correspondence between binary trees and a certain type of permutations”  In _Information processing letters_ 4, 1975, pp. 58–61
  * [14] N. J. A. Sloane and The OEIS Foundation Inc.  “The On-line Encyclopedia of Integer Sequences”, 2020  URL: http://oeis.org/?language=english
  * [15] J. West  “Generating trees and the Catalan and Schröder numbers”  In _Discrete Math._ 146.1, 1995, pp. 247–262
  * [16] J. West  “Permutations with restricted subsequences and stack-sortable permutations”  In _MIT Ph.D. Thesis_ , 1990
  * [17] D. Zeilberger  “A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length $n$ is $\frac{2}{(n+1)(2n+1)}\binom{3n}{n}$”  In _Discrete Math._ 102, 1992, pp. 8592