%% 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]{FPSAC2024}
\articlenumber{80}
%% 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}

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

\usepackage{lipsum}
\usepackage{microtype}
\usepackage{url}
\usepackage{mathtools}
%\usepackage[hidelinks]{hyperref}
\usepackage[capitalize,noabbrev]{cleveref}
\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{color}
\usepackage{centernot}
\usepackage{enumitem}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}

\usepackage{ytableau}
\usepackage{todonotes}

\DeclareMathOperator{\Des}{\mathrm{D}}
\DeclareMathOperator{\st}{\,|\,}
\DeclareMathOperator{\comaj}{\mathrm{comaj}}
\DeclareMathOperator{\SYT}{\mathrm{SYT}}
\DeclareMathOperator{\Lin}{\mathcal{L}}
\DeclareMathOperator{\ddeg}{\mathrm{ddeg}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
%\DeclareMathOperator{\cat}{Cat}
\DeclareMathOperator{\krew}{Krew}
\DeclareMathOperator{\bfc}{{\bf c}}

\newcommand{\qbinom}{\genfrac{[}{]}{0pt}{}}
\newcommand{\rect}[2]{#1 \times #2}
\newcommand{\RPP}{\mathcal{RPP}}

\newcommand{\AL}[1]{{\color{purple}\sf #1}}
\newcommand{\SL}[1]{{\color{orange}\sf #1}}

%\newtheorem{thm}{Theorem}[section]
\newtheorem{question}[thm]{Question}
\newtheorem{remark}[thm]{Remark}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{example}[thm]{Example}
\newtheorem{conjecture}[thm]{Conjecture}


\newcommand{\dfn}[1]{\textcolor{blue}{\emph{#1}}}
\DeclareMathOperator{\val}{Val}
\DeclareMathOperator{\hor}{Hor}
\DeclareMathOperator{\rbmotz}{RBMotz}
\DeclareMathOperator{\motz}{Motz}
\DeclareMathOperator{\motzE}{Motz^1}
\DeclareMathOperator{\motzT}{Motz^2}
\DeclareMathOperator{\motzET}{Motz^{1,2}}
\DeclareMathOperator{\bal}{Bal}
\newcommand{\SYTo}{\SYT^{+1}}
\DeclareMathOperator{\cat}{Cat}
\DeclareMathOperator{\im}{\mathrm{im}}
\newcommand{\NCM}{\mathrm{NCM}}

\newcommand{\bij}{\alpha}
\newcommand{\bijTwo}{\beta}

%% define your title in the usual way
\title{Two-Row Set-Valued Tableaux: Catalan$^{+k}$ Combinatorics}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Alexander Lazar\thanks{\href{mailto:alexander.leo.lazar@ulb.be}{alexander.leo.lazar@ulb.be}}\addressmark{1} and Svante Linusson\thanks{\href{mailto:linusson@kth.se}{linusson@kth.se}}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}D\'{e}partement de Math\'{e}matique, Universit\'{e} Libre de Bruxelles, Belgique \\ \addressmark{2}KTH Royal Institute of Technology, Stockholm, Sweden}

%% 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{Set-valued standard Young tableaux are a generalization of standard Young tableaux due to Buch (2002) with applications in algebraic geometry. The enumeration of set-valued SYT is significantly more complicated than in the ordinary case, although product formulas are known in certain special cases. In this work we study the case of two-rowed set-valued SYT with a fixed number of entries. These tableaux are a new combinatorial model for the Catalan, Narayana, and Kreweras numbers, and can be shown to be in correspondence with both $321$-avoiding permutations and a certain class of bicolored Motzkin paths. We also introduce a generalization of the set-valued comajor index studied by Hopkins, Lazar, and Linusson (2023), and use this statistic to find seemingly new $q$-analogs of the Catalan and Narayana numbers.}

%% 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{Catalan numbers, set-valued tableaux, pattern-avoidance}

%% 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; i.e., [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{PlusK.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
\section{Introduction}


\subsection{Set-Valued Tableaux}
Let $\lambda \vdash n$. A \emph{set-valued Young tableau} of shape $\lambda$ is a filling $S$ of the cells of the Ferrers diagram of $\lambda$ with nonempty sets of positive integers. They were introduced by Buch \cite{buch2002littlewood} to study the $K$-theory of the Grassmannian, and have since appeared in both algebro-geometric and combinatorial contexts (see, inter alia, \cite{anderson2017kclasses, chan2018genera, chan2021euler,drube2018setvalued, kim2020enumeration,reiner2018poset}). 

A set-valued Young tableau is \emph{standard} if:
\begin{enumerate}
\item The sets in the cells of $\lambda$ form a set partition of $[n+k]$ for some $k\geq 0$, and
\item If $u$ is (weakly) northwest of $v$ in $\lambda$ then $\max S(u) < \min S(v)$.
\end{enumerate}

We write $\SYT^{+k}(\lambda)$ for the set of set-valued standard Young tableaux of $\lambda$ with entries in $[n+k]$. Intuitively, a set-valued SYT $S$ can be thought of an integer filling of $\lambda$ (filling each cell $u$ with $\min S(u)$) along with $k$ \emph{extra elements}. The combinatorics of these objects is much more intricate than in the ordinary case; there is no known analog of the hook-length formula for counting set-valued SYT in general, although Anderson, Chen, and Tarasca \cite{anderson2017kclasses} proved a determinantal formula for counting them.

For the purposes of enumerating the elements of $\SYT^{+k}(\lambda)$, it is sometimes useful to view a set-valued tableaux $S$ from a different perspective.

\begin{proposition}\label{SVSYTTriple}
A standard set-valued Young tableau of shape $\lambda$ is equivalent to the following data:
\begin{enumerate}
\item A standard Young tableau $S^*$ of shape $\lambda$,
\item A weak chain $\lambda^{\bullet}$ of subshapes 
$\emptyset = \lambda_0 \subsetneq \lambda_1 \subseteq \cdots \subseteq \lambda_k \subseteq \lambda_{k+1} = \lambda$,
\item A choice of a corner cell $u_i$ of $\lambda_i$ for each $1\leq i \leq k$.
\end{enumerate}
\end{proposition}

In lieu of a proof, consider the following illustrative example.

\begin{example}\label{SVSYTEx}
Consider the following set-valued SYT $T \in \SYT^{+4}(3\times 4)$:
\begin{center}
$\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 7 & 8\\
\hline
3 & 4, 5 & 11 & 13\\
\hline
6, 9, 10 & 12 & 14, 15 & 16\\
\hline
\end{array}$
\end{center}
There are cells with extra entries at matrix coordinates $(2,2)$, $(3,1)$, and $(3,3)$. Among these, the cell at $(2,2)$ has the smallest extra entry: $5$. We define $\lambda_1$ to be the subshape of $3\times 4$ for which the entries of $T$ are between $1$ and $5$:
\begin{center}
\begin{ytableau}
*(yellow) & *(yellow) & & \\
*(yellow) & *(yellow) \star & & \\
& & &
\end{ytableau}
\end{center}
The starred cell at matrix position $(2,2)$ is $u_1$.
The next extra entry is $9$, at matrix position $(3,1)$. We define $\lambda_2$ to be the subshape for which the entries of $T$ are between $1$ and $9$:
\begin{center}
\begin{ytableau}
*(yellow) & *(yellow) & *(blue) & *(blue)\\
*(yellow) & *(yellow) & & \\
*(blue) \star & & &
\end{ytableau}
\end{center}
Then since $9$ belongs to the starred cell $(3,1)$, we define that cell to be $u_2$. The next extra entry is $10$, which is in the same cell as the extra entry $9$. Then $\lambda_3 = \lambda_2$ and $u_3 = u_2$.

The last extra entry is $15$, at matrix position $(3,3)$. We have that $\lambda_4$ is the subshape $(4,4,3)$ consisting of the cells of $T$ whose entries are between $1$ and $15$.
\begin{center}
\begin{ytableau}
*(yellow) & *(yellow) & *(blue) & *(blue)\\
*(yellow) & *(yellow) & *(red) & *(red) \\
*(blue)  & *(red) &*(red) \star &
\end{ytableau}
\end{center}
Since $15$ belongs to the cell at position $(3,3)$, we define $u_4$ to be that corner cell. Finally, $\lambda_5$ is the entire shape.

We obtain $T^*$ from $T$ by removing the $4$ extra entries from $T$ and decrementing the remaining entries of the cells in $\lambda_i\setminus \lambda_{i-1}$ by $i-1$ for each $i$:
\begin{center}
\begin{ytableau}
1 & 2 & 6 & 7\\
3 & 4 & 8 & 10\\
5 & 9 & 11 & 12
\end{ytableau}
\end{center}
The entries in the yellow cells are decremented by $0$; those in the blue cells are decremented by $1$; those in the red cells are decremented by $3$ (notice there are no cells in $\lambda_3\setminus \lambda_2$); and the entry of the bottom right square is decremented by $4$.

\end{example}

This construction allows us to define a version of the \emph{comajor index} for set-valued tableaux.
Let $S \in \SYT^{+k}(\lambda)$, and decompose $S$ into $\ell$ chunks $T_1,\dots, T_{\ell}$ and $k$ additional elements $x_1,\dots,x_k$ as in \cref{SVSYTEx}. A \emph{(natural) descent} of $T_i$ is an entry $j$ of $T_i$ such that $j+1$ is also an entry of $T_i$ and is in a higher row\footnote{This is different from the usual definition of a descent in a Young tableau; our definition instead comes from the theory of $P$-partitions.}.

We write $\Des(T_i)$ for the descent set of $T_i$, and we define the \emph{set-valued descents} of $S$ to be $$\Des^{+k}(S) \coloneqq \bigsqcup D(T_i) \sqcup \{x_1,\dots, x_k\}.$$

The \emph{set-valued comajor index} of $S$ is then defined as $$\comaj^{+k}(S) \coloneqq \displaystyle \sum_{x \in \Des^{+k}(S)}(n+k - x).$$

\begin{example}
Continuing from \cref{SVSYTEx}: $D^{+4}(S) = \{5,6,9,10,12,15\}$, so $\comaj^{+4}(S) = 38$.
\end{example}

The $k=1$ version set-valued comajor index was recently used by Hopkins, Lazar, and Linusson \cite{hopkins2021qenumeration} to find a product formula for $\displaystyle\sum_{S \in \SYT^{+1}(a\times b)}q^{\comaj^{+1}(S)}$ analogous to Stanley's hook-content formula. Our generalized version is motivated by the probabilistic reasoning used in \cite{hopkins2021qenumeration} --- when one attempts to extend their arguments to general $\SYT^{+k}$, the $\comaj^{+k}$ statistic emerges quite naturally and yields extensions of some of the results of \cite{hopkins2021qenumeration} to the general case (to appear in forthcoming work). 

\subsection{Main Results}
The present work considers set-valued SYT from a different perspective. Rather than fixing the shape and the number of extra elements of a set-valued tableau $S$, we instead fix the number of rows and total number of elements.

This change of perspective has proven to be fruitful; if we restrict our attention to the case of two-row tableaux and fix the total number of elements while letting the number of columns vary, we obtain several new results:
\begin{itemize}
    \item For fixed $n$ and $i$, exact counts of $\bigsqcup_{2b-i+k = n}\SYT^{+k}(b,b-i)$ for all $0\leq i \leq b$. For $i=0$, that is, rows of equal length, it is the Catalan number (Equation~\eqref{eq:sv_syt_cat}) and for general $i$ it is a ballot number plus a binomial coefficient (Theorem~\ref{BallotThm}). 
    \item New models for the Catalan (Proposition \ref{prop:321_bij}), Narayana, and Kreweras (Proposition \ref{prop:321_bij2}) numbers (proved via a bijection with $321$-avoiding permutations).
    \item A new summation formula for the $321$-avoiding permutations by the number of peaks (Corollary \ref{321PeaksCor}).
    \item Exact counts of several families of lattice paths arising from these tableaux (Proposition \ref{MotzProp} and Theorem \ref{BallotThm}).
    \item Seemingly-new families of $q$-Catalan and $q$-Narayana numbers (Section \ref{qCatSect}).
\end{itemize} 

\section{Bijection to 321-avoiding Permutations}

In this section we will use a bijection to 321-avoiding permutations of length $n-1$ prove that for any $n\ge 2$
\begin{equation} \label{eq:sv_syt_cat}
 \sum_{2b+k = n} \#\SYT^{+k}(\rect{2}{b}) = \cat(n-1).
\end{equation}
 A permutation $\pi=\pi_1\ldots\pi_n$ is called \emph{321-avoiding} if it does not have three elements $\pi_i>\pi_j>\pi_k$ for $ 1\le i<j<k\le n$. Another well-known way to describe 321 avoiding permutations is as follows. Recall that  a \emph{right-to-left minimum} in a permutation $\pi$ is an element $\pi_i$ such that $\pi_i<\pi_j$ for all $j>i$. The right-to-left minima of any permutation form an increasing sequence (when read from the left). The condition that a permutation is 321-avoiding is equivalent to asking that the elements 
that are not right-to-left minima  also form an increasing sequence. This characterization dates back to the early 1900s; see~\cite[Vol. I, Section V, Chapter III]{macmahon1915combinatory}. \footnote{The text considers $123$-avoiding permutations, which are the reverses of $321$-avoiding permutations.}
 Visualising the permutation with a permutation matrix, the right-to-left minima  will be on or below the main diagonal and the other elements above the diagonal. Forming a lattice path around the elements on or above the diagonal gives a direct bijection to south-east lattice paths above the diagonal, which is one of the many standard representations of Catalan objects. Alternatively, one can draw a lattice path below the right-to left minima and then rotate the drawing by a half turn. We also need to define an \emph{inner valley}\footnote{An inner valley differs from an ordinary valley in that neither the first nor the last position can be an inner valley.} in a permutation $\pi\in S_n$ as an element $\pi_j, 1<j<n$ such that $\pi_{j-1}>\pi_j<\pi_{j+1}$. 

\begin{example}\label{321Ex} The permutation $\pi = \ 3\  5 \ \overline 1\  \overline 2\  7\  8\ \overline 4\ {10}\ {11}\ \overline 6\ \overline9$ is $321$-avoiding. We overline the right-to-left-minima.
\end{example}
\begin{figure}

\begin{center}
    \includegraphics{FPSACMatWithPath.pdf}
\end{center}

\caption{The permutation matrix of $\pi$ from Example~\ref{321Ex}, along with its associated lattice path.}
\end{figure}

For a fixed $n$ we now define a map 
$$\bij: \displaystyle\bigsqcup_{2b+k = n} \SYT^{+k}(\rect{2}{b}) \mapsto \{\text{$321$-avoiding permutations of $[n-1]$}\}.$$ 
Let $T\in \SYT^{+k}(\rect{2}{b})$, with $k+2b=n$.
\begin{itemize}
\item [(1)] Remove the largest element $n$ from $T$, so it contains the numbers from 1 to $n-1$.
\item [(2)] The permutation $\bij(T)$ starts with all except the largest element in the top left box, followed by the entries of the box directly below it, and then the largest element of the top left box. The permutation 
continues with the elements in the second box in the top row except the largest, then all elements in the box below it, then the largest element in the second box in the top row. We continue in this way, placing the elements of the $i$th box from the left in the bottom row immediately before the largest element of the $i$th box in the top row.
\end{itemize}

\begin{example}
\ytableausetup{boxsize=2.7em}
%\vskip-3mm
\[
\begin{ytableau} 
 1,2 & 3,4,6 & 7 &10 \\ 5, 8& 9 & 11,12 &{13,14} 
 \end{ytableau}
\quad
\overset {\bij}\mapsto
 \pi= \overline 1 \ 5\   8\ \overline 2 \ \overline 3 \ \overline 4\ 9\   \overline 6\ 11\  12\  \overline 7\ 13\ \overline {10}
  \]
\end{example}

The resulting permutation $\bij(T)$ will by construction have the numbers in the top row as its right-to-left minima. The elements in the bottom row (except $n$, which has been deleted) will form another increasing sequence. The permutation formed is thus $321$-avoiding. Note that the largest elements in the top boxes in columns $1,\dots, b-1$ will be inner valleys in the permutation and there are no other inner valleys. 

The inverse of $\bij$ is reasonably simple; however, the full description requires checking several cases so we omit most of the details here. Intuitively, given a $321$-avoiding permutation $\pi$, the right-to-left minima are inserted into the top row (with the first run of right-to-left minima needing special handling), while the $i$th run of elements that are \emph{not} right-to-left minima is inserted into the $i$th box of the bottom row. 

\begin{example} We reuse the permutation from Example~\ref{321Ex} to illustrate $\bij^{-1}$.
    %\vskip-3mm
    \ytableausetup{boxsize=2.3em}
    \[
    \pi = \ 3\  5 \ \overline 1\  \overline 2\  7\  8\ \overline 4\ {10}\ {11}\ \overline 6\ \overline {9}
    \overset {\bij^{-1}}\mapsto
    \quad
    \begin{ytableau}
        1 &2,4 & 6 &9 \\ 3,5& 7,8 & 10,11 &12
        \end{ytableau}
    \]\end{example}

We summarize some basic properties of $\bij$. 
\begin{proposition} \label{prop:321_bij} For all $n\geq 2$:
\begin{itemize} 
\item The map $\alpha$ is a bijection from $\displaystyle\bigsqcup_{2b+k = n} \SYT^{+k}(\rect{2}{b})$ to the set of $321$-avoiding permutations of $[n-1]$.
\item The elements in the top row of $T$ form the sequence of right-to-left minima in $\alpha(T)$.
\item If $T$ has $b$ columns, then $\alpha(T)$ will have $b-1$ inner valleys.
\end{itemize}
\end{proposition}

An \emph{inner peak} in a permutation $\pi\in S_n$ is an element $\pi_j, 1<j<n$ such that $\pi_{j-1}<\pi_j>\pi_{j+1}$. For the set of 321-avoiding permutations the involution formed by rotating the permutation matrix a half turn shows that inner peaks and inner valleys are equidistributed for 321-avoiding permutations.\footnote{We thank FindStat \cite{FindStat}, which helped us find that the refinement into columns was equidistributed with number of inner peaks. This equidistribution was a key insight into finding the bijection $\bij$.}


Recall from the theory of Catalan numbers that the number of Dyck paths of length $2n$ is counted by the Catalan number $\cat(n)$, also the number of such paths with $m$ peaks
is enumerated by the Narayana number $N_{n,m}=\frac{1}{m}\binom{n}{m-1}\binom{n-1}{m-1}$. There is even one further refinement. Let $c_i$ be the number of upsteps in the Dyck 
paths directly before peak number $i$ in the path, which gives a partition ${\bfc}=(c_1,\dots,c_m)$ of $n$, that is $\sum_ic_i=n$. Further let ${\mu_j}$ be the 
number of $c_i$ that equals $j$. Thus 
$\mu$ (or sometimes written $[1^{\mu_1}2^{\mu_2}\dots n^{\mu_n}]$)  is the {\bf type} of the composition $\bfc$ and of the Dyck path. The number of Dyck paths with $m$ peaks and
of type $\mu$ is known to be the Kreweras number $\krew(n,m,\mu)=\frac{n(n-1)\dots(n-m+1)}{\prod_j \mu_j!}$\cite{KrewerasNumbers}. 
In the bijection $\bij$, a tableau with $m$ elements in the top row will be mapped to a
321-avoiding permutation with $m$ right-to-left minima. As discussed above, we can draw a lattice path under these in the permutation matrix and by rotating half a turn obtain 
a bijection to Dyck paths with $m$ peaks.  
The distance between two consecutive elements in the top row is mapped to the number of upsteps $c_i$ of the Dyck path. This proves the following proposition.

\begin{proposition} \label{prop:321_bij2} For any $b,k\ge 1$ we have the following refinements:
    \begin{enumerate}
    \item The number of
    tableaux in $\cup_{2b+k = n} \SYT^{+k}(\rect{2}{b})$ with $m$ elements in the top row is the Narayana number
    $N_{n-1,m}=\frac{1}{m}\binom{n-1}{m-1}\binom{n-2}{m-1}$
    \item The number of
    tableaux in $\cup_{2b+k = n} \SYT^{+k}(\rect{2}{b})$ with elements $a_1,\dots,a_m$ in the top row
    is the Kreweras number $\krew(n,m,\mu)$, where $\mu$ is the type of $(c_1,\dots,c_m)$ with $c_i=a_{i+1}-a_{i}$ and $a_{m+1}\coloneqq n$.
    \end{enumerate}
   \end{proposition}

The bijection $\bij$ also implies the following.

\begin{proposition} \label{prop:More shapes} { }For $n\ge 3$
\begin{enumerate} 
\item  $|\cup_{2b+k+1 = n} \SYT^{+k}(b+1,b)|=\cat(n)-\cat(n-1)=\frac{3}{n+1}\binom{2n-2}{n}$.
\item $|\cup_{2b+k = n} \SYT^{+k}(b+1,b)/(1)|=\cat(n)-2\cat(n-1)+\cat(n-2)$.
\end{enumerate}
\end{proposition}

\section{Enumeration According to Peaks}

In \cite[Corollary 5.4]{anderson2017kclasses}, Anderson, Chen, and Tarasca give a formula for the Euler characteristic of a certain \emph{Brill--Noether space}, which they had earlier shown to be equal to the (signed) count of a certain class of set-valued tableaux. Specializing to the two row case and translating into our notation, their formula becomes:
\begin{equation}\label{ACTFormula}
\#\{\SYT^{+k}(2\times b)\} = \frac{1}{k!}\sum_{c=0}^{\lfloor\frac{k}{2}\rfloor}f^{(k-c,c)}f^{(b+k-c,b+c)}(b+k-c-1)_{(k-c)}(b+c-2)_{(c)},
\end{equation}
where $f^{\lambda}$ is the number of SYT of shape $\lambda$, and $(x)_{(a)}$ is the falling factorial $x(x-1)\cdots(x-a+1)$.

For our purposes, it is convenient to use the hook length formula to rewrite Equation \ref{ACTFormula} purely in terms of factorials and binomial coefficients:

\begin{align}
\#\{\SYT&^{+k}(2\times b)\} \\ &= \frac{1}{k!}\sum_{c=0}^{\lfloor\frac{k}{2}\rfloor}\frac{k!(k-2c+1)}{c!(k-c+1)!}\frac{(2b+k)!(k-2c+1)}{(b+c)!(b+k-c+1)!}\frac{(b+k-c-1)!}{(b-1)!}\frac{(b+c-2)!}{(b-2)!} \nonumber\\
&= \sum_{c=0}^{\lfloor\frac{k}{2}\rfloor}\frac{(k-2c+1)^2}{(k-c+1)(b+k-c+1)}\binom{b+c-2}{c}\binom{b+k-c-1}{b-1}\binom{2b+k}{b+c}.\label{ACTFormula2}
\end{align}

In light of our bijection between $\SYT^{+k}(2\times b)$ and the set of $321$-avoiding permutations of $n=2b+k$ with exactly $k$ peaks, we immediately have the following result:

\begin{corollary}\label{321PeaksCor}
$$\#\{\mathfrak{S}_{2b+k}^{321}\} = \sum_{c=0}^{\lfloor\frac{k}{2}\rfloor}\frac{(k-2c+1)^2}{(k-c+1)(b+k-c+1)}\binom{b+c-2}{c}\binom{b+k-c-1}{b-1}\binom{2b+k}{b+c}.$$
\end{corollary}

This sort of closed form expression is a somewhat pleasant surprise; in \cite[Theorem 3]{Bukata2019DistributionsOS}, the authors give the following generating function formula for the sequence $a_{n,k}^{\mathrm{pk}}(321)$ of $321$-avoiding permutations of $[n]$ with $k$ peaks:
\begin{equation}\label{PeaksGenFun}
\sum_{n\geq 0}\sum_{k\geq 0}a_{n,k}^{\mathrm{pk}}(321)q^kz^n = 1 + z\left(-\frac{-1 + \sqrt{-4z^2q+4z^2-4z+1}}{2z(zq-z+1)}\right)^2,\end{equation}
It is not at all obvious how one would obtain \cref{ACTFormula2} from \cref{PeaksGenFun} (or vice-versa) using only elementary techniques.

\section{Motzkinlike and Ballotlike Paths}

In addition to $321$-avoiding permutations, we can interpret the $\SYT^{+k}(2\times b)$ in terms of a certain class of bicolored Motzkin paths. 
 
We recall that a \emph{Motzkin path} of length $n$ is a lattice path in $\Z^2$ from~$(0,0)$ to $(n,0)$ consisting of \emph{up steps} $U=(1,1)$, \emph{down steps} $D=(1,-1)$, and \emph{horizontal steps} $H=(1,0)$ in some order, with the property that the path never goes below the $x$-axis. 

We will color the horizontal steps of the Motzkin paths with $u$ (for upstairs or umber) and $d$ (downstairs or denim).
We will consider the following two restrictions on the coloring:
\begin{itemize}
\item [(1)] umber horizontal steps do not occur at height zero;
\item [(2)] denim horizontal steps do not occur before the first down step.
\end{itemize}
We use $\motz(n)$ to denote the set of bicolored Motzkin paths of length $n$, and $\motzE(n)$, $\motzT(n)$, and $\motzET(n)$ to denote the set of paths which satisfies the restrictions (1), (2), and both (1) and (2) respectively.

Extending the well-known bijection between two-rowed rectangular SYTs and Dyck paths, we have the following bijection. 

\begin{proposition} \label{prop:motzkin_bij}
There is a bijection $\bijTwo$ between $\SYT^k(\rect{2}{b})$ and $\motzET(2b+k)$ with $k$ horizontal steps. A tableau $S$ maps to the path $\Gamma$ for which:
\begin{itemize} 
\item up steps of $\Gamma$ occur at the minimal entries of boxes in the first row of $S$;
\item down-steps of $\Gamma$ occur at the minimal entries in the second row; 
\item we color a horizontal step of $\Gamma$ umber if its index is a (non-minimal) entry of a box in the first row of $S$, and denim if its index is a (non-minimal) entry in the second row.
\end{itemize}
\end{proposition}

The proof of Proposition \ref{prop:motzkin_bij} is reasonably straightforward and is omitted in this abstract.

\begin{figure}[h]
\begin{center}
\begin{tabular}{c|cc}
\begin{tabular}{c}$S$\end{tabular} & \begin{tabular}{c}{\begin{ytableau} 1,2 & 4 & 5 \\ 3 & 6 & 7 \end{ytableau}}\end{tabular} & \begin{tabular}{c}{\begin{ytableau} 1 & 4 & 5,7 \\ 2,3 & 6 & 8,9 \end{ytableau}}\end{tabular}\\ \\
\rule{0pt}{4ex}
\rule{0pt}{4ex}
\begin{tabular}{c}$\bijTwo(S)$\end{tabular} &\begin{tabular}{c}$
\begin{tikzpicture}[scale=0.5]
\draw[dashed] (-0.5,0) -- (7.5,0);
\draw[thick] (0,0) -- (1,1);
\draw[thick, brown] (1,1)--(2,1);
\node[above] at (1.5,1) {u}; 
\draw[thick] (2,1) -- (3,0) -- (4,1) -- (5,2) -- (6,1) -- (7,0);
\draw[fill] (0,0) circle (0.1);
\draw[fill] (1,1) circle (0.1);
\draw[fill] (2,1) circle (0.1);
\draw[fill] (3,0) circle (0.1);
\draw[fill] (4,1) circle (0.1);
\draw[fill] (5,2) circle (0.1);
\draw[fill] (6,1) circle (0.1);
\draw[fill] (7,0) circle (0.1);
\node[below] at (0.5,0) {1}; 
\node[below] at (1.5,0) {2}; 
\node[below] at (2.5,0) {3}; 
\node[below] at (3.5,0) {4}; 
\node[below] at (4.5,0) {5}; 
\node[below] at (5.5,0) {6}; 
\node[below] at (6.5,0) {7}; 
\end{tikzpicture}
$\end{tabular}
& \begin{tabular}{c}$
\begin{tikzpicture}[scale=0.5]
\draw[dashed] (-0.5,0) -- (9.5,0);
\draw[thick] (0,0) -- (1,1) -- (2,0);
\draw[thick,blue] (2,0) -- (3,0);
\node[above] at (2.5,0) {d}; 
\draw[thick] (3,0) -- (4,1) -- (5,2) -- (6,1);
\draw[thick,brown] (6,1) -- (7,1);
\node[above] at (6.5,1) {u}; 
\draw[thick] (7,1) -- (8,0);
\draw[thick,blue] (8,0) -- (9,0);
\node[above] at (8.5,0) {d}; 
\draw[fill] (0,0) circle (0.1);
\draw[fill] (1,1) circle (0.1);
\draw[fill] (2,0) circle (0.1);
\draw[fill] (3,0) circle (0.1);
\draw[fill] (4,1) circle (0.1);
\draw[fill] (5,2) circle (0.1);
\draw[fill] (6,1) circle (0.1);
\draw[fill] (7,1) circle (0.1);
\draw[fill] (8,0) circle (0.1);
\draw[fill] (9,0) circle (0.1);
\node[below] at (0.5,0) {1}; 
\node[below] at (1.5,0) {2}; 
\node[below] at (2.5,0) {3}; 
\node[below] at (3.5,0) {4}; 
\node[below] at (4.5,0) {5}; 
\node[below] at (5.5,0) {6}; 
\node[below] at (6.5,0) {7}; 
\node[below] at (7.5,0) {8}; 
\node[below] at (8.5,0) {9}; 
\end{tikzpicture}$
\end{tabular}
\end{tabular}
\end{center}
\caption{Examples of the bijection $\bijTwo$ between two-rowed rectangular set-valued SYTs and birestricted bicolored Motzkin paths.} \label{fig:motzkin}
\end{figure}

The first two equalities in the following proposition are well-known but the other two seem to be new. We construct a bijection that, when concatenated with $\bijTwo$ in Proposition \ref{prop:motzkin_bij}, gives us a second bijective proof of \eqref{eq:sv_syt_cat}. The details are omitted in this extended abstract.

\begin{proposition}\label{MotzProp} The Catalan numbers enumerate all four possible restriction on Motzkin paths: $|\motz(n)|=\cat(n+1), \quad |\motzE(n)|=\cat(n), \quad |\motzT(n)|=\cat(n),$ and $|\motzET(n)|=\cat(n-1), \text{ for }n\ge 2$.

\end{proposition}

\subsection{Ballotlike paths}
We can also consider a larger class of paths which we call \emph{ballotlike}. A ballotlike path $P$ is a lattice path in the $1$st quadrant starting at $(0,0)$ and ending at $(n,i)$ which uses the steps $U = (1,1)$, $D = (1,-1)$, $u = (1,0)^{\mathrm{umber}}$ and $d = (1,0)^{\mathrm{denim}}$, subject to the same conditions on $u$ and $d$ steps from the definition of $\motzET(n)$. We write $\bal^*(n,i)$ for the set of ballotlike paths ending at $(n,i)$. The enumeration turns out to be the sum of a classical ballot number and a binomial coefficient.

\begin{thm}\label{BallotThm}
For any $(n,i)$ with $0\leq i \leq n$, we have
$$\#\bal^*(n,i) = \binom{2n-2}{n-i-1} - \binom{2n - 2}{n-i-2} + \binom{n-2}{n-i}.$$


Moreover, if we take the obvious extension of the bijection between $\motzET(n)$ and set-valued SYT of shape $2\times b$, we have for any $(n,i)$ with $0\leq i \leq n$,
$$\# \bigsqcup_{2b+k-i = n} \SYT^{+k}(b,b-i) = \binom{2n-2}{n-i-1} - \binom{2n - 2}{n-i-2} + \binom{n-2}{n-i}.$$
\end{thm}
\begin{example}\label{Thm13} When $n=4$ and $i=2$ we have 6 set-valued SYT.
\begin{center}
\begin{tabular}{cccccc}
    $\begin{array}{|c|c|c|}
    \hline
    1 & 2 & 4\\
    \hline
    3 \\
    \cline{1-1}
    \end{array}$
&
    $\begin{array}{|c|c|c|}
    \hline
    1 & 3 & 4\\
    \hline
    2 \\ 
    \cline{1-1}
    \end{array}$ 
&
    $\begin{array}{|c|c|c|}
    \hline
    1 & 2 & 3\\
    \hline
    4\\
    \cline{1-1}
    \end{array}$
&
    $\begin{array}{|c|c|}
    \hline
    1,2,3 & 4 \\
    \hline
    \end{array}$
&
    $\begin{array}{|c|c|}
    \hline
    1,2 & 3,4 \\
    \hline
    \end{array}$
&
    $\begin{array}{|c|c|}
    \hline
    1& 2,3,4 \\
    \hline
    \end{array}$
\end{tabular}
\end{center}
\end{example}


\section{Future Work}
\subsection{$q$-Catalan and $q$-Narayana}\label{qCatSect}
Given the numerology for $\SYT^{+k}(2\times b)$, it is natural to consider the following $q$-analogs:
\begin{align*}
\overset{\sim}{\cat}_n(q) &\coloneqq \sum_{2b+k = n+1}\left(\sum_{S \in \SYT^{+k}(2\times b)}q^{\comaj^{+k}(S)}\right) \\
\overset{\sim}{N_{n,m}}(q) &\coloneqq \sum_{2b +k = n+1}\left(\sum_{\substack{S \in \SYT^{+k}(2 \times b)\\m\text{ elts in top row}}}q^{\comaj^{+k}(S)}\right).
\end{align*}

Using the bijection in Proposition \ref{prop:motzkin_bij} and a double recursion we can compute the polynomials $\overset{\sim}{\cat}_q$ and $\overset{\sim} {N_{n,m}}(q)$ for small values of $n,m$ (details omitted in this extended abstract). They do not seem to match any statistic we have found in the literature.

\begin{figure}
\begin{center}
\begin{tabular}{c|c}
$n$ & $\overset{\sim}{\cat}_n(q)$\\
\hline
$1$ & $1$\\
\hline
$2$ & $q+1$\\
\hline
$3$ & $q^3 + 2q^2 + q + 1$\\
\hline
$4$ & $q^6 + 2q^5 + 3q^4 + 3q^3 + 2q^2 + 2q + 1$\\
\hline
$5$ & $q^{10} + 2q^9 + 3q^8 + 7q^7 + 6q^6 + 5q^5 + 6q^4 + 7q^3 + 3q^2 + q + 1$
\end{tabular}
\end{center}
\caption{The first six $\overset{\sim}{\cat}_n(q)$ polynomials.}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{>{\bfseries}c|c|c|c|c}
n/m & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} \\
\hline
1 & $1$ &  &  &  \\
\hline
2 & $1$ & $q$ & & \\
\hline
3 & $q$ & $2q^2+1$ & $q^3$ &  \\
\hline
4 & $q^3$ & $2q^4 + q^3 + q^2 + q + 1$ & $2q^5 + q^4 + q^3 + q^2 + q$ & $q^6$ \\
\end{tabular}
\end{center}
\caption{$\overset{\sim}{N_{n,m}}(q)$ for $2\leq n \leq 5$.}
\end{figure}

\begin{question}
Are there better formulas for $\overset{\sim}{\cat}_n(q)$ and $\overset{\sim}{N_{n,m}}(q)$?
\end{question}

\subsection{Expected Number of Columns}

The results of \cite{hopkins2021qenumeration} draw heavily upon the language of probability theory. In particular, the authors consider several families of probability distributions on subshapes of the $a\times b$ rectangular partition, and compute the expected value of the number of corners of the subshapes with respect to these distributions. In this spirit, we consider the number of columns of a randomly-selected $S \in \displaystyle\bigsqcup_{2b+k=n}\SYT^{+k}(2\times b)$ (equivalently, the number of inner peaks of a randomly-selected $321$-avoiding permutation).

\begin{conjecture}
If we sample such an $S$ uniformly at random, we have for $n\ge 3$ that
$$\mathbb{E}\left(\text{\# of columns of $S$}\right) = \left(\binom{n}{2} + n -3\right) \Big/ (2n-3).$$
\end{conjecture}
\begin{question}
Is there a nice formula for the $q$-version? Specifically, is there a better formula for
$$\mathbb{E}_q\left(\text{\# of columns of $S$}\right) = \displaystyle\sum_{2b+k=n+1}b\cdot\left(\sum_{S \in \SYT^{+k}(2\times b)}q^{\comaj^{+k}(S)}\right)\Big/\overset{\sim}{\cat_n}(q)?$$
\end{question}

\acknowledgements{Both authors were supported by grant 2018-05218 from VR the Swedish Science Council. The first author was also partially supported by ARC “From algebra to combinatorics, and back.” The second author was also supported by by 2022-03875 from VR. \emph{Note added in proof: We thank Guillaume Chapuy, who outlined a way to prove Conjecture 16 during the conference.}} 

\printbibliography
\end{document}