%% 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]{FPSAC2021}
\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}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem*{problem*}{Problem}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exmp}[thm]{Example}
\newtheorem{rem}[thm]{Remark}


\usepackage{mathtools}
\usepackage{booktabs}
\usepackage{paralist}
\usepackage{comment}
\usepackage{bm}
\usepackage{textcmds}

\usepackage{xcolor}

\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing,shapes}
\usepackage[outline]{contour}
\contourlength{2pt}

\usepackage[centertableaux]{ytableau}

\DeclareMathOperator{\ASTZ}{\mathcal{AST\!Z}}
\DeclareMathOperator{\CSSPP}{\mathcal{CSSPP}}

%% define your title in the usual way
\title{Weight-preserving bijections between integer partitions and a family of alternating sign trapezoids}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Hans H{\"o}ngesberg\thanks{\href{mailto:hans.hoengesberg@univie.ac.at}{hans.hoengesberg@univie.ac.at}. The author acknowledges support from the Austrian Science Foundation FWF (SFB grant F50).}\addressmark{1}
%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Fakult{\"a}t f{\"u}r Mathematik, Universit{\"a}t Wien, Oskar-Morgenstern-Platz 1, 1090 Wien, Austria}}

%% 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{We construct weight-preserving bijections between column strict shifted plane partitions with one row and alternating sign trapezoids with exactly one column in the left half that sums to $1$. Amongst other things, it relates the number of $-1$s in the alternating sign trapezoids to certain entries in the column strict shifted plane partitions that generalise the notion of special parts in descending plane partitions.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Alternating sign trapezoids, Column strict shifted plane partitions, Bijection, Osculating paths}

%% 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{80Hoengesberg.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}
Alternating sign matrices (ASMs) are square matrices with entries $-1$, $0$, and $1$ such that the nonzero entries alternate in sign and sum to $1$ along each row and column. When Mills, Robbins, and Rumsey conjectured that $n \times n$ ASMs are equinumerous with totally symmetric self-complementary plane partitions (TSSCPPs) in an $2n \times 2n \times 2n$ box \cite{MRR86} and with descending plane partitions (DPPs) without parts exceeding $n$ \cite{MRR83}, they initiated a strenuous quest for weight-preserving bijections between ASMs and other presumably equinumerous families of objects. These conjectures were proved nonbijectively by establishing the same enumeration formula for each of the three classes: for DPPs \cite{And79}, TSSCPPs \cite{And94}, and ASMs \cite{Zei96}, \cite{Kup96}. A fourth equinumerous class was introduced in a recent work by Ayyer, Behrend, and Fischer \cite{ABF}, namely alternating sign triangles (ASTs). 

The realm of alternating sign arrays is known for the lack of bijective proofs. Most of the bijections that have been established only consider special cases. For instance, there are partial bijections between ASMs and TSSCPPs by Cheballah and Biane \cite{CB12} and Striker \cite{Str18} and between ASMs and DPPs by Ayyer \cite{Ayy10}, Striker \cite{Str11}, and Fulmek \cite{Ful20}.

It took around four decades to find the first general bijective proof. Fischer and Konvalinka \cite{FK20a}, \cite{FK20b} have recently constructed an explicit but rather intricate bijection that relates ASMs with DPPs. Its underlying concept is turning Fischer's nonbijective proof of the ASM enumeration formula \cite{Fis16} into a bijective proof by using a generalisation of the Garsia--Milne involution principle. See \cite{FK20c} for a concise overview of how the proof was found and how the bijections work.

Ayyer, Behrend, and Fischer \cite{ABF} announced a family of alternating sign arrays that are generalising ASTs: alternating sign trapezoids (ASTZs). Fischer \cite{Fis19} proved that ASTZs are equinumerous with column strict shifted plane partitions (CSSPPs) of a fixed class which are a simple generalisation of DPPs essentially introduced by Andrews \cite{And79}.

In the present extended abstract, we provide weight-preserving bijections between single-row CSSPPs of a fixed class and ASTZs with exactly one column in the left half that sums to $1$. We start with the definitions of ASTZs and CSSPPs and of the statistics we consider on these objects.

\section{Preliminaries}

\begin{defn}
	For $l \geq 2$, an \emph{$(n,l)$-alternating sign trapezoid} is an array
	of $-1$s, $0$s, and $+1$s in a trapezoidal shape with $n$ rows of the following form
	\begin{equation*}
	\begin{array}[t]{ccccccccc}
	a_{1,1}&a_{1,2}&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&a_{1,2n+l-2}\\
	&a_{2,2}&\cdots&\cdots&\cdots&\cdots&\cdots&a_{2,2n+l-3}&\\
	&&\ddots&&&&\reflectbox{$\ddots$}&&\\
	&&&a_{n,n}&\cdots&a_{n,n+l-1}&&&
	\end{array}
	\end{equation*}
	such that the following four conditions hold:
	\begin{compactitem}
		\item the nonzero entries alternate in sign in each row and each column;
		\item the topmost nonzero entry in each column is $1$;
		\item each row sums to $1$; 
		\item each of the central $l-2$ columns sums to $0$.
	\end{compactitem}
	
	If a column sums to $1$, we call it a \emph{$1$-column}. Otherwise, it is a \emph{$0$-column}. In addition, if the bottom entry of a $1$-column is $0$, we also call it a \emph{$10$-column}.
\end{defn}

Let $\ASTZ_{n,l}$ denote the set of $(n,l)$-ASTZs. We introduce four different statistics on ASTZs. For $A \in \ASTZ_{n,l}$, we define
%
\begin{align*}
\mu(A) &\coloneqq \text{\# $-1$s in $A$,}\\
r(A) &\coloneqq \text{\# $1$-columns among the $n$ leftmost columns of $A$,}\\
p(A) &\coloneqq \text{\# $10$-columns among the $n$ leftmost columns of $A$,}\\
q(A) &\coloneqq \text{\# $10$-columns among the $n$ rightmost columns of $A$.}
\end{align*}
%
The weight~$w(A)$ of $A$ is set to be $M^{\mu(A)} R^{r(A)} P^{p(A)} Q^{q(A)}$.

\begin{exmp}
	The following $(5,5)$-ASTZ has weight~$M^3 R^3 P$:
	\begin{equation*}
	\begin{array}{ccccccccccccc}
	0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
	& 0 & 1 & 0 & 0 & 0 & -1 & 0 & 1 & 0 & 0 & 0 & \\
	& & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & & \\
	& & & 1 & 0 & 0 & 0 & 0 & -1 & 1 & & & \\
	& & & & 1 & 0 & -1 & 0 & 1 & & & &
	\end{array}
	\end{equation*}
\end{exmp}

Note that ASTZs can be interpreted as a generalisation of ASTs as follows: We can construct the class of ASTs with $n+1$ rows by adding an additional bottom row that consists of a single $1$ below $(n,3)$-ASTZs such that we obtain a triangular array. Ayyer, Behrend, and Fischer \cite{ABF} showed that the number of $-1$s is equally distributed in ASTs with $n$ rows and $n \times n$ ASMs.

\begin{defn}	
	A \emph{strict partition} $\mu$ is a tuple of strictly decreasing positive integers $\mu_i$; the number of elements in $\mu$ is denoted by $\ell(\mu)$. A \emph{shifted Young diagram} of \emph{shape} $\mu$ is a finite collection of cells arranged in $\ell(\mu)$ rows such that row~$i$ has length $\mu_i$ and each row is indented by one cell compared to the row above.
	
	A \emph{column strict shifted plane partition} $\pi=(\pi_{i,j})_{1 \le i \le \ell(\mu),i \le j \le i + \mu_i -1}$ is a filling of a shifted Young diagram of shape $\mu$ with positive integers such that the entries weakly decrease along each row and strictly decrease down each column. We call the entries \emph{parts} and say that the partition is of \emph{class~k} if the first part of each row equals $k$ plus its corresponding row length, that is, $\pi_{i,i}=k+\mu_i$ for all $1 \le i \le \ell(\mu)$.
\end{defn}

Let $\CSSPP_{n,k}$ denote the set of CSSPPs of class $k$ with at most $n$ parts in the first row. Note that we consider the collection of zero cells to be a CSSPP of class $k$ for any $k$. We introduce four different statistics of which two depend on a fixed parameter~$d\in \{1,\dots,k\}$. For $\pi \in \CSSPP_{n,k}$ and $k \ge 1$, we define
%
\begin{align*}
\mu_d(\pi) &\coloneqq \text{\# parts $\pi_{i,j}\in\{2,3,\dots,j-i+k\} \setminus \{j-i+d\}$,}\\
r(\pi) &\coloneqq \text{\# rows of $\pi$,}\\
p_d(\pi) &\coloneqq \text{\# parts $\pi_{i,j}=j-i+d$,}\\
q(\pi) &\coloneqq \text{\# $1$s in $\pi$.}
\end{align*}
%
The weight~$w_d(\pi)$ of $\pi$ is set to be $M^{\mu_d(\pi)} R^{r(\pi)} P^{p_d(\pi)} Q^{q(\pi)}$.

\begin{exmp}
	The following CSSPP of class~$4$ has shape~$(6,4,3,1)$ and weight~$M R^4 P Q^2$ if $d=2$:
	\begin{center}
		\begin{ytableau}
			10 & 10 & 9 & 9 & 6 & 1\\
			\none & 8 & 8 & 8 & 2\\
			\none & \none & 7 & 6 & 1\\
			\none & \none & \none & 5\\
		\end{ytableau}
	\end{center}
\end{exmp}

Note that CSSPPs of class~$2$ correspond to DPPs by subtracting $1$ from each part of the CSSPP and eventually deleting all parts equal to $0$.
%
We call the parts $\pi_{i,j}\in\{2,3,\dots,j-i+k\} \setminus \{j-i+d\}$, that are counted by the statistic~$\mu_d$, \emph{$d$-special parts}. They generalise the \emph{special parts} defined by Mills, Robbins, and Rumsey \cite{MRR83} since the number of special parts in $\pi \in \CSSPP_{n,2}$ equals $\mu_2(\pi)$.

The author \cite{Hon20} showed that the joint distribution of the respective four statistics on the sets $\ASTZ_{n,l}$ and $\CSSPP_{n,l-1}$ coincide:
%
\begin{thm}
	Let $n \ge 1$, $l \ge 2$, and $1 \le d \le l-1$. The generating function $\sum_{A \in \ASTZ_{n,l}} w(A)$ of $(n,l)$-ASTZs equals the generating function $\sum_{\pi \in \CSSPP_{n,l-1}} w_d(\pi)$ of CSSPPs of class~$l-1$ with at most $n$ parts in the first row. In particular, they are each given by
	\begin{equation}
	\label{eq:GenFunc}
	\det_{0 \le i,j \le n-1} \left(R \sum_{k = 0}^{i} Q^{i-k} \sum_{m=0}^{j} \binom{j}{m} M^{k-m} \left( \binom{k+l-3}{k-m} +\frac{P}{M} \binom{k+l-3}{k-m-1} \right) + \delta_{i,j} \right).
	\end{equation}
\end{thm}

The purpose of the present extended abstract is to construct weight-preserving bijections between the sets $\{\pi \in \CSSPP_{n,l-1} \mid r(\pi) = 1\}$ and $\{A \in \ASTZ_{n,l} \mid r(A) = 1\}$.

Let us fix some notation: We number the $n$ leftmost columns of $A\in\ASTZ_{n,l}$ from $-n$ to $-1$ and the $n$ rightmost columns from $1$ to $n$. We observe that $A$ has exactly $n$ \mbox{$1$-columns}. If $r(A)=1$, that is, $A$ has exactly one $1$-column among the $n$ leftmost columns, then $A$ has also exactly one $0$-column among the $n$ rightmost columns. We denote the set of $(n,l)$-ASTZs with a unique $1$-column among the $n$ leftmost columns at position~$-i$ and a unique $0$-column among the $n$ rightmost columns at position~$j$ by $\ASTZ_{n,l}^{i,j}$. See Example~\ref{ex:RunningExampleA}.

We denote the subset of all single-row CSSPPs in $\CSSPP_{n,k}$ with exactly $j$ parts by  $\CSSPP_{n,k}^{j}$. Note that CSSPPs with only one row are ordinary integer partitions.

Our main goal is to construct bijections
\begin{equation*}
	\bigcup_{i=1}^{n} \ASTZ_{n,l}^{i,j} \longleftrightarrow \CSSPP_{n,l-1}^{j}
\end{equation*}
preserving the weights $(\mu,p,q)$ and $(\mu_d,p_d,q)$ for any $1 \le d \le l-1$, respectively. That is, we solve the following task:
%
\begin{problem*}
	For $l \ge 2$ and $1 \le d \le l-1$, construct bijections between $(n,l)$-ASTZs with exactly one $1$-column in the left half, $\mu$ entries equal to $-1$, $p$ $10$-columns in the left half, $q$ $10$-columns in the right half, and a $0$-column at position~$j$ and single-row CSSPPs of class $l-1$ with exactly $j$ parts, thereof $\mu$ $d$-special parts, $p$ parts at position~$k$ that are equal to $k-1+d$, and $q$ parts equal to $1$.
\end{problem*}
%
As a side benefit, we obtain an enumeration formula for the number of elements in $\ASTZ_{n,l}^{i,j}$:

\begin{thm}\label{thm:MainEnumeration}
	The number of $A \in \ASTZ_{n,l}^{i,j}$ such that $\mu(A)=\mu$, $p(A)=p$, and $q(A)=q$ is given by
	\begin{equation}\label{eq:MainEnumeration}
	\binom{j-i}{\mu+p+q} \binom{j+i+l-q-5}{\mu} - \binom{j-i-1}{\mu+p+q} \binom{j+i+l-q-4}{\mu}.
	\end{equation}
\end{thm}

We proceed as follows: In Section~\ref{sec:LatticePathsRepresentations}, we discuss the lattice path representations of ASTZs and CSSPPs as our main tool. In Section~\ref{sec:Bijection}, we present the actual construction of the bijections from ASTZs to CSSPPs. In the end, we conclude with some remarks about other bijections and a potential generalisation in Section~\ref{sec:Remarks}. Note that, for the sake of simplicity, we often write \emph{the bijection} despite meaning \emph{a family of bijections}.


\begin{rem}
	There is indeed a notion of $(n,1)$-ASTZs, also called \emph{quasi alternating sign triangles} (QASTs) \cite{ABF}. Fischer \cite{Fis19} proved that QASTs with $n$ rows are equinumerous with CSSPPs of class~$0$ with at most $n$ parts in the first row. Moreover, the author \cite{Hon20} defined weights~$w$ on QASTs and CSSPPs of class~$0$ -- similar to the weights for the case~$l \ge 2$ -- such that the generating functions are also given by \eqref{eq:GenFunc} for $l=1$. However, the sets $\{w(A) \mid A \in \ASTZ_{n,1}\}$ and $\{w(\pi) \mid \pi \in \CSSPP_{n,0}\}$ are not the same in general and the presented bijections do not apply to that case. Nonetheless, we conjecture that it is possible to obtain a bijective proof by adapting our bijection to the case $l=1$. Throughout the extended abstract, we assume $l \ge 2$.
\end{rem}

\section{Lattice path representations}
\label{sec:LatticePathsRepresentations}

\subsection{ASTZs as lattice paths}

The bijections are based on the concept of osculating paths. \emph{Osculating paths} are lattice paths that neither cross nor share edges but potentially share points. Describing ASMs in terms of osculating paths dates back to \cite{BH95} and was further investigated in \cite{Brak97} and \cite{Beh08}, among others. We adopt this idea for the case of ASTZs.

In the special case of $A\in\ASTZ_{n,l}^{i,j}$, the ASTZ $A$ is mapped to a single path. We consider a trapezoidal grid graph where every vertex presents an entry of $A$ and vertices are connected by an edge if the corresponding entries of $A$ are horizontally or vertically next to each other. The path starts at the corresponding vertex of the bottommost entry of the $1$-column at position~$-i$ and moves upwards. If the path reaches a vertex corresponding to a $1$ or a $-1$, then it turns to the right or to the left, respectively.  If the path reaches a vertex that corresponds to the bottommost entry of a $10$-column, it also turns to the left. Thus, the path ends at the vertex that corresponds to the bottommost entry of the $0$-column at position~$j$. 

We interpret the vertices of the grid graph as lattice points in the coordinate plane and identify the vertex corresponding to the bottommost entry of the column at position~$i$ with the origin. Thus, the elements of $\ASTZ_{n,l}^{i,j}$ are in one-to-one correspondence with lattice paths from $(-l-2i+3,0)$ to $(j-i,j-i)$ which only consist of rightward and upward unit steps and which do not cross the main diagonal.


The statistics on $A \in \ASTZ_{n,l}^{i,j}$ are reflected in the associated lattice path as follows: If the $1$-column we start with is a $10$-column, then the first step of the lattice path is an upward step; otherwise, it is a rightward step. For every $10$-column in the right half of $A$, we have a \emph{left turn} on the main diagonal, that is, a rightward step which is immediately followed by an upward step. All the other left turns in the lattice path result from the $-1$s in $A$.

\begin{exmp}\label{ex:RunningExampleA}
	The following ASTZ is an element of $\ASTZ_{9,4}^{2,8}$. The corresponding path is illustrated in grey. 
\begin{center}
	\begin{tikzpicture}[yscale=0.5,xscale=0.6,baseline=(current bounding box.center)]
		\draw[lightgray,line width=15pt] (8,-7.5) -- (8,-6) -- (11,-6) -- (11,-5) -- (15,-5) -- (15,-3) -- (16,-3) -- (16,-2) -- (18,-2) -- (18,-1) -- (19.5,-1);
		
		\node at (1,0) {$0$};
		\node at (2,0) {$0$};
		\node at (3,0) {$0$};
		\node at (4,0) {$0$};
		\node at (5,0) {$0$};
		\node at (6,0) {$0$};
		\node at (7,0) {$0$};
		\node at (8,0) {$0$};
		\node at (9,0) {$0$};
		\node at (10,0) {$0$};
		\node at (11,0) {$0$};
		\node at (12,0) {$0$};
		\node at (13,0) {$0$};
		\node at (14,0) {$0$};
		\node at (15,0) {$0$};
		\node at (16,0) {$0$};
		\node at (17,0) {$0$};
		\node at (18,0) {$0$};
		\node at (19,0) {$0$};
		\node at (20,0) {$1$};
		
		\node at (2,-1) {$0$};
		\node at (3,-1) {$0$};
		\node at (4,-1) {$0$};
		\node at (5,-1) {$0$};
		\node at (6,-1) {$0$};
		\node at (7,-1) {$0$};
		\node at (8,-1) {$0$};
		\node at (9,-1) {$0$};
		\node at (10,-1) {$0$};
		\node at (11,-1) {$0$};
		\node at (12,-1) {$0$};
		\node at (13,-1) {$0$};
		\node at (14,-1) {$0$};
		\node at (15,-1) {$0$};
		\node at (16,-1) {$0$};
		\node at (17,-1) {$0$};
		\node at (18,-1) {$1$};
		\node at (19,-1) {$0$};
		
		\node at (3,-2) {$0$};
		\node at (4,-2) {$0$};
		\node at (5,-2) {$0$};
		\node at (6,-2) {$0$};
		\node at (7,-2) {$0$};
		\node at (8,-2) {$0$};
		\node at (9,-2) {$0$};
		\node at (10,-2) {$0$};
		\node at (11,-2) {$0$};
		\node at (12,-2) {$0$};
		\node at (13,-2) {$0$};
		\node at (14,-2) {$0$};
		\node at (15,-2) {$0$};
		\node at (16,-2) {$1$};
		\node at (17,-2) {$0$};
		\node at (18,-2) {$0$};
		
		\node at (4,-3) {$0$};
		\node at (5,-3) {$0$};
		\node at (6,-3) {$0$};
		\node at (7,-3) {$0$};
		\node at (8,-3) {$0$};
		\node at (9,-3) {$0$};
		\node at (10,-3) {$0$};
		\node at (11,-3) {$0$};
		\node at (12,-3) {$0$};
		\node at (13,-3) {$0$};
		\node at (14,-3) {$0$};
		\node at (15,-3) {$1$};
		\node at (16,-3) {$-1$};
		\node at (17,-3) {$1$};
		
		\node at (5,-4) {$0$};
		\node at (6,-4) {$0$};
		\node at (7,-4) {$0$};
		\node at (8,-4) {$0$};
		\node at (9,-4) {$0$};
		\node at (10,-4) {$0$};
		\node at (11,-4) {$0$};
		\node at (12,-4) {$0$};
		\node at (13,-4) {$0$};
		\node at (14,-4) {$0$};
		\node at (15,-4) {$0$};
		\node at (16,-4) {$1$};
		
		\node at (6,-5) {$0$};
		\node at (7,-5) {$0$};
		\node at (8,-5) {$0$};
		\node at (9,-5) {$0$};
		\node at (10,-5) {$0$};
		\node at (11,-5) {$1$};
		\node at (12,-5) {$0$};
		\node at (13,-5) {$0$};
		\node at (14,-5) {$0$};
		\node at (15,-5) {$0$};
		
		\node at (7,-6) {$0$};
		\node at (8,-6) {$1$};
		\node at (9,-6) {$0$};
		\node at (10,-6) {$0$};
		\node at (11,-6) {$-1$};
		\node at (12,-6) {$0$};
		\node at (13,-6) {$0$};
		\node at (14,-6) {$1$};
		
		\node at (8,-7) {$0$};
		\node at (9,-7) {$0$};
		\node at (10,-7) {$0$};
		\node at (11,-7) {$0$};
		\node at (12,-7) {$0$};
		\node at (13,-7) {$1$};
		
		\node at (9,-8) {$0$};
		\node at (10,-8) {$0$};
		\node at (11,-8) {$0$};
		\node at (12,-8) {$1$};
	\end{tikzpicture}
\end{center}
	%
	We shall use that ASTZ as a running example throughout the extended abstract and call it $\bm{A}$. It has weight $M^2 R P Q^2$ and is mapped to the following lattice path.
	%
	\begin{center}
	\begin{tikzpicture}[scale=.5]
	\draw [help lines,step=1cm,dashed] (-5.75,0) grid (6.75,6.75);
	
	\draw[->,thick] (-5.75,0)--(6.75,0) node[right]{$x$};
	\draw[->,thick] (0,0)--(0,6.75) node[above]{$y$};
	
	\draw (0,0)--(6.75,6.75);
	
	\fill (-5,0) circle (5pt);
	
	\fill (6,6) circle (5pt);
	
	\draw[ultra thick] (-5,0) -- (-5,1) -- (-2,1) -- (-2,2) -- (2,2) -- (2,4) -- (3,4) -- (3,5) -- (5,5) -- (5,6) -- (6,6);
	
	\node at (-5.5,0.5) {$P$};
	\node at (-2.5,1.5) {$M$};
	\node at (1.5,2.5) {$Q$};
	\node at (2.5,4.5) {$M$};
	\node at (4.5,5.5) {$Q$};
	
	\end{tikzpicture}
	\end{center}
\end{exmp}

\subsection{CSSPPs as lattice paths}
\label{sec:CSSPPLatticePaths}

The representation of CSSPPs as a family of nonintersecting lattice paths is well-known. In the special case of $\lambda\in\CSSPP_{n,k}^{j}$, the CSSPP $\lambda$ is encoded by a single lattice path. If $\lambda$ is given by  \resizebox*{!}{\baselineskip}{\ytableaushort{{\lambda_1}{\lambda_2}{\dots}{\lambda_j}}} such that $\lambda_1=j+k$, then it is associated to a lattice path from $(0,j+k-1)$ to $(j-1,0)$ that only comprises rightward and downward unit steps in the following way: we start at the point $(-1,\lambda_1-1)$ and draw a lattice path to $(j-1,0)$ in such a way that its horizontal steps are exactly the steps from $(i-2,\lambda_i-1)$ to $(i-1,\lambda_i-1)$ for all $i\in\{1,\dots,j\}$. Eventually, we delete the first step. 

The statistics on $\lambda$ translate into the following properties: The lattice path has exactly $q(\lambda)$ horizontal steps at height $0$. The step right beneath the line $y=x+d$ is horizontal if and only if $p_d(\lambda)=1$. Finally, the number of horizontal steps below the line $y=x+k$ that are neither at height $0$ nor directly below $y=x+d$ equals $\mu_d(\lambda)$.

By using this lattice path representation, we obtain an expression for the number of partitions $\lambda \in \CSSPP_{n,k}^{j}$ with $\mu=\mu_d(\lambda)$, $p=p_d(\lambda)$, and $q=q(\lambda)$ for any $d\in\{1,\dots,k\}$. It is given by
\begin{equation}\label{eq:EnumCSSPP}
\binom{j-1}{\mu+p+q} \binom{j-q+k-3}{\mu}.
\end{equation}

This identity can easily be seen as follows: Consider a partition of class~$k$ and with $j$ parts. Its corresponding lattice path goes from $(0,j+k-1)$ to $(j-1,0)$ and crosses the line $y=x+k$. The intersection point divides the path into two smaller paths. The lower one contains all the steps possibly contributing a factor $M$, $P$, or $Q$ to the weight. It consists of $\mu+p+q$ horizontal steps, and, therefore, the coordinates of the intersection with the line $y=x+k$ are given by $(j-\mu-p-q-1,j+k-\mu-p-q-1)$. Next, we remove the following steps from the lower path: the $q$ horizontal steps at height $0$, the vertical step from height $0$ to height $1$, and the step just below the line $y=x+d$. Due to their uniquely determined positions, these steps can easily be reinserted after removing. In the end, we obtain a path consisting of $\mu$ horizontal and $j+k-\mu-q-3$ vertical steps. The final path looks as shown on the right-hand side in Example~\ref{exmp:CSSPPEnum}. Paths of this kind are enumerated by \eqref{eq:EnumCSSPP}. Note that we also obtain \eqref{eq:EnumCSSPP} by summing \eqref{eq:MainEnumeration} over all $1 \le i \le n$.

\begin{exmp}\label{exmp:CSSPPEnum}
	The CSSPP \resizebox*{!}{\baselineskip}{\ytableaushort{{11}9765411}} is of class~$3$ and has weight~$M^2 R P Q^2$ if $d=1$. It is mapped to the lattice path on the left-hand side. We call this CSSPP $\bm{\pi}$ for later reference. On the right-hand side, we see its reduced lattice path representation.

\begin{center}
	\begin{tikzpicture}[scale=.5,baseline=(current bounding box.center)]
	\draw [help lines,step=1cm,dashed] (0,0) grid (7.75,10.75);
	
	\draw[->,thick] (0,0)--(7.75,0) node[right]{$x$};
	\draw[->,thick] (0,0)--(0,10.75) node[above]{$y$};
	
	\draw (0,3)--(5.5,8.5);
	\draw (5.5,8.5) node[right]{\contour{white}{$y=x+k$}};
	
	\draw (0,1)--(5.5,6.5);
	\draw (5.5,6.5) node[right]{\contour{white}{$y=x+d$}};
	
	\fill (7,0) circle (5pt);
	
	\fill (0,10) circle (5pt);
	
	\node at (2.5,5.5) {\contour{white}{$M$}};
	\node at (3.5,4.5) {\contour{white}{$P$}};
	\node at (4.5,3.5) {$M$};
	\node at (5.5,.5) {$Q$};
	\node at (6.5,.5) {$Q$};
	
	\draw[ultra thick] (0,10) --++ (0,-1) --++ (0,-1) --++ (1,0) --++ (0,-1) --++ (0,-1) --++ (1,0) --++ (0,-1) --++ (1,0) --++ (0,-1) --++ (1,0) --++ (0,-1) --++ (1,0) --++ (0,-1) --++ (0,-1) --++ (0,-1) --++ (1,0) --++ (1,0);
	
	\end{tikzpicture}\qquad\qquad
	\begin{tikzpicture}[scale=.5,baseline=(current bounding box.center)]
	\draw [help lines,step=1cm,dashed] (-.75,.25) grid (4.75,10.75);	
	
	\fill (0,10) circle (5pt);
	
	\fill (2,5) circle (5pt);
	
	\fill (4,1) circle (5pt);
	
	\draw[ultra thick] (0,10) --++ (0,-1) --++ (0,-1) --++ (1,0) --++ (0,-1) --++ (0,-1) --++ (1,0) --++ (0,-1) --++ (1,0) --++ (0,-1) --++ (0,-1) --++ (1,0) --++ (0,-1) --++ (0,-1);
	
	\draw[decorate,thick,decoration={brace,amplitude=.125cm}]  (0,10.25) -- (2,10.25);
	\node[anchor=south] at (1,10.5) {$j-\mu-p-q-1$};
	
	\draw[decorate,thick,decoration={brace,amplitude=.125cm}]  (-.25,5) -- (-.25,10);
	\node[anchor=east] at (-.75,7.5) {$\mu+p+q$};
	
	\draw[decorate,thick,decoration={brace,mirror,amplitude=.125cm}]  (2,.75) -- (4,.75);
	\node[anchor=north] at (3,.5) {$\mu$};
	
	\draw[decorate,thick,decoration={brace,mirror,amplitude=.125cm}]  (4.25,1) -- (4.25,5);
	\node[anchor=west] at (4.5,3) {$j+k-\mu-q-3$};
	
	\end{tikzpicture}
\end{center}
\end{exmp}

\section{From ASTZs to CSSPPs}
\label{sec:Bijection}

So far, we have seen how to represent elements from $\ASTZ_{n,l}^{i,j}$ and $\CSSPP_{n,l-1}^{j}$ as lattice paths. In this section, we construct a  weight-preserving bijection between these two families of lattice paths. In particular, we show how to go from $\ASTZ_{n,l}^{i,j}$ to $\CSSPP_{n,l-1}^{j}$. We omit the construction of the inverse mapping.

For the sake of simplicity, we assume $i<j$ in the following construction. For $i > j$, the set $\ASTZ_{n,l}^{i,j}$ is empty. In the case $i=j$, there is only one $A\in\ASTZ_{n,l}^{j,j}$. It follows that $\mu(A)=p(A)=q(A)=0$. There is also only one $\lambda\in\CSSPP_{n,l-1}^{j}$ such that $\mu_d(\lambda)=p_d(\lambda)=q(\lambda)=0$, namely the integer partition that consists of $j$ times the part $j+l-1$. Note that it is still possible to accommodate the case $i=j$ into the following construction by a few small but cumbersome adjustments.

Let $i<j$. Consider $A \in \ASTZ_{n,l}^{i,j}$ and write $\mu = \mu(A)$, $p = p(A)$, and $q = q(A)$. We encode the respective lattice path by its \emph{left turn representation} \cite{KM93}, \cite{Kra97}: Since a lattice path with given starting point and endpoint is uniquely determined by the coordinates $(x_m, y_m)$ of its left turns, we can represent the lattice path associated to $A$ by the following two-rowed array:

\begin{equation}\label{eq:LeftTurn}
\begin{array}{ccccccccccc}
-2i-l+4 & \le & x_1 & < & x_2 & < & \dots & < & x_{\mu+q} & \le & j-i-1\\
p & \le & y_1 & < & y_2 & < & \dots & < & y_{\mu+q} & \le & j-i-1
\end{array}
\end{equation}
%
Since the lattice path stays weakly above the main diagonal, it follows that $x_m \le y_m$ for all $1 \le m \le \mu+q$.

Next, we transform each row of \eqref{eq:LeftTurn} into a lattice path that consists of upward and rightward unit steps. If the row is given by $a \le z_1 < \dots < z_c \le b$, then the lattice path goes from $(-c,a-b+c-1)$ to $(0,0)$ such that each $z_m$ corresponds to a horizontal step at height~$z_m-m-b+c$ for all $m \in \{1,\dots,c\}$.

We continue by possibly truncating these paths: Each factor of $Q$ in the weight of $A$ corresponds to a left turn with coordinates $(x_m,y_m)$ such that $x_m=y_m$. We remove these redundant pieces of information by deleting the corresponding horizontal steps in the path associated to the $x$-coordinates. If $p=0$, then $y_1=0$. In that case, we remove the first step in the path corresponding to the $y$-coordinates, too.

We draw the resulting paths as nonintersecting lattice paths. Take $S_x^i \coloneqq (-\mu,-j-i-l+4+\mu+q)$ as starting point and $(0,0)$ as endpoint for the reduced path associated to the $x$-coordinates and analogously $S_y^i \coloneqq (-\mu-p-q,-j+i+\mu+p+q)$ and $(-1,0)$ for the reduced path associated to the $y$-coordinates. These paths are nonintersecting by construction. Hence, the former path ends with the vertical step from $(0,-1)$ to $(0,0)$. We remove this step and change the endpoint from $(0,0)$ to $E_x \coloneqq (0,-1)$. In addition, we change the endpoint of the other path from $(-1,0)$ to $E_y \coloneqq (0,0)$ by adding the horizontal step from $(-1,0)$ to $(0,0)$.

\begin{exmp}\label{ex:leftturns}
The lattice path corresponding to $\bm{A}$ in Example~\ref{ex:RunningExampleA} has the following left turn representation:
%
\begin{equation*}
\begin{array}{ccccccccccc}
-4 & \le & -2 & < & 2 & < & 3 & < & 5 & \le & 5\\
1 & \le & 1 & < & 2 & < & 4 & < & 5 & \le & 5\\
\end{array}
\end{equation*}
%
The corresponding reduced paths are as follows:
%
\begin{center}
	\begin{tikzpicture}[scale=.5,baseline=(current bounding box)]
		
		\draw [help lines,step=1cm,dashed] (-.75,-.75) grid (2,6);
		
		\draw[->,thick] (-.75,6)--(2.75,6) node[right]{$x$};
		\draw[->,thick] (2,-.75)--(2,6.75) node[above]{$y$};
		
		\fill (0,0) circle (5pt);
		\fill (2,6) circle (5pt);
		
		\node at (.25,2.5) {\contour{white}{$-2$}};
		\node at (1.5,5.5) {$3$};
		
		\draw[ultra thick] (0,0) -- ++(0,1) -- ++(0,1) -- ++(1,0) -- ++(0,1) -- ++(0,1) -- ++(0,1) -- ++(1,0) -- ++(0,1);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=.5,baseline=(current bounding box)]
		
		\draw [help lines,step=1cm,dashed] (-.75,-.75) grid (4,1);
		
		\draw[->,thick] (-.75,1)--(4.75,1) node[right]{$x$};
		\draw[->,thick] (4,-.75)--(4,1.75) node[above]{$y$};
		
		\fill (0,0) circle (5pt);
		\fill (4,1) circle (5pt);
		
		\draw[ultra thick] (0,0) -- ++(1,0) -- ++(1,0) -- ++(0,1) -- ++(1,0) -- ++(1,0);
		
		\node at (.5,.5) {$1$};
		\node at (1.5,.5) {$2$};
		\node at (2.5,1.5) {$4$};
		\node at (3.5,1.5) {$5$};
	\end{tikzpicture}
\end{center}
%
Thus, we obtain these two nonintersecting lattice paths:
%
\begin{center}
\begin{tikzpicture}[scale=.5]
\draw [help lines,step=1cm,dashed] (-5.75,-6.75) grid (0.75,0.75);

\fill (-5,-1) circle (5pt);

\fill (0,0) circle (5pt);

\draw[ultra thick] (0,0) node[right]{\contour{white}{$E_y$}} --++ (-1,0) --++ (-1,0) --++ (-1,0) --++ (0,-1) --++ (-1,0) --++ (-1,0) node[left]{\contour{white}{$S_y^i$}};

\fill (-2,-6) circle (5pt);

\fill (0,-1) circle (5pt);

\draw[ultra thick] (0,-1) node[right]{\contour{white}{$E_x$}} --++ (-1,0) --++ (0,-1) --++ (0,-1) --++ (0,-1) --++ (-1,0) --++ (0,-1) --++ (0,-1) node[left]{\contour{white}{$S_x^i$}};
\end{tikzpicture}
\end{center}
\end{exmp}

Note that the number of pairs of nonintersecting lattice paths from $S_x^i$ and $S_y^i$ to $E_x$ and  $E_y$ can be calculated with the help of the well-known Lindstr{\"o}m-Gessel-Viennot lemma and is given by \eqref{eq:MainEnumeration}. Thus, we have proved Theorem~\ref{thm:MainEnumeration}.

Our next step is to \q{shuffle} the two paths. For $A \in \ASTZ_{n,l}^{i,j}$, we repeat the following process of shifting and switching paths $i-1$ times: At the beginning of the $\tilde{\imath}\textsuperscript{th}$ step, we have two nonintersecting lattice paths from $\{S_x^{i}, S_y^{i}-(0,\tilde{\imath}-1)\}$ to  $\{E_x-(0,\tilde{\imath}-1), E_y\}$.  We shift the path with endpoint $E_y$ down by one unit step and the other path up by $(0,\tilde{\imath})$. After switching the paths at the top right intersection point, we shift the path with endpoint $E_x$ down by $(0,\tilde{\imath})$. This procedure yields two nonintersecting lattice paths from from $\{S_x^{i}, S_y^{i}-(0,\tilde{\imath})\}$ to $\{E_x-(0,\tilde{\imath}), E_y\}$. By repeating this process $i-1$ times in total, we obtain a pair of nonintersecting lattice paths from $\{S_x^{i}, S_y^{i}-(0,i-1)\}$ to $\{E_x-(0,i-1), E_y\}$.


At the end, the upper path consists of $\mu+p+q$ horizontal steps and $j-\mu-p-q-1$ vertical steps, whereas the lower one consists of $\mu$ horizontal steps and $j+l-\mu-q-4$ vertical steps. Compare these paths with the illustration in Example~\ref{exmp:CSSPPEnum}. To construct the CSSPP, we have to rotate the upper path by $90^{\circ}$ and horizontally or vertically reflect the lower path. We have four possibilities in total for that. Each of them creates a possibly different but equally valid bijection. Finally, we insert the missing steps that correspond to the steps we removed as described in Section~\ref{sec:CSSPPLatticePaths}.

\begin{exmp}
	
	Since $\bm{A}\in\ASTZ_{9,4}^{2,8}$, we \q{shuffle} the paths from Example~\ref{ex:leftturns} once:
	\begin{center}
		\begin{tikzpicture}[scale=.5,baseline=(current bounding box.center)]
		\draw [help lines,step=1cm,dashed] (-5.75,-6.75) grid (.75,.75);
		
		\fill (-5,-1) circle (5pt);
		
		\fill (0,0) circle (5pt);
		
		\draw[ultra thick] (0,0) --++ (-1,0) --++ (-1,0) --++ (-1,0) --++ (0,-1) --++ (-1,0) --++ (-1,0);
		
		\fill (-2,-6) circle (5pt);
		
		\fill (0,-1) circle (5pt);
		
		\draw[ultra thick] (0,-1) --++ (-1,0) --++ (0,-1) --++ (0,-1) --++ (0,-1) --++ (-1,0) --++ (0,-1) --++ (0,-1);
		\end{tikzpicture}
		\quad$\longleftrightarrow$\quad
		\begin{tikzpicture}[scale=.5,baseline=(current bounding box.center)]
		\draw [help lines,step=1cm,dashed] (-5.75,-6.75) grid (.75,.75);
		
		\fill (-5,-2) circle (5pt);
		
		\fill (0,0) circle (5pt);

		\draw[ultra thick] (0,-1) --++ (-1,0) --++ (-1,0) --++ (-1,0) --++ (0,-1) --++ (-1,0) --++ (-1,0);
		
		\fill (-2,-5) circle (5pt);
		
		\fill (0,-1) circle (5pt);
		
		\draw[ultra thick] (0,0) --++ (-1,0) --++ (0,-1) --++ (0,-1) --++ (0,-1) --++ (-1,0) --++ (0,-1) --++ (0,-1);
		
		\fill[red] (-1,-1) circle (5pt);
		\end{tikzpicture}
		\quad$\longleftrightarrow$\quad
		\begin{tikzpicture}[scale=.5,baseline=(current bounding box.center)]
		\draw [help lines,step=1cm,dashed] (-5.75,-6.75) grid (.75,.75);
		
		\fill (-5,-2) circle (5pt);
		
		\fill (0,0) circle (5pt);
		
		\draw[ultra thick] (0,0) --++ (-1,0) --++ (0,-1) --++ (-1,0) --++ (-1,0) --++ (0,-1) --++ (-1,0) --++ (-1,0);
		
		\fill (-2,-6) circle (5pt);
		
		\fill (0,-2) circle (5pt);
		
		\draw[ultra thick] (0,-2) --++ (-1,0) --++ (0,-1) --++ (0,-1) --++ (-1,0) --++ (0,-1) --++ (0,-1);
		\end{tikzpicture}
	\end{center}
If we rotate the upper path clockwise by $90^{\circ}$, reflect the lower path along a vertical axis, and set $d=1$, $\bm{A}$ is mapped to $\bm{\pi}$ as displayed in Example~\ref{exmp:CSSPPEnum}. 
\end{exmp}


\section{Concluding remarks}
\label{sec:Remarks}

\subsection{Other bijections}

There are no general bijections known between ASTZs and CSSPPs. In comparison to the bijection presented above, Fischer \cite{Fis19} observed that there is a much simpler bijection in the case~$r=1$ if we disregard the statistics~$\mu$ and $\mu_d$, respectively. Even in the case of ASMs and DPPs, all established bijections by Ayyer \cite{Ayy10}, Striker \cite{Str11}, and Fulmek \cite{Ful20} are restricted to permutation matrices and DPPs without special parts. None of them has been extended to the general case yet.

\subsection{Towards a general bijection between ASTZs and CSSPPs}

The key idea of the bijection in the present extended abstract is the representation of ASTZs as a family of osculating lattice paths. A simple and naive approach to generalising the bijection would be to map each of these lattice paths separately to an integer partition in order to obtain the rows of a CSSPP.

For instance, there are five $(3,2)$-ASTZs with $0$-columns at positions $1$ and $3$ as shown below. Each of them corresponds to a family of two osculating paths. If we map each path individually to a partition, we would get a CSSPP of shape $(3,1)$. But there are seven CSSPPs of class~$1$ and of shape~$(3,1)$ in total.

\bigskip 

{\centering
\resizebox{\textwidth}{!}{\begin{math}
		\begin{array}{cccccc}
			1 & 0 & 0 & 0 & 0 & 0\\
			& 0 & 0 & 0 & 1 & \\
			& & 1 & 0 & & 
		\end{array}\qquad
		\begin{array}{cccccc}
			0 & 1 & 0 & 0 & 0 & 0\\
			& 0 & 0 & 0 & 1 & \\
			& & 1 & 0 & & 
		\end{array}\qquad
		\begin{array}{cccccc}
			0 & 0 & 1 & 0 & 0 & 0\\
			& 1 & -1 & 0 & 1 & \\
			& & 1 & 0 & & 
		\end{array}\qquad
		\begin{array}{cccccc}
			0 & 0 & 0 & 1 & 0 & 0\\
			& 1 & 0 & -1 & 1 & \\
			& & 1 & 0 & & 
		\end{array}\qquad
		\begin{array}{cccccc}
			0 & 0 & 0 & 0 & 1 & 0\\
			& 1 & 0 & 0 & 0 & \\
			& & 1 & 0 & & 
		\end{array}
\end{math}}

\bigskip 

\bigskip 

\resizebox{.75\textwidth}{!}{\begin{math}
		\begin{ytableau}
			4 & 4 & 4 \\
			\none & 2
		\end{ytableau}\qquad
		\begin{ytableau}
			4 & 4 & 3 \\
			\none & 2
		\end{ytableau}\qquad
		\begin{ytableau}
			4 & 4 & 2 \\
			\none & 2
		\end{ytableau}\qquad
		\begin{ytableau}
			4 & 4 & 1 \\
			\none & 2
		\end{ytableau}\qquad
		\begin{ytableau}
			4 & 3 & 3 \\
			\none & 2
		\end{ytableau}\qquad
		\begin{ytableau}
			4 & 3 & 2 \\
			\none & 2
		\end{ytableau}\qquad
		\begin{ytableau}
			4 & 3 & 1 \\
			\none & 2
		\end{ytableau}
\end{math}}
\par}

\bigskip 

Thus, our naive approach fails. However, this bijection might still serve as a basis for a general bijection between ASTZs and CSSPPs.	

%\acknowledgements{}

%% 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}
