\documentclass[finalversion]{FPSAC2020}
\articlenumber{4}
\addbibresource{fpsac.bib}

\usepackage{tabu}
\usepackage{makecell}

\DeclareMathOperator{\DL}{\Lambda\hspace{-.095cm}\Lambda}
\DeclareMathOperator{\rot}{rot}
\DeclareMathOperator{\swu}{swu}
\DeclareMathOperator{\swl}{swl}
\DeclareMathOperator{\Av}{Av}
\DeclareMathOperator{\NC}{NC}
\DeclareMathOperator{\PC}{PC}
\DeclareMathOperator{\Int}{Int}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\des}{des}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\crefname{theorem}{Theorem}{Theorems}
\crefname{conjecture}{Conjecture}{Conjectures}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\crefname{example}{Example}{Examples}




\title[Uniquely Sorted Permutations]{Uniquely Sorted Permutations}

\author{Colin Defant\thanks{\href{mailto:cdefant@princeton.edu}{cdefant@princeton.edu}. Supported by a Fannie and John Hertz Foundation Fellowship and an NSF Graduate Research Fellowship.}\addressmark{1}}


\address{\addressmark{1}Department of Mathematics, Princeton University, Princeton, NJ, USA}

\received{\today}


%\revised{}

\abstract{We say a permutation is \emph{uniquely sorted} if it has exactly $1$ preimage under West's stack-sorting map. In this extended abstract, we describe some of the rich enumerative structure that the set of such permutations possesses. After stating a characterization of uniquely sorted permutations, we study their enumeration, which is given by Lassalle's sequence and is connected to free probability theory. We then consider five well-studied classes of posets defined on Dyck paths, establishing bijections between uniquely sorted permutations that avoid various patterns and intervals in these posets. We end with several conjectures.}

\keywords{permutations, stack-sorting, uniquely sorted, Lassalle's sequence, free probability theory, poset intervals}



\begin{document}

\maketitle

\section{Introduction}

A \emph{permutation} is an ordering of a set of positive integers, which we view as a word. Let $S_n$ denote the set of permutations of $[n]:=\{1,\ldots,n\}$. The \emph{normalization} (sometimes called the \emph{standardization}) of a permutation $\pi=\pi_1\cdots\pi_n$ is the permutation in $S_n$ obtained by replacing the $i^{\text{th}}$-smallest entry in $\pi$ with $i$ for all $i$. For example, the normalization of $3649$ is $1324$. A permutation is \emph{normalized} if it is equal to its normalization. Given $\tau\in S_m$, we say a permutation $\sigma=\sigma_1\cdots\sigma_n$ \emph{contains the pattern} $\tau$ if there exist indices $i_1<\cdots<i_m$ in $[n]$ such that the normalization of $\sigma_{i_1}\cdots\sigma_{i_m}$ is $\tau$. We say $\sigma$ \emph{avoids} $\tau$ if it does not contain $\tau$. Let $\Av_n(\tau^{(1)},\ldots,\tau^{(r)})$ denote the set of permutations in $S_n$ that avoid the patterns $\tau^{(1)},\ldots,\tau^{(r)}$, and let $\Av(\tau^{(1)},\ldots,\tau^{(r)})=\bigcup_{n\geq 0}\Av_n(\tau^{(1)},\ldots,\tau^{(r)})$. 

The enormous body of research concerning permutation patterns began in the 1960's with Knuth's analysis of a ``stack-sorting algorithm'' in his book \emph{The Art of Computer Programming} \cite{Knuth}. Our focus is on West's stack-sorting map, one of the variants of Knuth's algorithm that has received the most vigorous attention. This function, which we denote by $s$, initially appeared in West's Ph.D. thesis in 1990 \cite{West}. The simplest way to define the map $s$ is as follows. First, $s$ sends the empty permutation to itself. If $\pi$ is a nonempty permutation, then we can write $\pi=LmR$, where $m$ is the largest entry in $\pi$. We then define $s(\pi)=s(L)s(R)m$. For example, 
\[s(416352)=s(41)\,s(352)\,6=s(1)\,4\,s(3)\,s(2)\,56=143256.\] We refer the reader to \cite{BonaSurvey, DefantCounting, DefantEngenMiller} and the references therein for the history of the stack-sorting map and related stack-sorting variants. 
  
Traditionally, researchers have taken interest in \emph{$t$-stack-sortable} permutations, which are the permutations $\pi$ such that $s^t(\pi)$ is increasing. Here, $s^t$ denotes the $t$-fold iterate of $s$. It follows from Knuth's analysis of his stack-sorting algorithm \cite{Knuth} that a permutation is $1$-stack-sortable if and only if it avoids the pattern $231$ and that the number of such permutations in $S_n$ is the Catalan number $C_n=\frac{1}{n+1}{2n\choose n}$. Settling a conjecture of West, Zeilberger proved \cite{Zeilberger} that the number of $2$-stack-sortable permutations in $S_n$ is $\frac{2}{(n+1)(2n+1)}{3n\choose n}$. There are now several proofs of this formula (see \cite{DefantCounting} and the references therein), but they are all somewhat arduous. For each fixed $t\geq 3$, the set of $t$-stack-sortable permutations is extremely complicated \cite{DefantCounting}. 

West defined the \emph{fertility} of a permutation $\pi$ to be $|s^{-1}(\pi)|$ \cite{West}. At a first glance, computing fertilities is very complicated. Indeed, West devoted ten pages of his thesis to computing the fertilities of some very specific permutations (a total of $3n-4$ permutations in $S_n$). Bousquet-M\'elou defined a permutation to be \emph{sorted} if its fertility is positive \cite{Bousquet}. She also found an algorithm for determining if a given permutation is sorted. 

Throughout its first 25 years of existence, the investigation of West's stack-sorting map was full of very difficult questions concerning complicated sets of permutations. Indeed, $t$-stack-sortable permutations and sorted permutations appear to be devoid of much structure and, hence, are excruciatingly difficult to understand. However, after developing methods for computing the fertilities of arbitrary permutations, the current author found that there is actually a huge amount of interesting combinatorial structure lurking beneath the surface of the stack-sorting map (see \cite{DefantCatalan,DefantCounting,
DefantEngenMiller} and the references therein). The goal of the present extended abstract is to expose one of the manifestations of this structure: the set of uniquely sorted permutations. 

\begin{definition}[\cite{DefantEngenMiller}]
We say a permutation is \emph{uniquely sorted} if its fertility is $1$. Let $\mathcal U_n$ be the set of uniquely sorted permutations in $S_n$. Let $\mathcal U_n(\tau^{(1)},\ldots,\tau^{(r)})$ be the set of permutations in $\mathcal U_n$ that avoid the patterns $\tau^{(1)},\ldots,\tau^{(r)}$. 
\end{definition}

This extended abstract is a summary of the main results from the papers \cite{DefantEngenMiller} and \cite{DefantCatalan}. The first of these papers introduces and characterizes uniquely sorted permutations and enumerates them via a bijection (which we will not describe here) with certain weighted matchings. In fact, this bijection is the restriction of a larger bijection that connects new combinatorial objects called ``valid hook configurations'' with the classical cumulants of the free Poisson law. The paper \cite{DefantCatalan} gives bijections between some sets of pattern-avoiding uniquely sorted permutations and sets of intervals in posets of Dyck paths. One of the interesting features here is that finding bijections that connect uniquely sorted permutations to other objects is often not nearly as difficult as proving that these maps are actually injective and/or surjective (though finding the maps is still difficult). Therefore, we have omitted the proofs, directing the reader to the relevant articles where they appear. We end with several conjectures, many (but not all) of which were proved in a recent paper by Mularczyk \cite{Hanna}. 

\section{Counting Uniquely Sorted Permutations}\label{Sec:Counting}

A \emph{descent} of a permutation $\pi=\pi_1\cdots\pi_n$ is an index $i\in[n-1]$ such that $\pi_i>\pi_{i+1}$. The following theorem characterizes uniquely sorted permutations.

\begin{theorem}[\cite{DefantEngenMiller}]\label{Thm1}
A permutation $\pi=\pi_1\cdots\pi_n$ is uniquely sorted if and only if it is sorted and has exactly $\frac{n-1}{2}$ descents.
\end{theorem}

One immediate consequence of the preceding theorem is that every uniquely sorted permutation has odd length. In order to make use of \cref{Thm1}, we need a method for determining whether or not a given permutation is sorted. We describe such a method next; it is essentially equivalent to the method described by Bousquet-M\'elou in \cite{Bousquet}.  

The \emph{plot} of a permutation $\pi=\pi_1\cdots\pi_n$ is the graph in $\mathbb R^2$ showing the points $(i,\pi_i)$ for all $i\in[n]$. A \emph{hook} $H$ of $\pi$ is drawn by starting at a point $(i,\pi_i)$, moving vertically upward, and then moving horizontally to the right to connect with another point $(j,\pi_j)$. The point $(i,\pi_i)$ is called the \emph{southwest endpoint} of $H$, and $(j,\pi_j)$ is called the \emph{northeast endpoint}. We say a point $(\ell,\pi_\ell)$ \emph{lies weakly below} $H$ if $i<\ell\leq j$ and $\pi_\ell\leq \pi_j$. For example, the image on the left in \cref{Fig1} shows the plot of a permutation along with a single hook whose southwest endpoint is $(5,9)$ and whose northeast endpoint is $(11,11)$. The points lying weakly below this hook are $(6,4)$, $(7,8)$, $(8,1)$, $(9,6)$, $(10,10)$, and $(11,11)$. 

\begin{figure}[h]
\begin{center}
\includegraphics[width=.7\linewidth]{UniquelySortedPIC2}
\caption{On the left is the plot of $2\,7\,3\,5\,9\,4\,8\,1\,6\,10\,11\,12$ along with one hook. The right image shows the canonical hook configuration of this permutation.}
\label{Fig1}
\end{center}  
\end{figure} 

Suppose we are given a permutation $\pi$ with descents $d_1<\cdots<d_k$. We will attempt to construct hooks $H_k^*,\ldots,H_1^*$ (building them in this order). In general, we choose $H_\ell^*$ to be the hook with southwest endpoint $(d_\ell,\pi_{d_\ell})$ whose northeast endpoint is the lowest point in the plot of $\pi$ that lies above and to the right of $(d_\ell,\pi_{d_\ell})$ and does not lie weakly below any of the hooks $H_k^*,\ldots,H_{\ell+1}^*$ that have already been constructed. If this procedure succeeds, we call $(H_1^*,\ldots,H_k^*)$ the \emph{canonical hook configuration} of $\pi$. On the other hand, if at any time during this procedure the hook $H_\ell^*$ does not exist, then $\pi$ does not have a canonical hook configuration. See the right image in \cref{Fig1} for an example. 

The next theorem follows from the much more general result that appears as Theorem 5.1 in \cite{DefantPostorder}. 

\begin{theorem}[\cite{DefantPostorder}]\label{Thm2}
A permutation is sorted if and only if it has a canonical hook configuration.
\end{theorem}

\cref{Thm1,Thm2} give us a decent understanding of uniquely sorted permutations; we now describe their enumeration. Define a sequence $(A_m)_{m\geq 1}$ via the recurrence relation 
\[A_m=(-1)^{m-1}C_m+\sum_{j=1}^{m-1}(-1)^{j-1}{2m-1\choose 2m-2j-1}A_{m-j}C_j
\] along with the initial condition $A_1=1$. As before, $C_r$ is the $r^\text{th}$ Catalan number. Zeilberger conjectured that the terms in this sequence are all positive and, furthermore, that they are increasing. This sequence is known as \emph{Lassalle's sequence} because Lassalle proved Zeilberger's conjecture using symmetric functions and hypergeometric series \cite{Lassalle}. According to Lassalle, Novak pointed out that $(-1)^{m-1}A_m$ is the $(2m)^\text{th}$ classical cumulant of the standard semicircular probability distribution. Josuat-Verg\`es then found a combinatorial interpretation for the terms in Lassalle's sequence via certain matchings that are weighted by values of the Tutte polynomials of certain graphs \cite{Josuat}. In \cite{DefantEngenMiller}, Engen, Miller, and the current author showed that the classical cumulants of the free Poisson law with rate $\lambda$ can be computed as simple sums over valid hook configurations. The proof relies on an intricate bijection that, when restricted to uniquely sorted permutations, yields the following theorem as a corollary. 

\begin{theorem}[\cite{DefantEngenMiller}]\label{Thm3}
For every $k\geq 0$, we have $|\mathcal U_{2k+1}|=A_{k+1}$. 
\end{theorem} 

\cref{Thm3} leads to an interesting refinement of Lassalle's sequence. Let $A_{k+1}(\ell)$ denote the number of permutations $\pi=\pi_1\cdots\pi_{2k+1}\in \mathcal U_{2k+1}$ such that $\pi_1=\ell$. It is rare that one would study the first entry of a permutation, but that is because this statistic is usually not too interesting. This is certainly not the case in the context of uniquely sorted permutations. 

\begin{theorem}[\cite{DefantEngenMiller}]\label{Thm4}
If $k\geq 0$ and $1\leq \ell\leq 2k+1$, then $A_{k+1}(\ell)=A_{k+1}(2k+2-\ell)$. In other words, the sequence $A_{k+1}(1),\ldots,A_{k+1}(2k+1)$ is symmetric.  
\end{theorem}

The stack-sorting map tries to transform a permutation $\pi\in S_n$ into a permutation $s(\pi)$ that is ``closer'' than $\pi$ to the identity permutation $123\cdots n$. Therefore, we should expect permutations with many preimages under $s$ to be close to the identity, meaning that they should begin with small numbers. Conversely, we should expect permutations with few preimages to start with large numbers. \cref{Thm4} tells us that the uniquely sorted permutations achieve a perfect balance in their first entries. In other words, when it comes to the fertility of a permutation, $1$ is not too big and not too small (this makes sense because $1$ is the average fertility of a permutation in $S_n$). That being said, \cref{Thm4} is not at all clear from the definition of a uniquely sorted permutation; the proof relies heavily on the bijection used to establish \cref{Thm3}. In fact, the following specific corollary is also not obvious \emph{a priori}.  

\begin{corollary}
If $k\geq 1$, then there are no permutations in $\mathcal U_{2k+1}$ that start with the entry $1$.
\end{corollary}

\begin{proof}
It is immediate from the definition of the stack-sorting map that every sorted permutation in $S_{2k+1}$ ends with the entry $2k+1$. In particular, the elements of $\mathcal U_{2k+1}$ all end with the entry $2k+1$. This implies that $A_{k+1}(2k+1)=0$, so it follows from \cref{Thm4} that $A_{k+1}(1)=0$. 
\end{proof}

There is one other strange interpretation of the numbers $A_{k+1}(\ell)$ that is a consequence of the bijection used to prove \cref{Thm3}. If $\pi\in\mathcal U_n$, then we know by \cref{Thm1} that $\pi$ has exactly $\frac{n-1}{2}$ descents in $\{1,\ldots,n-1\}$. Let $r$ be the largest element of $\{1,\ldots,n-1\}$ such that $\pi$ has exactly $\frac{n-r}{2}$ descents in $\{r,\ldots,n-1\}$. We call the entry $\pi_{r+1}$ the \emph{hotspot} of the permutation $\pi$. 

\begin{theorem}[\cite{DefantEngenMiller}]\label{Thm5}
For $k\geq 0$, there are $A_{k+1}(\ell)$ permutations in $\mathcal U_{2k+1}$ with hotspot $\ell-1$.  
\end{theorem}

\begin{example}
One can check that $A_3=5$, so there are $5$ uniquely sorted permutations in $S_5$. These are $21435$, $31425$, $32415$, $32145$, $42135$. Inspecting the first entries in these permutations shows that the sequence $(A_3(\ell))_{\ell=1}^5$ is $0,1,3,1,0$. The hotspots of these permutations are, in order, $3,2,1,2,2$, and this agrees with \cref{Thm5}. 
\end{example}

\section{Pattern-Avoiding Uniquely Sorted Permutations} 

A \emph{Dyck path of semilength} $k$ is a lattice path in the plane consisting of $k$ $(1,1)$ steps (also called \emph{up steps}) and $k$ $(1,-1)$ steps (also called \emph{down steps}) that starts at the origin and never passes below the horizontal axis. Letting $U$ and $D$ denote up steps and down steps, respectively, we can view a Dyck path of semilength $k$ as a word over the alphabet $\{U,D\}$ that contains $k$ copies of each letter and has the property that every prefix has at least as many $U$'s as it has $D$'s. It is well known that the number of such paths is $C_k$. 

Let ${\bf D}_k$ be the set of Dyck paths of semilength $k$. In this section, we consider five natural partial orders on ${\bf D}_k$. Some of these partial orders are more commonly defined on other sets of objects counted by Catalan numbers, but one can use bijections to transfer the orders to the sets ${\bf D}_k$. We omit the definitions of some of the following partial orders, but they can all be found in \cite{Bernardi} and \cite{DefantCatalan}. We also direct the curious reader to the references in those two articles for more historical information about these posets. 

\begin{itemize}
\item The $k^\text{th}$ \emph{Stanley lattice} $\mathcal L_k^S=({\bf D}_k,\leq_S)$ is a distributive lattice defined by declaring that $\Lambda\leq_S\Lambda'$ if $\Lambda$ lies below or is equal to $\Lambda'$.
\item The $k^\text{th}$ \emph{Tamari lattice} $\mathcal L_k^T=({\bf D}_k,\leq_T)$ is a well-studied lattice appearing in combinatorics, group theory, theoretical computer science, algebraic geometry, and algebraic topology. Their Hasse diagrams are the $1$-skeletons of associahedra.  
\item The $k^\text{th}$ \emph{noncrossing partition lattice} $\mathcal L_k^K=({\bf D}_k,\leq_K)$ (also called the $k^\text{th}$ \emph{Kreweras lattice}) is really just the lattice $\NC_k$ of noncrossing partitions ordered by refinement. We have transferred this order from noncrossing partitions to Dyck paths for the sake of consistency among the underlying sets in our various posets. Noncrossing partition lattices play a prominent role in a variety of areas, especially free probability theory. 
\item The $k^\text{th}$ \emph{Pallo comb poset} $\PC_k=({\bf D}_k,\leq_{\text{Pallo}})$ was introduced by Pallo in \cite{Pallo} as a natural subposet of the Tamari lattice $\mathcal L_k^T$. This order was originally defined on sets of binary trees, but we define it on ${\bf D}_k$ in \cite{DefantCatalan}.  
\item The antichain $\mathcal A_k$ is simply the poset on ${\bf D}_k$ with no nontrivial order relations.  
\end{itemize} 

\begin{figure}[h]
\begin{center}
\includegraphics[width=.72\linewidth]{UniquelySortedPIC3}
\caption{The Hasse diagrams of our Dyck path posets for $k=3$.}
\label{Fig3}
\end{center}  
\end{figure}

An \emph{interval} in a poset $P$ is a pair $(x,y)$ of elements of $P$ such that $x\leq y$. Let $\Int(P)$ be the set of intervals of $P$. Our goal in this section is to give an overview of some bijections between pattern-avoiding uniquely sorted permutations and intervals in the Dyck path posets defined above. 

\subsection{Stanley Lattices and $\mathcal U_{2k+1}(312)$}

Let $\pi=\pi_1\cdots\pi_{2k+1}\in\mathcal U_{2k+1}(312)$. By \cref{Thm1}, the permutation $\pi$ has $k$ descents. For $i\in[2k]$, let $\Lambda_i=D$ if $2k+1-i$ is a descent of $\pi$, and let $\Lambda_i=U$ otherwise. Let $\Lambda_i'=D$ if the entry $2k+1-i$ appears to the right of $2k+2-i$ in $\pi$, and let $\Lambda_i'=U$ otherwise. Form the words $\Lambda=\Lambda_1\cdots\Lambda_{2k}$ and  
$\Lambda'=\Lambda_1'\cdots\Lambda_{2k}'$ over the alphabet $\{U,D\}$, and let $\DL_k(\pi)=(\Lambda,\Lambda')$ (pronounce the symbol $\DL$ as ``double lambda''). See \cref{Fig4}. 

\begin{figure}[h]
\begin{center}
\includegraphics[width=.38\linewidth]{CatUniquePIC11}
\caption{An example illustrating the definition of $\DL_4$. Imagine taking the purple path drawn on the permutation and rotating it $180^{\circ}$ to obtain the purple Dyck path $\Lambda$ on the bottom. Similarly, rotate the green path drawn on the permutation by $90^{\circ}$ clockwise to obtain the \emph{reverse} of the green Dyck path $\Lambda'$ on the top.}
\label{Fig4}
\end{center} 
\end{figure} 

\begin{theorem}[\cite{DefantCatalan}]\label{Thm6}
For $k\geq 0$, the map $\DL_k:\mathcal U_{2k+1}(312)\to\Int(\mathcal L_k^S)$ is a bijection. Consequently, \[|\mathcal U_{2k+1}(312)|=C_kC_{k+2}-C_{k+1}^2=\frac{6}{(k+1)(k+2)^2(k+3)}{2k\choose k}{2k+2\choose k+1}.\]
\end{theorem}

The first statement in \cref{Thm6} is proven in \cite{DefantCatalan}. Although the definition of $\DL_k$ is fairly tame, the proof that it is a bijection is very involved. In fact, the proof of surjectivity relies on an ``energy argument'' similar to the one used to solve the game ``Conway's Soldiers.'' Note that it is not at all clear that the image of $\DL_k$ should even be contained in $\Int(\mathcal L_k^S)$. The formula appearing in the second half of \cref{Thm6} follows from the enumeration of intervals in Stanley lattices, which is due to De Sainte-Catherine and Viennot \cite{De}. 

\subsection{Tamari Lattices, $\mathcal U_{2k+1}(132)$, and $\mathcal U_{2k+1}(231)$}

For each $i\in[n]$, we define two ``sliding operators'' on $S_n$. The first, denoted\footnote{The name of the operator stands for ``southwest up.''} $\swu_i$, essentially takes the points in the plot of a permutation $\pi$ that lie southwest of the point with height $i$ and slides them up above all the points that are southeast of the point with height $i$. We illustrate this operator in \cref{Fig5}. To define this more precisely, let $L_i$ (respectively, $R_i$) be the set of elements of $[i-1]$ that lie to the left (respectively, right) of $i$ in $\pi$. If $\pi_j\geq i$, then the $j^\text{th}$ entry of $\swu_i(\pi)$ is $\pi_j$. If $\pi_j<\pi_i$, then either $\pi_j\in L_i$ or $\pi_j\in R_i$. If $\pi_j$ is the $m^\text{th}$-smallest element of $R_i$, then the $j^\text{th}$ entry of $\swu_i(\pi)$ is $m$. If $\pi_j$ is the $m^\text{th}$-largest element of $L_i$, then the $j^\text{th}$ entry of $\swu_i(\pi)$ is $i-m$.  

\begin{figure}[h]
\begin{center}
\includegraphics[width=.57\linewidth]{UniquelySortedPIC4}
\caption{The operator $\swu_6$ slides the points (shaded in pink) to the southwest of the point with height $6$ up above the points to the southeast (shaded in blue).}
\label{Fig5}
\end{center}  
\end{figure}

To define the second operator, we first define $\rot(\pi)$ (respectively, $\rot^{-1}(\pi)$) to be the permutation in $S_n$ whose plot is obtained by rotating the plot of $\pi$ counterclockwise (respectively, clockwise) by $90^\circ$. The second sliding operator is $\swl_i$, which is defined by \[\swl_i(\pi)=\rot^{-1}(\swu_i(\rot(\pi))).\] The map $\swl_i$ takes the points to the southwest of the point in position $i$ and slides them to the left. 

Define $\swu:S_n\to S_n$ and $\swl:S_n\to S_n$ by \[\swu=\swu_1\circ\swu_2\circ\cdots\circ\swu_n\quad\text{and}\quad\swl=\swl_1\circ\swl_2\circ\cdots\circ\swl_n.\] It is often convenient to consider the restrictions of $\swu$ and $\swl$ to $\Av(231)$ and $\Av(132)$. In \cite{DefantCatalan}, it is shown that $\swu:\Av(231)\to\Av(132)$ is a bijection; as far as we are aware, this bijection is new.\footnote{The paper \cite{DefantPolyurethane} provides a definition of the map $\swu^{-1}:\Av(132)\to\Av(231)$ that is completely different from the one given in \cite{DefantCatalan}. Namely, for $\pi\in\Av_n(132)$, we have $\swu^{-1}(\pi)=s(\pi)^{-1}\circ\pi$. Here, $s(\pi)^{-1}$ denotes the inverse of $s(\pi)$ in the group $S_n$, and $\circ$ denotes the operation in that group.} Transferring this result, one can then show that $\swl:\Av(132)\to\Av(312)$ is bijective as well.

We can now state the main theorem of this subsection. Recall the definition of $\DL_k$ from the previous subsection. 

\begin{theorem}[\cite{DefantCatalan}]\label{Thm7}
For $k\geq 0$, the maps \[\DL_k\circ\swl:\mathcal U_{2k+1}(132)\to\Int(\mathcal L_k^T)\quad\text{and}\quad\DL_k\circ\swl\circ\swu:\mathcal U_{2k+1}(231)\to\Int(\mathcal L_k^T)\] are bijections. Consequently, \[|\mathcal U_{2k+1}(132)|=|\mathcal U_{2k+1}(231)|=\frac{2}{(3k+1)(3k+2)}{4k+1\choose k+1}.\] 
\end{theorem}

As with \cref{Thm6}, the proof that the maps appearing in \cref{Thm7} are bijective is quite long and involved. The formula appearing in the second half of \cref{Thm7} follows from the enumeration of intervals in Tamari lattices, which is due to Chapoton \cite{Chapoton}.   

\subsection{Noncrossing Partition Lattices and $\mathcal U_{2k+1}(312,1342)$}

Recall that a set partition $\rho$ of the set $[k]$ is called \emph{noncrossing} if there do not exist distinct blocks $B,B'\in\rho$ and elements $i_1<i_2<i_3<i_4$ in $[k]$ with $i_1,i_3\in B$ and $i_2,i_4\in B'$. The noncrossing partition lattice $\NC_k$ is the lattice of noncrossing partitions of $[k]$ ordered by refinement (see \cite{Kreweras}). Earlier, we considered the lattice $\mathcal L_k^K$ defined on Dyck paths (for consistency), but it will be convenient to work with noncrossing partitions here. 

The article \cite{DefantCatalan} employs generating trees to show that permutations in $\mathcal U_{2k+1}(312,1342)$ are in bijection with intervals in $\NC_k$. It is possible to trace through the generating tree argument in order to obtain an explicit bijection, which we describe here.

Suppose we are given $\pi\in\mathcal U_{2k+1}(312,1342)$. Because $\pi$ is sorted, we know from \cref{Thm2} that it has a canonical hook configuration $\mathcal H=(H_1^*,\ldots,H_k^*)$. Let $\mathfrak W_1,\ldots,\mathfrak W_k$ be the northeast endpoints of the hooks in $\mathcal H$ listed in increasing order of height. Let $\mathfrak U_\ell$ be the southwest endpoint of the hook whose northeast endpoint is $\mathfrak W_\ell$. The \emph{partner} of $\mathfrak W_\ell$, which we denote by $\mathfrak V_\ell$, is the point immediately to the right of $\mathfrak U_\ell$ in the plot of $\pi$. Let $\rho$ and $\kappa$ be the partitions of $[k]$ obtained as follows. Place numbers $\ell,m\in [k]$ in the same block of $\rho$ if $\mathfrak V_\ell$ appears immediately above and immediately to the left of $\mathfrak V_m$ in the plot of $\pi$. Then, close all of these blocks by transitivity. Place numbers $\ell,m\in[k]$ in the same block of $\kappa$ if they are in the same block of $\rho$ or if $\mathfrak W_\ell$ appears immediately above and immediately to the left of $\mathfrak V_m$ in the plot of $\pi$. Then, close all of these blocks by transitivity. Let $\Upsilon_k(\pi)=(\rho,\kappa)$. \cref{Fig6} shows example applications of $\Upsilon_1,\Upsilon_2,\Upsilon_3,\Upsilon_4$. 

\begin{figure}[h]
\begin{center}
\includegraphics[width=.48\linewidth]{UniquelySortedPIC1}
\caption{Illustrations of the maps $\Upsilon_1,\Upsilon_2,\Upsilon_3,\Upsilon_4$. The uniquely sorted permutations are drawn with their canonical hook configurations. Each interval $(\rho,\kappa)$ of noncrossing partitions is drawn with $\rho$ below $\kappa$.} 
\label{Fig6}
\end{center}  
\end{figure}

As mentioned above, one can show that $\Upsilon_k:\mathcal U_{2k+1}(312,1342)\to\Int(\NC_k)$ is a bijection. Doing so amounts to showing that this map agrees with the bijection obtained using generating trees in \cite{DefantCatalan}. This was not written out explicitly in that article, but the proof of the following enumerative result (which follows from the generating tree argument) was. The specific formula in the next theorem comes from the enumeration of intervals in noncrossing partition lattices, which is due to Kreweras \cite{Kreweras}.
 
\begin{theorem}[\cite{DefantCatalan}]\label{Thm8}
For $k\geq 0$, we have $|\mathcal U_{2k+1}(312,1342)|=\displaystyle\frac{1}{2k+1}{3k\choose k}$. 
\end{theorem}

\subsection{Pallo Comb Posets and $\mathcal U_{2k+1}(231,4132)$}

Let $C(x)=\dfrac{1-\sqrt{1-4x}}{2x}$ be the generating function of the Catalan numbers. Aval and Chapoton \cite{Aval} proved that $\displaystyle\sum_{k\geq 0}|\Int(\PC_k)|x^k=C(xC(x))$. In \cite{DefantCatalan}, the author proved that the same generating function counts uniquely sorted permutations that avoid $231$ and $4132$. 

\begin{theorem}[\cite{DefantCatalan}]\label{Thm9}
We have $\displaystyle\sum_{k\geq 0}|\mathcal U_{2k+1}(231,4132)|x^k=C(xC(x))$. 
\end{theorem}

\subsection{Dyck Path Antichains}

Note that $|\Int(\mathcal A_k)|=|{\bf D}_k|=C_k$ since the intervals in the antichain $\mathcal A_k$ are simply the pairs of the form $(\Lambda,\Lambda)$ for $\Lambda\in{\bf D}_k$.  

\begin{theorem}[\cite{DefantCatalan}]\label{Thm10}
For every nonnegative integer $k$, we have \[|\mathcal U_{2k+1}(321)|=|\mathcal U_{2k+1}(231,312)|=|\mathcal U_{2k+1}(132,231)|=|\mathcal U_{2k+1}(132,312)|=C_k.\] In fact, we have bijections \[\DL_k:\mathcal U_{2k+1}(231,312)\to\Int(\mathcal A_k),\quad\DL_k\circ\swl:\mathcal U_{2k+1}(132,231)\to\Int(\mathcal A_k),\] \[\DL_k\circ\swu^{-1}:\mathcal U_{2k+1}(132,312)\to\Int(\mathcal A_k).\]
\end{theorem}

\section{Conjectures}

Recall from \cref{Sec:Counting} that $A_{k+1}(\ell)$ denotes the number of permutations in $\mathcal U_{2k+1}$ with first entry $\ell$ (by \cref{Thm5}, it is also the number of permutations in $\mathcal U_{2k+1}$ with hotspot $\ell-1$). We saw in \cref{Thm4} that the sequence $A_{k+1}(1),\ldots,A_{k+1}(2k+1)$ is symmetric. We also have the following conjecture. Recall that a sequence $a_1,\ldots,a_m$ of nonnegative real numbers is called \emph{log-concave} if $a_i^2\geq a_{i-1}a_{i+1}$ for all $i\in\{2,\ldots,m-1\}$.  

\begin{conjecture}[\cite{DefantEngenMiller}]\label{Conj1}
For $k\geq 0$, the sequence $A_{k+1}(1),\ldots,A_{k+1}(2k+1)$ is log-concave. 
\end{conjecture} 

The preceding conjecture implies the weaker statement that $A_{k+1}(1),\ldots,A_{k+1}(2k+1)$ is unimodal; this statement has also not been proven. It would be interesting to prove the unimodality of this sequence even if a proof of \cref{Conj1} remains elusive. 

The following table of 18 conjectures was given in \cite{DefantCatalan}. If $\tau^{(1)},\tau^{(2)}$ are the patterns in a given row, then the conjecture is that the numbers $\mathcal U_{2k+1}(\tau^{(1)},\tau^{(2)})$ appear as the corresponding OEIS sequence \cite{OEIS}. In the time since the preprint \cite{DefantCatalan} was posted, Mularczyk proved half of the conjectures in the table \cite{Hanna}. She used a mixture of generating function arguments and interesting bijections that link pattern-avoiding uniquely sorted permutations with Dyck paths, ${\bf S}$-Motzkin paths, and Schr\"oder paths. We have indicated the conjectures that she proved with the symbol ${\color{blue}\dagger}$. Mularczyk also posed the problem of considering sets of the form $\mathcal U_{2k+1}(\tau^{(1)},\tau^{(2)})$ with both $\tau^{(1)}$ and $\tau^{(2)}$ in $S_4$.  

{\tabulinesep=1.2mm
\begin{table}[h]
\footnotesize
\centering

\begin{tabu}{|c|[1.5pt]c|}

    \hline Patterns & Sequence \\\tabucline[2.5pt]{-}
    ${\color{blue}\dagger}$ $312,1432$ &  \\
    ${\color{blue}\dagger}$ $312,2431$ &  \\
    ${\color{blue}\dagger}$ $312,3421$ & A001764 \\
    ${\color{blue}\dagger}$ $132,3412$ &  \\
    ${\color{blue}\dagger}$ $231,1423$ &  \\\hline
    \hphantom{$\dagger$} $312,1243$ &  A122368 \\\hline
\end{tabu}
\quad
\begin{tabu}{|c|[1.5pt]c|}

    \hline Patterns & Sequence \\\tabucline[2.5pt]{-}
    ${\color{blue}\dagger}$ $132,3421$ &  \\
    ${\color{blue}\dagger}$ $132,4312$ & A001700 \\
    \hphantom{$\dagger$} $231,1243$ &  \\\hline \noalign{\vskip -.08cm}  
    \makecell{\,\,\hspace{.3cm}$132,2341$ \vspace{.05cm}\\ \hspace{.4cm}$132,4123$ \hspace{-.3cm}} & \hspace{.13cm}A109081 \vspace{-.155cm} \\\hline
    \hphantom{$\dagger$} $312,2341$ & A006605 \\\hline
\end{tabu}
\quad
\begin{tabu}{|c|[1.5pt]c|}

    \hline Patterns & Sequence \\\tabucline[2.5pt]{-}
    \hphantom{$\dagger$} $312,3241$ & A279569 \\\hline
    \hphantom{$\dagger$} $312,4321$ & A063020 \\\hline
    \hphantom{$\dagger$} $132,4231$ & A071725 \\\hline
    ${\color{blue}\dagger}$ $231,1432$ & A001003 \\\hline
    ${\color{blue}\dagger}$ $231,4312$ & A127632 \\\hline
    \hphantom{$\dagger$} $231,4321$ & A056010 \\\hline
\end{tabu}\vspace{.3cm}
\label{Tab1}
\end{table}}

\printbibliography

\end{document}
