%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2018}
\articlenumber{43}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
%\usepackage[T1]{fontenc}
%\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usepackage{pgfmath}
\usetikzlibrary{matrix,positioning}
\usetikzlibrary{arrows,automata}
%\usepackage{caption}
\usepackage{wrapfig}

\DeclareMathOperator{\Av}{\mathrm{Av}}
\DeclareMathOperator{\rev}{\mathrm{rev}}
\newcommand{\sym}{\mathcal{S}}
\newcommand{\word}{w}
\newcommand{\A}{\texttt{a}}
\newcommand{\D}{\texttt{d}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}

% \theoremstyle{plain}
% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{lemma}[theorem]{Lemma}
% \newtheorem{proposition}[theorem]{Proposition}
% \newtheorem*{proposition*}{Proposition}
% \newtheorem{corollary}[theorem]{Corollary}
% \newtheorem{conjecture}[theorem]{Conjecture}
% \newtheorem*{conjecture*}{Conjecture}
% \theoremstyle{definition}
% \newtheorem{definition}[theorem]{Definition}

% \newtheorem{thm}{Theorem}
% \newtheorem{lem}{Lemma}

%% define your title in the usual way
\title[Enumerating permutations sortable by $k$ passes through a pop-stack]
  {Enumerating permutations sortable by \\$k$ passes through a pop-stack}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
% \author{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}
\author{Anders Claesson\thanks{\href{mailto:akc@hi.is}{akc@hi.is}. This
work was supported by The Doctoral Grants of the University of Iceland
Research Fund and The Icelandic Infrastructure Fund.}\addressmark{1}
 \and Bjarki \'Ag\'ust
 Gu{\dh}mundsson\thanks{\href{mailto:suprdewd@gmail.com}{suprdewd@gmail.com}}\addressmark{1}} %\footnotemark[1]} % TODO: Fix!

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Science Institute, University of Iceland,
Dunhaga 5, 107 Reykjavik, Iceland}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
  In an exercise in the first volume of his famous series of books,
  Knuth considered sorting permutations by passing them through a stack.
  Many variations of this exercise have since been considered, including
  allowing multiple passes through the stack and using different data
  structures. We are concerned with a variation using pop-stacks that was
  introduced by Avis and Newborn in 1981. Let $P_k(x)$ be the generating
  function for the permutations sortable by $k$ passes through a
  pop-stack.  The generating function $P_2(x)$ was recently given by
  Pudwell and Smith (the case $k=1$ being trivial). We show that
  $P_k(x)$ is rational for any $k$. Moreover, we give an algorithm to
  derive $P_k(x)$, and using it we determine the generating functions
  $P_k(x)$ for $k\leq 6$.
}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{permutation, pop-stack, sortable, enumeration, generating function, rational, language}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{43-Claesson-Gudmundsson.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\customwidth{0.6pt}
\def\customscale{0.60}
%%
% usage: \comparray{<origin>>}{<binary-string-specifying-walls>}
%%
\newcommand{\comparray}[2]{
  \begin{scope}[shift={#1}]
    \foreach \row [count=\y from 0] in {#2} {
      \pgfmathparse{dim(\row)};
      \pgfmathsetmacro{\w}{\pgfmathresult};
      \foreach \b [count=\x from 0] in \row {
        \ifthenelse{\b=1}
          {\draw[line cap=round] (\x,-\y) -- (\x,1-\y);}{};
        \ifthenelse{\b=2}
          {\draw[loosely dotted,line cap=round] (\x,-\y) -- (\x,1-\y);}{};
        \ifthenelse{\b=3}
          {\draw[red,line cap=round] (\x,-\y) -- (\x,1-\y);}{};
      }
      \draw[line cap=round] (0,1-\y-1) -- (\w-1,-\y);
      \ifthenelse{\y=0}
        {\draw[line cap=round] (0,1-\y) -- (\w-1,1-\y);}
        {};
  }
  \end{scope}
}
\newcommand{\permutation}[3]{
  \begin{scope}[shift={#1}]
    \foreach \v [count=\x from 0] in {#3} {
      \node[text height=1.5ex,text depth=.25ex] at (\x+0.5,-#2+0.5) {$\v$};
      % \pgfmathparse{dim(\row)};
      % \pgfmathsetmacro{\w}{\pgfmathresult};
      % \foreach \b [count=\x from 0] in \row {
      %   \ifthenelse{\b=1}
      %     {\draw[line cap=round] (\x,-\y) -- (\x,1-\y);}
      %     {\draw[line width=1.15,loosely dotted,line cap=round] (\x,-\y) -- (\x,1-\y);};
      % }
      % \draw[line cap=round] (0,1-\y-1) -- (\w-1,-\y);
      % \ifthenelse{\y=0}
      %   {\draw[line cap=round] (0,1-\y) -- (\w-1,1-\y);}
      %   {};
  }
  \end{scope}
}
%%
% usage: \sortingpaths{<origin>}{<perm-length>}{<length-of-trail>}{<sorting-trail>}
%%
\newcommand{\sortingpaths}[4]{
  \begin{scope}[shift={#1}, xscale=0.9, yscale=1.3]
    \foreach \row [count=\y from 1] in {#4} {
      \foreach \b [count=\x from 1] in \row {
        \draw (\x,-\y) node[draw=black,circle,font=\footnotesize,inner sep=2.5pt] (n-\y-\b) {\b};
      }
    }
    \foreach \b in {1,2,...,#2} {
      \foreach \y [count=\yprev from 1] in {2,3,...,#3} {
        \draw[-] (n-\yprev-\b) -- (n-\y-\b);
      }
    }
  \end{scope}
}


\section{Introduction}

Knuth~\cite[Exercise~2.2.1.5]{knuth1968art} noted that permutations
sortable by a stack are precisely those that do not contain a
subsequence in the same relative order as the permutation $231$.  This
exercise inspired a wide range of research and can be seen as the
starting point of the research field we now call permutation patterns.
Our interest lies in Knuth's original exercise and its variations.

In 1972 Tarjan~\cite{tarjan1972sorting} considered sorting with networks
of stacks and queues, a problem that, in general, has proven itself to
be beyond the reach of current methods in permutation patterns and
enumeration.  There has been some recent significant progress though: In
2015 Albert and Bousquet-M{\'e}lou~\cite{albert2015permutations}
enumerated permutations sortable by two stacks in parallel.
The enumeration of permutations sortable by
two stacks in series is, however, an open problem. A related problem is
that of sorting permutations by $k$ passes through a stack, where the
elements on the stack are required to be increasing when read from top
to bottom. West~\cite{west1990permutations} characterized the
permutations sortable by two passes through a stack in terms of pattern
avoidance and conjectured their enumeration, a conjecture that was
subsequently proved by
Zeilberger~\cite{zeilberger1992proof}. Permutations sortable by three
passes have been characterized by
\'Ulfarsson~\cite{ulfarsson2012describing}, but their enumeration is
unknown.

In other variations of Knuth's exercise different data structures are
used for sorting. One notable example is that of pop-stacks: a stack
where each pop operation completely empties the stack. Avis and
Newborn~\cite{avis1981pop} enumerated the permutations sortable by
pop-stacks in series, with the modification that each pop leads to the
popped elements being immediately pushed to the following
pop-stack. Atkinson and Stitt~\cite{atkinson2002restricted} considered
two pop-stacks in genuine series. Permutations sortable by pop-stacks in
parallel have been studied by Atkinson and Sack~\cite{atkinson1999pop},
who characterized those permutations by a finite set of forbidden
patterns. They also conjectured that the generating function for their
enumeration is rational, which was subsequently proved by Smith and
Vatter~\cite{smith2009enumeration}, who gave an insertion
encoding~\cite{albert2005insertion} for the sortable permutations.

Pudwell and Smith~\cite{pudwell2017} recently
characterized the permutations sortable by two passes through a pop-stack in
terms of pattern avoidance and gave their enumeration. They also gave a
bijection between certain families of polyominoes and the permutations sortable
by one or two passes through a pop-stack, but noted that the bijection does not
generalize to three passes.
% We consider, more generally, the permutations sortable by $k$ passes. In particular,
We give an algorithm to
derive a rational generating function for the permutations sortable
by $k$ passes through a pop-stack, for any fixed $k$.

\section{Sorting plans and traces}

\begin{wrapfigure}{R}{0.41\textwidth}
\centering
\begin{tikzpicture}[line width=\customwidth, scale=\customscale]
  \useasboundingbox (0,-0.5) rectangle (9,1);
  \comparray{(0.0,0)}{{1,0,0,1,1,0,1,0,0,1}};
  \permutation{(0.0,0)}{0}{7,5,2,4,9,1,8,6,3};
  \permutation{(0.0,0)}{1}{2,5,7,4,1,9,3,6,8};
\end{tikzpicture}
    \caption{Single-pass sorting trace}
    \label{fig:example_sorting_trace_1}
\end{wrapfigure}
A single pass of the pop-stack sorting operator formally works as
follows. Processing a permutation $\pi=a_1a_2\dots a_n$ of
$[n]=\{1,\dots,n\}$ from left to right, if the stack is empty or its top
element is smaller than the current element $a_i$ then perform a single
pop operation ($\A$), emptying the stack and appending those elements to
the output permutation; else do nothing ($\D$). Next, push $a_i$ onto the
stack and proceed with element $a_{i+1}$, or if $i=n$ perform one final
pop operation ($\A$), again emptying the stack onto the output
permutation, and terminate. Define $P(\pi)$ as the final output
permutation and $\word(\pi)$ as the word over the alphabet $\{\A,\D\}$
defined by the operations performed when processing $\pi$.  For
instance, with $\pi=752491863$ we have $P(\pi)=257419368$ and
$\word(\pi)=\A\D\D\A\A\D\A\D\D\A$. Note that $\word(\pi)$ will always
begin and end with the letter $\A$. We will call any word of length $n+1$
with letters in $\{\A,\D\}$ that begin and end with the letter $\A$ an
\emph{operation sequence}.

Let us now introduce what we call sorting traces.  Consider applying the
pop-stack operator $P$ to a permutation $\pi$ of $[n]$. Start by interleaving $w(\pi)$
with $\pi$; for instance, with $\pi=752491863$ (as before) we have
$\A 7\D 5\D 2\A 4\A 9\D 1\A 8\D 6\D 3 \A$.  Replacing $\A$ with a bar
and $\D$ with a space, and placing $P(\pi)$ below this string, we get
Figure~\ref{fig:example_sorting_trace_1}.

We call the numbers between pairs of successive \A's \emph{blocks}. Above,
the blocks of $\pi$ are $752$, $4$, $91$, and $863$.
Note that $P(\pi)$ can be obtained from $\pi$ by reversing each block.
An index $i\in[n-1]$ of a permutation $\pi=a_1a_2\dots a_n$ is an
\emph{ascent} if $a_i<a_{i+1}$.
Similarly, $i$ is a \emph{descent} if $a_i>a_{i+1}$. With this terminology
 $\word(\pi) = c_1c_2\dots c_{n+1}$ is simply the ascent/descent word of
$-\infty\hspace{1pt}\pi\hspace{1pt}\infty$; i.e.\ $c_1=c_{n+1}=\A$ and, for $2\leq i\leq n$,
$c_i = \A$ if $i-1$ is an ascent, and $c_i = \D$ if $i-1$ is a descent.
\begin{wrapfigure}{R}{0.37\textwidth}
\centering
\begin{tikzpicture}[line width=\customwidth, scale=\customscale]
  \useasboundingbox (0,-3.5) rectangle (9,1);
  \comparray{(0.0,0)}{{1,0,0,1,1,0,1,0,0,1},
    {1,1,1,0,0,1,0,1,1,1},
    {1,1,0,1,1,0,1,0,1,1},
    {1,0,1,0,0,1,0,1,0,1}};
  \permutation{(0.0,0)}{0}{7,5,2,4,9,1,8,6,3};
  \permutation{(0.0,0)}{1}{2,5,7,4,1,9,3,6,8};
  \permutation{(0.0,0)}{2}{2,5,1,4,7,3,9,6,8};
  \permutation{(0.0,0)}{3}{2,1,5,4,3,7,6,9,8};
  \permutation{(0.0,0)}{4}{1,2,3,4,5,6,7,8,9};
\end{tikzpicture}
    \caption{A sorting trace}
    \label{fig:example_sorting_trace_2}
\end{wrapfigure}

A figure such as Figure~\ref{fig:example_sorting_trace_1} can be
extended to depict multiple passes. Applying $P$ to the example permutation,
$\pi$, until it is sorted gives
Figure~\ref{fig:example_sorting_trace_2}.
\begin{wrapfigure}{R}{0pt}
\centering
$
\begin{array}{c}
  \A\,\D\,\D\,\A\,\A\,\D\,\A\,\D\,\D\,\A \\[-0.6ex]
  \A\,\A\,\A\,\D\,\D\,\A\,\D\,\A\,\A\,\A \\[-0.6ex]
  \A\,\A\,\D\,\A\,\A\,\D\,\A\,\D\,\A\,\A \\[-0.6ex]
  \A\,\D\,\A\,\D\,\D\,\A\,\D\,\A\,\D\,\A
\end{array}
$
    \caption{}
    \label{fig:example_sorting_trace_3}
\end{wrapfigure}

We will call such figures sorting traces, or traces for short.
The structure that remains when removing the numbers from a trace we
call its sorting plan.  Each row of a sorting plan corresponds to an operation
sequence, and for convenience we shall number the rows $1$ through $k$,
from top to bottom. The example sorting plan can be viewed as the
array of operation sequences given in Figure~\ref{fig:example_sorting_trace_3}.
By interpreting each column as a binary number with $a=0$ and $d=1$ the
sorting plan can more compactly be represented, or \emph{encoded}, with
the sequence of numbers
0, 9, 10, 5, 5, 10, 5, 10, 9, 0.
Formally, we define a trace and its sorting plan as follows.

\begin{definition}
    \label{def:trace}
    Let $A = (\alpha_1,\alpha_2,\ldots,\alpha_k,\alpha_{k+1})$ be a
    $(k+1)$-tuple of permutations of $[n]$ in which $\alpha_{k+1}$ is the
    identity permutation. Let
    $M = (\mu_1,\mu_2,\ldots,\mu_k)$ be a $k$-tuple of
    operation sequences, each of length $n+1$.
    We call $T=(A,M)$ a \emph{trace} of \emph{length} $n$ and
    \emph{order} $k$, and $M$ its \emph{sorting plan}, if the following
    conditions are satisfied for $i=1,\ldots,k$:
    \begin{enumerate}
    \item\label{traceprop1} The word $\mu_i$ records the sequence of
      operations performed by the pop-stack operator when applied to
      $\alpha_i$---in symbols, $\word(\alpha_i)=\mu_i$. As to the
      picture of the trace, two adjacent numbers form an ascent if and
      only if they are separated by a bar.
    \item\label{traceprop2} The sequence of permutations in $A$ records
      repeated application of the pop-stack operator to the permutation
      $\alpha_1$---in symbols, $P(\alpha_i) = \alpha_{i+1}$.  Or,
      assuming the first condition is satisfied,
      $\rev(\alpha_i,\mu_i) = \alpha_{i+1}$, where the operator $\rev$
      is defined below.
    \end{enumerate}
\end{definition}

\begin{definition}
  \label{def:rev}
  Let $\pi$ be a permutation of $[n]$ and $\mu=c_1c_2\dots c_{n+1}$ be an
  operation sequence. Let
  $i_1< i_2< \dots< i_k$ be the sequence of indices $i$ for which
  $c_i=\A$.  Write $\pi=\gamma_1\gamma_2\dots\gamma_{k-1}$, where
  $|\gamma_j|=i_{j+1}-i_{j}$ for $j=1,\dots,k-1$. In other words, the
  length of $\gamma_j$ is the same as the length of the $j$th block of
  $\pi$ with respect to $\mu$.  Define
  $\rev(\pi,\mu) = \gamma_1^r\gamma_2^r\dots\gamma_{k-1}^r$, where $(\,\cdot\,)^r$ is the reversal operator.
  We call this the \emph{blockwise reversal of $\pi$ according to $\mu$}.
\end{definition}

Much of the information stored in a trace is redundant:
As we have seen, $\alpha_1$ alone determines the complete
trace. Similarly, from the sorting plan $M$
we can recover $\alpha_1$, \dots, $\alpha_{k+1}$. This is
because the last permutation $\alpha_{k+1}$ is the identity,
the permutation $\alpha_k$ is the blockwise reversal of $\alpha_{k+1}$ according to $\mu_k$,
the permutation $\alpha_{k-1}$ is the blockwise reversal of $\alpha_{k}$ according to $\mu_{k-1}$, etc.
In symbols, $\rev(\alpha_i,\mu_i) = \alpha_{i+1}$ if and only if
$\alpha_i = \rev(\alpha_{i+1},\mu_i)$. In this way a sorting plan uniquely
determines a trace.

Our goal is to count the permutations of $[n]$ that are sortable by $k$
passes through a pop-stack and for brevity we will sometimes
refer to such permutations as \emph{$k$-pop-stack-sortable}.
Note that a $k$-pop-stack-sortable permutation is also $(k+1)$-pop-stack-sortable.
Starting with a $k$-pop-stack-sortable permutation of $[n]$ and
performing $k$ passes of the pop-stack sorting operator results in a
trace of length $n$ and order $k$. Conversely, the first row of that
trace is the $k$-pop-stack-sortable permutation we started with. Thus,
$k$-pop-stack-sortable permutations of $[n]$ are in one-to-one
correspondence with traces of length $n$ and order $k$. Those are, in
turn, in one-to-one correspondence with their sorting plans, and hence
it suffices to count sorting plans of length $n$ and order $k$.

Let us call any $k$-tuple of operation sequences of length $n+1$ an
\emph{operation array} of length $n+1$ and order $k$. Note that
sorting plans are operation arrays, but not all operation arrays are sorting plans.
Let an operation array $(\mu_1,\mu_2,\ldots,\mu_k)$ be given. Let the
permutations $\alpha_1$, $\alpha_2$, \ldots, $\alpha_{k+1}$ be defined
by requiring that the permutation $\alpha_{k+1}$ is the identity,
the permutation $\alpha_k$ is the blockwise reversal of $\alpha_{k+1}$ according to $\mu_k$,
the permutation $\alpha_{k-1}$ is the blockwise reversal of $\alpha_{k}$ according to $\mu_{k-1}$,
etc. In symbols, $\rev(\alpha_i,\mu_i) = \alpha_{i+1}$. Then
the tuple $(\alpha_1,\ldots,\alpha_{k+1})$ is called a
\emph{semitrace}. In other words, a semitrace is defined by requiring
that Property~\ref{traceprop2} of Definition~\ref{def:trace} holds, but
not necessarily Property~\ref{traceprop1} of the same definition.

We shall characterize those operation arrays
that are sorting plans, then count the sorting plans of order $k$, and by
extension the $k$-pop-stack-sortable permutations. We start by
considering cases where $k$ is small.

\subsection{1-pop-stack-sortable permutations}

\begin{wrapfigure}{R}{0.37\textwidth}
\centering
\begin{tikzpicture}[line width=\customwidth, scale=\customscale]
  \useasboundingbox (0,-0.5) rectangle (8,1);
  \comparray{(0.0,0)}{{1,0,0,1,1,0,1,0,1}};
  \permutation{(0.0,0)}{0}{3,2,1,4,6,5,8,7};
  \permutation{(0.0,0)}{1}{1,2,3,4,5,6,7,8};
\end{tikzpicture}
    \caption{Semitrace for $\A\D\D\A\A\D\A\D\A$}
    \label{fig:some_semitrace}
\end{wrapfigure}
We want to determine which operation sequences of length $n+1$ when
interpreted as operation arrays are sorting plans.  Consider the
operation sequence $\A\D\D\A\A\D\A\D\A$.  The semitrace corresponding to
it is given in Figure~\ref{fig:some_semitrace}.
Is this a trace? By definition of a semitrace it satisfies
Property~\ref{traceprop2} of Definition~\ref{def:trace}, but does it
also satisfy Property~\ref{traceprop1}? Yes, because the bottom-most
permutation is the identity, any two adjacent numbers separated by a bar
form an ascent, and two adjacent numbers within a block form a descent.
Thus, each operation sequence represents a sorting plan of order 1.  An
operation sequence starts and ends with the letter $\A$. The remaining
letters can be either $\A$ or $\D$. Thus, for $n>0$, there are $2^{n-1}$
operation sequences of length $n+1$, and hence $2^{n-1}$
1-pop-stack-sortable permutations of $[n]$. It is easy to see that these
are precisely the layered permutations (direct sums of decreasing
permutations).

While this simple example outlines our approach to count $k$-pop-stack-sortable
permutations, it is a little too simple, as for larger $k$, most operation
arrays will not be sorting plans. As an example, we present the following
lemma.
\begin{lemma}
    \label{lem:blocks3}
  In a trace of order $2$ or greater, each operation sequence---except for
  the first one---contains at most $2$ consecutive $\D$'s. Or, equivalently,
  each row of the sorting plan---except for the first one---has blocks of size at
  most $3$.
\end{lemma}
\begin{proof}
  Given a trace of order $2$ or greater, consider any block
  $a_1 > a_2 > \cdots > a_k$ from any row of its sorting plan, excluding
  the first row. For contradiction, assume that $k\geq 4$. The
  neighborhood around the block then looks as in
  Figure~\ref{fig:proof3a}.
  \begin{figure}
    \centering
    \begin{minipage}{0.5\textwidth}
      \centering
      \begin{tikzpicture}[line width=\customwidth, yscale=\customscale*1.1, xscale=\customscale*1.55]
        \useasboundingbox (0,-1+0.2) rectangle (6,1);
        \comparray{(0.0,0)}{{2,2,2,2,2,2,2},{1,0,0,0,0,0,1}};
        \permutation{(0.0,0)}{0}{,,,\hspace{0.2em}\cdots,,};
        \permutation{(0.0,0)}{1}{a_1,a_2,a_3,\hspace{0.2em}\cdots,a_{k-1},a_k};
      \end{tikzpicture}
      \captionof{figure}{The neighborhood around a given block, where
        a dotted line can either be a bar or not}
      \label{fig:proof3a}
    \end{minipage}%
    \begin{minipage}{0.5\textwidth}
      \centering
      \begin{tikzpicture}[line width=\customwidth, yscale=\customscale*1.1, xscale=\customscale*1.55]
        \useasboundingbox (0,-1+0.2) rectangle (6,1);
        \comparray{(0.0,0)}{{2,1,1,1,1,1,2},{1,0,0,0,0,0,1}};
        \permutation{(0.0,0)}{0}{,a_2,a_3,\hspace{0.2em}\cdots,a_{k-1},};
        \permutation{(0.0,0)}{1}{a_1,a_2,a_3,\hspace{0.2em}\cdots,a_{k-1},a_k};
      \end{tikzpicture}
      \captionof{figure}{The same neighborhood, as to the left, after
        inferring the status of most dotted lines}
      \label{fig:proof3b}
    \end{minipage}
    \vspace{-1em}
  \end{figure}
  Consider the dotted lines in the upper row, except for the
  two outermost dotted lines. If any of them were not solid, then at least two
  of $a_1,a_2,\ldots,a_k$ would be together in a block. These two
  elements would occur in increasing order, violating Property~\ref{traceprop1}
  of Definition~\ref{def:trace}. These dotted lines must thus be solid, as
  is illustrated in Figure~\ref{fig:proof3b}.
  Now, however, $a_2$ and $a_3$ are two adjacent numbers in distinct
  blocks that do not form an ascent, again violating
  Property~\ref{traceprop1}.
\end{proof}

This lemma characterizes a certain class of operation arrays that are not sorting
plans, namely those that have at least one block of size $4$ or larger in rows
$2$ to $k$. In the next section we will take a more general approach towards
characterizing operation arrays that are not sorting plans by introducing
what we call forbidden segments.

\section{Forbidden segments}

A semitrace fails to be a trace precisely when there is a pair of elements
witnessing Property~\ref{traceprop1} of Definition~\ref{def:trace}
fail. With the following definition we single out such pairs.

\begin{definition}\label{def:violating_pair}
  Let $T$ be a semitrace of length $n$ and let $a$ and $b$ be two
  distinct elements of $[n]$. We call $(a,b)$ a \emph{violating pair} of
  $T$ if, in any row, $a$ and $b$ occur in adjacent positions such that
  they violate Property~\ref{traceprop1}. That is, $a$ and $b$ form a
  descent and are separated by a bar, or $a$ and $b$ form an ascent and
  are not separated by a bar.
\end{definition}

From Definitions~\ref{def:trace} and~\ref{def:violating_pair} we
get the following characterization of sorting plans.
\begin{lemma}\label{lem:invalid_skeleton_violating_pair}
  An operation array is a sorting plan if and only if its semitrace
  has no violating pair. % $(a,b)$.
\end{lemma}

\begin{definition}
  Let $\psi$ be the bijection mapping a sorting plan to its encoding.
  Let $M$ be a sorting plan of length $n$ and suppose that
  $1\leq i\leq j\leq n+1$. Let $\psi(M) = c_1c_2\ldots c_{n+1}$ be the encoding of
  $M$. Then we call $S = \psi^{-1}(c_ic_{i+1}\ldots c_{j})$ a
  \emph{segment} of $M$, and $|S| = j-i+1$ its length.
\end{definition}

\begin{definition}
  Let $T=(A,M)$ be a semitrace of length $n$ and let $a$ and $b$ be two
  distinct elements of $[n]$. Let $B$ be the set of blocks that contain either
  $a$ or $b$, excluding blocks in the first row. We define \emph{the segment of $T$
  determined by $a$ and $b$}, denoted $T_{a,b}$, as the smallest segment of $M$
  that fully contains all the blocks in $B$.
\end{definition}

% For instance, the segment $T_{4,5}$ of the trace
% $$
% \begin{tikzpicture}[line width=\customwidth, scale=\customscale]
%   \useasboundingbox (0,-2.5) rectangle (8,1);
%   \comparray{(0.0,0)}{
%     {1,0,1,1,0,0,0,0,1},
%     {1,1,1,0,1,1,1,1,1},
%     {1,1,1,1,0,1,1,1,1}};
%   \permutation{(0.0,0)}{0}{2,1,5,8,7,6,4,3};
%   \permutation{(0.0,0)}{1}{1,2,5,3,4,6,7,8};
%   \permutation{(0.0,0)}{2}{1,2,3,5,4,6,7,8};
%   \permutation{(0.0,0)}{3}{1,2,3,4,5,6,7,8};
% \end{tikzpicture}
% $$
% is the length 3 sorting plan
% $$
%   \begin{tikzpicture}[line width=\customwidth, scale=\customscale]
%     \useasboundingbox (0,-2+0.2) rectangle (3,1);
%     \comparray{(0.0,0)}{
%       {1,1,0,0},
%       {1,0,1,1},
%       {1,1,0,1}};
%   \end{tikzpicture}
% $$


\begin{figure}
  \begin{minipage}{0.5\textwidth}
  \centering
      \vspace{-2em}
\begin{tikzpicture}[line width=\customwidth, scale=\customscale]
  \useasboundingbox (0,-5+0.5) rectangle (8,1);
  \comparray{(0.0,0)}{
    {1,0,0,1,1,0,0,0,1},
    {1,0,1,0,1,1,1,0,1},
    {1,1,0,1,0,0,1,1,1},
    {1,0,1,0,1,1,0,1,1},
    {1,1,0,1,0,1,1,1,1}};
  \permutation{(0.0,0)}{5}{1,2,3,4,5,6,7,8};
  \permutation{(0.0,0)}{4}{1,3,2,5,4,6,7,8};
  \permutation{(0.0,0)}{3}{3,1,5,2,4,7,6,8};
  \permutation{(0.0,0)}{2}{3,5,1,7,4,2,6,8};
  \permutation{(0.0,0)}{1}{5,3,7,1,4,2,8,6};
  \permutation{(0.0,0)}{0}{7,3,5,1,6,8,2,4};
\end{tikzpicture}
      \captionof{figure}{An example semitrace}
  \label{fig:example-semitrace-1}
  \end{minipage}%
  \begin{minipage}{0.5\textwidth}
  \centering
\begin{tikzpicture}[line width=\customwidth, scale=\customscale]
  \useasboundingbox (0,-5+0.4) rectangle (8,1);
  \comparray{(0.0,0)}{
    {1,0,0,1,1,0,0,0,1},
    {1,0,1,0,1,1,1,0,1},
    {1,1,0,1,0,0,1,1,1},
    {1,0,1,0,1,1,0,1,1},
    {1,1,0,1,0,1,1,1,1}};
  \draw[black] (1.5,-4.5) --
               (2.5,-3.5) --
               (3.5,-2.5) --
               (5.5,-1.5) --
               (5.5,-0.5) --
               (6.5,0.5);
  \draw[black] (3.5,-4.5) --
               (4.5,-3.5) --
               (4.5,-2.5) --
               (4.5,-1.5) --
               (4.5,-0.5) --
               (7.5,0.5);
  \foreach \y/\x in {5/1,
                     4/2,
                     3/3,
                     2/5,
                     1/5,
                     0/6,
                     5/3,
                     4/4,
                     3/4,
                     2/4,
                     1/4,
                     0/7} {
      \fill[white] (\x+0.5,-\y+0.5) circle [radius=0.85em];
      \draw[black] (\x+0.5,-\y+0.5) circle [radius=0.85em];
  };
  \permutation{(0.0,0)}{5}{1,2,3,4,5,6,7,8};
  \permutation{(0.0,0)}{4}{1,3,2,5,4,6,7,8};
  \permutation{(0.0,0)}{3}{3,1,5,2,4,7,6,8};
  \permutation{(0.0,0)}{2}{3,5,1,7,4,2,6,8};
  \permutation{(0.0,0)}{1}{5,3,7,1,4,2,8,6};
  \permutation{(0.0,0)}{0}{7,3,5,1,6,8,2,4};
\end{tikzpicture}
      \captionof{figure}{The progress of $2$ and $4$ through the semitrace to the left}
  \label{fig:example-semitrace-2}
  \end{minipage}
\vspace{-1em}
\end{figure}

\begin{figure}
  \begin{minipage}{0.5\textwidth}
  \centering
      % \vspace{-2em}
\begin{tikzpicture}[line width=\customwidth, scale=\customscale]
  \useasboundingbox (0,-4+0.2) rectangle (5,1);
  \comparray{(0.0,0)}{
    {0,0,1,1,0,0},
    {0,1,0,1,1,1},
    {1,0,1,0,0,1},
    {0,1,0,1,1,0},
    {1,0,1,0,1,1}};
\end{tikzpicture}
      \captionof{figure}{The segment $T_{2,4}$ of the trace above}
  \label{fig:example-semitrace-3}
  \end{minipage}%
  \begin{minipage}{0.5\textwidth}
  \centering
  \begin{tikzpicture}[line width=\customwidth, scale=\customscale]
    \useasboundingbox (0,-4.6) rectangle (5,1);
    \comparray{(0.0,0)}{
      {0,0,1,1,0,0},
      {0,1,0,1,1,1},
      {1,0,1,0,0,1},
      {0,1,0,1,1,0},
      {1,0,1,0,1,1}};
    \draw[black] (0.5,-4.5) --
                 (1.5,-3.5) --
                 (2.5,-2.5) --
                 (4.5,-1.5) --
                 (4.5,-0.5);
    \draw[black,densely dotted] (4.5,-0.5) -- (4.5,0.5);
    \draw[black] (2.5,-4.5) --
                 (3.5,-3.5) --
                 (3.5,-2.5) --
                 (3.5,-1.5) --
                 (3.5,-0.5);
    \draw[black,dotted] (3.5,-0.5) -- (5.5,0.5);

    \draw[black,dotted] (5,1) --
                        (6.5,1) --
                        (6.5,0) --
                        (5,0);

    \foreach \y/\x in {5/1,
                       4/2,
                       3/3,
                       2/5,
                       1/5,
                       0/5,
                       5/3,
                       4/4,
                       3/4,
                       2/4,
                       1/4,
                       0/6} {
        \fill[white] (\x-1+0.5,-\y+0.5) circle [radius=0.85em];
        \draw[black] (\x-1+0.5,-\y+0.5) circle [radius=0.85em];
      };
    \permutation{(0.0,0)}{5}{a,,b,,,,};
    \permutation{(0.0,0)}{4}{,a,,b,,,};
    \permutation{(0.0,0)}{3}{,,a,b,,,};
    \permutation{(0.0,0)}{2}{,,,b,a,,};
    \permutation{(0.0,0)}{1}{,,,b,a,,};
    \node[text height=1.5ex,text depth=.25ex] at (4.5,0.5) {$a$};
    \node[text height=1.5ex,text depth=.25ex] at (5.5,0.5) {$b$};
  \end{tikzpicture}
      \captionof{figure}{Following the elements $a$ and $b$ up the segment to the left}
  \label{fig:example-semitrace-4}
  \end{minipage}
\vspace{-1em}
\end{figure}

As an example, consider the semitrace in Figure~\ref{fig:example-semitrace-1}.
It contains four violating pairs, namely $(1,5)$, $(2,4)$, $(3,5)$, and
$(6,8)$. Looking at the pair $(2,4)$, Figure~\ref{fig:example-semitrace-2}
shows how these two numbers progress through the trace.
The segment $T_{2,4}$, shown in Figure~\ref{fig:example-semitrace-3}, is the smallest segment that contains all blocks
on rows $2$, $3$, $4$, and $5$ with at least one circled element.

Any sorting plan of order $5$ that contains this segment, no matter where
it occurs horizontally, will violate Property~\ref{traceprop1}, just as the
above semitrace. This is because we can follow the two elements $a$ and $b$ playing
the roles of $2$ and $4$ from the bottom to the second row, as shown in Figure~\ref{fig:example-semitrace-4}.
Formally, we make the following definition.
\begin{definition}\label{def:forbidden_segment}
  A segment
  $T_{a,b}$ is \emph{forbidden} if, after inferring the positions of
  $a$ and $b$ in rows $2$ to
  $k$, either the two numbers violate Property~\ref{traceprop1} on row
  $i$, where $2 \leq i \leq k$, or
  \begin{enumerate}
  \item\label{forbidden_segment_case_1} $a$ and $b$ form a descent on row $2$ and, if
    $a$ and $b$ are in columns $i$ and $i+1$ on row $2$, there is no bar
    separating columns $i$ and $i+1$ on row $1$, or
  \item\label{forbidden_segment_case_2} $a$ and
    $b$ are in decreasing order on row $2$ and, if $a$ and
    $b$ are in columns $i$ and $j$ on row $2$, with
    $i<j$, there is a bar immediately to the left of column
    $i$ on row $1$, a bar immediately to the right of column $j$ on row
    $1$, and exactly one bar between columns $i$ and $j$ on row $1$.
  \end{enumerate}
  In both cases the bars that we reference belong to the segment
  $T_{a,b}$. In other words, we can determine if
  $T_{a,b}$ is forbidden or not without knowing in which semitrace it is embedded.
\end{definition}

\begin{lemma}\label{lem:forbidden_segment_violating_pair}
  A segment $T_{a,b}$ is forbidden if and only if $(a,b)$ is a violating
  pair of $T$.
\end{lemma}
\begin{proof}
  Consider a forbidden segment $T_{a,b}$. If, after inferring the
  positions of $a$ and $b$ in rows $2$ to $k$, the two numbers violate
  Property~\ref{traceprop1} on row $i$, where $2\leq i\leq k$, then
  $(a,b)$ is a violating pair of $T$. Otherwise we have two cases,
  corresponding to the two cases of Definition~\ref{def:forbidden_segment},
  and these are illustrated in Figures~\ref{fig:forbidden_segment_1} and
  \ref{fig:forbidden_segment_2}, respectively.
  In the first case $a$ and  $b$ form an ascent and are in the same block on row $1$.
  In the second case $a$ and $b$ form a descent and are separated by a bar on row $1$.
  In both cases we have found a violation of Property~\ref{traceprop1}
  and hence $(a,b)$ is a violating pair of $T$.

  Conversely, consider a violating pair $(a,b)$ of $T$, as well as the
  segment $T_{a,b}$. If $a$ and $b$ violate Property~\ref{traceprop1} on row
  $i$, where $2\leq i\leq k$, then $T_{a,b}$ is a forbidden segment. If, on
  the other hand, the two numbers violate Property~\ref{traceprop1} on row $1$, then
  we have two cases.

  If $a$ and $b$ form an ascent on row $1$ and are not separated by a
  bar, then the two numbers are in the same block on row $1$, and will
  form a descent on row $2$. Furthermore, if the two numbers are in
  columns $i$ and $i+1$ on row $2$, there will not be a bar separating
  columns $i$ and $i+1$ on row $1$. Hence $T_{a,b}$ is a forbidden
  segment.

  If $a$ and $b$ form a descent on row $1$ and are
  separated by a bar, then the two numbers are in adjacent blocks on row
  $1$. If $i$ is the leftmost column that the left block intersects, and
  $j$ is the rightmost column that the right block intersects, then the
  two numbers will be in decreasing order on row $2$, with the larger
  number number in column $i$ and the smaller number in column $j$.
  Furthermore, there is a bar immediately to the left of column $i$ on
  row $1$ and a bar immediately to the right of column $j$ on row $1$,
  and exactly one bar between columns $i$ and $j$ on row $1$. Hence
  $T_{a,b}$ is a forbidden segment.
\end{proof}
\begin{figure}
  \begin{minipage}{0.5\textwidth}
  \centering
  \begin{tikzpicture}[line width=\customwidth, scale=\customscale, xscale=0.8]
    \useasboundingbox (-1,0.5) rectangle (13,2.5);
    \draw (0,2) rectangle (12,1);
    \begin{scope}[every node/.style={text height=1.5ex,text depth=.25ex}]
      \node at (2.5, 1.5) {$a$}; \node at ( 3.5, 1.5) {$b$};
      \node at (8.5, 0.5) {$b$}; \node at ( 9.5, 0.5) {$a$};
      \foreach \y in {1,2} {
        \node at (-0.8,-\y+2.5) {$\scriptstyle{\y}$};
      }
      \foreach \y in {1,2} { % invisible numbers on rhs
        \node[white] at (12.8,-\y+2.5) {$\scriptstyle{\y}$};
      }
      \node at (8.5, 2.5) {$\scriptstyle{i}$};
      \node at (9.5, 2.5) {$\scriptstyle{i+1}$};
    \end{scope}
  \end{tikzpicture}
  \captionof{figure}{The first case of Definition~\ref{def:forbidden_segment}, assuming $a<b$}
  \label{fig:forbidden_segment_1}
  \end{minipage}%
  \begin{minipage}{0.5\textwidth}
  \centering
  \begin{tikzpicture}[line width=\customwidth, scale=\customscale, xscale=0.8]
    \useasboundingbox (-1,0.5) rectangle (13,2.5);
    \draw (0,2) rectangle (6,1); \draw (6,2) rectangle (12,1);
    \begin{scope}[every node/.style={text height=1.5ex,text depth=.25ex}]
      \node at (5.5, 1.5) {$b$}; \node at (  6.5, 1.5) {$a$};
      \node at (0.5, 0.5) {$b$}; \node at ( 11.5, 0.5) {$a$};
      \foreach \y in {1,2} {
        \node at (-0.8,-\y+2.5) {$\scriptstyle{\y}$};
      }
      \foreach \y in {1,2} { % invisible numbers on rhs
        \node[white] at (12.8,-\y+2.5) {$\scriptstyle{\y}$};
      }
      \node at ( 0.5, 2.5) {$\scriptstyle{i}$};
      \node at (11.5, 2.5) {$\scriptstyle{j}$};
    \end{scope}
  \end{tikzpicture}
  \captionof{figure}{The second case of Definition~\ref{def:forbidden_segment}, assuming $a<b$}
  \label{fig:forbidden_segment_2}
  \end{minipage}
    \vspace{-2em}
\end{figure}

From Lemmas~\ref{lem:invalid_skeleton_violating_pair} and
\ref{lem:forbidden_segment_violating_pair} we get the following result.
\begin{lemma}\label{lem:operation_array_skeleton}
  An operation array is a sorting plan if and only if it does not contain
  any forbidden segment $T_{a,b}$.
\end{lemma}

Because there are potentially an infinite number of forbidden segments
$T_{a,b}$ this lemma is of limited practical use as stated. This
motivates the following definition.

\begin{definition}
  A segment of order $k$ is \emph{bounded} if each of its blocks in rows
  $2$ to $k$ has size at most $3$. Equivalently, a segment is bounded
  if its operation array has no occurrence of three consecutive \D's on
  rows $2$ to $k$.
\end{definition}

Combining
Lemmas~\ref{lem:blocks3}~and~\ref{lem:operation_array_skeleton} we
arrive at the following proposition.

\begin{proposition}\label{prop:operation_array_skeleton_bounded}
  An operation array is a sorting plan if and only if it does not contain any
  bounded forbidden segment $T_{a,b}$ and each block on rows $2$ through $k$ is
  of size at most $3$.
\end{proposition}

Through a series of lemmas we shall establish that there are finitely many
bounded forbidden segments $T_{a,b}$ of order $k$, for any fixed $k$.

\begin{lemma}\label{lem:forbidden_segment_bound}
    Let $T$ be a semitrace of length $n$ and order $k$ and let $a$ and $b$ be
    two distinct elements of $[n]$. If $T_{a,b}$ is a bounded segment, and there is
    a block, not on the first row, that includes both $a$ and $b$, then
    $|T_{a,b}| \leq 4k-5$.
\end{lemma}
\begin{proof}
  We can disregard the first row, as neither this lemma nor the
  definition of $T_{a,b}$ includes blocks on that row. Since $T_{a,b}$
  is a bounded segment, each of the remaining blocks that either
  contains $a$ or $b$ has size at most $3$. Thus, if we consider two adjacent
  rows and $x\in\{a,b\}$, then the horizontal distance
  between $x$ in the upper row and $x$ in the lower row is at most
  $2$. In total, the horizontal distance between $x$ on the second row
  and $x$ on the $k$-th row is at most $2(k-2)$ and, consequently,
  the length of the segment $T_{a,b}$ is at most $4(k-2)+m$, where
  $m\leq 3$ is the size of the block containing $a$ and $b$.
\end{proof}

\begin{lemma}\label{lem:block_with_ab}
    Let $T$ be a semitrace and $(a,b)$ a violating pair of $T$. Then there
    is a block, not on the first row, that includes both $a$ and $b$.
\end{lemma}
\begin{proof}
    Consider a row $i$ where the pair $(a,b)$ violates
    Property~\ref{traceprop1}.
    If $a$ and $b$ form a descent and are separated by a bar, then
    the two elements are in distinct blocks on row $i$, and will
    still be in descending order on row $i+1$ after performing the
    blockwise reversals.
    If, on the hand, $a$ and $b$ form an ascent and are not separated by a bar,
    then the two elements are in the same block on row $i$, and will
    be in descending order on row $i+1$ after performing the
    blockwise reversals.
    In either case, $a$ and $b$ will be in descending order on row
    $i+1$. Since the two elements are in increasing order in the last
    permutation the two elements must be reversed on at least one of the
    rows between $i+1$ and $k$. As the relative order of elements is
    only reversed when they appear together in a block, there is a
    block on one of the rows between $i+1$ and $k$ that includes both
    $a$ and $b$.
\end{proof}

\begin{lemma}\label{lem:finite_forbidden_segments}
  For a fixed $k$, there are finitely many bounded forbidden segments $T_{a,b}$
  of order $k$, and they can be listed.
\end{lemma}
\begin{proof}
  If $T_{a,b}$ is a bounded forbidden segment then $(a,b)$ is a
  violating pair by
  Lemma~\ref{lem:forbidden_segment_violating_pair}. Using
  Lemma~\ref{lem:block_with_ab} we find a block, not on the first row,
  that includes $a$ and $b$; and
  Lemma~\ref{lem:forbidden_segment_bound} gives $|T_{a,b}|\leq
  4k-5$. Thus, there are at most as many forbidden segments as there are
  words in $\{\A,\D\}^{(4k-5)k}$, and they can be listed by checking
  against Definition~\ref{def:forbidden_segment}.
\end{proof}

\section{Regular language}

We will use the characterization of sorting plans in terms of
forbidden segments to count sorting
plans of order $k$, and hence the $k$-pop-stack-sortable
permutations. To that end, we will employ the theory of formal
languages. We will assume that the reader is familiar with basic
constructions such as taking the complement of a deterministic finite
automaton (DFA) or the intersection of two DFAs~\cite{hopcroft2001introduction}.

Recall that we can encode an operation array of length $n$ and order $k$ as a
sequence of $n$ integers, each in the range $[0,2^k-1]$.
In this way we can consider operation arrays as strings of a formal language over the
alphabet $\Sigma = \{0,1,\ldots,2^k-1\}$. Conversely, strings over this
alphabet can be considered as operation arrays, under one condition: that they both
begin and end with a solid boundary. Noting that a solid boundary corresponds
to the integer $0$ from $\Sigma$, and letting $\overline{0} =
\Sigma\setminus\{0\}$, the DFA $W$ in
Figure~\ref{fig:DFA-solid}
recognizes the strings over $\Sigma$ that begin and end with a solid boundary,
i.e.\ the strings that correspond to an operation array.

\begin{figure}
  \begin{minipage}{0.47\textwidth}
    \qquad
    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
                        semithick,state/.prefix style={scale=0.7}]
      \node[initial,state] (A) {};
      \node[accepting,state] (B) [right of=A] {};
      \node[state] (C) [right of=B] {};
      \node[state] (D) [below right of=A] {};

      \path (A) edge node {$0$} (B)
        (B) edge[bend left] node {$\overline{0}$} (C)
        (C) edge[bend left] node {$0$} (B)
        (B) edge[loop above] node {$0$} (B)
        (C) edge[loop above] node {$\overline{0}$} (C)
        (D) edge[loop right] node {$\Sigma$} (D)
        (A) edge node {$\overline{0}$} (D);
    \end{tikzpicture}
    \captionof{figure}{A DFA recognizing strings that begin and end with a solid boundary}
    \label{fig:DFA-solid}
  \end{minipage}%
  \begin{minipage}{0.53\textwidth}
    \qquad
    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
      semithick,state/.prefix style={scale=0.7}]
      \node[initial,accepting,state] (A) {};
      \node[accepting,state] (B) [below right of=A] {};
      \node[accepting,state] (C) [above right of=B] {};
      \node[state] (D) [right of=C] {};

      \path (A) edge[bend left] node {$\overline{A_i}$} (B)
      (B) edge[bend right] node {$\overline{A_i}$} (C)
      (C) edge node {$\overline{A_i}$} (D)
      (D) edge[loop above] node {$\Sigma$} (D)
      (A) edge[loop above] node {$A_i$} (A)
      (B) edge[bend left] node[below] {$A_i$} (A)
      (C) edge[bend right] node[above] {$A_i$} (A);
    \end{tikzpicture}
    \captionof{figure}{A DFA that when intersected with $W$ recognizes
      operation arrays with blocks of size at most $3$ in row $i$}
    \label{fig:DFA-3}
  \end{minipage}
    \vspace{-2em}
\end{figure}

For ease of notation we will use the name of a DFA to also denote the
language that it recognizes. Here, $W$ denotes the DFA recognizing
strings that begin and end with a solid boundary as well as the language
consisting of such strings. We want to find the subset of $W$
corresponding to sorting plans. Recall from
Proposition~\ref{prop:operation_array_skeleton_bounded} that an operation array is
a sorting plan if and only if it does not contain any bounded forbidden segments and
each block on rows $2$ through $k$ is of size at most $3$. We shall start
with the latter condition.

If $A_i$ is the set of symbols from $\Sigma$ that represent a column
from the operation array that has a bar in the $i$th row, and $\overline{A_i} =
\Sigma\setminus A_i$, then the intersection of $W$ with the automaton, $R_i$, in Figure~\ref{fig:DFA-3} recognizes the operation
arrays that have blocks of size at most $3$ in row $i$.
Therefore, the set of operation arrays that have blocks of size at most $3$ in
all but the first row is recognized by the automaton $W\cap R_2 \cap \cdots \cap R_k$.

The other condition that sorting plans satisfy is that they do not contain any
bounded forbidden segments. Consider a segment $M$ and let us encode it in the
same manner as we encode operation arrays, resulting in the sequence
$m_1,\ldots,m_{\ell}$. Note that an operation array $A$ contains $M$
if and only if the encoding of $A$ contains $m_1\cdots m_{\ell}$ as a factor.
Furthermore, the following nondeterministic finite automaton (NFA), $Q_M$, recognizes
the set of strings over $\Sigma$ that contain the encoding of $M$ as a
factor:
\vspace{-0.4em}
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.3cm,
                    semithick,state/.prefix style={scale=0.7}]
    \node[initial,state] (A) {};
    \node[state] (B) [right of=A] {};
    \node[scale=0.7] (C) [right of=B] {$\;\ldots\,$};
    \node[state] (D) [right of=C] {};
    \node[accepting,state] (E) [right of=D] {};
    \path (A) edge node {$m_1$} (B)
          (B) edge node {$m_2$} (C)
          (C) edge node {$m_{\ell-1}$} (D)
          (D) edge node {$m_{\ell}$} (E)
          (A) edge[loop above] node {$\Sigma$} (A)
          (E) edge[loop above] node {$\Sigma$} (E);
\end{tikzpicture}\vspace{-0.4em}
\end{center}
Taking the complement of $Q_M$ we get an automaton $\overline{Q_M}$ that
recognizes the set of strings over $\Sigma$ that do not contain the factor
$M$. In particular, if $F$ is a forbidden segment, then $W\cap \overline{Q_F}$
recognizes the set of operation arrays that do not contain $F$.
Let $\mathcal{F}$ be the set of bounded forbidden segments, which is finite by
Lemma~\ref{lem:finite_forbidden_segments}. Then the automaton
\[
    S = W\cap \bigcap_{i=2}^k R_i \cap \bigcap_{F\in\mathcal{F}} \overline{Q_F}
\]
recognizes the set of operation arrays that have blocks of size at most $3$ in
rows $2$ through $k$, and do not contain any bounded forbidden segments. Hence, by
Proposition~\ref{prop:operation_array_skeleton_bounded}, $S$ recognizes exactly
the set of sorting plans, giving us the following proposition:
\begin{proposition}\label{prop:skel_regular}
    % The set of encoded sorting plans forms a regular language.
    The language $S = \{\ w\in\Sigma^{*}\ |\ w\text{ is a sorting plan}\ \}$ is regular.
\end{proposition}

We can now present our main theorem.
\begin{theorem}
  For a fixed $k$, the generating function
  $P(x) = \sum_{n=0}^{\infty}p_{n} x^{n}$, where $p_{n}$
  is the number of $k$-pop-stack-sortable permutations of length $n$, is
  rational.
\end{theorem}
\begin{proof}
    We have a bijection between the $k$-pop-stack-sortable permutations of
    length $n$ and the sorting plans of order $k$ and length $n$, so the two sets
    are equinumerous. The sorting plans of length $n$ are in bijection with words
    of length $n+1$ recognized by the automaton $S$, which is regular by
    Proposition~\ref{prop:skel_regular}. It is well known that regular languages have
    rational generating functions~\cite{schutzenberger1961definition}, and
    they can be derived from the corresponding DFA by setting up a system of
    linear equations. If $S(x)$ is the rational generating function for
    $S$, it is clear that $P(x) = S(x)/x$ and that this generating function
    is rational.
\end{proof}

Note that all of the above results are constructive, meaning that the
generating function can be computed for any fixed $k$.
\begin{table}
    \centering
    \newcolumntype{L}{>{\centering\arraybackslash}m{0.98\textwidth}}
    % \newcolumntype{L}{>{\centering\arraybackslash}m{1.8\textwidth}}
    {\small
    \begin{tabular}{cL}
        $k$ & Generating function \\[0.6em]

        $1$ & $(x - 1)/(2x - 1)$ \\[0.5em]
        $2$ & $(x^{3} + x^{2} + x - 1)/(2x^{3} + x^{2} + 2x - 1)$ \\[0.7em]
        $3$ & $(2x^{10} + 4x^{9} + 2x^{8} + 5x^{7} + 11x^{6} + 8x^{5} + 6x^{4} + 6x^{3} + 2x^{2} + x - 1)/(4x^{10} + 8x^{9} + 4x^{8} + 10x^{7} + 22x^{6} + 16x^{5} + 8x^{4} + 6x^{3} + 2x^{2} + 2x - 1)$ \\[0.7em]
        $4$ & $(64x^{25} + 448x^{24} + 1184x^{23} + 1784x^{22} + 2028x^{21} + 1948x^{20} + 1080x^{19} + 104x^{18} - 180x^{17} + 540x^{16} + 1156x^{15} + 696x^{14} + 252x^{13} + 238x^{12} + 188x^{11} + 502x^{10} + 806x^{9} + 544x^{8} + 263x^{7} + 185x^{6} + 99x^{5} + 33x^{4} + 13x^{3} + 3x^{2} + x - 1)/(128x^{25} + 896x^{24} + 2368x^{23} + 3568x^{22} + 3928x^{21} + 3064x^{20} + 176x^{19} - 2304x^{18} - 2664x^{17} - 1580x^{16} - 352x^{15} - 576x^{14} - 1104x^{13} - 760x^{12} - 138x^{11} + 686x^{10} + 1238x^{9} + 869x^{8} + 382x^{7} + 210x^{6} + 102x^{5} + 27x^{4} + 12x^{3} + 3x^{2} + 2x - 1)$
    \end{tabular}
    }
    \caption{The generating functions for the $k$-pop-stack-sortable permutations, $k\leq 4$}
    \label{tbl:generating_functions}
\end{table}
We did so for $k=1,\ldots,6$ and in
Table~\ref{tbl:generating_functions} we list the resulting generating
functions, except for $k=5$ and $k=6$ whose expressions are too large to
display.  For each of them the degree of the polynomial in the numerator
is the same as the degree of the polynomial in the denominator.
Those degrees, the growth rates of coefficients of the generating functions,
and the corresponding sequences for the
number of vertices and edges in the final DFAs can be found in the table
below.
$$
{\small
\begin{array}{c|cccccc}
  k & 1 & 2 & 3 & 4 & 5 & 6 \\\hline
  \text{degree} &1&3&10&25&71&213 \\
  \text{growth rate} & 2.0000 & 2.6590 & 3.4465 & 4.2706 & 5.1166 & 5.9669 \\
  \text{vertices}&4&5&12&32&99&339 \\
  \text{edges}&8&11&34&120&477&2010
\end{array}
}
$$
All the generating functions, source code, and text files defining the
DFAs can be found on GitHub~\cite{popstacksgithub}. The growth rate of
the coefficients of a rational power series $p(x)/q(x)$ is given by
$\max\{1/|\zeta|: q(\zeta)=0\}$ and Sage~\cite{sage} code for
calculating the approximate growth rates, in the table above, can be found
on the same GitHub page.

It would be interesting to find a closed formula for the generating
functions, possibly leading to the distribution of the number of passes
needed to sort a permutation using a pop-stack. It is not clear whether
our approach can be used as a basis for such a formula.  Finally, as we
only considered their enumeration, finding a useful permutation pattern
characterization of the $k$-pop-stack-sortable permutations, for
$k\geq 3$, remains open.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
