% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \usepackage{amscd} \usepackage{hyperref} \usepackage{enumerate} \usepackage{graphicx,tikz} \usetikzlibrary{arrows, automata,chains,fit,shapes} \newcommand\bc{\begin{center}} \newcommand\ec{\end{center}} \newcommand\Z{\mathbb Z} \newcommand\N{\mathbb N} \newcommand\ra{\rightarrow} \newcommand\e{\varepsilon} \newcommand\noi{\noindent} \newcommand\lan{\mathcal{L}} \newcommand\perms{\mathcal P} \newcommand\diffrl{D_{\rho,\lambda}} \newcommand\difflu{D_{\lambda,\mu}} % references \newcommand{\HU}{MR645539} \newcommand{\Estacks}{MR2240774} \newcommand{\Knuth}{MR0445948} \newcommand{\Bona}{MR1485138} \newcommand{\Gessel}{MR1041448} \newcommand{\SimSch}{MR829358} \newcommand{\noonanZ}{MR1422065} \newcommand{\AALRa}{MR2176523} \newcommand{\AALRb}{MR1453845} \newcommand{\AALRc}{MR2000167} \newcommand{\aerwz}{MR2199982} \newcommand{\twopatterns}{MR2577304} \newcommand{\Rusetal}{MR1932896} \newcommand{\Flajolet}{MR2483235} \newcommand{\albertmir}{DBLP:journals/ejc/AlbertB15} \newcommand{\ElderCS}{ElderCS} \newcommand{\wikipatterns}{wikipatterns} \newcommand{\tony}{MR3300327} \newcommand{\PR}{MR3181450} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf Permutations generated by a depth $2$ and infinite stack in series are algebraic} \author{Murray Elder \qquad Geoffrey Lee\\ \small School of Mathematical and Physical Sciences\\[-0.8ex] \small The University of Newcastle\\[-0.8ex] \small Callaghan, New South Wales, 2308, Australia\\ \small\tt murray.elder@newcastle.edu.au \qquad geoffrey.a.lee@uon.edu.au\\ \and Andrew Rechnitzer\\ \small Department of Mathematics\\[-0.8ex] \small University of British Columbia\\[-0.8ex] \small Vancouver, British Columbia, V6T-1Z2, Canada\\ \small\tt andrewr@math.ubc.ca } \date{\dateline{Aug 1, 2014}{Apr 15, 2015}\\ \small Mathematics Subject Classifications: 05A05} \begin{document} \maketitle \begin{abstract} We prove that the class of permutations generated by passing an ordered sequence $12\dots n$ through a stack of depth 2 and an infinite stack in series is in bijection with an unambiguous context-free language, where a permutation of length $n$ is encoded by a string of length $3n$. It follows that the sequence counting the number of permutations of each length has an algebraic generating function. We use the explicit context-free grammar to compute the generating function: \begin{align*} \sum_{n\geq 0} c_n t^n &= \frac{(1+q)\left(1+5q-q^2-q^3-(1-q)\sqrt{(1-q^2)(1-4q-q^2)}\right)}{8q} \end{align*} where $c_n$ is the number of permutations of length $n$ that can be generated, and $q \equiv q(t) = \frac{1-2t-\sqrt{1-4t}}{2t}$ is a simple variant of the Catalan generating function. This in turn implies that $c_n^{1/n} \to 2+2\sqrt{5}$. \bigskip\noindent \textbf{Keywords:} Pattern avoiding permutation; Algebraic generating function; Context-free language\end{abstract} \section{Introduction} Let $p=p_1p_2\dots p_n$ and $q=q_1q_2\dots q_k$ be permutations of length $n\geq k$. We say $p$ {\em avoids} $q$ if there are no $k$ indices $i_1<\dots] (4,2.4) -- node[above] {$\rho$} (2.66,2.4) -- (2.66,1.7); \draw (5,2.5) node {$123\dots n$}; \draw[dotted, bend left, ->] (2.33,1.7) -- (2.33,2.4) -- node[above] {$\lambda$} (0.66,2.4) -- (0.66,1.7); \draw[dotted, <-] (-1.2,2.4) -- node[above] {$\mu$} (0.33,2.4) -- (0.33,1.7); \end{tikzpicture}\ec \caption{\label{fig:rholambdamu}Token passing moves $\rho,\lambda$ and $\mu$ for two stacks in series.} \end{figure} \begin{definition}[$D_{a,b}(u)$] If $u$ is a word over an alphabet that includes the letters $a$ and $b$, define $D_{a,b}(u)$ to be the number of $a$ letters minus the number of $b$ letters contained in $u$. \end{definition} \begin{definition}[$\lan_{k,\infty}$]\label{defn:Lk-infty} Let $k\in\mathbb N$. The language $\lan_{k,\infty}$ is the set of words $w\in\{\rho,\lambda,\mu\}^*$ satisfying \begin{enumerate} \item $ \diffrl(u)\in [0,k]$ and $\difflu(u)\in [0,\infty)$ for all prefixes, $u$, of $w$, \item $\diffrl(w)=\difflu(w)=0$. \end{enumerate} \end{definition} \begin{lemma}\label{lem:L2inf} A word $w\in \{\rho,\lambda,\mu\}^*$ encodes a permutation in $\perms$ if and only if $w\in \lan_{2,\infty}$. Moreover, a word of length $3n$ in $\lan_{2,\infty}$ encodes a permutation of length $n$. \end{lemma} \begin{proof} The first claim is clear from the definition. If $w\in \lan_{2,\infty}$ has $n$ $\rho$ letters, then $\diffrl(w)=0$ implies $w$ has $n$ $\lambda$ letters, and $\difflu(w)=0$ then implies $w$ has $n$ $\mu$ letters, so the length of $w$ is $3n$, and the number of tokens moves through the stacks is $n$. \end{proof} The language $ \lan_{2,\infty}$ consists of all possible ways to pass tokens through the system of stacks as in Figure~\ref{fig:rholambdamu}. We wish to find a sublanguage that is in bijection with $\perms$. From the set of all words in $ \lan_{2,\infty}$ that generate the same permutation, we will try to choose the string that outputs tokens as soon as possible, that is, has more $\mu$ letters closer to the front. The next definition will help to formalise this. \begin{definition}[$\mu$-ordering] Define an ordering, $\prec_\mu$, on words in $ \{\rho,\lambda,\mu\}^*$ as follows. Let $\theta: \{\rho,\lambda,\mu\}^*\ra \{\nu,\mu\}^*$ be a monoid homomorphism defined by $\theta(\mu)=\mu$ and $\theta(\rho)=\theta(\lambda)=\nu$. If $u\neq v$ as strings then $u\prec_\mu v$ if $|u|=|v|$ and $\theta(u)$ precedes $\theta(v)$ in lexographic ordering on $\{\mu,\nu\}^*$ where $\mu<\nu$. \end{definition} For example, if $u=\rho\lambda\mu\rho\lambda\mu$ and $v=\rho\lambda\rho\mu\lambda\mu$ then $u \prec_\mu v$. Note that both words generate the permutation $12$, and $u$ is obtained from $v$ by replacing the subword $\rho\mu$ by $\mu\rho$, which has no affect on the permutation being produced. More generally we have the following. \begin{lemma}\label{lem:badsubwords} Let $w\in \lan_{2,\infty}$. \begin{enumerate}\item If $w=w_0\rho\mu w_1$ then $w'=w_0\mu\rho w_1$ generates the same permutation as $w$, and $w'\prec_\mu w$. \item If $w=w_0\rho\lambda w_1\lambda \mu w_2$ with $\diffrl(w_0)=1$ and $w_1\in\lan_{1,\infty}$, then $w'=w_0\lambda\rho w_1\mu\lambda w_2$ generates the same permutation as $w$, and $w'\prec_\mu w$. \item If $w= w_0\lambda\rho w_1\lambda \mu w_2$ with $\diffrl(w_0)=1$ and $w_1\in\lan_{1,\infty}$, then $w'=w_0\rho\lambda w_1\mu\lambda w_2$ generates the same permutation as $w$, and $w'\prec_\mu w$. \end{enumerate} \end{lemma} \begin{proof} In each case it is clear that $w'\prec_\mu w$. We must show that in each case the two strings generate the same permutation. For case (1) this is clear since $\rho$ and $\mu$ do not interact. For case (2), since $\diffrl( w_0)=1$, there must be one token (say $a$) left in the first stack after reading $w_0$, and since the next letter to be read is $\rho$, there must be one token (say $b$) ready to enter the first stack. See Figure~\ref{fig:replace}. \begin{figure} \bc \begin{tikzpicture} \draw (-4,1) node {After $w_0$:}; \draw[very thick] (0,2) -- (0,-1) -- (1,-1) -- (1,2); \draw (2.5,-1.5) node {$A$}; \draw[very thick] (2,2) -- (2,1) -- (3,1) -- (3,2); \draw (0.5,-1.5) node {$B$}; \draw (2.5,1.35) node {$a$}; \draw (4.8,2.5) node {$b$ - - - -}; \draw (-1.6,2.5) node {- - - - }; \draw (0.5,-0.75) -- (0.5,-0.5); \draw (0.5,-0.25) -- (0.5,0); \end{tikzpicture} \\ \vspace{1cm} \begin{tikzpicture} \draw (-4,1) node {After $w_0\rho\lambda$:}; \draw[very thick] (0,2) -- (0,-1) -- (1,-1) -- (1,2); \draw (2.5,-1.5) node {$A$}; \draw[very thick] (2,2) -- (2,1) -- (3,1) -- (3,2); \draw (0.5,-1.5) node {$B$}; \draw (2.5,1.35) node {$a$}; \draw (4.8,2.5) node {- - - -}; \draw (-1.6,2.5) node { - - - -}; \draw (0.5,0.5) node {$b$}; \draw (0.5,-0.75) -- (0.5,-0.5); \draw (0.5,-0.25) -- (0.5,0); \end{tikzpicture}\\ \vspace{1cm} \begin{tikzpicture} \draw (-4,1) node {After $w_0\rho\lambda w_1\lambda\mu$:}; \draw[very thick] (0,2) -- (0,-1) -- (1,-1) -- (1,2); \draw (2.5,-1.5) node {$A$}; \draw[very thick] (2,2) -- (2,1) -- (3,1) -- (3,2); \draw (0.5,-1.5) node {$B$}; \draw (4.8,2.5) node {- - - -}; \draw (-1.6,2.5) node { - - - - $a$}; \draw (0.5,0.5) node {$b$}; \draw (0.5,-0.75) -- (0.5,-0.5); \draw (0.5,-0.25) -- (0.5,0); \end{tikzpicture} \ec \caption{\label{fig:replace}Stack configurations in the proof of Lemma~\ref{lem:badsubwords}.} \end{figure} After reading $\rho\lambda$, $b$ moves to the top of stack $B$ and $a$ stays in stack $A$. Reading $w_1$ leaves $a$ and $b$ in place and outputs some permutation of input tokens. Finally $\lambda\mu$ outputs $a$, leaving $b$ on the top of stack $B$ and stack $A$ empty. Starting from the initial configuration in Figure~\ref{fig:replace}, the prefix $w_0\lambda\rho w_1\mu\lambda$ of $w'$ moves $a$ to the top of stack $B$ and places $b$ in stack $A$. The permutation generated by $w_1$ is then passed across as before, then $a$ is output, and finally $b$ is moved to stack $B$, leaving the stacks in the same configuration as the prefix $w_0\rho\lambda w_1\lambda \mu$ of $w$. A similar argument applies for Case (3) and is left to the reader. \end{proof} \begin{definition}[$\lan$]\label{DefL} The language $\lan$ is the set of words $w\in \lan_{2,\infty}$ that do not \begin{enumerate} \item contain a subword $\rho\mu$, \item have a prefix $w_0\rho\lambda w_1\lambda \mu$ with $w_1\in\lan_{1,\infty}$ and $\diffrl(w_0)=1$, \item have a prefix $w_0\lambda\rho w_1\lambda \mu$ with $w_1\in\lan_{1,\infty}$ and $\diffrl(w_0)=1$. \end{enumerate} \end{definition} \begin{lemma}\label{lem:replaceKnuth} Let $w\in \lan_{2,\infty}$. If either \begin{enumerate}\item $w=w_0 \rho\lambda w_1\lambda w_2 \mu w_3$ with $\diffrl(w_0)=1, w_1\in\lan_{1,\infty}$, and $w_2\in\lan_{2,\infty} $ generates a permutation that avoids $312$, or \item $w=w_0\lambda \rho w_1\lambda w_2 \mu w_3$ with $\diffrl(w_0)=1, w_1\in\lan_{1,\infty}$, and $w_2\in\lan_{2,\infty} $ generates a permutation that avoids $312$, \end{enumerate} then $w\not\in\lan$. \end{lemma} \begin{proof} Suppose for contradiction that $w\in\lan$, $w=w_0 v w_1\lambda w_2 \mu w_3$ with $v\in\{\rho\lambda, \lambda\rho\}$, $\diffrl(w_0)=1, w_1\in\lan_{1,\infty}, w_2$ generates a permutation that avoids $312$, and moreover that $w_0$ is the longest prefix of $w$ with this property. That is, if $w=u_0v u_1\lambda u_2 \mu u_3$ with $v\in\{\rho\lambda, \lambda\rho\}, \diffrl(u_0)=1, u_1\in\lan_{1,\infty}$ and $u_2$ generates a permutation that avoids $312$, then $|u_0|\leq |w_0|$. Since $\diffrl(w_0vw_1)=1$ and $\lambda$ moves a token from stack $A$ to stack $B$, after reading $w_0vw_1\lambda$ we have no tokens in stack $A$, and some token, say $a$, in stack $B$. See Figure~\ref{fig:replaceKnuth}. \begin{figure} \bc \begin{tikzpicture} \draw (-4,1) node {After $w_0vw_1\lambda$:}; \draw[very thick] (0,2) -- (0,-1) -- (1,-1) -- (1,2); \draw (2.5,-1.5) node {$A$}; \draw[very thick] (2,2) -- (2,1) -- (3,1) -- (3,2); \draw (0.5,-1.5) node {$B$}; \draw (0.5,0.5) node {$a$}; \draw (4.8,2.5) node {$b$ - - - -}; \draw (-1.6,2.5) node {- - - - }; \draw (0.5,-0.75) -- (0.5,-0.5); \draw (0.5,-0.25) -- (0.5,0); \end{tikzpicture} \\ \vspace{1cm} \begin{tikzpicture} \draw (-4,1) node {After $w_0vw_1\lambda \rho_b$:}; \draw[very thick] (0,2) -- (0,-1) -- (1,-1) -- (1,2); \draw (2.5,-1.5) node {$A$}; \draw[very thick] (2,2) -- (2,1) -- (3,1) -- (3,2); \draw (0.5,-1.5) node {$B$}; \draw (0.5,0.5) node {$a$}; \draw (2.5,1.35) node {$b$}; \draw (4.8,2.5) node {- - - -}; \draw (-1.6,2.5) node {- - - - }; \draw (0.5,-0.75) -- (0.5,-0.5); \draw (0.5,-0.25) -- (0.5,0); \end{tikzpicture} \\ \vspace{1cm} \begin{tikzpicture} \draw (-4,1) node {\begin{tabular}{l} After $w_0vw_1\lambda \rho_b s\lambda_b$\\ if $\difflu(s)>0$:\end{tabular}}; \draw[very thick] (0,2) -- (0,-1) -- (1,-1) -- (1,2); \draw (2.5,-1.5) node {$A$}; \draw[very thick] (2,2) -- (2,1) -- (3,1) -- (3,2); \draw (0.5,-1.5) node {$B$}; \draw (0.5,0.5) node {$a$}; \draw (0.5,1.5) node {$c$}; \draw (0.5,2) node {$b$}; \draw (4.8,2.5) node { - - - -}; \draw (-1.6,2.5) node {- - - - }; \draw (0.5,-0.75) -- (0.5,-0.5); \draw (0.5,-0.25) -- (0.5,0); \draw (0.5,0.85) -- (0.5,1.1); \end{tikzpicture} \ec \caption{\label{fig:replaceKnuth}Stack configurations in the proof of Lemma~\ref{lem:replaceKnuth}.} \end{figure} Since $w\in\lan$, $w_2$ cannot be empty, and since $w_2$ is a subword of $w\in\lan$ we have $w_2\in\lan$. So $w_2$ moves some sequence of tokens completely through the stacks, leaving $a$ in place. The first letter of $w_2$ must be $\rho$, which moves some token, say $b$, onto stack $A$. Let $\rho_b,\lambda_b,\mu_b$ be the letters in $w_2$ that correspond to moving $b$ through the stacks. Then $w_2$ has prefix $\rho_b s\lambda_bt\mu_b$ where $s,t$ are subwords. Since stack $A$ contains $b$ while $s$ is read, if $\rho$ occurs in $s$ it must be immediately followed by $\lambda$, so $\diffrl(u)\in[0,1]$ for all prefixes $u$ of $s$, and $\diffrl(s)=0$. Further, if $\difflu(u)<0$ for any prefix $u$ of $s$, then $a$ would be output. Either $\difflu(s)=0$ (and $s\in \lan$) or $\difflu(s)>0$. If $s\in\lan_{1,\infty}$ then $t\in\lan_{2,\infty}$ and generates a permutation avoiding $312$ since it is a subword of $w_2$. In this case $w$ has prefix $w=w_0 v w_1\lambda \rho_b s\lambda_b t \mu_b$ with $\difflu(w_0 v w_1)=1$ and $t$ generating a permutation avoiding $312$, which contradicts the choice of $w_0$ as the longest such prefix. Therefore we must have $\difflu(s)>0$. In this case, after reading $s$ at least one token, say $c$, remains on top of $a$ in stack $B$ when $b$ is moved into it. After reading $\lambda_b$, the stack configuration is as in the third diagram shown in Figure~\ref{fig:replaceKnuth}. Note that $ac$ to the output. This means $w_2$ generates the subpermutation $dbc$ which is order equivalent to $312$, contradicting our assumption. Thus $t=\e$ and $w_2$ has prefix $\rho_b s\lambda_b\mu_b$, with $s\in\{\rho\lambda, \mu\}^*$. Either $s$ ends with $\rho\lambda$, or $s=u\rho\lambda s'$ where $\difflu(u)=\difflu(s)$ since $\difflu$ starts at zero and increases to this value. Thus $s'\in\lan$, and $w=w_0 v w_1\lambda \rho_b u\rho\lambda s' \lambda_b\mu_b$ with $\diffrl(w_0 v w_1\lambda \rho_b u)=1$, which contradicts $w\in\lan$. \end{proof} \begin{theorem}\label{thm:bijection} There is a bijection between permutations in $\perms$ of length $n$ and words in $\lan$ of length $3n$. \end{theorem} \begin{proof} Consider the map that sends a word of length $3n$ in $\lan\subseteq \lan_{2,\infty}$ to the permutation of length $n$ it generates. If $\sigma\in\perms$ then there is some word $w\in \lan_{2,\infty}$ that generates it by Lemma~\ref{lem:L2inf}. If $w\notin\lan$, then $w$ must either contain $\rho\mu$, or have prefix $w_0\rho\lambda w_1\lambda\mu$ or $w_0\lambda\rho w_1\lambda\mu$ with $\diffrl(w_0)=1$ and $w_1\in\lan_{1,\infty}$. We rewrite $w$ as follows. While $w$ contains $\rho\mu$ or has prefix $w_0\rho\lambda w_1\lambda\mu$ or $w_0\lambda\rho w_1\lambda\mu$: \begin{enumerate} \item[1.] Replace $\rho\mu$ with $\mu\rho$ \item[2.] Replace $w_0\rho\lambda w_1\lambda \mu$ with $w_0\lambda\rho w_1\mu \lambda$ \item[3.] Replace $w_0\lambda\rho w_1\lambda \mu$ with $w_0\rho\lambda w_1\mu \lambda$ \end{enumerate} Each iteration replaces the current word by a word which generates the same permutation and is shorter in the $\mu$-ordering by Lemma~\ref{lem:badsubwords}, so the procedure must terminate (there are finitely many words less than $w$ in the $\mu$-ordering). It follows that the map is surjective. We complete the proof by showing it is injective. Suppose we have two words $u,v\in\lan$ that generate the same permutation, and that $u\neq v$ as strings. Write \[u=u_1u_2\dots u_n \ \mathrm{and} \ v=v_1v_2\dots v_n\] where $u_i,v_i\in\{\rho,\lambda,\mu\}$. Since $u,v\in\lan$ we have $u_1=v_1=\rho$. Let $k\in [2,n]$ be such that $u_i=v_i$ for $i0$ then $v$ has prefix $(z\lambda\rho_b (\rho\lambda)^{i-1})\rho\lambda\lambda_b\mu_b$ with $\diffrl(z\lambda\rho_b (\rho\lambda)^{i-1})=1$ which violates the second condition of Definition~\ref{DefL}, so $v\not\in\lan$. Thus $w$ is nonempty, so moves some tokens, say $t_1,\dots, t_s$, from the input to the output. Since $v$ generates the same permutation as $u$, it must also move the tokens $t_1,\dots, t_s$ through the stacks and output them before $b$ is output. The subword $w_1$ cannot leave any tokens covering $b$ in stack $A$, so $w_1\in\{\rho\lambda, \mu\}^*$. If $w_1$ leaves some token $t_i$ in stack $B$, then $\lambda_b$ will cover $t_i$ with $b$ so $t_i$ will appear after $b$ in the permutation generated by $v$, which is different to the permutation generated by $u$.\ Thus after $w_1$ the stacks are the same as before $w_1$, so $w_1\in\lan_{1,\infty}$. Let $t_1,\dots t_r$ with $r\leq s$ be the tokens moved to the output by $w_1$. The situation is shown in Figure~\ref{fig:beforew2}. \begin{figure}[h!] \bc \begin{tikzpicture} \draw[very thick] (0,2) -- (0,-1) -- (1,-1) -- (1,2); \draw (2.5,-1.5) node {$A$}; \draw[very thick] (2,2) -- (2,1) -- (3,1) -- (3,2); \draw (0.5,-1.5) node {$B$}; \draw (4.5,2.5) node {$t_{r+1}\ t_2\ \cdots\ t_s$ - -}; \draw (-1.5,2.5) node {- - - - -}; \draw (0.5,-0.75) -- (0.5,-0.5); \draw (0.5,-0.25) -- (0.5,0); \draw (0.5,0.75) node {$b$}; \draw (0.5,0.3) node{$a$}; \end{tikzpicture} \ec \caption{\label{fig:beforew2}Stack configuration after $z\lambda\rho_b w_1\lambda_b$ in Case 2 in Theorem~\ref{thm:bijection}. } \end{figure} If $w_2$ is empty then $v$ has prefix $z\lambda\rho w_1\lambda_b\mu_b$ with $w_1\in\lan_{1,\infty}$ which is forbidden, so $w_2$ must move some tokens. The subword $w_2$ cannot leave any tokens in stack $B$. Either $w_2$ leaves some tokens in stack $A$, or not. If $w_2$ leaves a token in stack $A$, this token cannot be one of $t_{r+1},\dots, t_s$ or else $v$ would generate a different permutation to $u$. Therefore this token is moved into stack $A$ after $t_r$ by a letter $\rho$. This letter cannot be followed by $\mu$, and since it remains in stack $A$ it is not followed by $\lambda$. So this letter is either the last letter of $w_2$, or is followed by another $\rho$, which must also remain in stack $A$. Thus $w_2$ ends with $\rho$, but this is a contradiction since $w_2$ is followed by $\mu_b$. Thus $w_2$ does not leave any tokens in stacks $A$ or $B$, so moves $t_{r+1},\dots, t_s$ from the input to the output, and $w_2\in\lan_{2,\infty}$. Note that $w_1w_2$ produces the same permutation of $t_1,\dots, t_s$ as $w$ does, and $w\in\lan_{1,\infty}$ so generates a $312$-avoiding permutation of $t_1,\dots,t_s$. The subword $w_1$ permutes the first $r$ tokens, and so $w_2$ must produce a permutation of $t_{r+1},\dots, t_s$ that avoids $312$. In this case $v$ has prefix $z\lambda\rho_b w_1\lambda_b w_2 \mu_b$ where $\diffrl(z\lambda\rho_b)=1$, $w_1\in \lan_{1,\infty}$ and $w_2$ generates a $312$-avoider, so by Lemma~\ref{lem:replaceKnuth} $v$ must also contain a prefix that is not allowed if $v\in \lan$. This is a contradiction, so we cannot have two such words $u$ and $v$. \end{proof} \subsection{A related class of permutations} A natural question to ask is whether switching the order of the stacks makes any difference to the problem. Let $\mathcal Q$ be the set of permutations that can be generated by passing an ordered sequence through an infinite stack followed by a depth 2 stack in series. Each word $w\in\lan_{2,\infty}$ encodes a permutation in $\mathcal Q$ as follows: reading $w$ from right to left, for each $\mu$ move a token from the input to the infinite stack, for each $\lambda$ move a token from the infinite stack to the depth 2 stack, and for each $\rho$ move a token from the depth 2 stack to the output. It follows that $\mathcal P$ and $\mathcal Q$ are in bijection. \section{Constructing a pushdown automaton}\label{sec:pda} In this section we construct a deterministic pushdown automaton accepting on empty stack, which accepts the language \[\lan\$=\{w\$ \mid w\in\lan\}.\] A {\em pushdown automaton accepting on empty stack} $M$ is the following: \begin{enumerate}\item $Q$ a finite set of {\em states}, \item $\Sigma$ a finite {\em input alphabet}, \item $\Gamma$ a finite {\em stack alphabet}, \item $q_0\in Q$ the {\em start state}, \item $0\in\Gamma$ a special stack symbol, \item a map $\delta$ from $Q\times (\Sigma\cup\e)\times \Gamma$ to finite subsets of $Q\times (\Gamma^*)$, called the {\em transition function}, \end{enumerate} which runs as follows. Before reading input, the stack contains a single $0$. Input strings are accepted as soon as the stack becomes empty. A {\em configuration} of $M$ is a pair $(q, \omega)$ where $q$ is the current state and $\omega\in\Gamma^*$ is a string of stack symbols representing the contents of the stack (the first letter of $\omega$ is the top of the stack). The notation $\delta(q_i,a, k)=\{(q_{j_1}, \gamma_1), \dots,(q_{j_s}, \gamma_s)\}$ means that if $M$ has the configuration $(q_i, k\omega)$ and $a\in\Sigma\cup\{\e\}$ is the next input letter to be read, then $M$ can move to the configuration $(q_{j_l}, \gamma_l\omega)$ for some $1\leq l\leq s$, removing the token $k$ from the top of the stack and replacing it by $\gamma_l$. See \cite{\HU} for more details. A pushdown automaton is {\em deterministic} if for each state $q$ and stack symbol $i$ \begin{enumerate} \item if $|\delta(q,\e, i)|=1$ then $|\delta(q,a,i)|=0$ for all $a\in \Sigma$, \item for each $a\in\Sigma\cup\{\e\}$ the set $\delta(q,a,i)$ has size at most one. \end{enumerate} Note that a determistic pushdown automaton accepting on empty stack cannot accept the empty string (unless this is the only string it accepts) since there would have to be a transition $\delta(q_0, \e, 0)$ as well as a transition $\delta(q_0, a, 0)$ for some letter $a$. Let $M$ be the pushdown automaton shown in Figure~\ref{fig:PDA}, which accepts on empty stack. \begin{figure}[h!] \bc \begin{tikzpicture}[node distance = 4cm,->,>=stealth'] \node [state, initial] (s) {$q_0$}; \node [state] (q1) [right of=s] {$q_1$}; \node [state] (q2) [right of=q1] {$q_2$}; \node [state] (q3) [below of=s] {$q_3$}; \node [state] (q4) [below of = q1] {$q_4$}; \node [state] (q5) [below of=q2] {$q_5$}; \node [state] (q7) [below of=q4] {$q_7$}; \node [state] (q6) [below of =q7] {$q_6$}; \node [state] (q8) [below of = q5] {$q_8$}; \path (s) edge [loop, style={min distance = 1cm,in = 65, out = 115},above] node {$\begin{array}{l}\$,0\ra\e\\\mu,1\ra\e\\\mu,2\ra\e\end{array}$} (s); \path (s) edge [above] node {$\rho, i\ra i$} (q1); \path (q1) edge [above] node {$\rho, i\ra i$} (q2); \path (q1) edge [left] node {$\lambda,i\ra 1i$} (q3); \path (q2) edge [right] node {$\lambda,i\ra 1i$} (q5); \path (q3) edge [style={in = 180, out = 270}, left] node {$\rho, i\ra i$} (q6); \path (q5) edge [left] node {$\lambda,i\ra 1i$} (q7); \path (q4) edge [right] node {$\rho, i\ra i$} (q2); \path (q4) edge [above] node {$\lambda,i\ra 1i$} (q3); \path (q5) edge [above] node {$\mu,1\ra\e$} (q4); \path (q4) edge [loop, style={min distance = 1cm,in = 65, out = 115},above] node {$\begin{array}{l}\mu,1\ra\e\\\mu,2\ra\e\end{array}$} (q4); \path (q3) edge [left] node {$\mu,1\ra\e$} (s); \path (q8) edge [style={min distance = 1cm,in = 285, out = 75},right] node {$\lambda,i\ra 2i$} (q5); \path (q5) edge [style={min distance = 1cm,in = 105, out = 255},left] node {$\rho, i\ra i$} (q8); \path (q5) edge [loop,style={min distance = 1cm,in = 335, out = 25},right] node {$\mu,2\ra\e$} (q5); \path (q6) edge [style={min distance = 1cm,in = 255, out = 105}, left] node {$\lambda,i\ra 1i$} (q7); \path (q7) edge [style={min distance = 1cm,in = 75 , out = 285 },right] node {$\rho, i\ra i$} (q6); \path (q6) edge [right] node {$\rho, i\ra i$} (q8); \end{tikzpicture} \ec \caption{\label{fig:PDA}Pushdown automaton $M$ accepting on empty stack, with start configuration $(q_0,0)$. The symbol $i\in\{0,1,2\}$ represents a stack token that is kept in place by a transition.} \end{figure} $M$ uses its stack to keep track of $\difflu$ as it reads its input, and its states to keep track of $\diffrl$. It uses the stack symbol $2$ as a device to flag when the input has the potential to have a prefix of the form $w_0\rho\lambda$ or $w_0\lambda\rho$ with $\diffrl(w_0)=1$. Paths $\rho\mu$ are forbidden. We will prove that the language of this automaton is precisely the language $\lan\$$. Here is the formal description of $M$. Note that states $q_3,q_6,q_7$ are reached only when 1 is on top of the stack, and $q_5,q_8$ are reached when either 1 or 2 are on top of the stack, so we have omitted transitions from configurations that are not possible. \begin{enumerate}\item states $Q=\{q_0,\dots, q_{8}\}$, \item input alphabet $\Sigma=\{\rho,\lambda, \mu, \$\}$, \item stack alphabet $\Gamma=\{0,1,2\}$, \item start state $q_0$, \item transition function $\delta$ defined as follows. \[\begin{array}{lll} \delta(q_0, \$, 0) = (q_0, \e) \\ \delta(q_0, \mu, 1) = (q_0, \e) \\ \delta(q_0, \mu, 2) = (q_0, \e) \\ \delta(q_3, \mu, 1) = (q_0, \e) \\ \delta(q_4, \mu, 1) = (q_4, \e) \\ \delta(q_4, \mu, 2) = (q_4, \e) \\ \delta(q_5, \mu, 1) = (q_4, \e)\\ \delta(q_5, \mu, 2) = (q_5, \e)\\ \delta(q_0, \rho, 0) = (q_1, 0) \\ \delta(q_0, \rho, 1) = (q_1, 1) \\ \delta(q_0, \rho, 2) = (q_1, 2) \\ \delta(q_1, \rho, 0) = (q_2, 0) \\ \end{array}\ \ \ \ \ \ \begin{array}{lll} \delta(q_1, \rho, 1) = (q_2, 1) \\ \delta(q_1, \rho, 2) = (q_2, 2) \\ \delta(q_3, \rho, 1) = (q_6, 1)\\ \delta(q_4, \rho, 0) = (q_2, 0)\\ \delta(q_4, \rho, 1) = (q_2, 1) \\ \delta(q_4, \rho, 2) = (q_2, 2)\\ \delta(q_5, \rho, 1) = (q_8, 1) \\ \delta(q_5, \rho, 2) = (q_8, 2)\\ \delta(q_6, \rho, 1) = (q_8, 1)\\ \delta(q_7, \rho, 1) = (q_6, 1)\\ \delta(q_1, \lambda, 0) = (q_3, 10) \\ \delta(q_1, \lambda, 1) = (q_3, 11) \\ \end{array}\ \ \ \ \ \ \begin{array}{lll} \delta(q_1, \lambda, 2) = (q_3, 12) \\ \delta(q_2, \lambda, 0) = (q_5, 10) \\ \delta(q_2, \lambda, 1) = (q_5, 11) \\ \delta(q_2, \lambda, 2) = (q_5, 12) \\ \delta(q_4, \lambda, 0) = (q_3, 10) \\ \delta(q_4, \lambda, 1) = (q_3, 11) \\ \delta(q_4, \lambda, 2) = (q_3, 12) \\ \delta(q_5, \lambda, 1) = (q_7, 11) \\ \delta(q_5, \lambda, 2) = (q_7, 12) \\ \delta(q_6, \lambda, 1) = (q_7, 11) \\ \delta(q_8, \lambda, 1) = (q_5, 21) \\ \delta(q_8, \lambda, 2) = (q_5, 22) \\ \end{array}\] \end{enumerate} To prove that $M$ accepts precisely the language $\lan\$$, we first show that $M$ is deterministic. This allows us to identify input words with unique paths in $M$ and simplify our arguments slightly. \begin{lemma} The pushdown automaton $M$ is deterministic. \end{lemma} \begin{proof} The claim is easily verified by considering the formal description for $M$. \end{proof} \begin{proposition}\label{prop:PDAcorrect} The pushdown automaton $M$ accepts the language $\lan\$=\{w\$ \mid w\in\lan\}$. \end{proposition} \begin{proof} Since $M$ is deterministic, we identify input words with their corresponding unique path in $M$. Let $w\in\{\rho,\lambda,\mu\}^*$. We must show that \begin{enumerate} \item if $w$ contains $\rho\mu$, then $w\$$ is rejected. \item if $w$ fails to be in $\lan_{2,\infty}$, then $w\$$ is rejected, \item if $w$ has a bad prefix (conditions (2) and (3) in Definition~\ref{DefL}), then $w\$$ rejected. \item if $w\$$ is rejected, then $w\not\in \lan$.\end{enumerate} The only states that can be reached by a path $u\rho$ for $u\in\{\rho,\lambda, \mu\}^*$ from the start configuration are $q_1, q_2, q_6$ and $ q_8$ and since none are the source of a $\mu$ transition, any word containing $\rho\mu$ will be rejected. Next, we show that if $w$ is not in $\lan_{2,\infty}$, then $w\$$ is rejected by $M$. Each state represents the endpoint of a path labeling a prefix of an input string accepted by the automaton. One can verify the values of $D_{\rho,\lambda}(u)$ for each path labeled $u$ ending at state $q_i$ given by Table~\ref{tableD}. \begin{table}[h!] \[ \begin{array}{|c||c|c|c|c|c|c|c|c|c|c|c|} \hline \mathrm{state} & q_0 & q_1 & q_2 & q_3 & q_4 & q_5 & q_6 & q_7 & q_8\\ \hline D_{\rho,\lambda} & 0 & 1 & 2 & 0 & 1 & 1 & 1 & 0 & 2\\ \hline \end{array} \] \caption{Value of $D_{\rho,\lambda}$ for any prefix ending at each state\label{tableD}} \end{table} Let $h(u)$ be the height of the second (infinite) stack after reading $u\in \{\rho,\lambda,\mu\}^*$ starting from the start configuration $(q_0,0)$. Then $h(\e)=1$, $h(u\rho)=h(u), h(u\lambda)=h(u)+1$ and $h(u\mu)=h(u)-1$ since $\lambda$ pushes a token to the stack, $\mu$ pops a token and $\rho$ keeps the stack unchanged. It follows that $h(u)=D_{\lambda,\mu}(u)+1$, and since $0$ stays on the stack until $\$$ is read, $h(u)\geq 1$ for all prefixes $u\in \{\rho,\lambda,\mu\}^*$, so $D_{\lambda,\mu}(u)\geq 0$. If $w\$$ is accepted then the stack must contain only $0$ after reading $w$, so $D_{\lambda,\mu}(w)=0$. It follows that if $D_{\rho,\lambda}(u)>2, D_{\rho,\lambda}(u)$ ,$D_{\lambda,\mu}(u)<0$ for some prefix $u$, or $D_{\lambda,\mu}(w)\neq 0$, then $M$ will reject $w\$$. Next, suppose $w\in \lan_{2,\infty}$ has no $\rho\mu$ substring and a prefix of the form $w_0vw_1\lambda\mu$ where $D_{\rho,\lambda}(w_0)=1, v\in\{\rho\lambda,\lambda\rho\}$ and $w_1\in\lan_{1,\infty}$. The string $w_0$ labels a path in the automaton starting at $q_0$ and ending at state $q_1, q_4, q_5$ or $q_6$ by Table~\ref{tableD}. From each of these states, reading $v=\rho\lambda$ ends in state $q_5$, and reading $v=\lambda\rho$ ends in state $q_6$. From $q_5$, the word $w_1$ labels a path that visits only states $q_5$ and $q_8$, since $D_{\lambda,\mu}(z)\geq 0$ for all prefixes $z$ of $w_1$, so the 1 on top of the stack before reading $w_1$ remains (and is covered by 2s, which are removed by the $\mu$ loop at $q_5$), and ends at $q_5$ since $D_{\lambda,\mu}(w_1)= 0$. From here reading $\lambda\mu$ is rejected. From $q_6$, if $w_1=\e$ then $u\lambda\rho\lambda\mu$ is rejected. Otherwise $w_1$ labels a path from $q_6$ to $q_8$ and then moves between $q_5$ and $q_8$, and ends at $q_5$. From here reading $\lambda\mu$ is rejected. We have now established that if $w\not\in \lan$ then $w\$$ is rejected by $M$. To complete the proof we must show that if $w\$$ is rejected, then $w\not \in\lan$. To show this, assume $w\in \lan_{2,\infty}$ with no $\rho\mu$ substring, but $w\$$ is rejected by $M$. We will prove that $w$ must have a bad prefix. Let $p$ be the longest prefix of $w\$$ labeling a path that is not rejected by $M$. Since $w\in \lan_{2,\infty}$ we have $D_{\lambda,\mu}(w)=0$, so if $w=p$, after reading $w$ the stack contains just $0$ so $w\$$ will be accepted, a contradiction. Thus $p$ is strictly shorter than $w$. Let $w=pxw'$ where $x\in\{\rho\lambda,\mu\}$ is the next letter input after reading $p$. We now consider the possible states where $p$ can end. \begin{enumerate} \item Suppose $p$ ends at $q_0$. Then $D_{\rho,\lambda}(p)=0$ so $x\neq \lambda$. If the top of stack is $0$ then $D_{\lambda, \mu}(p)=0$ so $x\neq \mu$. Otherwise $M$ cannot reject on reading $\rho,\mu$. \item Suppose $p$ ends at $q_1$, so its last letter is $\rho$, and $D_{\rho,\lambda}(p)=1$. Then $x\neq \mu$. Otherwise $M$ cannot reject on reading $\rho,\lambda$. \item Suppose $p$ ends at $q_2$, so its last letter is $\rho$, and $D_{\rho,\lambda}(p)=2$. Then $x\neq \mu, \rho$. Otherwise $M$ cannot reject on reading $\lambda$. \item Suppose $p$ ends at $q_3$, so $D_{\rho,\lambda}(p)=0$ and the top of stack is $1$. Then $x\neq \lambda$. Otherwise $M$ cannot reject on reading $\rho,(\mu, 1\ra \e)$. \item Suppose $p$ ends at $q_4$, so $D_{\rho,\lambda}(p)=1$. The only way $M$ could reject is if the top of stack is $0$ and $x=\mu$, which is not possible since $w\in\lan_{2,\infty}$. \item Suppose $p$ ends at $q_5$, so $D_{\rho,\lambda}(p)=1$ and $1$ is on top of the stack. Then no letter will cause $M$ to reject. \item Suppose $p$ ends at $q_6$, so $D_{\rho,\lambda}(p)=1$ and $p$ ends with $\lambda\rho$. Then $x$ cannot be $\mu$, and otherwise $px$ is not rejected. \item Suppose $p$ ends at $q_8$, so its last letter is $\rho$, and $D_{\rho,\lambda}(p)=2$. Then $x\neq \mu,\rho$ and $M$ cannot reject if $x=\lambda$. \end{enumerate} These cases show that if $p$ ends at any state except $q_7$, then $M$ does not reject $w$ on reading the next input letter. We finish the proof by showing that if $p$ ends at $q_7$, then $px$ is a bad prefix. Since $p$ ends at $q_7$, $p$ ends with $\lambda$, $\diffrl(p)=2$, and $\difflu(p)>0$. If $x=\rho$ then $px$ is not rejected. If $x=\lambda$ then $w\not\in\lan_{2,\infty}$. So we must have $x=\mu$. Let $p=p_1\lambda$. If $p_1$ ends at $q_6$, then $p_1=p_2\lambda\rho$, and $px=p_2\lambda\rho\lambda\mu$ where $\diffrl(p_2)=1$ and so $px$ is a bad prefix. The machine correctly rejects the string on reading $x=\mu$. Otherwise $p_1$ ends at $q_5$. Either $p_1$ ends with $\rho\lambda$, or $\mu$. If $p_1=p_2\rho\lambda$ then $\diffrl(p_2)=1$ and $px=p_2\rho\lambda\lambda\mu$ is a bad prefix. Otherwise $p_1$ ends in $\mu$, and must pop a token $2$ from the stack. Let $\lambda_*$ be the last $\lambda$ letter in $p_1$ that pushed a $1$ on top of the stack (which must exist, since all paths to $q_5$ must cross such an edge). Write $p_1=p_2\lambda_*p_3\mu$. The letter $\lambda_*$ labels one of the following edges: \begin{enumerate} \item from $q_2$ to $q_5$, \item from $q_1$ to $q_3$, \item from $q_4$ to $q_3$, \item from $q_5$ to $q_7$, \item from $q_6$ to $q_7$. \end{enumerate} In the first case, $p_2$ ends at $q_2$ so must have the form $p_2=u\rho$ with $\diffrl(u)=1$. Then $p_3\mu$ labels a path that moves between states $q_5$ and $q_8$, reading $\rho\lambda$ and pushing a 2, or reading $\mu$ and popping a 2, so $p_3\mu\in\lan_{1,\infty}$. It follows that $w$ has the bad prefix $u\rho\lambda_*(p_3\mu)\lambda\mu$, and so $M$ correctly rejects it. In the other four cases we have that $\diffrl(p_2)=1$ since $p_2$ ends at state $q_1, q_4, q_5$ or $q_6$, $\lambda_*$ must be immediately followed by a letter $\rho$, and $p_2\lambda_*\rho$ ends at state $q_6$. Let $p_3=\rho p_4$. Then $p_4\mu$ labels a path that starts at $q_6$, goes to $q_8$, then moves between states $q_5$ and $q_8$, reading $\rho\lambda$ and pushing a 2, or reading $\mu$ and popping a 2. So $p_4\mu\in\lan_{1,\infty}$. It follows that $w$ has the bad prefix $p_2\lambda_*\rho(p_4\mu)\lambda\mu$, and so $M$ correctly rejects it. \end{proof} \section{Obtaining the generating function} \begin{theorem}\label{thm:gfun} The sequence counting the number of permutations of each length in $\mathcal P$ has an algebraic generating function: \begin{align*} \sum_{n\geq 0} c_n z^n &= \frac{(1+q)\left(1+5q-q^2-q^3-(1-q)\sqrt{(1-q^2)(1-4q-q^2)}\right)}{8q} \end{align*} where $c_n$ is the number of permutations in $\mathcal P$ of length $n$, and $q \equiv q(z) = \frac{1-2z-\sqrt{1-4z}}{2z}$. \end{theorem} \begin{proof} We convert the pushdown automaton given in the previous section to an unambiguous context-free language, following the standard procedure as described in Hopcroft and Ullman \cite{\HU}. Theorem~10.12 of Hopcroft and Ullman guarantees that the grammar obtained from a deterministic pushdown automaton accepting on empty stack is $LR(0)$ and hence unambiguous. We then apply the Chomsky and Sch\"utzenberger theorem, as outlined for example in \cite{\Flajolet} I.5.4, to obtain an algebraic generating function. Since each step in this procedure is constructive, we can find the generating function explicitly. We start by converting the pushdown automaton to a grammar. See Theorem~5.4 \cite{\HU} for full details. Define a grammar with nonterminals $S$ and $[q_i,j,q_k]=N_{i,j,k}$ for each pair of states $q_i,q_k$ and stack symbol $j$. The nonterminal $[q_i,j,q_k]$ represents a path in the configuration space of the pushdown automaton starting at $q_i$ with $j$ on top of the stack and ending at some state $q_k$. The productions ``fill out" these paths with subpaths according to the transitions that are possible. The production rules are then defined as follows: \begin{enumerate} \item for each state $q_i$ we have a production $S\ra N_{00i}$, \item for each transition $\delta(q_i,a, j)=\{(q_k, \e)\}$ with $a\in\{\$,\mu\}$, add a production $N_{ijk}=a$, \item for each transition $\delta(q_i,\rho, j)=\{(q_k, l)\}$, add productions $N_{ijx}=\rho N_{klx}$ for $0\leq x \leq 8$, \item for each transition $\delta(q_i,\lambda, j)=\{(q_k, lm)\}$, add productions $N_{ijx}=\lambda N_{kly}N_{ymx}$ $0\leq x,y\leq 8$. \end{enumerate} This gives the following set of productions, where $0\leq x,y\leq 8$: \[\begin{array}{lcl} N_{000}& \ra &\$\\ N_{010}& \ra &\mu\\ N_{020}& \ra &\mu \\ N_{310}& \ra &\mu \\ N_{414}& \ra &\mu \\ N_{424}& \ra &\mu \\ N_{514}& \ra &\mu \\ \end{array}\ \ \ \ \ \ \begin{array}{lcl} N_{41x}& \ra & \rho N_{21x} \\ N_{42x}& \ra & \rho N_{22x} \\ N_{11x}& \ra & \rho N_{21x} \\ N_{12x}& \ra & \rho N_{22x} \\ N_{31x}& \ra & \rho N_{61x} \\ N_{40x}& \ra & \rho N_{20x} \\ N_{51x}& \ra & \rho N_{81x} \\ \end{array}\ \ \ \ \ \ \begin{array}{lcl} N_{12x}& \ra & \lambda N_{31y}N_{y2x} \\ N_{20x}& \ra & \lambda N_{51y}N_{y0x} \\ N_{21x}& \ra & \lambda N_{51y}N_{y1x} \\ N_{22x}& \ra & \lambda N_{51y}N_{y2x} \\ N_{40x}& \ra & \lambda N_{31y}N_{y0x} \\ N_{41x}& \ra & \lambda N_{31y}N_{y1x} \\ N_{42x}& \ra & \lambda N_{31y}N_{y2x} \\ \end{array}\] \[\begin{array}{lcl} N_{525}& \ra &\mu\\ N_{00x}& \ra & \rho N_{10x} \\ N_{01x}& \ra & \rho N_{11x} \\ N_{02x}& \ra & \rho N_{12x} \\ N_{10x}& \ra & \rho N_{20x} \\ \end{array}\ \ \ \ \ \ \begin{array}{lcl} N_{52x}& \ra & \rho N_{82x} \\ N_{61x}& \ra & \rho N_{81x} \\ N_{71x}& \ra & \rho N_{61x} \\ N_{10x}& \ra & \lambda N_{31y}N_{y0x} \\ N_{11x}& \ra & \lambda N_{31y}N_{y1x} \\ \end{array}\ \ \ \ \ \ \begin{array}{lcl} N_{51x}& \ra & \lambda N_{71y}N_{y1x} \\ N_{52x}& \ra & \lambda N_{71y}N_{y2x} \\ N_{61x}& \ra & \lambda N_{71y}N_{y1x} \\ N_{81x}& \ra & \lambda N_{52y}N_{y1x} \\ N_{82x}& \ra & \lambda N_{52y}N_{y2x} \\ \end{array}\] We can reduce the size of the grammar description as follows. First, observe that the only productions that eliminate nonterminals (by generating $\$$ or $\mu$) are of the form $N_{\ast j k}$ for $k\in\{0,4,5\}$, and $j=0$ implies $k=0$. Since all productions with nonterminals on the right side have the form $N_{\ast ij}\ra \rho N_{\ast ij}$ or $N_{\ast ij}\ra \lambda N_{\ast\ast\ast}N_{\ast ij}$, it follows that any nonterminal $N_{\ast\ast k}$ with $k$ not equal to $0,4$ or $5$ cannot be eliminated, so we can exclude them from the grammar. Also, if we start a derivation with $S\ra N_{00k}$ for $k\neq 0$, there will always be a nonterminal of the form $N_{\ast 0k}$ that cannot be eliminated. Therefore it suffices to make $N_{000}$ the start nonterminal and remove all productions involving $S$. Lastly, the resulting grammar contain nonterminals $N_{500},N_{504},N_{505}$ that will never produce a string of only terminals, since the configuration $(q_5,0)$ is never realised (to reach $q_5$ the top of stack symbol is either $1$ or $2$. We modify the above grammar one step further by removing any production involving these nonterminals. Taking these factors into consideration, and collecting productions with the same left side together we obtain the following grammar: \bigskip $ \begin{array}{lll} N_{000} & \ra & \$ \mid \rho N_{100},\\ N_{004} & \ra & \rho N_{104},\\ N_{005} & \ra & \rho N_{105},\\ N_{010} & \ra & \mu \mid \rho N_{110},\\ N_{014} & \ra & \rho N_{114},\\ N_{015} & \ra & \rho N_{115},\\ N_{020} & \ra & \mu \mid \rho N_{120},\\ N_{024} & \ra & \rho N_{124},\\ N_{025} & \ra & \rho N_{125}, \end{array}$ $ \begin{array}{lll} N_{100} & \ra & \rho N_{200} \mid \lambda N_{310} N_{000} \mid \lambda N_{314} N_{400},\\ N_{104} & \ra & \rho N_{204} \mid \lambda N_{310} N_{004} \mid \lambda N_{314} N_{404},\\ N_{105} & \ra & \rho N_{205} \mid \lambda N_{310} N_{005} \mid \lambda N_{314} N_{405}, \end{array}$ $ \begin{array}{lll} N_{110} & \ra & \rho N_{210} \mid \lambda N_{310} N_{010} \mid \lambda N_{314} N_{410} \mid \lambda N_{315} N_{510},\\ N_{114} & \ra & \rho N_{214} \mid \lambda N_{310} N_{014} \mid \lambda N_{314} N_{414} \mid \lambda N_{315} N_{514},\\ N_{115} & \ra & \rho N_{215} \mid \lambda N_{310} N_{015} \mid \lambda N_{314} N_{415} \mid \lambda N_{315} N_{515},\\ \end{array}$ $ \begin{array}{lll} N_{120} & \ra & \rho N_{220} \mid \lambda N_{310} N_{020} \mid \lambda N_{314} N_{420} \mid \lambda N_{315} N_{520},\\ N_{124} & \ra & \rho N_{224} \mid \lambda N_{310} N_{024} \mid \lambda N_{314} N_{424} \mid \lambda N_{315} N_{524},\\ N_{125} & \ra & \rho N_{225} \mid \lambda N_{310} N_{025} \mid \lambda N_{314} N_{425} \mid \lambda N_{315} N_{525}, \end{array}$ $ \begin{array}{lll} N_{200} & \ra & \lambda N_{510} N_{000} \mid \lambda N_{514} N_{400},\\ N_{204} & \ra & \lambda N_{510} N_{004} \mid \lambda N_{514} N_{404},\\ N_{205} & \ra & \lambda N_{510} N_{005} \mid \lambda N_{514} N_{405}, \end{array}$ $ \begin{array}{lll} N_{210} & \ra & \lambda N_{510} N_{010} \mid \lambda N_{514} N_{410} \mid \lambda N_{515} N_{510},\\ N_{214} & \ra & \lambda N_{510} N_{014} \mid \lambda N_{514} N_{414} \mid \lambda N_{515} N_{514},\\ N_{215} & \ra & \lambda N_{510} N_{015} \mid \lambda N_{514} N_{415} \mid \lambda N_{515} N_{515},\\ N_{220} & \ra & \lambda N_{510} N_{020} \mid \lambda N_{514} N_{420} \mid \lambda N_{515} N_{520},\\ N_{224} & \ra & \lambda N_{510} N_{024} \mid \lambda N_{514} N_{424} \mid \lambda N_{515} N_{524},\\ N_{225} & \ra & \lambda N_{510} N_{025} \mid \lambda N_{514} N_{425} \mid \lambda N_{515} N_{525}, \end{array}$ $ \begin{array}{lll} N_{310} & \ra & \mu \mid \rho N_{610},\\ N_{314} & \ra & \rho N_{614},\\ N_{315} & \ra & \rho N_{615}, \end{array}$ $ \begin{array}{lll} N_{400} & \ra & \rho N_{200} \mid \lambda N_{310} N_{000} \mid \lambda N_{314} N_{400},\\ N_{404} & \ra & \rho N_{204} \mid \lambda N_{310} N_{004} \mid \lambda N_{314} N_{404},\\ N_{405} & \ra & \rho N_{205} \mid \lambda N_{310} N_{005} \mid \lambda N_{314} N_{405},\\ N_{410} & \ra & \rho N_{210} \mid \lambda N_{310} N_{010} \mid \lambda N_{314} N_{410} \mid \lambda N_{315} N_{510},\\ N_{414} & \ra & \mu \mid \rho N_{214} \mid \lambda N_{310} N_{014} \mid \lambda N_{314} N_{414} \mid \lambda N_{315} N_{514},\\ N_{415} & \ra & \rho N_{215} \mid \lambda N_{310} N_{015} \mid \lambda N_{314} N_{415} \mid \lambda N_{315} N_{515},\\ N_{420} & \ra & \rho N_{220} \mid \lambda N_{310} N_{020} \mid \lambda N_{314} N_{420} \mid \lambda N_{315} N_{520},\\ N_{424} & \ra & \mu \mid \rho N_{224} \mid \lambda N_{310} N_{024} \mid \lambda N_{314} N_{424} \mid \lambda N_{315} N_{524},\\ N_{425} & \ra & \rho N_{225} \mid \lambda N_{310} N_{025} \mid \lambda N_{314} N_{425} \mid \lambda N_{315} N_{525}, \end{array}$ $ \begin{array}{lll} N_{510} & \ra & \rho N_{810} \mid \lambda N_{710} N_{010} \mid \lambda N_{714} N_{410} \mid \lambda N_{715} N_{510},\\ N_{514} & \ra & \mu \mid \rho N_{814} \mid \lambda N_{710} N_{014} \mid \lambda N_{714} N_{414} \mid \lambda N_{715} N_{514},\\ N_{515} & \ra & \rho N_{815} \mid \lambda N_{710} N_{015} \mid \lambda N_{714} N_{415} \mid \lambda N_{715} N_{515},\\ N_{520} & \ra & \rho N_{820} \mid \lambda N_{710} N_{020} \mid \lambda N_{714} N_{420} \mid \lambda N_{715} N_{520},\\ N_{524} & \ra & \rho N_{824} \mid \lambda N_{710} N_{024} \mid \lambda N_{714} N_{424} \mid \lambda N_{715} N_{524},\\ N_{525} & \ra & \mu \mid \rho N_{825} \mid \lambda N_{710} N_{025} \mid \lambda N_{714} N_{425} \mid \lambda N_{715} N_{525}, \end{array}$ $ \begin{array}{lll} N_{610} & \ra & \rho N_{810} \mid \lambda N_{710} N_{010} \mid \lambda N_{714} N_{410} \mid \lambda N_{715} N_{510},\\ N_{614} & \ra & \rho N_{814} \mid \lambda N_{710} N_{014} \mid \lambda N_{714} N_{414} \mid \lambda N_{715} N_{514},\\ N_{615} & \ra & \rho N_{815} \mid \lambda N_{710} N_{015} \mid \lambda N_{714} N_{415} \mid \lambda N_{715} N_{515}, \end{array}$ $ \begin{array}{lll} N_{710} & \ra & \rho N_{610},\\ N_{714} & \ra & \rho N_{614},\\ N_{715} & \ra & \rho N_{615}, \end{array}$ $ \begin{array}{lll} N_{810} & \ra & \lambda N_{520} N_{010} \mid \lambda N_{524} N_{410} \mid \lambda N_{525} N_{510},\\ N_{814} & \ra & \lambda N_{520} N_{014} \mid \lambda N_{524} N_{414} \mid \lambda N_{525} N_{514},\\ N_{815} & \ra & \lambda N_{520} N_{015} \mid \lambda N_{524} N_{415} \mid \lambda N_{525} N_{515}, \end{array}$ $ \begin{array}{lll} N_{820} & \ra & \lambda N_{520} N_{020} \mid \lambda N_{524} N_{420} \mid \lambda N_{525} N_{520},\\ N_{824} & \ra & \lambda N_{520} N_{024} \mid \lambda N_{524} N_{424} \mid \lambda N_{525} N_{524},\\ N_{825} & \ra & \lambda N_{520} N_{025} \mid \lambda N_{524} N_{425} \mid \lambda N_{525} N_{525}. \end{array}$ \bigskip The next step is to convert nonterminals to generating functions, terminals to $z$ and productions to equations, as described in \cite{\Flajolet} I.5.4. \bigskip $ \begin{array}{lll} f_{000} & = & z + z f_{100},\\ f_{004} & = & z f_{104},\\ f_{005} & = & z f_{105},\\ f_{010} & = & z + z f_{110},\\ \end{array}$ $ \begin{array}{lll} f_{014} & = & z f_{114},\\ f_{015} & = & z f_{115},\\ f_{020} & = & z + z f_{120},\\ f_{024} & = & z f_{124},\\ f_{025} & = & z f_{125}, \end{array}$ $ \begin{array}{lll} f_{100} & = & z f_{200} + z f_{310} f_{000} + z f_{314} f_{400},\\ f_{104} & = & z f_{204} + z f_{310} f_{004} + z f_{314} f_{404},\\ f_{105} & = & z f_{205} + z f_{310} f_{005} + z f_{314} f_{405},\\ f_{110} & = & z f_{210} + z f_{310} f_{010} + z f_{314} f_{410} + z f_{315} f_{510},\\ f_{114} & = & z f_{214} + z f_{310} f_{014} + z f_{314} f_{414} + z f_{315} f_{514},\\ f_{115} & = & z f_{215} + z f_{310} f_{015} + z f_{314} f_{415} + z f_{315} f_{515},\\ f_{120} & = & z f_{220} + z f_{310} f_{020} + z f_{314} f_{420} + z f_{315} f_{520},\\ f_{124} & = & z f_{224} + z f_{310} f_{024} + z f_{314} f_{424} + z f_{315} f_{524},\\ f_{125} & = & z f_{225} + z f_{310} f_{025} + z f_{314} f_{425} + z f_{315} f_{525}, \end{array}$ $ \begin{array}{lll} f_{200} & = & z f_{510} f_{000} + z f_{514} f_{400},\\ f_{204} & = & z f_{510} f_{004} + z f_{514} f_{404},\\ f_{205} & = & z f_{510} f_{005} + z f_{514} f_{405},\\ f_{210} & = & z f_{510} f_{010} + z f_{514} f_{410} + z f_{515} f_{510},\\ f_{214} & = & z f_{510} f_{014} + z f_{514} f_{414} + z f_{515} f_{514},\\ f_{215} & = & z f_{510} f_{015} + z f_{514} f_{415} + z f_{515} f_{515},\\ f_{220} & = & z f_{510} f_{020} + z f_{514} f_{420} + z f_{515} f_{520},\\ f_{224} & = & z f_{510} f_{024} + z f_{514} f_{424} + z f_{515} f_{524},\\ f_{225} & = & z f_{510} f_{025} + z f_{514} f_{425} + z f_{515} f_{525}, \end{array}$ $ \begin{array}{lll} f_{310} & = & z + z f_{610},\\ f_{314} & = & z f_{614},\\ f_{315} & = & z f_{615}, \end{array}$ $ \begin{array}{lll} f_{400} & = & z f_{200} + z f_{310} f_{000} + z f_{314} f_{400},\\ f_{404} & = & z f_{204} + z f_{310} f_{004} + z f_{314} f_{404},\\ f_{405} & = & z f_{205} + z f_{310} f_{005} + z f_{314} f_{405},\\ f_{410} & = & z f_{210} + z f_{310} f_{010} + z f_{314} f_{410} + z f_{315} f_{510},\\ f_{414} & = & z + z f_{214} + z f_{310} f_{014} + z f_{314} f_{414} + z f_{315} f_{514},\\ f_{415} & = & z f_{215} + z f_{310} f_{015} + z f_{314} f_{415} + z f_{315} f_{515},\\ f_{420} & = & z f_{220} + z f_{310} f_{020} + z f_{314} f_{420} + z f_{315} f_{520},\\ f_{424} & = & z + z f_{224} + z f_{310} f_{024} + z f_{314} f_{424} + z f_{315} f_{524},\\ f_{425} & = & z f_{225} + z f_{310} f_{025} + z f_{314} f_{425} + z f_{315} f_{525}, \end{array}$ $ \begin{array}{lll} f_{510} & = & z f_{810} + z f_{710} f_{010} + z f_{714} f_{410} + z f_{715} f_{510},\\ f_{514} & = & z + z f_{814} + z f_{710} f_{014} + z f_{714} f_{414} + z f_{715} f_{514},\\ f_{515} & = & z f_{815} + z f_{710} f_{015} + z f_{714} f_{415} + z f_{715} f_{515},\\ f_{520} & = & z f_{820} + z f_{710} f_{020} + z f_{714} f_{420} + z f_{715} f_{520},\\ f_{524} & = & z f_{824} + z f_{710} f_{024} + z f_{714} f_{424} + z f_{715} f_{524},\\ f_{525} & = & z + z f_{825} + z f_{710} f_{025} + z f_{714} f_{425} + z f_{715} f_{525},\\ f_{610} & = & z f_{810} + z f_{710} f_{010} + z f_{714} f_{410} + z f_{715} f_{510},\\ f_{614} & = & z f_{814} + z f_{710} f_{014} + z f_{714} f_{414} + z f_{715} f_{514},\\ \end{array}$ $ \begin{array}{lll} f_{615} & = & z f_{815} + z f_{710} f_{015} + z f_{714} f_{415} + z f_{715} f_{515},\\ f_{710} & = & z f_{610},\\ f_{714} & = & z f_{614},\\ f_{715} & = & z f_{615}, \end{array}$ $ \begin{array}{lll} f_{810} & = & z f_{520} f_{010} + z f_{524} f_{410} + z f_{525} f_{510},\\ f_{814} & = & z f_{520} f_{014} + z f_{524} f_{414} + z f_{525} f_{514},\\ f_{815} & = & z f_{520} f_{015} + z f_{524} f_{415} + z f_{525} f_{515},\\ f_{820} & = & z f_{520} f_{020} + z f_{524} f_{420} + z f_{525} f_{520},\\ f_{824} & = & z f_{520} f_{024} + z f_{524} f_{424} + z f_{525} f_{524},\\ f_{825} & = & z f_{520} f_{025} + z f_{524} f_{425} + z f_{525} f_{525}.\end{array}$ \bigskip Using Maple (version 14) we can solve to obtain an expression for the algebraic generating function $f_{000}(z)$, which counts the number of words in $\lan\$$ of each length. Since words in $\lan\$$ of length $3n+1$ are in bijection with permutations in $\mathcal P$ of length $n$, the generating function $\sum_{n\geq 0} c_nt^n$ where $c_n$ is the number of permutations of length $n$ in $\mathcal P$ is obtained by dividing $f_{000}$ by $z$ and substituting $z^3=t$. \end{proof} From the expression for the generating function we can easily obtain the first few terms of the sequence: $1+z+2z^2+6z^3+24z^4+114z^5+592z^6+3216z^7+17904z^8+101198z^9+578208z^{10}+3332136z^{11}+19343408z^{12}+\dots .$ We can also use standard analytic combinatorial methods \cite{MR2483235} to deduce the asymptotic growth of the number of such permutations: \begin{align*} c_n \sim \frac{\sqrt{25-11\sqrt{5}}}{2\sqrt{\pi n^3}} \cdot (2+2\sqrt{5})^n \cdot \left(1 + O(n^{-1}) \right). \end{align*} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} The bulk of this paper is the result of a University of Newcastle summer vacation project undertaken by the second author under supervision of the first. Research was supported by the Australian Research Council (ARC) grant FT110100178, and the Natural Sciences and Engineering Research Council of Canada (NSERC). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{10} \bibitem{MR2000167} M.~H. Albert, M.~D. Atkinson, and N.~Ru{\v{s}}kuc. \newblock Regular closed sets of permutations. \newblock {\em Theoret. Comput. Sci.}, 306(1-3):85--100, 2003. \bibitem{MR2199982} M.~H. Albert, M.~Elder, A.~Rechnitzer, P.~Westcott, and M.~Zabrocki. \newblock On the {S}tanley-{W}ilf limit of 4231-avoiding permutations and a conjecture of {A}rratia. \newblock {\em Adv. in Appl. Math.}, 36(2):96--105, 2006. \bibitem{DBLP:journals/ejc/AlbertB15} Michael Albert and Mireille Bousquet{-}M{\'{e}}lou. \newblock Permutations sortable by two stacks in parallel and quarter plane walks. \newblock {\em Eur. J. Comb.}, 43:131--164, 2015. \bibitem{MR2577304} Michael~H. Albert, M.~D. Atkinson, and Vincent Vatter. \newblock Counting 1324, 4231-avoiding permutations. \newblock {\em Electron. J. Combin.}, 16(1):Research Paper 136, 9, 2009. \bibitem{MR2176523} Michael~H. Albert, Steve Linton, and Nik Ru{\v{s}}kuc. \newblock The insertion encoding of permutations. \newblock {\em Electron. J. Combin.}, 12:Research Paper 47, 31, 2005. \bibitem{MR1453845} M.~D. Atkinson, M.~J. Livesey, and D.~Tulley. \newblock Permutations generated by token passing in graphs. \newblock {\em Theoret. Comput. Sci.}, 178(1-2):103--118, 1997. \bibitem{MR1932896} M.~D. Atkinson, M.~M. Murphy, and N.~Ru{\v{s}}kuc. \newblock Sorting with two ordered stacks in series. \newblock {\em Theoret. Comput. Sci.}, 289(1):205--223, 2002. \bibitem{MR1485138} Mikl{\'o}s B{\'o}na. \newblock Exact enumeration of {$1342$}-avoiding permutations: a close link with labeled trees and planar maps. \newblock {\em J. Combin. Theory Ser. A}, 80(2):257--272, 1997. \bibitem{MR3300327} Andrew~R. Conway and Anthony~J. Guttmann. \newblock On 1324-avoiding permutations. \newblock {\em Adv. in Appl. Math.}, 64:50--69, 2015. \bibitem{ElderCS} M.~Elder. \newblock Pattern avoiding permutations are context-sensitive, 2004. \newblock ArXiv: math/0412019. \bibitem{MR2240774} Murray Elder. \newblock Permutations generated by a stack of depth 2 and an infinite stack in series. \newblock {\em Electron. J. Combin.}, 13(1):Research Paper 68, 12 pp. (electronic), 2006. \bibitem{MR2483235} Philippe Flajolet and Robert Sedgewick. \newblock {\em Analytic combinatorics}. \newblock Cambridge University Press, Cambridge, 2009. \bibitem{MR1041448} Ira~M. Gessel. \newblock Symmetric functions and {P}-recursiveness. \newblock {\em J. Combin. Theory Ser. A}, 53(2):257--285, 1990. \bibitem{MR645539} John~E. Hopcroft and Jeffrey~D. Ullman. \newblock {\em Introduction to automata theory, languages, and computation}. \newblock Addison-Wesley Publishing Co., Reading, Mass., 1979. \newblock Addison-Wesley Series in Computer Science. \bibitem{MR0445948} Donald~E. Knuth. \newblock {\em The art of computer programming. {V}olume 3}. \newblock Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. \newblock Sorting and searching, Addison-Wesley Series in Computer Science and Information Processing. \bibitem{MR3181450} Adeline Pierrot and Dominique Rossin. \newblock 2-stack sorting is polynomial. \newblock In {\em 31st {I}nternational {S}ymposium on {T}heoretical {A}spects of {C}omputer {S}cience}, volume~25 of {\em LIPIcs. Leibniz Int. Proc. Inform.}, pages 614--626. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2014. \bibitem{MR829358} Rodica Simion and Frank~W. Schmidt. \newblock Restricted permutations. \newblock {\em European J. Combin.}, 6(4):383--406, 1985. \bibitem{wikipatterns} Wikipedia. \newblock Enumerations of specific permutation classes --- {W}ikipedia{,} the free encyclopedia, 2014. \newblock Accessed 5 July 2014. \end{thebibliography} \end{document}