# Alternating Sign Pentagons and Magog Pentagons

Moritz Gangl  Fakultät für Mathematik, Universität Wien, Austria
<EMAIL_ADDRESS>
(Date: March 2023)

###### Abstract.

Alternating sign triangles have been introduced by Ayyer, Behrend and Fischer
in 2016 and it was proven that there is the same number of alternating sign
triangles with $n$ rows as there is of $n\times n$ alternating sign matrices.
Later on Fischer gave a refined enumeration of alternating sign triangles with
respect to a statistic $\rho$, having the same distribution as the unique 1 in
the top row of an alternating sign matrix, by connecting alternating sign
triangles to $(0,n,n)$ \- Magog trapezoids. We introduce two more statistics
counting the all $0$-columns on the left and right in an alternating sign
triangle yielding objects we call alternating sign pentagons. We then show the
equinumeracy of these alternating sign pentagons with Magog pentagons of a
certain shape taking into account the statistic $\rho$. Furthermore we deduce
a generating function of these alternating sign pentagons with respect to the
statistic $\rho$ in terms of a Pfaffian and consider the implications of our
new results on some open conjectures.

The author acknowledges the financial support from the Austrian Science
Foundation FWF, grant P34931.

##  1\. Introduction

An _alternating sign matrix_ (ASM) of order $n$, as introduced by Robbins and
Rumsey (see [RR86]), is an $n\times n$ matrix with entries in $\\{-1,0,1\\}$
such that all column- and row-sums are equal to $1$ and the non-zero entries
alternate in sign along rows and columns. For example the matrix below is an
alternating sign matrix of order $7$.

$\begin{pmatrix}0&0&0&1&0&0&0\\\ 0&1&0&-1&1&0&0\\\ 1&-1&0&1&-1&1&0\\\
0&0&1&-1&0&0&1\\\ 0&1&-1&1&0&0&0\\\ 0&0&1&-1&1&0&0\\\
0&0&0&1&0&0&0\end{pmatrix}$

They conjectured that the set of ASMs of order $n$ is enumerated by the
following beautiful product formula.

$\prod_{i=0}^{n-1}\frac{(3i+1)!}{(n+i)!}$

In 1994 Zeilberger [Zei96] gave the first proof of this conjecture by showing
that for all $n\geq 1$ the number of $n\times n$ _\- Gog trapezoids_ , which
are in bijective correspondence with alternating sign matrices (ASMs) of order
$n$, is equal to the number of $n\times n$ _\- Magog trapezoids_. It relied on
a result of Andrews [And94] enumerating the set of _totally symmetric self
complementary plane partitions_ (TSSCPPs) in a $2n\times 2n\times 2n$ box,
which are in bijective correspondence with $n\times n$ \- Magog trapezoids.
However, Zeilberger was able to prove even more, he actually showed that for
all $n\geq k\geq 1$, the number of $n\times k$ \- Gog trapezoids is equal to
the number of $n\times k$ \- Magog trapezoids.

Over 20 years later, Ayyer, Behrend and Fischer [ABF20] introduced another
class of objects enumerated by the same sequence, so called _alternating sign
triangles_ (ASTs). In 2019 Fischer [Fis19] came up with an alternative proof
of this enumeration formula, using a constant term approach which she
developed over the years [Fis06, Fis07, Fis10, Fis11, Fis16]. This way, she
was able to relate ASTs to $n\times n$ \- Magog trapezoids. In the same paper
she stated a conjecture by Behrend, relating ASMs with a certain number of all
zero south-east diagonals, counted from the top right corner, and all zero
south-west diagonals, counted from the top left corner, to _alternating sign
pentagons_ (ASPs), i.e. ASTs with a certain number of all zero columns on the
right and on the left, including two further statistics on both sides. The
above mentioned ASMs with cut off top corners are in easy bijection with a
class of objects called _Gog pentagons_ , a generalisation of Gog trapezoids
and Gog trapezoids in turn are equinumerous with Magog trapezoids as shown by
Zeilberger [Zei96]. However it is still an open problem whether there is a
generalisation of the Magog trapezoids corresponding to Gog pentagons. While
already in 2016 Biane and Cheballah [BC16] introduced a family of objects, so
called _GOGAm pentagons_ which they conjectured to be equinumerous with the
family of Gog pentagons, this is still an open problem. In this paper we will
define so called _Magog pentagons_ , not related to the GOGAm pentagons, and
give a proof similar in style to Fischers proof from 2019, relating the family
of alternating sign pentagons mentioned in the conjecture by Behrend with the
newly defined Magog pentagons. This shows that the newly introduced objects
are a good candidate for the Gog pentagon equivalent on the Magog-side and
yields an equivalent conjecture to the one formulated by Behrend. We will even
be able to include a statistic on both sides for this result and as a
corollary we will also prove a partial result of the conjecture by Behrend.

##  2\. Prerequisites and Main Results

In 2017 Ayyer, Behrend and Fischer introduced alternating sign triangles in
[ABF20] as defined below.

######  Definition 2.1.

An _alternating sign triangle_ (AST) of order $n$ is a triangular array of the
form

$\begin{matrix}a_{1,1}&a_{1,2}&a_{1,3}&...&...&...&a_{1,2n-1}\\\
&a_{2,2}&a_{2,3}&...&...&a_{2,2n-2}&\\\ &&...&...&...&&\\\
&&&a_{n,n}&&&\end{matrix}$

with $a_{i,j}\in\\{-1,0,1\\}$ such that

  1. (1)

the non-zero entries alternate along each row and column,

  2. (2)

the row sums are equal to $1$,

  3. (3)

and the top most non-zero entry of each column is equal to $1$, if it exists.

A $1$-_column_ is a column of an AST which sums up to $1$. Sticking to the
notation in [Fis19], we further differentiate between $10$-_columns_ and
$11$-_columns_. The former are those $1$-columns whose bottom entry is $0$,
whereas in the latter the bottom entry is $1$. Furthermore we define for an
AST $T$ the following statistic $\rho$ by

(2.1) $\rho(T)=\\#(\textrm{of }11\textrm{-columns to the left of the central
column})\\\ +\\#(\textrm{of }10\textrm{-columns to the right of the central
column})+1.$

We are also sticking to the following notation introduced by Fischer in
[Fis19] and label the columns of the AST from left to right, starting with
$0$, skipping the central column and ending with $2n-3$. See for example the
labels of the columns of the AST of order $4$ in blue below.

$\begin{matrix}0&0&0&1&0&0&0\\\ &1&0&-1&0&1&\\\ &&1&0&0&&\\\ &&&1&&&\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}&&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}5}\end{matrix}$

Note that the central column of an AST is always a $1$-column since its bottom
entry $a_{n,n}$ is equal to $1$ and there are $n$ $1$-columns in any AST of
order $n$. For example the seven ASTs of order $3$ and their $\rho$-statistic
are given by

$\displaystyle\begin{matrix}1&0&0&0&0\\\ &1&0&0&&\rho=3\\\
&&1&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}1&0&0&0&0\\\
&0&0&1&&\rho=2\\\
&&1&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}0&0&0&0&1\\\
&0&0&1&&\rho=1\\\ &&1&&\end{matrix}\quad\textrm{,}\quad$
$\displaystyle\begin{matrix}0&0&0&0&1\\\ &1&0&0&&\rho=2\\\
&&1&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}0&0&0&1&0\\\
&1&0&0&&\rho=3\\\
&&1&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}0&1&0&0&0\\\
&0&0&1&&\rho=1\\\ &&1&&\end{matrix}\quad\textrm{,}\quad$
$\displaystyle\begin{matrix}0&0&1&0&0\\\ &1&-1&1&&\rho=2\\\
&&1&&\end{matrix}\quad\textrm{,}\quad$

In the paper [ABF20] Ayyer, Behrend and Fischer showed that for any positive
integer $n$ there is the same number of ASTs of order $n$ as there is of ASMs
of order $n$. Similar to many other results relating equinumerous objects like
TSSCPPs in a $2n\times 2n\times 2n$ box [MRR86] or descending plane partitions
(DPPs) whose parts do not exceed $n$ [MRR83] with ASMs, the proof is not
bijective. Note that finding bijective proofs in this area is very hard, some
say even impossible. For the reader interested in an overview on what has been
tried we refer to the literature(see [Bet19, BC13, CB12, FZJ08, Kra16] for
ASMs and TSSCCPs and [FSA23, FK20a, FK22, FK20c, FK20b, FH22] for ASMs and
DPPs). The main objects of interest in this paper are a generalisation of
ASTs, so called alternating sign pentagons.

######  Definition 2.2.

Let $n\in\mathbb{N}$ and $0\leq l\leq n-2<r\leq 2n-3$. An
$(n,l,r)$-_alternating sign pentagon_ (ASP) is an AST of order $n$, where the
positions $j_{1},...,j_{n-1}$ of the $n-1$ non-central $1$-columns satisfy
$l\leq j_{1}<...<j_{n-1}\leq r$.

Note that then necessarily all the columns indexed by $0,...,l-1,r+1,...,2n-3$
only consist of $0$’s, so we can simply cut them off. To see this assume the
contrary and consider the right most $0$-column not consisting of all $0$’s.
Since it is not a $1$-column, the bottom most non-zero entry has to be $-1$,
but then the row of this entry cannot sum to $1$ as there are non nonzero
entries to the right of it. A similar argument works for the left side. This
justifies also the name alternating sign pentagon. See below an $(6,3,8)$ \-
ASP $T$ with $\rho(T)=2$.

$\setcounter{MaxMatrixCols}{11}\begin{matrix}0&0&0&0&0&1&0&0&0&0&0\\\
&0&0&0&1&-1&0&0&0&1&\\\ &&0&0&0&1&0&0&0&&\\\ &&&1&-1&0&0&1&&&\\\
&&&&1&-1&1&&&&\\\ &&&&&1&&&&\end{matrix}\begin{matrix}&&0&0&1&0&0&0&0\\\
&&0&1&-1&0&0&0&1\\\ &\leftrightarrow&0&0&1&0&0&0&\\\ &&1&-1&0&0&1&&&\\\
&&&1&-1&1&&&&\\\ &&&&1&&&&\end{matrix}$

These objects were already hinted at in [Fis19]. Our main result relates the
$(n,l,r)$ \- ASPs to combinatorial objects related to TSSCCPs, making them fit
into the bigger picture connecting ASMs, ASTs, TSSCCPs, DPPs. It is well known
(see for example [Kra16, Zei96]) that TSSCCPs correspond bijectively to
$(0,n,n)$ \- Magog trapezoids as defined below, where we borrow the
terminology from [Zei96].

######  Definition 2.3.

An $(m,n,k)$-_Magog trapezoid_ is an array of positive integers consisting of
the top $k$ rows of an array

$\begin{matrix}a_{1,1}&a_{2,1}&...&...&a_{n,1}\\\
a_{2,2}&a_{3,2}&...&a_{n,2}&\\\ ...&...&...&&\\\ a_{n-1,n-1}&a_{n,n-1}&&&\\\
a_{n,n}&&&&\end{matrix}$

such that entries along rows are weakly increasing, entries along columns are
weakly decreasing, and and such that the entries in the first row are bounded
by $a_{k,1}\leq m+k$.

We now define a new object generalising the $(m,n,k)$ \- Magog trapezoids from
above.

######  Definition 2.4.

An $(m,n,k,l)$-_Magog pentagon_ consists of the first $l$ south-east
diagonals, where we count the diagonals from top right to bottom left, of an
$(m,n,k)$ \- Magog trapezoid. In other words, it is an array of positive
integers consisting of the intersection of the top $k$ rows and the first $l$
south-east diagonals, where we count the diagonals from top right to bottom
left, of an array

$\begin{matrix}a_{1,1}&a_{2,1}&...&...&a_{n,1}\\\
a_{2,2}&a_{3,2}&...&a_{n,2}&\\\ ...&...&...&&\\\ a_{n-1,n-1}&a_{n,n-1}&&&\\\
a_{n,n}&&&&\end{matrix}$

such that entries along rows are weakly increasing, entries along columns are
weakly decreasing, and such that the entries in the first row are bounded by
$a_{k,1}\leq m+k$. We define a statistic $\tau$ on $(m,n,k,l)$ \- Magog
pentagons $P$ by

(2.2) $\tau(P)=n+\sum_{i=1}^{k}(a_{n-1,i}-a_{n,i}).$

Note that since $(m,n,k,2n-1)$ \- Magog pentagons are simply $(m,n,k)$ \-
Magog trapezoids this statistic is also defined on Magog trapezoids. This
statistic was introduced by Mills, Robbins and Rumsey on Magog triangles
[MRR86].

See for example below the $(0,10,4,11)$ \- Magog pentagon with weight
$\tau(P)=5$.

$\begin{matrix}1&2&2&4&5&6&7&7&8&9\\\ 1&2&2&4&5&5&5&5&7\\\ &2&2&4&4&4&4&5\\\
&&2&2&2&2&3\\\ \end{matrix}$

Our main result explains the connection between weighted $(n,l,r)$ \- ASPs and
certain weighted Magog pentagons, generalising the relation of ASTs and
$(0,n,n)$ \- Magog trapezoids proven by Fischer in [Fis19].

######  Theorem 2.5.

Let $n\in\mathbb{N}$, $1\leq p\leq n$ and $0\leq l\leq n-2<r\leq 2n-3$, such
that $l+r<2n-2$ and $r-l>n-3$. The set of $(n,l,r)$ \- ASPs $P$ with
$\rho(P)=p$ and the set of $(n,2n-3-r,2n-3-l)$ \- ASPs $T$ with
$\rho(T)=n+1-p$ are equinumerous with the set of $(0,n,r+2-n,r-l)$ \- Magog
pentagons $M$ with $\tau(M)=p$.

Consider for example for $n=3$, $l=0$, $r=2$ the five $(3,0,2)$ \- ASPs,
$(3,1,3)$ \- ASPs and their $\rho$-statistic and the five $(0,3,1,2)$ \- Magog
pentagons with their $\tau$-statistic below.

$\displaystyle\begin{matrix}1&0&0&0&\\\ &1&0&0&\\\ &&1&&\\\
&&\rho=3&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}0&0&0&1&\\\ &1&0&0&\\\
&&1&&\\\ &&\rho=3&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}0&0&1&0&\\\
&1&-1&1&\\\ &&1&&\\\ &&\rho=2&&\end{matrix}\quad\textrm{,}\quad$
$\displaystyle\begin{matrix}1&0&0&0&\\\ &0&0&1&\\\ &&1&&\\\
&&\rho=2&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}0&1&0&0&\\\ &0&0&1&\\\
&&1&&\\\ &&\rho=1&&\end{matrix}\quad\textrm{,}\quad$
$\displaystyle\begin{matrix}&0&0&0&1\\\ &0&0&1&\\\ &&1&&\\\
&&\rho=1&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}&1&0&0&0\\\ &0&0&1&\\\
&&1&&\\\ &&\rho=1&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}&0&0&0&1\\\
&1&0&0&\\\ &&1&&\\\ &&\rho=2&&\end{matrix}\quad\textrm{,}\quad$
$\displaystyle\begin{matrix}&0&1&0&0\\\ &1&-1&1&\\\ &&1&&\\\
&&\rho=2&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}&0&0&1&0\\\ &1&0&0&\\\
&&1&&\\\ &&\rho=3&&\end{matrix}\quad\textrm{,}\quad$
$\displaystyle\begin{matrix}&&1&1&\\\
&&\tau=3&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}&&2&2&\\\
&&\tau=3&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}&&2&3&\\\
&&\tau=2&&\end{matrix}$ $\displaystyle\begin{matrix}&&1&2&\\\
&&\tau=2&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}&&1&3&\\\
&&\tau=1&&\end{matrix}\quad\textrm{.}\quad$

Although we have some restriction on $l$ and $r$ in Theorem 2.5 this still
exhausts the full class of ASPs due to two simple reasons of symmetry
explained in the following two lemmata.

######  Lemma 2.6.

Let $n\in\mathbb{N}$, $1\leq p\leq n$ and $0\leq l\leq n-2<r\leq 2n-3$, such
that $l+r<2n-2$. The number of $(n,l,r)$ \- ASPs $P$ with $\rho(P)=p$ is the
same as the number of $(n,2n-3-r,2n-3-l)$ \- ASPs $T$ with $\rho(T)=n+1-p$.

###### Proof.

Note that ASTs are symmetric with respect to reflection along the central
column. This reflection turns $(n,l,r)$ \- ASPs into $(n,2n-3-r,2n-3-l)$ \-
ASPs and if $l+r-2n+2<0$, then

$(2n-3-r)+(2n-3-l)-2n+2=2n-4-l-r=-(l+r-2n+3)-1\geq-1.$

So really all possible ASPs of order $n$ are in bijction with some class in
the first family. It remains to check the effect of the reflection on the
$\rho$-statistic. Since columns on the left of the central column turn into
columns on the right of the central column by reflection and vice versa, we
have that

$n+1=\rho(T)+\rho(T^{\prime}),$

for any AST $T$, where $T^{\prime}$ denotes the reflection of $T$ along its
central column, since the central column is counted twice and all other
$1$-columns are counted exactly once. ∎

Note that if in the above lemma one has $l+r=2n-3$, then $l=2n-3-r$ and also
$(2n-3-r)+(2n-3-l)-2n+2=-1$. Such $(n,l,r)$ \- ASPs are clearly symmetric with
respect to reflection along the central column and are special, since the
classes of $(n,l,r)$ \- ASPs $P$ and order $n$ with $\rho(P)=p$ and those
$(n,l,r)$ \- ASPs $T$ and order $n$ with $\rho(T)=n+1-p$ are equinumerous. See
for example the three $(3,1,2)$ \- ASPs and their $\rho$-statistics below.

$\displaystyle\begin{matrix}0&0&1\\\ 1&0&0&\\\ &1&\\\
&\rho=3&\end{matrix}\quad\textrm{,}\quad\begin{matrix}0&1&0\\\ 1&-1&1&\\\
&1&\\\ &\rho=2&\end{matrix}\quad\textrm{,}\quad\begin{matrix}1&0&0\\\
0&0&1&\\\ &1&\\\ &\rho=1&\end{matrix}$

The second lemma explains, why we can assume the other restriction on $l$ and
$r$ in Theorem 2.5.

######  Lemma 2.7.

Let $n\in\mathbb{N}$ and $0\leq l\leq n-2<r\leq 2n-3$, such that $l+r<2n-3$.
If $r-l\leq n-3$ there do not exist any $(n,l,r)$ \- ASPs.

###### Proof.

This follows from the fact, that if $r-(l-1)\leq n-2$, there can not exist any
$(n,l,r)$ \- ASPs, since then there are at most $r-(l-1)+1\leq n-1$ columns
and so in particular at most $r-(l-1)+1\leq n-1$ $1$-columns, which is
impossible as any such object is an AST of order $n$ and hence has to have
exactly $n$ $1$-columns. ∎

We also obtain a formula for the generating function of these newly defined
objects in terms of a Pfaffian.

######  Theorem 2.8.

Let $n\in\mathbb{N}$, $1\leq p\leq n$ and $0\leq l\leq n-2<r\leq 2n-3$, such
that $l+r<2n-2$ and $r-l>n-3$. The generating function for the set of
$(0,n,r+2-n,r-l)$ \- Magog pentagons $P$ with respect to $\tau$ is given by

(2.3) $t\times\underset{1\leq k_{2}<k_{1}\leq
n-1}{\mathrm{Pf}}\Bigg{(}\sum_{1\leq e_{1}<e_{2}\leq r+1}\det_{1\leq i,j\leq
2}\Big{(}\scalebox{0.9}{$t\binom{k_{j}-1}{e_{i}-k_{j}}-t\binom{k_{j}-1}{r-e_{i}-l+2n-1-k_{j}}+\binom{k_{j}-1}{e_{i}-1-k_{j}}-\binom{k_{j}-1}{r-e_{i}-l+2n-k_{j}}$}\Big{)}\Bigg{)},$

if $n$ is odd. If $n$ is even, we have to add an $n$-th column to the pfaffian
with entries $a_{j,n}=\sum_{1\leq e_{1}\leq
r+1}t\binom{j-1}{e_{1}-j}-t\binom{j-1}{r-e_{1}-l+2n-1-j}+\binom{j-1}{e_{1}-1-j}-\binom{j-1}{r-e_{1}-l+2n-j}$
for $j\in[n]$.

To conclude the proof of our main result Theorem 2.5 in the fourth section, we
need to introduce another class of objects closely related to Magog trapezoids
and Magog pentagons, so called Gelfand-Tsetlin-patterns.

######  Definition 2.9.

Let $n\in\mathbb{N}$. A _Gelfand-Tsetlin pattern_ of order $n$ is an array of
positive integers of the following form

$\begin{matrix}&&&&a_{1,1}&&&&\\\ &&&a_{2,2}&&a_{2,1}&&&\\\
&&...&&...&&...&&\\\ &a_{n-1,n-1}&&...&&...&&a_{n-1,1}&\\\
a_{n,n}&&a_{n,n-1}&&...&&a_{n,2}&&a_{n,1}\end{matrix}$

such that along all north-east and south-east diagonals we have a weak
increase. We label the $n$ south-east diagonals and the $2n-1$ columns of the
Gelfand-Tsetlin-pattern of order $n$ from right to left.

Throughout the paper we will always assume that $a_{k,1}\leq k$ for all
$k\in[n]$ for all Gelfand-Tsetlin-patterns of order $n$.

##  3\. An intermediate result

As mentioned in the introduction, the proof of Theorem 2.5 makes use of a
constant-term approach developed by Fischer in [Fis06, Fis07, Fis10, Fis11,
Fis16] and used by her in 2019 to give another proof of the equinumeracy of
ASTs of order $n$ and TSSCCPs in an $2n\times 2n\times 2n$ box in [Fis19]. In
the same paper she was able to prove a conjecture formulated in [ABF20],
relating the $\rho$ statistic on the AST side with the position of the unique
$1$ in the top row of an ASM. We state [Fis19, Theorem 2], one of the main
results of Fischer’s paper, formulated in a way which we will make use of.

######  Theorem 3.1 ([Fis19], Theorem 2).

Let $n\in\mathbb{N}$ and $1\leq p\leq n$. The number of ASTs $T$ of order $n$
with $\rho(T)=p$ and non central $1$-columns in positions $0\leq
j_{1}<j_{2}<...j_{n-1}\leq 2n-3$ is given by the constant term with respect to
$X_{1},...,X_{n-1},t$ of

(3.1) $t^{-p+1}\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-j_{i}}\prod_{1\leq i<j\leq
n-1}(1+X_{i}+X_{i}X_{j})(X_{j}-X_{i}).$

As an immediate consequence of the above Theorem 3.1, we obtain a constant
term expression for the number of $(n,l,r)$ \- ASPs $P$ with $\rho(P)=p$.

######  Corollary 3.2.

Let $n\in\mathbb{N}$, $1\leq p\leq n$ and $0\leq l\leq n-2<r\leq 2n-3$. The
number of $(n,l,r)$ \- ASPs $P$ with $\rho(P)=p$ is given by the constant term
with respect to $X_{1},...,X_{n},t$ of

(3.2) $t^{1-p}\sum_{l\leq j_{1}<j_{2}<...<j_{n-1}\leq
r}\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-j_{i}}\prod_{1\leq i<j\leq
n-1}(1+X_{i}+X_{i}X_{j})(X_{j}-X_{i}).$

Our first step in the proof of Theorem 2.5 is the following intermediate
result giving a closed form for this constant term.

######  Theorem 3.3.

Let $n\in\mathbb{N}$, $1\leq p\leq n$ and $0\leq l\leq n-2<r\leq 2n-3$. The
number of $(n,l,r)$ \- ASPs $P$ with $\rho(P)=p$ is the constant term with
respect to $t$ in

(3.3) $t^{1-p}\sum_{1\leq e_{1}<e_{2}<...<e_{n-1}\leq r+1}\det_{1\leq i,j\leq
n-1}\bigg{(}t\binom{j-1}{e_{i}-j}-t\binom{j-1}{r-e_{i}-l+2n-1-j}\\\
+\binom{j-1}{e_{i}-1-j}-\binom{j-1}{r-e_{i}-l+2n-j}\bigg{)}.$

We define the _symmetrizer_ $\mathbf{Sym}_{X_{1},...,X_{n}}$ and
_antisymmetrizer_ $\mathbf{ASym}_{X_{1},...,X_{n}}$ of a function
$f(X_{1},...,X_{n})$ with respect to $X_{1},...,X_{n}$.

$\displaystyle\mathbf{Sym}_{X_{1},...,X_{n}}f(X_{1},...,X_{n})\overset{\operatorname{def}}{=}\sum_{\sigma\in\mathcal{S}_{n}}f(X_{\sigma(1)},...,X_{\sigma(n)}),$
$\displaystyle\mathbf{ASym}_{X_{1},...,X_{n}}f(X_{1},...,X_{n})\overset{\operatorname{def}}{=}\sum_{\sigma\in\mathcal{S}_{n}}\mathrm{sgn}(\sigma)f(X_{\sigma(1)},...,X_{\sigma(n)}).$

We will make use of the following fact, telling us that for any function
$s(X_{1},...,X_{n})$ symmetric in $X_{1},...,X_{n}$, we have that

$\mathbf{Sym}_{X_{1},...,X_{n}}s(X_{1},...,X_{n})=n!s(X_{1},...,X_{n}),$

therefore since any constant function is symmetric, we have in particular that
the constant term of a function $f(X_{1},...,X_{n})$ with respect to
$X_{1},...,X_{n}$ is equal to the constant term of
$\frac{1}{n!}\mathbf{Sym}_{X_{1},...,X_{n}}f(X_{1},...,X_{n})$ with respect to
$X_{1},...,X_{n}$. We will refer to this as the “symmetrizer trick”.

Another important property which we will make use of frequently throughout the
following calculations is that for a function $a(X_{1},...,X_{n})$
antisymmetric in $X_{1},...,X_{n}$ and a function $f(X_{1},...,X_{n})$, we
have that

(3.4)
$\mathbf{Sym}_{X_{1},...,X_{n}}\Big{(}f(X_{1},...,X_{n})a(X_{1},...,X_{n})\Big{)}\\\
=a(X_{1},...,X_{n})\mathbf{ASym}_{X_{1},...,X_{n}}\big{(}f(X_{1},...,X_{n})\big{)}.$

Furthermore we will also use that for any function $s(X_{1},...,X_{n})$
symmetric in $X_{1},...,X_{n}$ and a function $f(X_{1},...,X_{n})$, we have
that

(3.5)
$\mathbf{Sym}_{X_{1},...,X_{n}}\Big{(}f(X_{1},...,X_{n})s(X_{1},...,X_{n})\Big{)}\\\
=s(X_{1},...,X_{n})\mathbf{Sym}_{X_{1},...,X_{n}}\big{(}f(X_{1},...,X_{n})\big{)}.$

One of the main ingredients of the proof is a special case of Corollary 1.2 by
Fischer from [Fis22] obtained by setting $w=0$ provided in the following Lemma
$3.4$.

######  Lemma 3.4 ([Fis22], Cor. 1.2).

For $n\in\mathbb{N}$ we have that

(3.6) $\mathbf{ASym}_{X_{1},...,X_{n}}\bigg{[}\prod_{1\leq i<j\leq
n}(1+X_{j}+X_{i}X_{j})\sum_{0\leq k_{1}<k_{2}<...<k_{n}\leq
r}\prod_{i=1}^{n}X_{i}^{k_{i}}\bigg{]}\\\ =\frac{\det_{1\leq i,j\leq
n}\bigg{(}X_{i}^{j-1}(1+X_{i})^{j-1}-X_{i}^{r+2n-j}(1+X_{i}^{-1})^{j-1}\bigg{)}}{\prod_{i=1}^{n}(1-X_{i})\prod_{1\leq
i<j\leq n}(1-X_{j}X_{i})}.$

Having collected the necessary ingredients, we can start with the proof, so
recall what we actually want to prove in Theorem 3.3 and let $n\in\mathbb{N}$,
$1\leq p\leq n$ and $0\leq l\leq n-2<r\leq 2n-3$. By Corollary 3.2, we know
that the number of all $(n,l,r)$ \- ASPs $T$ with $\rho(T)=p$ is given by the
constant term with respect to $X_{1},...,X_{n-1},t$ of

(3.7) $t^{1-p}\sum_{l\leq j_{1}<j_{2}<...<j_{n-1}\leq
r}\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-j_{i}}\prod_{1\leq i<j\leq
n-1}(1+X_{i}+X_{i}X_{j})(X_{j}-X_{i})\\\
=t^{1-p}\prod_{i=1}^{n-1}X_{i}^{-l}\sum_{0\leq j_{1}<j_{2}<...<j_{n-1}\leq
r-l}\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-j_{i}}\prod_{1\leq i<j\leq
n-1}(1+X_{i}+X_{i}X_{j})(X_{j}-X_{i}).$

Since we are only looking for the constant term with respect to
$X_{1},...,X_{n-1}$ we may substitute $X_{i}=X_{n-i}$ to transform the
expression as below.

$t^{1-p}\prod_{i=1}^{n-1}X_{n-i}^{-l}\sum_{0\leq j_{1}<j_{2}<...<j_{n-1}\leq
r-l}\prod_{i=1}^{n-1}(t+X_{n-i})X_{n-i}^{-j_{i}}\\\ \times\prod_{1\leq i<j\leq
n-1}(1+X_{n-i}+X_{n-i}X_{n-j})(X_{n-j}-X_{n-i})\\\
=t^{1-p}\prod_{i=1}^{n-1}X_{i}^{-l}\sum_{0\leq j_{1}<j_{2}<...<j_{n-1}\leq
r-l}\prod_{i=1}^{n-1}(t+X_{i})X_{n-i}^{-j_{i}}\prod_{1\leq i<j\leq
n-1}(1+X_{j}+X_{i}X_{j})(X_{i}-X_{j}).$

Now we make use of the symmetrizer trick and consider the constant term of the
expression below instead.

$\frac{t^{1-p}}{(n-1)!}\mathbf{Sym}_{X_{1},...,X_{n-1}}\bigg{[}\sum_{0\leq
j_{1}<j_{2}<...<j_{n-1}\leq
r-l}\prod_{i=1}^{n-1}(t+X_{i})X_{n-i}^{-j_{i}}\prod_{i=1}^{n-1}X_{i}^{-l}\\\
\times\prod_{1\leq i<j\leq n-1}(1+X_{j}+X_{i}X_{j})(X_{i}-X_{j})\bigg{]}$

Observing that $\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-l}$ is symmetric and
$\prod_{1\leq i<j\leq n-1}(X_{i}-X_{j})$ is antisymmetric we can rewrite this
as follows.

$\frac{t^{1-p}}{(n-1)!}\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-l}\\\
\times\mathbf{Sym}_{X_{1},...,X_{n-1}}\bigg{[}\sum_{0\leq
j_{1}<j_{2}<...<j_{n-1}\leq r-l}\prod_{i=1}^{n-1}X_{n-i}^{-j_{i}}\prod_{1\leq
i<j\leq n-1}(1+X_{j}+X_{i}X_{j})(X_{i}-X_{j})\bigg{]}\\\
=\frac{t^{1-p}}{(n-1)!}\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-l}\prod_{1\leq
i<j\leq n-1}(X_{i}-X_{j})\\\
\times\mathbf{ASym}_{X_{1},...,X_{n-1}}\bigg{[}\prod_{1\leq i<j\leq
n-1}(1+X_{j}+X_{i}X_{j})\sum_{0\leq j_{1}<j_{2}<...<j_{n-1}\leq
r-l}\prod_{i=1}^{n-1}X_{n-i}^{-j_{i}}\bigg{]}$

Noting that

$\sum_{0\leq j_{1}<j_{2}<...<j_{n-1}\leq
r-l}\prod_{i=1}^{n-1}X_{n-i}^{-j_{i}}=\prod_{i=1}^{n-1}X_{n-i}^{-(r-l)}\sum_{0\leq
j_{1}<j_{2}<...<j_{n-1}\leq r-l}\prod_{i=1}^{n-1}X_{n-i}^{r-l-j_{i}}\\\
=\prod_{i=1}^{n-1}X_{i}^{l-r}\sum_{0\leq k_{1}<k_{2}<...<k_{n-1}\leq
r-l}\prod_{i=1}^{n-1}X_{i}^{k_{i}}.$

and since $\prod_{i=1}^{n-1}X_{i}^{l-r}$ is symmetric, we see that the
expression is equal to

$\frac{t^{1-p}}{(n-1)!}\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-r}\prod_{1\leq
i<j\leq n-1}(X_{i}-X_{j})\\\
\times\mathbf{ASym}_{X_{1},...,X_{n-1}}\bigg{[}\prod_{1\leq i<j\leq
n-1}(1+X_{j}+X_{i}X_{j})\sum_{0\leq k_{1}<k_{2}<...<k_{n-1}\leq
r-l}\prod_{i=1}^{n-1}X_{i}^{k_{i}}\bigg{]}.$

Using Lemma 3.4 for $n-1$, we see that this is equal to

$\frac{t^{1-p}}{(n-1)!}\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-r}\prod_{1\leq
i<j\leq n-1}(X_{i}-X_{j})\\\ \times\frac{\det_{1\leq i,j\leq
n-1}\bigg{(}X_{i}^{j-1}(1+X_{i})^{j-1}-X_{i}^{r-l+2n-2-j}(1+X_{i}^{-1})^{j-1}\bigg{)}}{\prod_{i=1}^{n-1}(1-X_{i})\prod_{1\leq
i<j\leq n-1}(1-X_{j}X_{i})}.$

Now we make use of an identity equivalent to the so called “Littlewood-
identity”

$\mathbf{ASym}_{X_{1},...,X_{n-1}}\bigg{[}\prod_{i=1}^{n-1}X_{i}^{i-1}\Big{(}1-\prod_{j=i}^{n-1}X_{j}\Big{)}^{-1}\bigg{]}=\prod_{i=1}^{n-1}(1-X_{i})^{-1}\prod_{1\leq
i<j\leq n-1}\frac{X_{j}-X_{i}}{(1-X_{j}X_{i})}\\\
=(-1)^{\binom{n-1}{2}}\prod_{i=1}^{n-1}(1-X_{i})^{-1}\prod_{1\leq i<j\leq
n-1}\frac{X_{i}-X_{j}}{(1-X_{j}X_{i})},$

which can be found in [Zei96] as Subsublemma 1.1.3 and yields for our
expression from above

$\frac{t^{1-p}}{(n-1)!}\det_{1\leq i,j\leq
n-1}\bigg{(}X_{i}^{j-1}(1+X_{i})^{j-1}-X_{i}^{r-l+2n-2-j}(1+X_{i}^{-1})^{j-1}\bigg{)}\\\
\times\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-r}(1-X_{i})^{-1}\prod_{1\leq i<j\leq
n-1}\frac{(X_{i}-X_{j})}{(1-X_{j}X_{i})}\\\
=\frac{t^{1-p}(-1)^{\binom{n-1}{2}}}{(n-1)!}\det_{1\leq i,j\leq
n-1}\bigg{(}X_{i}^{j-1}(1+X_{i})^{j-1}-X_{i}^{r-l+2n-2-j}(1+X_{i}^{-1})^{j-1}\bigg{)}\\\
\times\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-r}\mathbf{ASym}_{X_{1},...,X_{n-1}}\bigg{[}\prod_{i=1}^{n-1}X_{i}^{i-1}\Big{(}1-\prod_{j=i}^{n-1}X_{j}\Big{)}^{-1}\bigg{]}.$

Since any determinant is antisymmetric, we can push the determinant into the
antisymmetrizer and this transforms it into a symmetrizer.

$\frac{t^{1-p}(-1)^{\binom{n-1}{2}}}{(n-1)!}\mathbf{Sym}_{X_{1},...,X_{n-1}}\bigg{[}\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-r}X_{i}^{i-1}\Big{(}1-\prod_{j=i}^{n-1}X_{j}\Big{)}^{-1}\\\
\times\det_{1\leq i,j\leq
n-1}\bigg{(}X_{i}^{j-1}(1+X_{i})^{j-1}-X_{i}^{r-l+2n-2-j}(1+X_{i}^{-1})^{j-1}\bigg{)}\bigg{]}$

Again making use of the symmetrizer trick, the constant term of this
expression is the same as the constant term of the expression below.

$t^{1-p}(-1)^{\binom{n-1}{2}}\det_{1\leq i,j\leq
n-1}\bigg{(}X_{i}^{j-1}(1+X_{i})^{j-1}-X_{i}^{r-l+2n-2-j}(1+X_{i}^{-1})^{j-1}\bigg{)}\\\
\times\prod_{i=1}^{n-1}(t+X_{i})X_{i}^{-r}X_{i}^{i-1}\Big{(}1-\prod_{j=i}^{n-1}X_{j}\Big{)}^{-1}$

Now observe that

$\prod_{i=1}^{n-1}X_{i}^{i-1-r}\Big{(}1-\prod_{j=i}^{n-1}X_{j}\Big{)}^{-1}=\prod_{i=1}^{n-1}X_{i}^{i-1-r}\Big{(}\sum_{k_{i}\geq
0}\prod_{j=i}^{n-1}X_{j}^{k_{i}}\Big{)}=\sum_{k_{1},...,k_{n-1}\geq
0}\prod_{i=1}^{n-1}X_{i}^{i-1-r}\prod_{j=i}^{n-1}X_{j}^{k_{i}}\\\
=\sum_{k_{1},...,k_{n-1}\geq
0}\prod_{i=1}^{n-1}X_{i}^{k_{1}+...+k_{i}+i-1-r}=\sum_{0\leq
b_{1}<b_{2}<...<b_{n-1}}\prod_{i=1}^{n-1}X_{i}^{b_{i}-r},$

hence using the multilinearity of the determinant, the above is equal to

$t^{1-p}(-1)^{\binom{n-1}{2}}\sum_{0\leq b_{1}<b_{2}<...<b_{n-1}}\det_{1\leq
i,j\leq n-1}\bigg{(}X_{i}^{b_{i}-r}(t+X_{i})\\\
\times\big{(}X_{i}^{j-1}(1+X_{i})^{j-1}-X_{i}^{r-l+2n-2-j}(1+X_{i}^{-1})^{j-1}\big{)}\bigg{)}.$

We only need to calculate the constant term with respect to
$X_{1},...,X_{n-1}$ of this sum of determinants, i.e. the constant term of
every determinant. For this note that the determinant is a sum of products of
the entries, again it suffices to calculate the constant term of each of the
products. But since in each of the products exactly one entry from each row
appears, the only way we can obtain a constant is by multiplying constants.
This is because the variable $X_{i}$ appears only in row $i$, so if the factor
from row $i$ in the product is not constant, then it contains a power of
$X_{i}$ which cannot be canceled with the other factors in the product. hence
it suffices to calculate the constant term of

$X_{i}^{b_{i}-r}(t+X_{i})\big{(}X_{i}^{j-1}(1+X_{i})^{j-1}-X_{i}^{r-l+2n-j}(1+X_{i}^{-1})^{j-1}\big{)}$

for arbitrary $i,j,b_{i}$. Using the binomial theorem, a calculation yields

(3.8) $t^{1-p}(-1)^{\binom{n-1}{2}}\sum_{0\leq
b_{1}<b_{2}<...<b_{n-1}}\det_{1\leq i,j\leq
n-1}\bigg{(}t\binom{j-1}{r+1-j-b_{i}}-t\binom{j-1}{b_{i}-l+2n-2-j}\\\
+\binom{j-1}{r-b_{i}-j}-\binom{j-1}{b_{i}-l-1+2n-j}\bigg{)}.$

Note that the sum is actually bounded, since for $b_{i}>r$, the $i$-th row is
all $0$, hence we can substitute $s_{i}=r+1-b_{n-i}$ and reorder the columns
via $\begin{pmatrix}1&2&...&n-2&n-1\\\ n-1&n-2&...&2&1\end{pmatrix}$,
cancelling the sign, to obtain (3.3).

##  4\. Proof of Theorem 2.5

Now the first major part of the proof of Theorem 2.5 is the following
proposition, giving a combinatorial interpretation in terms of non-
intersecting lattice paths for our constant term expression obtained in
Theorem 3.3. For this let us define the weighted set $\mathcal{P}_{n}^{l,r}$
of all non-intersecting $(n-1)$-tuples of lattice paths consisting of north-
and east-steps in the integer lattice with

  * •

starting points $S_{1}=(1,-2),S_{2}=(2,-4),...,S_{n-1}=(n-1,-2(n-1))$,

  * •

end-points in $E_{1}=(1,-1),E_{2}=(2,-2),...,E_{r+1}=(r+1,-r-1)$,

  * •

the path starting at $S_{n-1}$ staying weakly above the line $y=x+l-r-2n+1$,

and where a path in a tuple is weighted by $t$ if and only if it ends with a
north step.

######  Proposition 4.1.

Let $n\in\mathbb{N}$, $1\leq p\leq n$ and $0\leq l\leq n-2<r\leq 2n-3$, such
that $l+r<2n-2$ and $r-l>n-3$. Then

$\sum_{1\leq e_{1}<e_{2}<...<e_{n-1}\leq r+1}\det_{1\leq i,j\leq
n-1}\bigg{(}t\binom{j-1}{e_{i}-j}-t\binom{j-1}{r-e_{i}-l+2n-1-j}\\\
+\binom{j-1}{e_{i}-1-j}-\binom{j-1}{r-e_{i}-l+2n-j}\bigg{)}$

is the generating function of the weighted set $\mathcal{P}_{n}^{l,r}$.

###### Proof.

The idea is to make use of the Lindström-Gessel-Viennot Lemma, see [GV85] and
[Lin73], and the reflection principle for lattice paths [And87], see for
example [Kra15] for a nice overview. First of all observe the following:

  1. (1)

The points $E_{m}$ lie strictly above the line $L:y=x+l-r-2n$ for all $1\leq
m\leq r+1$, since $l+r-2n+2<0$.

  2. (2)

The points
$E_{m}^{E}\overset{\operatorname{def}}{=}(m-1,-m),E_{m}^{N}\overset{\operatorname{def}}{=}(m,-m-1)$
lie weakly above the line $L$ for all $1\leq m\leq r+1$, since $l+r-2n+2<0$.

  3. (3)

The point $R(E_{m}^{N})\overset{\operatorname{def}}{=}(r-m-l+2n-1,l+m-r-2n)$
is the reflection of the point $(m,-m-1)$ along the line $L$ for all $1\leq
m\leq r+1$,

  4. (4)

The point $R(E_{m}^{E})\overset{\operatorname{def}}{=}(r-m-l+2n,l+m-r-2n-1)$
is the reflection of the point $(m-1,-m)$ along the line $L$ for all $1\leq
m\leq r+1$,

  5. (5)

The intersection point
$P\overset{\operatorname{def}}{=}(\frac{2n+r-l}{3},\frac{2(l-2n-r)}{3})$ of
the line $y=-2x$ and $L$, lies below the line $y=-2(n-1)$, thus in particular
below all $S_{j}$ for $j\in[n-1]$, since $\frac{2n+r-l}{3}>n-1$ which is
equivalent to our assumption $r-l>n-3$.

See Figure 1 for the setup described above with parameters $n=10,r=12,l=3$.

$S_{1}$$S_{2}$$S_{3}$$S_{4}$$S_{5}$$S_{6}$$S_{7}$$S_{8}$$S_{9}$$R(E_{r+1})$$1$$t$$1$$t$$R(E_{r+1}^{N})$$R(E_{r+1}^{E})$$y=-2(n-1)$$y=-2x$$y=-x$$E_{1}$$E_{r+1}$$E_{r+1}^{N}$$E_{r+1}^{E}$$R(E_{r+2-l})$$L:y=x+l-r-2n$$P$
Figure 1. Setup for the parameters $n=10,r=12,l=3$.

For now let us fix some $j\in[n-1]$ and $1\leq e_{1}<e_{2}<...<e_{n-1}\leq
r+1$. We claim that upon using the reflection principle, we can interpret

$t\binom{j-1}{e_{i}-j}-t\binom{j-1}{r-e_{i}-l+2n-1-j}+\binom{j-1}{e_{i}-1-j}-\binom{j-1}{r-e_{i}-l+2n-j},$

as the generating function of the set of lattice paths with starting point
$S_{j}$ and end-point $E_{e_{i}}$ staying above the line $L$ shifted up by
$1$, i.e. $y=x+l-r-2n+1$, where a path is weighted by $t$ if and only if it
ends with a north-step. To see this, recall that by (3) and (4) the points
$E_{e_{i}}^{N}$ and $R(E_{e_{i}}^{N})$ as well as $E_{e_{i}}^{E}$ and
$R(E_{e_{i}}^{E})$ are the reflection of one another along the line $L$. By
(2) the points $E_{e_{i}}^{E},E_{e_{i}}^{N}$ lie weakly above the line $L$,
hence by (3) and (4) the points $R(E_{e_{i}}^{E}),R(E_{e_{i}}^{N})$ lie weakly
below $L$. Recall that by (5) also $S_{j}$ lies above the line $L$, thus upon
using the reflection principle twice, we see that the difference
$t\binom{j-1}{e_{i}-j}-t\binom{j-1}{r-e_{i}-l+2n-1-j}$ weighted by $t$, gives
the number of path starting at $S_{j}$ and ending at $E_{e_{i}}^{N}$ and
staying weakly above the line $y=x+l-r-2n+1$, whereas the unweighted
difference $\binom{j-1}{e_{i}-1-j}-\binom{j-1}{r-e_{i}-l+2n-j}$ yields the
number of paths starting at $S_{j}$, ending at $E_{e_{i}}^{E}$ and staying
weakly above the line $y=x+l-r-2n+1$. This shows our claim. See again Figure 1
above for $e_{i}=r+1$ and the distribution of the weights.

Now since by simple geometric reasons any path starting at $S_{i}$ and ending
at $E_{e_{k}}$ intersects any path starting at $S_{j}$ and ending at
$E_{e_{l}}$ for $i<j$ and $l<k$ or $j<i$ and $k<l$, we can conclude from the
Lindström-Gessel-Viennot Lemma, that

$\det_{1\leq i,j\leq
n-1}\bigg{(}t\binom{j-1}{e_{i}-j}-t\binom{j-1}{r-e_{i}-l+2n-1-j}+\binom{j-1}{e_{i}-1-j}-\binom{j-1}{r-e_{i}-l+2n-j}\bigg{)}$

is the generating function of all $(n-1)$-tuples of non-intersecting lattice
paths from $S_{j}$ to $E_{e_{j}}$ staying weakly above the line
$y=x+l-r-2n+1$, for $j\in[n-1]$, where a path is weighted by $t$ if and only
if it ends with a north step. Note that since the paths are non-intersecting
this condition of all paths staying weakly above the line $y=x+l-r-2n+1$ is
equivalent to the lowest path, i.e. the path starting at $S_{n-1}$ and ending
at $E_{e_{n-1}}$, staying weakly above the line $y=x+l-r-2n+1$. Now simply
summing over all possible tuples $1\leq e_{1}<e_{2}<...<e_{n-1}\leq r+1$
yields the proposition. ∎

For completeness let us restate the unchecked part of the theorem before we
finish the proof.

_Let $n\in\mathbb{N}$, $1\leq p\leq n$ and $0\leq l\leq n-2<r\leq 2n-3$, such
that $l+r<2n-2$ and $r-l>n-3$. The set of $(n,l,r)$ \- ASPs $P$ with
$\rho(P)=p$ is equinumerous with the set of $(0,n,r+2-n,r-l)$ \- Magog
pentagons $M$ with $\tau(M)=p$._

After showing the following claim, we will be done by Proposition 4.1.

Claim: _Let $n\in\mathbb{N}$, $1\leq p\leq n$ and $0\leq l\leq n-2<r\leq
2n-3$, such that $l+r<2n-2$ and $r-l>n-3$. There is a weight preserving
bijection between the set $\mathcal{P}_{n}^{l,r}$ and the set of
$(0,n,r+2-n,r-l)$ \- Magog pentagons $M$ with $\tau(M)=p$._

###### Proof.

The bijection we use is actually well known and translates such tuples of
paths into Gelfand-Tsetlin-patterns, see for example [Fis19]. Nevertheless we
will go through the details here because we have some additional properties
for our paths and the $\rho$-statistic which we have to keep track of.

So let us consider the weighted set $\mathcal{P}_{n}^{l,r}$ as defined in
Proposition 4.1. Taking $T\in\mathcal{P}_{n}^{l,r}$, we start by shifting the
path $P_{j}$ starting at $S_{j}$ by $(x,y)\mapsto(x-j,y+j)$ such that it now
starts at $\tilde{S}_{j}=(0,-j)$, for all $j\in[n-1]$. Now we obtain an
$(n-1)$-tuple $\tilde{T}$ of kissing lattice paths. By kissing we mean that
the path $\tilde{P}_{j}$ starting at $\tilde{S}_{j}$ stays weakly below the
path starting at $\tilde{S}_{j-1}$. We claim that this is a bijection between
the set $\mathcal{P}_{n}^{l,r}$ and the set $\tilde{\mathcal{P}}_{n}^{l,r}$,
where $\tilde{\mathcal{P}}_{n}^{l,r}$ is the set of all $(n-1)$-tuples of
kissing lattice paths $\tilde{P}_{j}$ consisting of north- and east-steps in
the integer square lattice with

  * •

starting points $\tilde{S}_{1}=(0,-1),...,\tilde{S}_{n-1}=(0,-n+1)$,

  * •

end-points in $\tilde{E}_{0}=(0,0),...,\tilde{E}_{r-n+2}(r-n+2,n-r-2)$,

  * •

the path $\tilde{P}_{n-1}$ starting at $\tilde{S}_{n-1}$ staying weakly above
the line $y=x+l-r-1$,

where a path is weighted by $t$ if and only if it ends with a north-step. This
is clear by definition of the map, except for the second and third property.
Note that since the paths are kissing, the end-points of the paths
$\tilde{P}_{1},...,\tilde{P}_{n-1}$ have to stay weakly above the end-point of
the path $\tilde{P}_{n-1}$. Since the lowest possible end-point for $P_{n-1}$
is given by $E_{r+1}=(r+1,-r-1)$, we know by definition of the map that the
lowest possible end-point for $\tilde{P}_{n-1}$ is given by
$\tilde{E}_{r-n+2}=(r+1-(n-1),n-1-r-1)$. Similarly the highest possible end-
point for $P_{1}$ is given by $E_{1}$ thus the highest possible end-point for
$\tilde{P}_{1}$ is given by $\tilde{E}_{0}$, hence the second property
follows. The argument for the third property is similar. Since $P_{n-1}$ has
to stay weakly above the line $y=x+l-r-2n+1$ and we shift the path by
$(x,y)\mapsto\Big{(}x-(n-1),y+(n-1)\Big{)}$, we know that $\tilde{P}_{n-1}$
has to stay weakly above the line $y=x+l-r-1$. Consider for example the tuple
$T\in\mathcal{P}_{10}^{1,12}$ of paths for $n=10,r=12,l=1$ on the left and its
corresponding tuple $\tilde{T}$ on the right.

$S_{1}$$S_{2}$$S_{3}$$S_{4}$$S_{5}$$S_{6}$$S_{7}$$S_{8}$$S_{9}$$(r+1,-r-1)$$y=x+l-r-2n$$y=x+l-r-2n+1$$y=x+l-r-2$$y=x+l-r-1$$\tilde{S}_{1}$$\tilde{S}_{2}$$\tilde{S}_{3}$$\tilde{S}_{4}$$\tilde{S}_{5}$$\tilde{S}_{6}$$\tilde{S}_{7}$$\tilde{S}_{8}$$\tilde{S}_{9}$

To translate this into Gelfand-Tsetlin-patterns we introduce a coordinate
lattice on a Gelfand-Tsetlin-pattern of order $n$ in the following way.

$a_{1,1}$$a_{2,1}$$a_{2,1}$$...$$...$$...$$...$$a_{n-1,2}$$a_{n-1,1}$$a_{n-1,n-1}$$...$$a_{n,2}$$...$$a_{n,1}$$a_{n,n}$$\hat{S}_{n-1}$$\hat{S}_{n-2}$$\hat{S}_{1}$$\hat{E}_{0}$$\hat{E}_{1}$$\hat{E}_{2}$$\hat{E}_{r+2-n}$$\hat{E}_{n-1}$

Next we take a tuple $\tilde{T}\in\tilde{\mathcal{P}}_{n}^{l,r}$ and construct
bijectively a Gelfand-Tsetlin-pattern $G(\tilde{T})$ of order $n$. See below
for an example. For this we take the path $\tilde{P}_{j}$ starting at
$\tilde{S}_{j}$ and ending at say $\tilde{E}_{a}$, and construct out of it a
path $\hat{P}_{j}$ starting at $\hat{S}_{j}$ and ending at $\hat{E}_{a}$ in
the coordinate system above simply by making a south-east step in
$\hat{P}_{j}$ whenever $\tilde{P}_{j}$ makes a north-step and a south-west
step in $\hat{P}_{j}$ whenever $\tilde{P}_{j}$ makes an east-step. Then we
fill in the number $j$, starting with $1$ all the way up to $n-1$, in all
slots to the left of the path starting at $\hat{S}_{n-j}$. The remaining empty
slots will be filled with $n$. This process is clearly reversible and thus a
bijection. See for example the tuple of paths
$\tilde{T}\in\tilde{\mathcal{P}}_{10}^{1,12}$ from above and its corresponding
Gelfand-Tsetlin-pattern below.

$\tilde{S}_{1}$$\tilde{S}_{2}$$\tilde{S}_{3}$$\tilde{S}_{4}$$\tilde{S}_{5}$$\tilde{S}_{6}$$\tilde{S}_{7}$$\tilde{S}_{8}$$\tilde{S}_{9}$$1$$1$$2$$2$$2$$1$$2$$2$$4$$1$$2$$4$$1$$5$$1$$1$$1$$2$$4$$5$$6$$1$$1$$1$$2$$4$$5$$7$$1$$1$$1$$1$$2$$4$$5$$7$$1$$1$$1$$1$$1$$2$$4$$5$$8$$1$$1$$1$$1$$1$$1$$3$$5$$7$$9$$18$$16$$14$$12$$10$$8$$6$$4$$2$$19$$17$$15$$13$$11$$9$$7$$5$$3$$1$$\hat{S}_{9}$$\hat{S}_{8}$$\hat{S}_{7}$$\hat{S}_{6}$$\hat{S}_{5}$$\hat{S}_{4}$$\hat{S}_{3}$$\hat{S}_{2}$$\hat{S}_{1}$$\hat{E}_{0}$$\hat{E}_{1}$$\hat{E}_{2}$$\hat{E}_{3}$$\hat{E}_{4}$$\hat{E}_{5}$$\hat{E}_{6}$$\hat{E}_{7}$$\hat{E}_{8}$$\hat{E}_{9}$

Now we have to translate our conditions on the tuples
$\tilde{T}\in\tilde{\mathcal{P}}_{n}^{l,r}$. Recall that $\tilde{P}_{j}$ is
the set of all $(n-1)$-tuples of kissing lattice paths $\tilde{P}_{j}$
consisting of north- and east-steps in the integer lattice with

  * •

starting points $\tilde{S}_{1}=(0,-1),...,\tilde{S}_{n-1}=(0,-n+1)$,

  * •

end-points in $\tilde{E}_{0}=(0,0),...,\tilde{E}_{r-n+2}(r-n+2,n-r-2)$,

  * •

the path $\tilde{P}_{n-1}$ starting at $\tilde{S}_{n-1}$ staying weakly above
the line $y=x+l-r-1$,

where a path is weighted by $t$ if and only if it ends with a north-step. The
second condition simply translates into the fact that the paths in
$G(\tilde{T})$ end at the points $\hat{E}_{0},...,\hat{E}_{r+1-(n-1)}$. This
means that to the left of the north-west diagonal through the point
$\hat{E}_{r+2-n}$ all entries of $G(\tilde{T})$ equal to $1$. In other words
all entries to the left and on the $(r+3-n)$-th north-west diagonal of the
Gelfand-Tsetlin-pattern are equal to $1$.

Note that the intersection point of the line $y=-x$ and $y=x+l-r-1$ is given
by $(\frac{r+1-l}{2},-\frac{r+1-l}{2})$ and because south-west to north-east
steps in $\tilde{T}$ translate to simple south steps in $G(\tilde{T})$, the
fact that $\tilde{P}_{n-1}$ stays weakly above the line $y=x+l-r-1$,
translates into the fact that the path $\hat{P}_{n-1}$ stays weakly to the
right of the $(r+1-l)$-th column of the Gelfand-Tsetlin-pattern. See for
example below the tuple of paths $\tilde{T}\in\tilde{\mathcal{P}}_{10}^{1,12}$
from above and its corresponding Gelfand-Tsetlin-pattern with the $(r+1-l)$-th
column marked.

$y=x+l-r-2$$y=x+l-r-1$$\tilde{S}_{1}$$\tilde{S}_{2}$$\tilde{S}_{3}$$\tilde{S}_{4}$$\tilde{S}_{5}$$\tilde{S}_{6}$$\tilde{S}_{7}$$\tilde{S}_{8}$$\tilde{S}_{9}$$1$$1$$2$$2$$2$$1$$2$$2$$4$$1$$2$$4$$1$$5$$1$$1$$1$$2$$4$$5$$6$$1$$1$$1$$2$$4$$5$$7$$1$$1$$1$$1$$2$$4$$5$$7$$1$$1$$1$$1$$1$$2$$4$$5$$8$$1$$1$$1$$1$$1$$1$$3$$5$$7$$9$$18$$16$$14$$12$$10$$8$$6$$4$$2$$19$$17$$15$$13$$11$$9$$7$$5$$3$$1$$\hat{S}_{9}$$\hat{S}_{8}$$\hat{S}_{7}$$\hat{S}_{6}$$\hat{S}_{5}$$\hat{S}_{4}$$\hat{S}_{3}$$\hat{S}_{2}$$\hat{S}_{1}$$\hat{E}_{0}$$\hat{E}_{1}$$\hat{E}_{2}$$\hat{E}_{3}$$\hat{E}_{4}$$\hat{E}_{5}$$\hat{E}_{6}$$\hat{E}_{7}$$\hat{E}_{8}$$\hat{E}_{9}$

Since a path is weighted by $t$ in $\tilde{T}$ if and only if it ends with a
north step, the Gelfand-Tsetlin pattern $G(\tilde{T})$ is weighted by

$t^{n-1}\prod_{i=1}^{r+2-n}t^{a_{n-1,i}-a_{n,i}}.$

In order to see this, first observe that
$\prod_{i=1}^{r+2-n}t^{a_{n,i}-a_{n-1,i}}$ counts the paths in $G(\tilde{T})$
that end with a south-west step, because in any path ending with a south-west
step one creates a difference of $1$ between the entry in the bottom column to
the right of the end-point of the path and the entry directly above it along
the north-west diagonal, when filling in the numbers between the paths as in
the construction. Since there are $n-1$ paths, the statement follows.

We see that the set $\mathcal{P}_{n}^{l,r}$ is in weight-preserving bijection
with the set $\mathcal{G}_{n}^{l,r}$ of all Gelfand-Tsetlin-patterns $G$ of
order $n$ where

  * •

all entries to the left and on the $(r+3-n)$-th north-west diagonal are equal
to $1$,

  * •

all entries to the left and on the $(r+1-l)$-th column are equal to $1$,

and $G$ is weighted by $t^{n-1}\prod_{i=1}^{r+2-n}t^{a_{n-1,i}-a_{n,i}}$. Note
that because $n-1\leq r\leq 2n-3$, we have $2\leq r+3-n\leq n$ and since
$0\leq l\leq n-2$ we have $2\leq r+1-l\leq 2n-2$, hence both $r+3-n$ and
$r+1-l$ are the index of an existing diagonal and column. Now simply using the
rotation by $45^{\circ}$ bijection described in Definition 2.9 and cutting off
all the entries forced to be equal to $1$, we obtain a weight preserving
bijection between $\mathcal{P}_{n}$ and the set of all $(0,n,r+2-n,r-l)$ \-
Magog pentagons where a pentagon is weighted by
$t^{n-1}\prod_{i=1}^{r+2-n}t^{a_{n-1,i}-a_{n,i}}$. Since in Theorem 3.3 the
number of $(n,l,r)$ \- ASPs $P$ with $\rho(P)=p$ is given by the coefficient
of $t^{p-1}$, we multiply the statistic on the Magog pentagons with an
additional $t$, giving us the $\tau$-statistic and the statement of the
theorem. For the example $T\in\mathcal{P}_{10}^{1,12}$ above, we would obtain
the $(0,10,4,11)$ \- Magog pentagon $M$ below with weight
$\tau(M)-1=4=\\#\textrm{paths ending with a north step in the example }T$.

$\begin{matrix}1&2&2&4&5&6&7&7&8&9\\\ 1&2&2&4&5&5&5&5&7\\\ &2&2&4&4&4&4&5\\\
&&2&2&2&2&3\\\ \end{matrix}$

∎

##  5\. Proof of Theorem 2.8

Again one of the main ingredients of the proof of theorem 2.8 will be Theorem
3.3 that was established in Section 3. The other ingredient is a result of
Stembridge, which we will state in a form useful for our purposes. For this we
define the _Pfaffian_ of a $2n\times 2n$-skew symmetric matrix.

######  Definition 5.1.

Let $A=(a_{i,j})_{1\leq i<j\leq 2n}$ be a skew symmetric matrix. We define its
_Pfaffian_ by

(5.1) $\underset{1\leq i<j\leq
2n}{\mathrm{Pf}}(a_{i,j})\overset{\operatorname{def}}{=}\frac{1}{2^{n}n!}\sum_{\sigma\in
S_{2n}}\mathrm{sgn}(\sigma)\prod_{i=1}^{n}a_{\sigma(2i-1),\sigma(2i)},$

where $S_{2n}$ is the _symmetric group_ of order $2n!$ and $\mathrm{sgn}$ is
the _sign_ of a permutation.

######  Theorem 5.2 ([Ste90], Theorem 3.1).

Let $G$ be an acyclic, directed graph, $u_{1},...,u_{r}$ be an $r$-tuple of
vertices of $G$, $I$ a totally ordered subset of the vertices of $G$ such that
for all $i<j\in[r]$ and $v<v^{\prime}\in I$ any directed path in $G$ from
$u_{j}$ to $v$ intersects any directed path in $G$ from $u_{i}$ to
$v^{\prime}$. Denote by

$\mathcal{GF}_{0}[u_{1},...,u_{r};I\mid
G]=\sum_{(P_{1},...,P_{r})}\prod_{i=1}^{r}\mathrm{Wt}(P_{i})$

where we sum over all $r$-tuples of non-intersecting directed paths with
starting points $u_{1},...,u_{r}$ and end-points in $I$ inside $G$ and
$\mathrm{Wt}(P_{i})$ is the weight of the path $P_{i}$.

If $r$ is even we have that

$\mathcal{GF}_{0}[u_{1},...,u_{r};I\mid G]=\underset{1\leq i<j\leq
r}{\mathrm{Pf}}\Big{(}\mathcal{GF}_{0}[u_{i},u_{j};I\mid G]\Big{)}.$

Note that if $r$ is odd we may adjoin a phantom vertex $u_{r+1}$ to $G$ with
no incident edges. We then include $u_{r+1}$ in $I$ and order all vertices of
$I$ before it. Denote $I\cup\\{u_{r+1}\\}$ by $I^{*}$. Now
$u_{1},...,u_{r},u_{r+1}$ and the new $I^{*}$ satisfy all conditions of the
above statement and we can provide a Pfaffian of order $r+1$ for
$\mathcal{GF}_{0}[u_{1},...,u_{r};I]=\mathcal{GF}_{0}[u_{1},...,u_{r},u_{r+1};I^{*}]$.
Note that in this case for all $i\in[r]$ we have
$\mathcal{GF}_{0}[u_{i},u_{r+1};I]=\mathcal{GF}_{0}[u_{i};I]$.

Fix $n\in\mathbb{N}$ and $0\leq l\leq n-2<r\leq 2n-3$ such that $l+r-2n+2<0$
and $\frac{2n+r-l}{3}>n-1$. Now consider the graph $G_{n,l,r}$ with vertex set
consisting of all integer lattice points in the plane lying weakly above the
line $y=x+l-r-2n+1$ and oriented edges given by north- and east-steps between
those points. This graph is directed and clearly acyclic. Let
$S_{i}\overset{\operatorname{def}}{=}(-i,-2i)$ as in Proposition 4.1 and
consider $I\overset{\operatorname{def}}{=}\\{(1,-1),...,(r+1,-r-1)\\}$. It is
clear by elementary geometric arguments, see Figure 1, that these vertices
satisfy the conditions of Stembridge’s Theorem. We assign a weight $t$ to a
path in $G_{n,l,r}$ if and only if it ends with a north step. By Proposition
4.1, we know that

$\mathcal{GF}_{0}[S_{1},...,S_{n-1};I\mid G_{n,l,r}]=\sum_{1\leq
e_{1}<e_{2}<...<e_{n-1}\leq r+1}\det_{1\leq i,j\leq
n-1}\bigg{(}t\binom{j-1}{e_{i}-j}\\\
-t\binom{j-1}{r-e_{i}-l+2n-1-j}+\binom{j-1}{e_{i}-1-j}-\binom{j-1}{r-e_{i}-l+2n-j}\bigg{)}.$

Furthermore we can, similarly as in the proof of Proposition 4.1, deduce that
for $i,j\in[n-1]$ we have

$\mathcal{GF}_{0}[S_{i},S_{j};I\mid G_{n,l,r}]\\\ =\sum_{1\leq e_{1}<e_{2}\leq
r+1}\det_{1\leq c\leq
2}\begin{pmatrix}t\binom{j-1}{e_{c}-j}-t\binom{j-1}{r-e_{c}-l+2n-1-j}+\binom{j-1}{e_{c}-1-j}-\binom{j-1}{r-e_{c}-l+2n-j}\\\
t\binom{i-1}{e_{c}-i}-t\binom{i-1}{r-e_{c}-l+2n-1-i}+\binom{i-1}{e_{c}-1-i}-\binom{i-1}{r-e_{c}-l+2n-i}\end{pmatrix},$

where we denote by $\det_{1\leq i\leq n}(v_{i})$ the determinant of the matrix
with column vectors $v_{1},..,v_{n}$. Note that for $j\in[n-1]$ we have

$\mathcal{GF}_{0}[S_{j};I\mid G_{n,l,r}]=\sum_{1\leq e_{1}\leq
r+1}\Bigg{(}t\binom{j-1}{e_{1}-j}-t\binom{j-1}{r-e_{1}-l+2n-1-j}\\\
+\binom{j-1}{e_{1}-1-j}-\binom{j-1}{r-e_{1}-l+2n-j}\Bigg{)},$

by a similar reasoning. Therefore by Stembridge’s Theorem we can deduce that
for odd $n$ we have that

$\sum_{1\leq e_{1}<e_{2}<...<e_{n-1}\leq r+1}\det_{1\leq i,j\leq
n-1}\bigg{(}t\binom{j-1}{e_{i}-j}-t\binom{j-1}{r-e_{i}-l+2n-1-j}+\binom{j-1}{e_{i}-1-j}\\\
-\binom{j-1}{r-e_{i}-l+2n-j}\bigg{)}\\\
=\mathcal{GF}_{0}[S_{1},...,S_{n-1};I\mid G_{n,l,r}]=\underset{1\leq i<j\leq
n-1}{\mathrm{Pf}}\Big{(}\mathcal{GF}_{0}[S_{i},S_{j};I\mid
G_{n,l,r}]\big{)}\\\ =\underset{1\leq i<j\leq
n-1}{\mathrm{Pf}}\Bigg{(}\sum_{1\leq e_{1}<e_{2}\leq r+1}\det_{1\leq c\leq
2}\begin{pmatrix}t\binom{j-1}{e_{c}-j}-t\binom{j-1}{r-e_{c}-l+2n-1-j}+\binom{j-1}{e_{c}-1-j}-\binom{j-1}{r-e_{c}-l+2n-j}\\\
t\binom{i-1}{e_{c}-i}-t\binom{i-1}{r-e_{c}-l+2n-1-i}+\binom{i-1}{e_{c}-1-i}-\binom{i-1}{r-e_{c}-l+2n-i}\end{pmatrix}\Bigg{)}\\\
=\underset{1\leq k_{2}<k_{1}\leq n-1}{\mathrm{Pf}}\Bigg{(}\sum_{1\leq
e_{1}<e_{2}\leq r+1}\det_{1\leq i,j\leq
2}\Big{(}\scalebox{0.9}{$t\binom{k_{j}-1}{e_{i}-k_{j}}-t\binom{k_{j}-1}{r-e_{i}-l+2n-1-k_{j}}+\binom{k_{j}-1}{e_{i}-1-k_{j}}-\binom{k_{j}-1}{r-e_{i}-l+2n-k_{j}}$}\Big{)}\Bigg{)}.$

The above equality still holds if $n$ is even, but by Stembridge’s Theorem we
have to append an $n$-th column to the Pfaffian with entries

$a_{j,n}\overset{\operatorname{def}}{=}\mathcal{GF}_{0}[S_{j};I\mid
G_{n,l,r}]=\sum_{1\leq e_{1}\leq
r+1}\Bigg{(}t\binom{j-1}{e_{1}-j}-t\binom{j-1}{r-e_{1}-l+2n-1-j}\\\
+\binom{j-1}{e_{1}-1-j}-\binom{j-1}{r-e_{1}-l+2n-j}\Bigg{)}.$

Now Theorem 2.8 follows from Theorem 3.3 and Theorem 2.5.

##  6\. Consequences and Conjectures

As mentioned in Section 2, the definition of $(n,l,r)$ \- ASPs is inspired by
the conjectures of Behrend in [Fis19]. The main goal of the paper was to
relate the AST side to the Magog-side, which we managed to accomplish within
Theorem 2.5. This gives us a new point of view on some open conjectures
connected to ASPs and Gog pentagons as well as Magog pentagons. In this
chapter we will discuss how exactly our results interact or extend those
aforementioned conjectures and while the full conjecture of Behrend remains
open, how we got a part of it as a byproduct of our investigations.

To formulate the precise results we obtained, we will need the following three
statistics for an ASM $M$ of order $n$.

  * •

$T_{L}(M)$ the number of south-west diagonals, counted starting in the top
left corner, consisting of all zeros,

  * •

$T_{R}(M)$ the number of south-east diagonals, counted starting in the top
right corner, consisting of all zeros,

  * •

$\rho(M)$ the position of the unique $1$ in the top row.

Let us also formally introduce Gog trapezoids.

######  Definition 6.1.

An $(m,n,k)$-_Gog trapezoid_ is an array of positive integers consisting of
the first $k$ columns of an array

$\begin{matrix}a_{1,1}&a_{1,2}&...&...&a_{1,n}\\\
a_{2,1}&a_{2,2}&...&a_{2,n-1}&\\\ ...&...&...&&\\\ a_{n-1,1}&a_{n-1,2}&&&\\\
a_{n,1}&&&&\end{matrix}$

such that entries along rows are strictly increasing, entries along columns
are weakly increasing, and entries along diagonals from lower-left to upper-
right are weakly increasing, and such that the entries in the right most
column are bounded by $a_{1,k}\leq m+k,a_{2,k}\leq m+k+1,...,a_{n+1-k,k}\leq
m+n$.

It is not hard to see that we can transform any $n\times n$ \- ASM one to one
into a $(0,n,n)$ \- Gog trapezoid by first mapping the ASM to the matrix
obtained by replacing the $i$-th row of the ASM by the sum of rows
$i,i+1,..,n$ and then recording the positions of the $1$’s in the so obtained
matrix in a triangular array.

$\begin{pmatrix}0&0&1&0&0&0\\\ 1&0&-1&1&0&0\\\ 0&0&1&-1&0&1\\\ 0&1&-1&1&0&0\\\
0&0&1&-1&1&0\\\
0&0&0&1&0&0\end{pmatrix}\quad\rightarrow\quad\begin{pmatrix}1&1&1&1&1&1\\\
1&1&0&1&1&1\\\ 0&1&1&0&1&1\\\ 0&1&0&1&1&0\\\ 0&0&1&0&1&0\\\
0&0&0&1&0&0\end{pmatrix}\quad\rightarrow\quad\begin{matrix}1&2&3&4&5&6\\\
1&2&4&5&6\\\ 2&3&5&6\\\ 2&4&5\\\ 3&5\\\ 4\end{matrix}$

Note that under this bijection the statistics $T_{L}(M)$ and $T_{R}(M)$ of an
ASM $M$ translate into the number of all $1$ south-west diagonals, counted
starting in the top left corner, and the number of all $1$ south-east
diagonals, counted starting in the top right corner, of the in-between matrix
respectively. These then translate into fixed pattern triangles of the Gog
trapezoid. More precisely if $T_{L}(M)=l$ then we have the pattern

$\begin{matrix}1&2&...&l+1\\\ 1&...&l&\\\ \vdots&\vdots\\\ 1\end{matrix}$

in the top left corner of the Gog trapezoid and if $T_{R}(M)=r$ then we have
the pattern

$\begin{matrix}n-r&n+1-r&...&n\\\ n+1-r&...&n&\\\ \vdots&\vdots\\\
n\end{matrix}$

in the top right corner of the Gog trapezoid. In particular this tells us that
the number of $n\times n$ \- ASM with $T_{R}(M)=r$ is equal to the number of
$(0,n,n-1-r)$ \- Gog trapezoids. The following statement is a simple corollary
of Theorem 2.5.

######  Corollary 6.2.

Let $3<n\in\mathbb{N}$, $1\leq p\leq n$ and $n-1\leq r\leq 2n-3$. The number
of $(n,0,r)$ \- ASPs $T$ of order $n$ with $\rho(T)=p$ is equal to the number
of $(n,2n-3-r,2n-3)$ \- ASPs $T$ of order $n$ with $\rho(T)=n+1-p$ and equal
to the number of $(0,n,r+2-n)$ \- Magog trapezoids $P$ with $\tau(P)=p$.

###### Proof.

Note that a $(0,n,r+2-n,r)$ \- Magog pentagon is simply a $(0,n,r+2-n)$ \-
Magog trapezoid, since the $r$-th south-east diagonal of the pentagon lies to
the left of the $(r+2-n)$-th row. The claim now follows directly from Theorem
2.5. ∎

Combining the above with Zeilberger’s famous Lemma 1 we obtain a partial proof
of Behrend’s conjecture.

######  Corollary 6.3.

Let $n\in\mathbb{N}$ and $n-1\leq r\leq 2n-3$. The number of ASMs $M$ of order
$n$ with $T_{R}(M)=2n-3-r$ is equal to the number of $(n,0,r)$ \- ASPs and the
number of ASMs $M$ of order $n$ with $T_{L}(M)=2n-3-r$ is equal to the number
of $(n,2n-3-r,2n-3)$ \- ASPs.

###### Proof.

By Corollary 6.2 we know that the number of $(n,0,r)$ \- ASPs of order $n$ is
equal to the number of $(0,n,r+2-n)$ \- Magog trapezoids. In [Zei96]
Zeilberger proved in his Lemma 1, that the number of such $(0,n,r+2-n)$ \-
Magog trapezoids is equal to the number of $(0,n,r+2-n)$ \- Gog trapezoids. By
the above observation we know that these $(0,n,r+2-n)$ \- Gog trapezoids are
equinumerous with $n\times n$ \- ASMs $M$ where $T_{R}(M)=n-1-(r+2-n)=2n-3-r$.
The second statement follows by the horizontal reflection symmetry of both
classes of objects. ∎

See for example below the five $(3,0,2)$ \- ASPs and five $3\times 3$ ASMs
with $T_{R}=1$.

$\displaystyle\begin{matrix}1&0&0&0&0\\\ &1&0&0&\\\
&&1&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}1&0&0&0&0\\\ &0&0&1&\\\
&&1&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}0&0&0&1&0\\\ &1&0&0&\\\
&&1&&\end{matrix}\quad\textrm{,}\quad$
$\displaystyle\begin{matrix}0&1&0&0&0\\\ &0&0&1&\\\
&&1&&\end{matrix}\quad\textrm{,}\quad\begin{matrix}0&0&1&0&0\\\ &1&-1&1&\\\
&&1&&\end{matrix}\quad\textrm{,}\quad$ $\displaystyle\begin{pmatrix}0&1&0\\\
1&-1&1\\\ 0&1&0\end{pmatrix}\quad,\quad\begin{pmatrix}0&1&0\\\ 1&0&0\\\
0&0&1\end{pmatrix}\quad,\quad\begin{pmatrix}0&1&0\\\ 0&0&1\\\
1&0&0\end{pmatrix}\quad,\quad$ $\displaystyle\begin{pmatrix}1&0&0\\\ 0&1&0\\\
0&0&1\end{pmatrix}\quad,\quad\begin{pmatrix}1&0&0\\\ 0&0&1\\\
0&1&0\end{pmatrix}$

Let us introduce another object, so called Gog pentagons.

######  Definition 6.4.

An $(m,n,k,l)$ \- Gog pentagon is an $(m,n,k)$ \- Gog trapezoid with the top
left corner being equal to the fixed pattern

$\begin{matrix}1&2&...&l\\\ 1&...&l-1&\\\ \vdots&\vdots\\\ 1\end{matrix}$

Since this pattern is fixed we may cut it off, this justifies the name
pentagon. See for example below the $(0,6,4,2)$ \- Gog pentagon.

$\begin{matrix}1&2&3&4\\\ 1&3&4&5\\\ 2&3&4&5\\\ 2&4&5\\\ 5&6\\\
6\end{matrix}\quad\leftrightarrow\quad\begin{matrix}&&3&4\\\ &3&4&5\\\
2&3&4&5\\\ 2&4&5\\\ 5&6\\\ 6\end{matrix}$

With this new object we can describe the translation of all three statistics
$T_{L}(M)$ and $T_{R}(M)$ and the position of the unique $1$ in the top row of
an ASM $M$ to the Gog trapezoid side. That is, if $T_{L}(M)=l$ and
$T_{R}(M)=r$ then $M$ corresponds to an $(0,n,n-1-r,l+1)$ \- Gog pentagon.
This lets us rephrase the conjecture of Behrend in terms of Gog and Magog
pentagons.

######  Conjecture 6.5 (Behrend, [Fis19]).

Let $n\in\mathbb{N}$ and $1\leq l\leq n-2<r\leq 2n-3$ such that $l+r-2n+2<0$
and $\frac{2n+r-l}{3}>n-1$. The number of $(0,n,r+2-n,r-l)$ \- Magog pentagons
is the same as the number of $(0,n,r+2-n,l+1)$ \- Gog pentagons.

See for example below the set of nine $(0,4,2,2)$ \- Magog pentagons and
$(0,4,2,3)$ \- Gog pentagons for $n=4$, $r=4$, $l=2$.

$\displaystyle\begin{matrix}1&1\end{matrix}\quad\textrm{,}\quad\begin{matrix}1&2\end{matrix}\quad\textrm{,}\quad\begin{matrix}1&3\end{matrix}\quad\textrm{,}\quad\begin{matrix}1&4\end{matrix}\quad\textrm{,}\quad\begin{matrix}2&2\end{matrix}\quad\textrm{,}\quad\begin{matrix}2&3\end{matrix}\quad\textrm{,}\quad$
$\displaystyle\begin{matrix}2&4\end{matrix}\quad\textrm{,}\quad\begin{matrix}3&3\end{matrix}\quad\textrm{,}\quad\begin{matrix}3&4\end{matrix}$
$\displaystyle\begin{matrix}&2\\\
1\end{matrix}\quad\textrm{,}\quad\begin{matrix}&3\\\
1\end{matrix}\quad\textrm{,}\quad\begin{matrix}&4\\\
1\end{matrix}\quad\textrm{,}\quad\begin{matrix}&2\\\
2\end{matrix}\quad\textrm{,}\quad\begin{matrix}&3\\\
2\end{matrix}\quad\textrm{,}\quad\begin{matrix}&4\\\
2\end{matrix}\quad\textrm{,}\quad$ $\displaystyle\begin{matrix}&3\\\
3\end{matrix}\quad\textrm{,}\quad\begin{matrix}&4\\\
3\end{matrix}\quad\textrm{,}\quad\begin{matrix}&4\\\ 4\end{matrix}$

Note that the conjecture can not be extended to more general paramaters, i.e.
we do not have that the set of $(0,n,k,l)$ \- Gog pentagons is equinumerous to
the set of $(0,n,k,k-l-1+n)$ \- Magog pentagons for $1\leq l\leq n$ and $1\leq
k\leq n$. For $n=3$, we see that for $k=2$ and $l=3$, there exists a unique
$(0,3,2,3)$ \- Gog pentagon given by

$\begin{matrix}1&2&3\\\ 1&2\\\ 1\end{matrix}\quad,$

whereas there exist three $(0,3,2,1)$ \- Magog pentagons given by

$\begin{matrix}1&1&1\\\ 1&1\\\ 1\end{matrix}\quad,\quad\begin{matrix}1&1&2\\\
1&1\\\ 1\end{matrix}\quad,\quad\begin{matrix}1&1&3\\\ 1&1\\\
1\end{matrix}\quad.$

Also note that the other statistics mentioned by Behrend can also be included
in the above discussion, giving a full reformulation of his conjecture.

There is another conjecture by Biane and Cheballah [BC16], relating Gog
pentagons to GOGAm pentagons, objects introduced in [BC16]. These GOGAm
pentagons are obtained by applying the Schützenberger-involution to $(0,n,n)$
\- Magog trapezoids and then cutting off certain parts of the so obtained
triangle. They conjectured that there are equally many Gog pentagons of a
fixed shape as there are GOGAm pentagons of that shape. This is different in
our conjectured correspondence as the Magog pentagons have a different shape
than the Gog pentagons in general. Nevertheless combining these two, we can
state another conjecture concerning our new objects.

######  Conjecture 6.6.

Let $n\in\mathbb{N}$ and $1\leq l\leq n-2<r\leq 2n-3$ such that $l+r-2n+2<0$
and $\frac{2n+r-l}{3}>n-1$. The number of $(0,n,r+2-n,r-l)$ \- Magog pentagons
is the same as the number of $(0,n,r+2-n,l+1)$ \- GOGAm pentagons.

The following observation regarding Theorem 2.8 is also worth noting. We know
that in the unrestricted case the number of ASTs of order $n$ is given by a
simple product formula as mentioned in the introduction. When considering
$(n,l,r)$ \- ASPs this does not seem to generalise when considering arbitrary
$r$ and $l$, so the Pfaffian obtained in Theorem 2.8 does not seem to have a
simple product factorization. See that the tables below, giving the number of
$(n,l,r)$ \- ASPs, contain too large prime factors to yield a simple product
formula. Checking the OEIS-database it seems that none of the sequences except
for the case $l=0$ and $r=n-1$ as well as its symmetric case $l=n-2$ and
$r=2n-3$ is enumerated by a known sequence. In the two symmetric cases
mentioned we obtain the Catalan numbers. But this is easy to see, since
$(0,n,1)$ \- Magog trapezoids are simply sequences $a_{1}\leq...\leq a_{n}$
such that $a_{i}\leq i$, which are known to be enumerated by the Catalan
numbers (see [Sta99]).

$n=4$ | $l=0$ | $l=1$ | $l=2$
---|---|---|---
$r=3$ | $2\cdot 7$ | $3^{2}$ | $0$
$r=4$ | $5\cdot 7$ | $2^{2}\cdot 7$ | $3^{2}$
$r=5$ | $2\cdot 3\cdot 7$ | $5\cdot 73$ | $2\cdot 7$
$n=5$ | $l=0$ | $l=1$ | $l=2$ | $l=3$
---|---|---|---|---
$r=4$ | $2\cdot 3\cdot 7$ | $2^{2}\cdot 7$ | $0$ | $0$
$r=5$ | $3\cdot 73$ | $2^{3}\cdot 23$ | $2^{3}\cdot 3^{2}$ | $0$
$r=6$ | $3^{2}\cdot 43$ | $3\cdot 5\cdot 23$ | $2^{3}\cdot 23$ | $2^{2}\cdot 7$
$r=7$ | $3\cdot 11\cdot 13$ | $3^{2}\cdot 43$ | $3\cdot 73$ | $2\cdot 3\cdot 7$
$n=6$ | $l=0$ | $l=1$ | $l=2$ | $l=3$ | $l=4$
---|---|---|---|---|---
$r=5$ | $2^{2}\cdot 3\cdot 11$ | $2\cdot 3^{2}\cdot 5$ | $0$ | $0$ | $0$
$r=6$ | $2\cdot 797$ | $5^{3}\cdot 11$ | $3\cdot 199$ | $0$ | $0$
$r=7$ | $2\cdot 11\cdot 13\cdot 17$ | $5^{2}\cdot 179$ | $2\cdot 5^{3}\cdot 11$ | $3\cdot 199$ | $0$
$r=8$ | $7^{2}\cdot 11\cdot 13$ | $2\cdot 11\cdot 13\cdot 23$ | $5^{2}\cdot 179$ | $5^{6}\cdot 11$ | $2\cdot 3^{2}\cdot 5$
$r=9$ | $2^{2}\cdot 11\cdot 13^{2}$ | $7^{2}\cdot 11\cdot 13$ | $2\cdot 11\cdot 13\cdot 17$ | $2\cdot 797$ | $2^{2}\cdot 3\cdot 11$
$n=7$ | $l=0$ | $l=1$ | $l=2$ | $l=3$ | $l=4$ | $l=5$
---|---|---|---|---|---|---
$r=6$ | $3\cdot 11\cdot 13$ | $3^{3}\cdot 11$ | $0$ | $0$ | $0$ | $0$
$r=7$ | $5\cdot 13\cdot 199$ | $11\cdot 1031$ | $3^{2}\cdot 11\cdot 53$ | $0$ | $0$ | $0$
$r=8$ | $5\cdot 11\cdot 13\cdot 107$ | $3\cdot 11\cdot 13\cdot 167$ | $2\cdot 11^{2}\cdot 197$ | $11\cdot 31\cdot 37$ | $0$ | $0$
$r=9$ | $2^{3}\cdot 3\cdot 13^{2}\cdot 41$ | $13\cdot 12253$ | $13^{2}\cdot 709$ | $2\cdot 11^{2}\cdot 197$ | $3^{2}\cdot 11\cdot 53$ | $0$
$r=10$ | $2^{5}\cdot 3\cdot 13^{3}$ | $2^{2}\cdot 7\cdot 13^{2}\cdot 43$ | $13\cdot 12253$ | $3\cdot 11\cdot 13\cdot 167$ | $11\cdot 1031$ | $3^{3}\cdot 11$
$r=11$ | $2^{2}\cdot 13^{2}\cdot 17\cdot 19$ | $2^{5}\cdot 3\cdot 13^{3}$ | $2^{3}\cdot 3\cdot 13^{2}\cdot 41$ | $5\cdot 11\cdot 13\cdot 107$ | $5\cdot 13\cdot 199$ | $3\cdot 11\cdot 13$

## References

  * [ABF20] A. Ayyer, R. E. Behrend, and I. Fischer.  Extreme diagonally and antidiagonally symmetric alternating sign matrices of odd order.  Adv. Math., 367:107125, 56, 2020.
  * [And87] D. André.  Solution directe du problème résolu par m. bertrand.  C. R. Acad. Sci. Paris, 105, (1):436–437, 1887.
  * [And94] G. E. Andrews.  Plane partitions. V. The TSSCPP conjecture.  J. Combin. Theory Ser. A, 66(1):28–39, 1994.
  * [BC13] P. Biane and H. Cheballah.  Gog, Magog and Schützenberger II: left trapezoids.  In 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math. Theor. Comput. Sci. Proc., AS, pages 349–360. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2013.
  * [BC16] P. Biane and H. Cheballah.  Gog and GOGAm pentagons.  J. Combin. Theory Ser. A, 138:133–154, 2016.
  * [Bet19] J. Bettinelli.  A simple explicit bijection between $(n,2)$-Gog and Magog trapezoids.  Sém. Lothar. Combin., 75:Art. B75e, 9, [2015–2019].
  * [CB12] H. Cheballah and P. Biane.  Gog and Magog triangles, and the Schützenberger involution.  Sém. Lothar. Combin., 66:Art. B66d, 20, 2011/12.
  * [FH22] I. Fischer and H. Höngesberg.  Bounded littlewood identity related to alternating sign matrices.  Preprint arXiv:2207.04469, 2022.
  * [Fis06] I. Fischer.  The number of monotone triangles with prescribed bottom row.  Adv. in Appl. Math., 37(2):249–267, 2006.
  * [Fis07] I. Fischer.  A new proof of the refined alternating sign matrix theorem.  J. Combin. Theory Ser. A, 114(2):253–264, 2007.
  * [Fis10] I. Fischer.  The operator formula for monotone triangles—simplified proof and three generalizations.  J. Combin. Theory Ser. A, 117(8):1143–1157, 2010.
  * [Fis11] I. Fischer.  Refined enumerations of alternating sign matrices: monotone $(d,m)$-trapezoids with prescribed top and bottom row.  J. Algebraic Combin., 33(2):239–257, 2011.
  * [Fis16] I. Fischer.  Short proof of the ASM theorem avoiding the six-vertex model.  J. Combin. Theory Ser. A, 144:139–156, 2016.
  * [Fis19] I. Fischer.  Enumeration of alternating sign triangles using a constant term approach.  Trans. Amer. Math. Soc., 372(2):1485–1508, 2019.
  * [Fis22] I. Fischer.  Bounded littlewood identity related to alternating sign matrices.  Preprint arXiv:2301.00175, 2022.
  * [FK20a] I. Fischer and M. Konvalinka.  A bijective proof of the ASM theorem Part I: the operator formula.  Electron. J. Combin., 27(3):Paper No. 3.35, 29, 2020.
  * [FK20b] I. Fischer and M. Konvalinka.  The first bijective proof of the alternating sign matrix theorem.  In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, volume 159 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 12, 12. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020.
  * [FK20c] I. Fischer and M. Konvalinka.  The first bijective proof of the refined ASM theorem.  Sém. Lothar. Combin., 84B:Art. 18, 12, 2020.
  * [FK22] I. Fischer and M. Konvalinka.  A bijective proof of the ASM theorem Part II: ASM enumeration and ASM-DPP relation.  Int. Math. Res. Not. IMRN, (10):7203–7230, 2022.
  * [FSA23] I. Fischer and F. Schreier-Aigner.  The relation between alternating sign matrices and descending plane partitions: $n+3$ pairs of equivalent statistics.  Adv. Math., 413:Paper No. 108831, 47, 2023.
  * [FZJ08] T. Fonseca and P. Zinn-Justin.  On the doubly refined enumeration of alternating sign matrices and totally symmetric self-complementary plane partitions.  Electron. J. Combin., 15(1):Research Paper 81, 35, 2008.
  * [GV85] I. Gessel and G. Viennot.  Binomial determinants, paths, and hook length formulae.  Adv. in Math., 58(3):300–321, 1985.
  * [Kra96] C. Krattenthaler.  A gog-magog conjecture, 1996.
  * [Kra15] C. Krattenthaler.  Lattice path enumeration.  In Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), pages 589–678. CRC Press, Boca Raton, FL, 2015.
  * [Kra16] C. Krattenthaler.  Plane partitions in the work of Richard Stanley and his school.  In The mathematical legacy of Richard P. Stanley, pages 231–261. Amer. Math. Soc., Providence, RI, 2016.
  * [Lin73] B. Lindström.  On the vector representations of induced matroids.  Bull. London Math. Soc., 5:85–90, 1973.
  * [MRR82] W. H. Mills, D. P. Robbins, and H. Rumsey, Jr.  Proof of the Macdonald conjecture.  Invent. Math., 66(1):73–87, 1982.
  * [MRR83] W. H. Mills, D. P. Robbins, and H. Rumsey, Jr.  Alternating sign matrices and descending plane partitions.  J. Combin. Theory Ser. A, 34(3):340–359, 1983.
  * [MRR86] W. H. Mills, D. P. Robbins, and H. Rumsey, Jr.  Self-complementary totally symmetric plane partitions.  J. Combin. Theory Ser. A, 42(2):277–292, 1986.
  * [Oka89] S. Okada.  On the generating functions for certain classes of plane partitions.  J. Combin. Theory Ser. A, 51(1):1–23, 1989.
  * [RR86] D. P. Robbins and H. Rumsey, Jr.  Determinants and alternating sign matrices.  Adv. in Math., 62(2):169–184, 1986.
  * [Sta99] R. P. Stanley.  Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1999.  With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
  * [Ste90] J. R. Stembridge.  Nonintersecting paths, Pfaffians, and plane partitions.  Adv. Math., 83(1):96–131, 1990.
  * [Zei96] D. Zeilberger.  Proof of the alternating sign matrix conjecture.  volume 3, pages Research Paper 13, approx. 84. 1996.  The Foata Festschrift.