%% 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]{FPSAC2025}
\articlenumber{94}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{ytableau}
\usepackage[enableskew]{youngtab}


\newcommand \uu{{\mathbf u}}
\newcommand \vv{{\mathbf v}}
\newcommand \ww{{\mathbf w}}
\newcommand \xx{{\mathbf x}}
\newcommand \aaa{{\mathbf a}}
\newcommand \ccc{{\mathbf c}}
\newcommand \bb{{\mathbf b}}
\newcommand \jj{{\mathbf j}}
\newcommand \kk{{\mathbf k}}

\newcommand\NN{\mathbb{N}}



\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}

\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}


\newcommand\bbinom[2]%
{\mathchoice{\left(\kern-0.48em{\binom{#1}{#2}}\kern-0.48em\right)}
            {\bigl(\kern-0.3em{\binom{#1}{#2}}\kern-0.3em\bigr)}
            {\bigl(\kern-0.3em{\binom{#1}{#2}}\kern-0.3em\bigr)}
            {\bigl(\kern-0.3em{\binom{#1}{#2}}\kern-0.3em\bigr)}}


%\usepackage{lipsum}

%% define your title in the usual way

\title[Volume and Lattice Points of Generalized Pitman--Stanley polytopes]{Volume and Lattice Points of Generalized Pitman--Stanley Flow Polytopes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[W. T. Dugan, M. Hegarty, A. H. Morales, A. Raymond]{\texorpdfstring{William T. Dugan\addressmark{1}, Maura Hegarty\addressmark{2}\thanks{MH was supported by a Lee-SIP REU.},\\ Alejandro H. Morales\addressmark{3}\thanks{WD and AHM were partially supported by NSF grant  DMS-2154019.}, \and Annie Raymond\addressmark{1}\thanks{AR was partially supported by NSF grant DMS-2054404.}}{William T. Dugan, Maura Hegarty, Alejandro H. Morales, and Annie Raymond}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Statistics, UMass Amherst, Amherst, MA, USA \\ \addressmark{2}Operations Research Center, MIT, Cambridge, MA, USA\\
\addressmark{3}LACIM, D\'epartement de Math\'ematiques, UQAM, Montr\'eal, QC, Canada}


%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author

%% then use \addressmark to match authors to institutions here


%% 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{The Pitman--Stanley polytope is well-studied and related to plane partitions of  skew shape with entries $0$ and $1$. We study a generalization of this polytope related to plane partitions with entries $0,1, \ldots, m$. 
%Having previously showed that this polytope is a flow polytope of a grid graph, 
We study formulas for the volume and lattice points of this polytope. These formulas have rich combinatorics including connections to standard Young tableaux of rectangular shape. We also give a combinatorial proof for a special case, partially answering a question of Pitman and Stanley.}

\resume{Nous \'etudions des
formules pour le nombre de points \`a coordonnées entières et le volume d'une g\'en\'eralisation du polytope de Pitman--Stanley
reli\'ee aux partitions de plan avec entr\'ees $\{0,1,\ldots, m\}$. Ces formules \'etablissent des liens avec les tableaux standards de Young  de forme rectangulaire. Nous pr\'esentons une preuve combinatoire pour le cas $n=2$, r\'epondant ainsi partiellement \`a une question de Pitman et Stanley.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Pitman--Stanley polytope, plane partitions, tableaux, Fuss--Catalan}

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

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

\newcommand{\ar}[1]{ {\color{blue}{Annie: #1}}}

\DeclareMathOperator{\PS}{PS}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\SYT}{SYT}
\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}


The eponymous Pitman--Stanley polytope introduced in \cite{Pitman_Stanley_1999} is a well-studied polytope in geometric, algebraic, and enumerative combinatorics. This polytope is defined as follows. For a positive integer $n$ and vectors $\textbf{a}$ and $\textbf{b}$ in $\mathbb{N}^n$, let
\begin{align*}
    \PS_n(\textbf{a},\textbf{b}) := \{\xx\in\mathbb{R}_{\geq 0}^n\quad\big{|}
     \quad b_1+\cdots+b_i \leq x_1+\cdots+x_i\leq a_1+\cdots+a_i \ \text{ for } i=1,\ldots,n\},
\end{align*}
i.e., $\PS_n({\bf a},{\bf b})$ consists of the nonnegative vectors $\xx$ in $\mathbb{R}^n$ that are between vectors ${\bf a}$ and ${\bf b}$ in {\em dominance order}. Recall that, for $\vv,\ww\in \NN^n$, we say that $\vv$ {\em dominates} $\ww$ if $\sum_{j=1}^i v_j \geq \sum_{j=1}^i w_j$ for every $i=1,\ldots,n$. The polytope $\PS_n({\bf a}):=\PS_n(\textbf{a},\textbf{0})
$ is an example of a generalized permutahedron \cite{AP}, and a flow polytope \cite{Baldoni_Vergne_2008}. The skew case $\PS_n(\textbf{a},\textbf{b})$ is related to lattice path matroids \cite[Section 4.5]{BidPhd}.


Pitman and Stanley showed the lattice points of $\PS_n(\textbf{a},\textbf{b})$ correspond to {\em plane partitions} of a skew shape $\theta(\aaa,\bb)=(a_1+\cdots+a_n,\ldots,a_1+a_2,a_1)/(b_1+\ldots+b_n,\ldots,b_1+b_2,b_1)$ with entries $0,1$. In their paper, they mentioned in passing a generalization of their polytope whose lattice entries correspond to plane partitions of shape $\theta(\aaa,\bb)$ with entries $0,1,\ldots,m$. We call this the {\em  generalized Pitman--Stanley polytope} defined as follows:
\begin{align*}
\PS^m_n({\bf a},{\bf b}) := \{ & (x_{ij})_{1\leq i\leq n,1\leq j \leq m}  \in \mathbb{R}_{\geq 0}^{nm} \quad\big{|} \quad b_1 + \dots + b_i \leq x_{1m}+x_{2m}+\ldots+x_{im} \leq \cdots \\ &\cdots
%\leq x_{12}+x_{22}+\ldots+x_{i2}
\leq  x_{11}+x_{21}+\ldots+x_{i1} \leq a_1 + \dots + a_i \text{ for } i=1,\ldots,n\}.
\end{align*}
In \cite{genPSvertices}, we started an in-depth study of this polytope. We showed that $\PS^m_n({\bf a},{\bf b})$ is integrally equivalent to a flow polytope of a grid graph $G(n,m)$  (the flow on the horizontal edges correspond to the coordinates of the polytope, see \Cref{fig:gridgraph}, left)
% \begin{equation} \label{eq: PSmn integral equiv flow poly}
% \PS_n^m(\aaa,\bb) \equiv \mathcal{F}_{G(n,m)}(\aaa,-\bb),
% \end{equation}
and studied its vertices and faces. In this extended abstract, we study formulas for its volume and lattice points. 

% \begin{figure}
%     \centering
%             \includegraphics[scale=0.7]{figures_superset/grid_graph_G34_blob_labels_noys_bigl.pdf} 
%     \caption{The grid graph $G(3,4)$ that realizes $\PS^4_3(\aaa,\bb)$ as the flow polytope $\mathcal{F}_{G(3,4)}(\aaa,\bb)$.}
%     \label{fig:gridgraph}
% \end{figure}


Pitman and Stanley \cite{Pitman_Stanley_1999} found the following nonnegative formulas for the volume and lattice points of $\PS_n(\aaa)$.
\[
\vol \PS_n(\aaa) = \sum_{{\bf j}} \binom{n}{j_1,\ldots,j_n} a_1^{j_1}\cdots a_n^{j_n},~
\#(\PS_n(\aaa)\cap \mathbb{Z}^n) = \sum_{{\bf j}} \bbinom{a_i+1}{j_1} \bbinom{a_2}{j_2}\cdots \bbinom{a_n}{j_n},
\]
  where $\bbinom{n}{k}=\binom{n+k-1}{k}$ and the sum is over compositions ${\bf j}=(j_1,\ldots,j_n)$ of $n$ that dominate ${\bf 1}$. The number of such compositions is $C_n:=\frac{1}{n+1}\binom{2n}{n}$, the $n$th Catalan number which counts Dyck paths of size $n$, Standard Young tableaux (SYT) of shape $(n^2)$ (or shape $(2^n)$, among others. Their formula for lattice points implies that the Ehrhart polynomial $\#(\PS_n(t{\bf a}) \cap \mathbb{Z}^n)$ of this polytope has nonnegative coefficients in $t$.

\medskip

\noindent {\bf Straight shape case $\PS_n^m(\aaa,{\bf 0})$:} Using the connection between the generalized Pitman--Stanley polytope and flow polytopes, we use the {\em Lidskii volume formula} of the latter \cite{Baldoni_Vergne_2008,Mészáros_Morales_2018} to give a nonnegative formula for the volume of $\PS_n^m(\aaa):=\PS_n^m(\aaa,{\bf 0})$ (see \Cref{thm:lidskii vol for PSnm}). The number of terms of the formula is the {\em Fuss--Catalan number} $FC_{n,m}:=\frac{1}{nm+1}\binom{(m+1)n}{n}$ which count $m$-Dyck paths of size $n$ \cite{stump2018catalandfuss}. Another important ingredient of the formula are certain multiplicities $K_{G(n,m)}({\bf j}-{\bf 1})$ that are {\em mixed volumes} and count several interesting objects including: certain integer flows on the graphs $G(n,m)$, certain tuples of generalized Dyck paths, and the number of SYT of shape $n^{m+1}$ with prescribed last (or first) row.  In \Cref{combinatorics volume formula}, we give bijections among these objects (\Cref{m-Dyck path interpretation,prop:SYT-to-dyck}), other interpretations, and enumerative properties. The latter include a determinantal formula for the generating polynomial of these multiplicities (\Cref{cor:det of gen poly Kgs}).  

The case of ${\bf a}={\bf 1}$ is particularly interesting as shown algebraically in \cite[Theorem 14]{Pitman_Stanley_1999}. 

%\begin{theorem}[{\cite[Theorem 14]{Pitman_Stanley_1999}}]
%The polytope $\PS^m_n({\bf 1})$ has the following  volume
\begin{equation} \label{eq:volume formula case 1}
 \vol \PS_n^m({\bf 1}) = \SYT(n^m) \cdot \prod_{i = 1}^m i!(n+i)^{n-m-1+i},
\end{equation}
where $\SYT(n^m)$ is the number of SYT of shape $m\times n$. In particular  $\vol\PS_n({\bf 1})=(n+1)^{n-1}$, the number of parking functions of size $n$. 
Pitman and Stanley gave in \cite{Pitman_Stanley_1999}  a combinatorial proof for the case $m=1$ and asked for a combinatorial proof for general $m$ and $n$. In \Cref{sec: combinatorial proof volume formulas}, we use our volume formula to give a combinatorial proof for the case $n=2$ (which has $\binom{m+2}{3}$ vertices), where the volume is $C_m \prod_{i=1}^m i!(2+i)^{1-m+i}$.

In \Cref{thm:Ehrhart formula from order cones tableaux version}, we also give a nonnegative  formula for the number of lattice points of $\PS_n^m(\aaa)$, that reduces to Pitman--Stanley's formula for $m=1$ and also implies our volume formula \eqref{eq:lidskii vol for PSnm}.  The summation formula is in terms of SYT of shape $n^{m+1}$ and their {\em natural descents}. Calculations suggest that $\PS_n^m(\aaa)$ is Ehrhart positive but this is not evident from our lattice point formula. 

\medskip

\noindent {\bf Skew shape case $\PS_n^m(\aaa,\bb)$:} Lattice points of $\PS_n^m({\bf a},{\bf b})$ correspond to plane partitions with bounded entries, their number is given by a determinant formula of Kreweras \cite{Kreweras_1965}:
\begin{equation} \label{eq:kreweras number lp}
\#(\PS_n^m(\textbf{a}, \textbf{b}) \cap \mathbb{Z}^{mn}) \,=\, \det\left[ \binom{a_1+\cdots+a_{i}-b_1 - \cdots -b_{j}+m}{i-j+m} \right]_{i,j=1}^n.
\end{equation}
Note that from the subtractions in the binomials above, these formulas for generic ${\bf a}$ and ${\bf b}$ are piecewise polynomial. In \Cref{thm:Ehrhart formula skew shape} we give nonnegative formulas for $\#(\PS_n^m(\textbf{a}, \textbf{b}) \cap \mathbb{Z}^{mn})$. Two salient features of these formulas are that (i) they are in terms of SYT of shape $n^{m+2}$ and their descents, and (ii) for fixed $n$, there are $C_n$ possible formulas depending on the relative order of the partial sums of the $a_i$s and $b_i$s. From the lattice point formulas one can also extract a formula for the volume of $\PS_n^m(\aaa,\bb)$ (\Cref{cor:eq:vol formula skew shape}). 
These lattice point formulas for $\PS_n^m(\aaa)$ and $\PS_n^m(\aaa,\bb)$ are obtained using Stanley's theory of {\em marked order polytopes} \cite{Pitman_Stanley_1999,Stanley_AF} and not from the {Lidskii formula} for lattice points of flow polytopes.


% \section{Old Introduction}

% Later, Baldoni and Vergne \cite{Baldoni_Vergne_2008} realized $\PS_n({\bf a})$ as a {\em flow polytope} of a certain graph (see \Cref{fig:comparing flows PS}). In addition, Pitman and Stanley related this polytope to the {\em associahedron} \cite[Section 6]{Pitman_Stanley_1999}, Postnikov showed that $\PS_n({\bf a}):=\PS_n(\textbf{a},\textbf{0})$ is an example of a {\em generalized permutahedron} \cite{AP}, and Bidkhori related it to {\em lattice path matroids} \cite[Section 4.5]{BidPhd}.  The volume of the polytope  $\PS_n(\textbf{a})$ is of interest in probability \cite[Section 2]{Pitman_Stanley_1999} and is related to {\em parking functions}  (see \cite[Theorem 11]{Pitman_Stanley_1999} and \cite[Section 13.4]{Yan_pf_handbook}), the Tutte polynomial \cite{KonvPak} and {\em Cayley compositions} \cite{KonvPak2}.  






% \begin{corollary}\label{lattice_points} The number of lattice points of $\PS_n^m(\textbf{a},\textbf{b})$ has the following formula
% \[
% \#(\PS_n^m(\textbf{a}, \textbf{b}) \cap \mathbb{Z}^{mn}) \,=\, \det\left[ \binom{a_1+\cdots+a_{i}-b_1 - \cdots -b_{j}+m}{i-j+m} \right]_{i,j=1}^n.
% \]
% \end{corollary}


% % Note that from the subtraction in the binomials above, these formulas for generic ${\bf a}$ and ${\bf b}$ are piecewise polynomial. For the case  ${\bf b}={\bf 0}$ we have that 
% % \begin{equation} \label{eq:vol1}
% % \vol \PS_n^m({\bf a}) = \det \left[ \frac{(a_1+\cdots + a_{i})^{i-j+m}}{(i-j+m)!} \right]_{i,j=1}^n 
% %\\ 
% %&= \det \left[ \frac{((a_1+\cdots + a_{i})-(b_1+\cdots + b_j))^{j-i+m}}{(j-i+m)!} \right]_{i,j=1}^n\label{eq:vol2}
% % \end{equation}
% The case ${\bf a}={\bf 1}$ and ${\bf b}={\bf 0}$ is particularly nice for both lattice points and volume \cite[Theorem 14]{Pitman_Stanley_1999}.

% %\subsection{Volume formulas}

% %\subsubsection*{Straight shape case}

% \begin{theorem} \label{cor:lidskii vol for PSnm}
% \[
% \vol \PS^m_n(\aaa) = \sum_{{\bf j}} \binom{mn}{j_1,\ldots,j_n} a_1^{j_1}\cdots a_n^{j_n} K_{G(n,m)}({\bf j}-{\bf 1}),
% \]    
% where the sum is over compositions ${\bf j}=(j_1,\ldots,j_n)$ of $mn$ such that $\sum_{i=1}^k j_i \geq km$ for $k=1,\ldots,n-1$. $K_{G(n,m)}({\bf j}-{\bf 1})$ is the number of SYT of shape $n^{m+1}$ where the $(m+1)th$ row has values $(j_1+1,j_1+j_2+2,\ldots,j_1+\cdots +j_{n-1}+n-1,n(m+1))$.
% \end{theorem}


% \textcolor{blue}{The m=1 case of the gen PS is an example of a genearlized polymatroid.}

% \begin{theorem}[{\cite[Theorem 14]{Pitman_Stanley_1999}}]
% The polytope $\PS^m_n({\bf 1})$ has the following  volume
% \begin{equation} \label{eq:volume formula case 1}
%  \vol \PS_n^m({\bf 1}) = \SYT(n^m) \cdot \prod_{i = 1}^m i!(n+i)^{n-m-1+i},
% \end{equation}
% where $\SYT(n^m)$ is the number of SYT of shape $m\times n$.
% \end{theorem}

% Pitman and Stanley asked in \cite{Pitman_Stanley_1999} for a combinatorial proof of the volume formula above. We give such a proof  and give a bijection between SYT of shape $(m+1) \times n$ and the pieces of a subdivision of $\PS_n^m({\bf 1})$ coming from the {\em Lidskii formula} for flow polytopes \cite{Baldoni_Vergne_2008,Mészáros_Morales_2018}. 

% %\subsubsection*{Skew shape case}


% Given $\aaa$ and $\bb$ in $\mathbb{Z}^n_{\geq 0}$, let $\alpha_i=\sum_{j=1}^i a_j$ and $\beta_i = \sum_{j=1}^i b_j$. There are $C_n$ different relative orders of the numbers $\alpha_1,\ldots,\alpha_n$ and $\beta_1,\ldots,\beta_n$ (one for each SYT of shape $(n,n)$). For each such relative order, we give a formula for the volume of the skew generalized Pitman--Stanley polytope (see \Cref{cor:eq:vol formula skew shape}). 

% % Given $\aaa$ and $\bb$ in $\mathbb{Z}^n_{\geq 0}$, let $\alpha_i=\sum_{j=1}^i a_j$ and $\beta_i = \sum_{j=1}^i b_j$. Let $\SYT_{\aaa,\bb}(n^{m+2})$ be the set of SYT of shape $n^{m+2}$ such that the first and last row have the same relative order as the numbers $\alpha_1,\ldots,\alpha_n$ and $\beta_1,\ldots,\beta_n$. We denote this relative order by $\pi(T)=(\pi_1,\ldots,\pi_{2n})$. Note that in the generic case where $a_i>0$ and $b_i>0$, then there are Catalan ($\SYT(n,n)=C_n$) many different sets $\SYT_{\aaa,\bb}(n^{m+2})$.

% % \begin{corollary}
% %    \begin{equation} \label{eq:Ehrhart formula skew shape}
% %  \vol \PS_n^m({\bf a},{\bf b})  =  \sum_{T \in \SYT_{\aaa,\bb}(n^{m+2})} \binom{mn}{c_1-1,c_2-c_1-1,\ldots,c_{2n}-c_{2n-1}-1} \prod_{i=1}^{2n} (\pi_i-\pi_{i-1})^{c_i-c_{i-1}-1},
% %   \end{equation}
% %   where $1=c_1<c_2<\cdots<c_{2n}=n(m+2)$ are the entries in the first and last row of $T$, $d_i(T)$,  are the number of descents as defined above, $\pi(T)$ is the relative order of $\alpha_i$s and $\beta_i$s from $T$ where $\pi_0=0$.
% % \end{corollary}




% %\subsection{Lattice points and Ehrhart polynomial}


% %\subsubsection*{Straight shape case}





% Given a SYT $T$, a {\em (natural) descent} of $T$ is a value $i$ of $T$ such that $i+1$ occurs strictly above $i$ in $T$ \cite{MO}. Given a SYT $T$ of shape $n^{m+1}$ ($n\times (m+1)$) with last row $c_1<c_2<\cdots<c_n=(m+1)n$. For $i=1,\ldots,n$ Let $d_i(T)$ be the number of descents of $T$ between and including $c_{i-1}$ up to $c_i$ (where $c_0=0$).

% \begin{corollary}
%    \begin{equation} \label{eq:Ehrhart formula from order cones tableaux version}
%   \#(PS_n^m({\bf a}) \cap \mathbb{Z}^{nm}) =  \sum_{T \in SYT(n^{m+1})} \prod_{i=1}^n \bbinom{a_i -d_i(T)+1}{c_i-c_{i-1}-1},
%   \end{equation}
%   where $c_1<c_2<\cdots<c_n=(m+1)n$ is the last row of $T$ and $d_i(T)$ are as defined above.
% \end{corollary}


% \begin{corollary}[\cite{Pitman_Stanley_1999}]
% The polytope $\PS^m_n({\bf 1})$ has the following number of lattice points and volume
% \[
% \#(\PS_n^m({\bf 1}) \cap \mathbb{Z}^{mn}) =\prod_{\mathclap{1\leq i<j\leq n+1}}\frac{2m+i+j-1}{i+j-1}.
% \]
% \end{corollary}

% %\subsubsection*{Skew shape case}

% Similarly to the volume, for each of the $C_n$ relative order of the $\alpha_i=a_1+\cdots +a_i$ and $\beta_i = b_1+\cdots+b_i$, we give a formula for the lattice points and Ehrhart polynomial of the skew generalized Pitman--Stanley polytope (see \Cref{thm:Ehrhart formula skew shape formula skew shape}). 

% % Given a SYT $T$ of shape $n^{m+2}$ with entries $1=c_1<c_2<\cdots<c_{2n}=n(m+2)$ in the first and last row of $T$. For $i=1,\ldots,2n$ Let $d_i(T)$ be the number of descents of $T$ between and including $c_{i-1}$ up to $c_i$ (where $c_0=0$).

% % \begin{theorem}
% %    \begin{equation} \label{eq:Ehrhart formula skew shape}
% %   \#(\PS_n^m({\bf a},{\bf b}) \cap \mathbb{Z}^{nm}) =  \sum_{T \in \SYT_{\aaa,\bb}(n^{m+2})} \prod_{i=1}^{2n} \bbinom{\pi_i-\pi_{i-1} -d_i(T)+1}{c_i-c_{i-1}-1},
% %   \end{equation}
% %   where $1=c_1<c_2<\cdots<c_{2n}=n(m+2)$ are the entries in the first and last row of $T$, $d_i(T)$,  are the number of descents as defined above, $\pi(T)$ is the relative order of $\alpha_i$s and $\beta_i$s from $T$ where $\pi_0=0$.
% % \end{theorem}





\section{The Lidskii volume formula for \texorpdfstring{$PS_n^m$$($$\aaa,$$\bb$$)$}{PSnm(a,b)}}
\label{combinatorics volume formula}



\subsection{Lidskii volume formulas for \texorpdfstring{$PS_n^m({\bf a})$}{PSnm(a)}}\label{Lidskii volume formulas}



% \textcolor{blue}{write the Lidskii volume formulas here and the version for the graph $G(n,m)$}
The Lidskii formula can be used to calculate the volume of a flow polytope \cite{Baldoni_Vergne_2008,Mészáros_Morales_2018}. Considering we have shown that $\PS_n^m(\aaa)$ is a flow polytope \cite[Theorem 3.4]{genPSvertices}, we can use the Lidskii volume formula of the latter \cite{Baldoni_Vergne_2008,Mészáros_Morales_2018} to calculate the volume of $PS_n^m(\textbf{a})$.

% \begin{definition} \label{def:kpfg}
% We denote the number of lattice points of $\FF_G(\ccc)$ which are the integer $\ccc$-flows on $G$ by $K_G(\ccc)$. The name comes from the fact when $G$ is the complete graph, this number is known as Kostant's vector partition function.
% \end{definition}

% Let $\mathcal{F}_G(\ccc)$ denote the {\em flow polytope} of a graph $G$ with netflow $\ccc$, which is the set of $\ccc$-flows on $G$  and $K_G({\bf \ccc})$ denote the number of lattice points (i.e. integer flows) of $\mathcal{F}_G(\aaa)$ (see e.g. \cite{Mészáros_Morales_2018} for precise definitions).

% \begin{theorem}\label{Lidskii_theorem} Let $G$ be a connected directed acyclic graph on the vertex set $[N+1]$, with $M$ edges $i\xrightarrow{}j$ where $i<j$, with at least one outgoing edge at vertex $i$ for $i=1,\dots, N$, and let $\bf a$ $=(a_1, \dots, a_N, -\sum_{i=1}^na_i)$ where each $a_i$ is nonnegative. Then 
% \begin{align} \label{eq:vol}
%     \textup{vol}\mathcal{F}_G(\textup{\textbf{a}}) = \sum_{\bf j} \binom{M-N}{j_1, \dots, j_N}a_1^{j_1}\cdots a_N^{j_N}\cdot K_G(j_1-\textup{out}_1, \dots, j_N-\textup{out}_N, 0),
% \end{align}
% where $\textup{out}_i=\textup{outd}_i-1$ such that $\textup{outd}_i$ indicates the outdegree of vertex $i$ in $G$. Each sum is over weak compositions $\bf j$ $=(j_1, j_2, \dots, j_N)$ dominate $(out_1,\ldots,out_N)$.
% \end{theorem}

\begin{definition}\label{def:KGflows}
For the grid graph $G(n,m)$ and a composition ${\bf j}=(j_1,\ldots,j_n)$ of $mn$, let $K_{G(n,m)}({\bf j}-{\bf 1}):=K_{G(n,m)}({\bf c})$, where ${\bf c}$ is the concatenation of ${\bf j}-{\bf 1}$ of length $n$, of ${\bf -1}$ of length $n(m-1)$ and ${\bf 0}$ of length $n+1$, be the number of integral flows on $G(n,m)$ where the net flow of the leftmost vertices of $G(n,m)$ is ${\bf j}-{\bf 1}$, of the rightmost vertices is ${\bf 0}$ (including the sink), and all internal vertices of the graph have net flow $-1$. Note that we do not draw the sink and the edges adjacent to the sink in future figures as they carry no flow.
\end{definition}



\begin{theorem} \label{thm:lidskii vol for PSnm}
\begin{equation} \label{eq:lidskii vol for PSnm}
\vol \PS^m_n(a_1,\ldots,a_n) = \sum_{{\bf j}} \binom{mn}{j_1,\ldots,j_n} a_1^{j_1}\cdots a_n^{j_n} K_{G(n,m)}({\bf j}-{\bf 1}),
\end{equation}
where the sum is over compositions ${\bf j}=(j_1,\ldots,j_n)$ of $mn$ that dominate $m\bf{1}$.
\end{theorem}

\begin{proof}[Proof Sketch]
$\PS^m_n(\aaa)$ is integrally equivalent to the flow polytope $\mathcal{F}_{G(n,m)}(\ccc)$ where $\ccc=(\aaa,{\bf 0},-\sum_i a_i)$ indicates netflow $a_i$ for vertices on the left boundary of the graph, zero netflow for every vertex  in $G(n,m)$ that is not on the left boundary or is a sink of the graph. We can thus apply the Lidskii volume formula \cite[Theorem 38]{Baldoni_Vergne_2008}  to $\PS^m_n(\aaa)$.% Note that for nonzero terms of the formula, for vertices $i$ such that $c_i=0$, we must have $j_i=0$ so that $c_i^{j_i}=0^0=1$. Further, note that the out degree of every vertex of $G(n,m)$ is 2 except on the right boundary of the graph where it is 1. Finally, observe that for $K_G(j_1-\textup{out}_1, \dots, j_N-\textup{out}_N, 0)>0$, we need $\textbf{j}$ to be such that $j_1 \geq m$, $j_1+j_2\geq 2m$, $\ldots$, $j_1+j_2+\ldots+j_{n-1} \geq (n-1)m$ and $j_1+j_2+\ldots+j_n=nm$.
% If we apply \eqref{eq:vol} to the $\PS^m_n(\aaa)$ we obtain the RHS of \eqref{eq:vol} where the sum is over compositions $(j_1,\ldots,j_{mn})$ of $mn$ that are $\geq (1,\ldots,1)$ in dominance order. 

% First recall that $\mathbf{a}=(1,\ldots,1)$ hides $a_i=0$ for every vertex $i$ in $G(n,m)$ that is not on the left boundary of the graph. Thus, for nonzero terms of the formula, $j_i=0$ for such vertices so that we have $a_i^{j_i}=0^0=1$. Further, note that the out degree of every vertex of $G(n,m)$ is 2 except on the right boundary of the graph where it is 1. Thus, setting $j_i=0$ for vertices not on the left boundary,  $K_G(j_1-\textup{out}_1, \dots, j_N-\textup{out}_N, 0)$ is the number of integer flows on the graph $G(n,m)$ where vertices on the left boundary have in-flow of $j_i-1$, vertices on the right boundary have in-flow or $0$ and all other vertices have in-flow of $-1$. For $K_G(j_1-\textup{out}_1, \dots, j_N-\textup{out}_N, 0)>0$, we need $\textbf{j}$ to be such that $j_1 \geq m$, $j_1+j_2\geq 2m$, $\ldots$, $j_1+j_2+\ldots+j_{n-1} \geq (n-1)m$ and $j_1+j_2+\ldots+j_n=nm$ since there is no directed path from any source that is lower than any sink.   
\end{proof}

\begin{example} \label{ex:running ex m=n=2}
For $n=m=2$, we have from \Cref{fig:SYT3by2} that 
\begin{equation*}\label{eq:voln=m=2}
\vol \PS^2_2(a_1,a_2) = \binom{4}{4,0}\cdot a_1^4 \cdot 2+ \binom{4}{3,1} \cdot a_1^3a_2\cdot 2 + \binom{4}{2,2}\cdot a_1^2a_2^2\cdot 1 = 2a_1^4 + 8a_1^3a_2 + 6a_1^2a_2^2.
\end{equation*}
\end{example}




\subsection{Interpretations of \texorpdfstring{$K_{G(n,m)}({\bf j}-{\bf 1})$}{KG(n,m)(j-1)}}

We now give different combinatorial interpretations for $K_{G(n,m)}({\bf j}-{\bf 1})$, but first, we show a recursion.

\begin{lemma}\label{lem:recurrenceKG}
    We have that
    $K_{G(n,m)}(\mathbf{j}-\mathbf{1})=\sum_{\mathbf{k}} K_{G(n,m-1)}(\mathbf{k}-\mathbf{1})$
    %$$K_{G(n,m)}(\mathbf{j}-\mathbf{1})=\sum_{\substack{\mathbf{k}:\\ \mathbf{k} \succeq (m-1, 2(m-1), \ldots, n(m-1))\\ \sum k_i = n(m-1) \\  \mathbf{k} \preceq \mathbf{j}-\mathbf{1} }} K_{G(n,m-1)}(\mathbf{k}-\mathbf{1})$$ 
    % or equivalently $$A_{n,m}(\mathbf{j})=\sum_{\substack{\mathbf{k}:\\ \mathbf{k} \succeq (m-1, 2(m-1), \ldots, n(m-1))\\ \sum k_i = n(m-1) \\  \mathbf{k} \preceq \mathbf{j}-\mathbf{1} }} A_{n,m-1}(\mathbf{k}).$$
    where the sum is over compositions $\mathbf{k}$ of $(m-1)n$ such that $\mathbf{k}$ dominates $(m-1)\bf{1}$ and is dominated by $\mathbf{j}-\mathbf{1}$.
\end{lemma}

\begin{proof}[Proof sketch]
The sum of flows in the first column of $G(n,m)$ is $n(m-1)$, and the vector of the flows in the first column must be dominated by $\mathbf{j}-\mathbf{1}$. 
\end{proof}

\begin{definition}
We call a Dyck path that stays above (but may touch) the line $y=\frac{1}{m}x$ an \emph{$m$-Dyck} path.  We say an $m$-Dyck path is \emph{$i$-stepping} if between every two North steps, there are at least $i$ East steps. We call a set of $m+1$ non-crossing $m$-Dyck paths from $(0,0)$ to $(mn,n)$ $\{P_0, P_1, \ldots, P_m\}$ a \emph{lengthening $m$-Dyck set for $n$} if $P_i$ is above or equal to $P_{i+1}$ everywhere, and if $P_i$ is $i$-stepping for every $i$. We let $\mathcal{D}_{m,n}$ be the collection of  lengthening $m$-Dyck sets for $n$.
\end{definition}

\begin{proposition} \label{m-Dyck path interpretation}
$K_{G(n,m)}({\bf j}-{\bf 1})$ counts sets of Dyck paths $\{P_0,P_1, \ldots, P_m\}$ in $\mathcal{D}_{m,n}$ where the lengths of horizontal steps of $P_0$ are given by $\bf{j}$ (starting from the top right corner).
\end{proposition}

\begin{proof}[Proof sketch]
The flows counted by $K_{G(n,m)}({\bf j}-\mathbf{1})$ (see \Cref{def:KGflows}) are uniquely characterized by $\mathbf{j}$ and the flows on the horizontal edges of $G(n,m)$. Moreover, $x_{1k}+x_{2k}+\ldots+x_{nk}$, the sum of the flows on the horizontal edges in the $k$th column of the graph is $n(m-k)$ for each $1\leq k\leq m$. Let $P_k$ be the Dyck path where the lengths of horizontal steps (starting from the top right corner of the grid) are the flows of the horizontal edges in the $k$th column of the graph plus $k$, and let $P_0=\mathbf{j}$. Then $\{P_0, P_1, \ldots, P_m\}\in \mathcal{D}_{m,n}$. 

    % As explained in the proof of \Cref{lem:numtermslidskii}, $K_{G(n,m)}({\bf j}-\mathbf{1})$ counts the number of integer flows on the graph $G(n,m)$ where vertices on the left boundary have in-flow of $j_i-1$, vertices on the right boundary have in-flow or $0$ and all other vertices have in-flow of $-1$. These flows are uniquely characterized by $\mathbf{j}$ and the flows on the horizontal edges of $G(n,m)$. Note that since $j_1+j_2+\ldots+j_n=nm$ and since we can think of each vertex has having an out-flow of $1$, every flow will be such that $x_{1k}+x_{2k}+\ldots+x_{nk}=n(m-k)$. So for each $1\leq k\leq m-1$, \ar{need to make a choice: does $k$ go to $m-1$ or $m-2$? The last Dyck path will always be $(m,m)$.} create a Dyck path called $D_k$ with horizontal steps of lengths $x_{1k}+k, x_{2k}+k, \ldots, x_{nk}+k$.
    % We claim that $\mathbf{j}$, $D_1$, $D_2$, \ldots, $D_{m-1}$ is a set of $m$ non-crossing lengthening $m$-Dyck paths. ADD PROOF
\end{proof}






\begin{proposition}\label{prop:SYT-to-dyck}
We have that $K_{G(n,m)}({\bf j}-{\bf 1})$ counts the number of SYT of shape $n^{m+1}$ where the $(m+1)th$ row has values $(j_1+1,j_1+j_2+2,\ldots,j_1+\cdots +j_{n-1}+n-1,n(m+1))$. This implies that $\#\mathcal{D}_{m,n}=\SYT(n^{m+1})$.
\end{proposition}

\begin{proof}[Proof sketch]
    We use \Cref{m-Dyck path interpretation} to give a bijection with such SYTs. Consider a standard Young tableau $Y$ of shape $n^{m+1}$ with entries $y_{ij}$ for $1\leq i \leq m+1$ and $1\leq j \leq n$. Now build an auxiliary $(m+1)\times n$ array $X$ where $x_{i,1}=y_{i,1}$ for all $1\leq i\leq m+1$ and $x_{i,j}=y_{i,j}-y_{i,j-1}-s_{i,j}$ for all $2\leq j \leq n$ and $1 \leq i \leq m+1$ where $$s_{i,j}\,:=\,\#\{y_{i',j'}\,|\,y_{i,j-1} < y_{i',j'} < y_{i,j} \textup{ such that } j'<j \textup{ and } i'>i\}.$$ Now consider an $(m+1)\times n$ array $Z$ where $z_{i,j}=x_{i,j}+m-i$. Each row gives the horizontal steps of a Dyck path (starting from the top right corner). One can show that this set of Dyck paths is in $\mathcal{D}_{m,n}$, and that the top Dyck path (given by the last row of $Z$) has horizontal steps of length $(y_{m+1,1}-1, y_{m+1,2}-y_{m+1,1}-1, y_{m+1,3}-y_{m+1,2}-1, \ldots, y_{m+1,n}-y_{m+1,n-1}-1)$.  One can then show that this gives $\#\mathcal{D}_{m,n}=\SYT(n^{m+1})$. 
\end{proof}
% \begin{proof}
% \textcolor{blue}{switch to convention that is $(m+1)\times n$}
%     We give a bijection between sets of Dyck paths in $\mathcal{D}_{m,n}$ and the number of standard Young Tableaux of shape $((m+1)^n)$ (which is known to be equal to $C_{m+1}(n)$, see, e.g., \cite{}).

%     Consider a standard Young tableau of shape $((m+1)^n)$
% \begin{align*}
%     \ytableausetup{mathmode, boxsize=3em}
%     \begin{ytableau}
%     y_{1,1} & y_{1,2} & \none[\cdots]  & y_{1,m+1}\\
%     y_{2,1} & y_{2,2} & \none[\cdots]  & y_{2,m+1}\\
%     \none[\vdots]   & \none[\vdots] & \none & \none[\vdots]  \\
%     y_{n,1} & y_{n,2} & \none[\cdots]  & y_{n,m+1}
%     \end{ytableau}.
% \end{align*}

% By definition, we have that $y_{i,j}<y_{i+1, j}$ and $y_{i,j}< y_{i, j+1}$ for all $1\leq i <n$ and $1\leq j <m+1$. Now build an auxiliary $n\times(m+1)$ array $X=(x)_{1\leq i \leq n, 1 \leq j \leq m+1}$ where $x_{1,j}=y_{1,j}$ for all $1\leq j\leq m+1$ and $x_{i,j}=y_{i,j}-y_{i-1,j}-s_{i,j}$ for all $2\leq i \leq n$ and $1 \leq j \leq m+1$ where $$s_{i,j}:=|\{y_{i',j'}|y_{i-1,j} < y_{i',j'} < y_{i,j} \textup{ such that } i'<i \textup{ and } j'>j\}|.$$ In other words, $x_{i,j}$ is the difference between $y_{i,j}$ and the entry directly above it, $y_{i-1,j}$, minus the number of entries northeast of $(i,j)$ that are between $y_{i-1,j}$ and $y_{i,j}$. Now consider an $n\times (m+1)$ array $Z=(z)_{1\leq i \leq n, 1 \leq j \leq m+1}$ where $z_{i,j}=x_{i,j}+m-j$ where the columns give the horizontal steps of some Dyck paths. 

% We now show that this set of Dyck paths belongs in $\mathcal{D}_{m,n}$. First observe that the paths are lengthening (from the path given by column $m$ to the path given by column $1$ of $Z$) since we add $m-j$ to entries in column $j$, i.e., entries in column $j$ are all at least $m-j+1$. To show that the paths are non-crossing, we need to prove that

% \begin{align*}
%     \sum_{k=1}^i z_{k,j} \leq \sum_{k=1}^i z_{k,j+1} 
% \end{align*}
% for all $i \in [n]$ and $j\in [m]$. From our constructions of $X$ and $Z$, we know that for any $i \in [n]$ and $j\in [m]$,
% \begin{align*}
%     \sum_{k=1}^i z_{k,j} &=\sum_{k=1}^i (x_{k,j} +m-j)\\
%     &=y_{1,j}+m-j+\sum_{k=2}^i (y_{k,j}-y_{k-1,j}-s{k,j}+m-j)\\
%     &=y_{i,j}+i(m-j)-\sum_{k=2}^i s_{k,j}.
% \end{align*}

% Moreover, $\sum_{k=2}^i s_{k,j}$ is the number of entries northeast of $(i,j)$ in the standard Young tableau that are smaller than $y_{i,j}$, say $S_{i,j}$. %Indeed, suppose $(i',j')$ is an entry northeast of $(i,j)$ (i.e., $i'<i$ and $j'>j$) such that $y_{i',j'}<y_{i,j}$. Let $i''$ be the smallest row index such that $y_{i'',j}>y_{i',j'}$

% Therefore, we need to show that
% $$y_{i,j}+i(m-j)-S_{i,j} \leq y_{i,j+1}+i(m-j-1)-S_{i,j+1}$$ or equivalently that $$y_{i,j}-S_{i,j} \leq y_{i,j+1}-i-S_{i,j+1}.$$

% Any entry smaller than $y_{i,j}$ northeast of $(i,j+1)$ is counted by both $S_{i,j}$ and $S_{i,j+1}$; suppose there are $a$ of them. Suppose there are $b$ entries northeast of $(i,j+1)$ that are bigger than $y_{i,j}$ but smaller than $y_{i,j+1}$. Then $S_{i,j+1}=a+b$.  Finally, suppose there are $c$ entries in column $j+1$ above $(i,j+1)$ that are smaller than $y_{i,j}$. Since those entries are northeast of $(i,j)$ (but aren't northeast of $(i,j+1)$), we have that $S_{i,j}=a+c$. Thus we must show that $y_{i,j+1} - y_{i,j}\geq i+b-c$.

% Note that, by definition of a standard tableau, all $i-1$ entries above $(i,j+1)$ are smaller than $y_{i,j+1}$. Thus since $c$ of the entries above $(i,j+1)$ are smaller than $y_{i,j}$, this means that $i-1-c$ are between $y_{i,j}$ and $y_{i,j+1}$. Therefore, $b\leq y_{i,j+1}-y{i,j}-1-(i-1-c)$ (since not all $y_{i,j+1}-y_{i,j}-1$ entries between $y_{i,j}$ and $y_{i,j+1}$ must be northeast of $(i,j)$). So $y_{i,j+1} - y_{i,j}\geq i+b-c$ as desired.


\begin{example}\label{ex:algorithm}
    Consider the following standard Young tableau where $m=3$ and $n=6$.
$$
\ytableausetup{boxsize=1.25em}
  Y =\raisebox{20pt}{ \ytableausetup{boxsize=1.25em}
    \begin{ytableau}
    1&4&5&11&14&16\\
    2&6&9&*(yellow)15&18&19\\
    *(yellow)3&*(yellow)8&12&*(yellow)17&21&22\\
    *(yellow)7&*(yellow)10&*(yellow)13&*(yellow)20&23&24
    \end{ytableau}}\ , 
     \qquad X=\begin{pmatrix}
    1&1&1&1&1&1\\
    2&3&1&3&2&1\\
    3&4&3&4&3&1\\
    7&3&3&7&3&1
    \end{pmatrix}, \qquad 
    %$$
     %   and then the second array
Z=\begin{pmatrix}
   3&3&3&3&3&3\\
   3&4&2&4&3&2\\
   3&4&3&4&3&1\\
   6&2&2&6&2&0
    \end{pmatrix}
%     \begin{ytableau}
% 1&4&5&11&14&16\\
% 2&6&9&15&18&19\\
% 3&8&12&17&21&22\\
% 7&10&13&20&23&24
%     \end{ytableau}
\label{ex:SYT m=3, n=6}
$$
    (Ignore for now the highlighted cells.) \Cref{prop:SYT-to-dyck} yields arrays $X$  and $Z$, the latter which corresponds to the set of $m+1$ lengthening $m$-Dyck paths in \Cref{fig:dyckalgorithm}, center. Subtracting 1 from every entry in $X$ yields the flows on horizontal edges in $G(6,3)$ in \Cref{fig:dyckalgorithm}, right.

    \begin{figure}[ht]
    \centering
\includegraphics[scale=0.65]{grid_graph_G34_blob_labels_noys_bigl.pdf} 
\qquad
\includegraphics[scale=0.6]{algorithmexample.pdf}
        \qquad
        \includegraphics[scale=0.6]
        {flowbijectionexample.pdf}
       % \includegraphics[scale=0.7]{figures_superset/algorithmexample2.pdf}
        \caption{The grid graph $G(3,4)$ that realizes $\PS^4_3(\aaa,\bb)$ as the flow polytope $\mathcal{F}_{G(3,4)}(\aaa,\bb)$. Set of generalized Dyck paths from \Cref{ex:algorithm} and the corresponding flow on $G(6,3)$.}
        \label{fig:dyckalgorithm}
         \label{fig:gridgraph}
    \end{figure}
\end{example}



\begin{corollary} \label{prop: SYT interpretation KG}
We have that  %\begin{equation} %\label{eq:SYT to sum of KGs}
\(
\SYT(n^{m+1}) = \sum_{{\bf j}} K_{G(n,m)}({\bf j} - {\bf 1}).
\)

\end{corollary}

\Cref{prop: SYT interpretation KG} could be recovered as a particular case by combining results \cite[Theorem 6.6]{Mészáros_Morales_2018} and \cite[Theorem 3.11]{MMS}; however, the bijective proof of the statement is new.

%\begin{proof}[Proof sketch]
%The first result follows by combining \Cref{m-Dyck path interpretation} and \Cref{lemma:SYT-to-dyck}\footnote{Alternatively, it can also be derived combining some general results of flow polytopes \cite[Theorem 6.6]{Mészáros_Morales_2018} and \cite[Theorem 3.11]{MMS}.}. The second result can be derived from tracking ${\bf j}$ in the correspondence between integer flows, tuples of paths in $\mathcal{D}_{m,n}$ and standard tableaux of shape $n^{m+1}$.
%\end{proof}

\begin{remark}
The numbers $K_{G(n,m)}({\bf j}-{\bf 1})$ are also {\em mixed-volumes} and therefore are log-concave in {\em root directions} by the {\em Alexandrov--Fenchel inequalities} e.g. \cite[Proposition 11]{HMMStD}. 
\end{remark}

\begin{remark}
The role that rectangular SYT play in this volume formula and the lattice point formulas below is analogous to the role that shifted SYT of staircase shape play in volume and lattice point formulas for {\em Gelfand--Tsetlin polytopes} \cite{AP,LMStD1}.    
\end{remark}

\begin{example} \label{ex:running example n=m=2}
For $n=m=2$, we have the five SYT in \Cref{fig:SYT3by2} and so for ${\bf j}$=$(4,0)$,$(3,1)$,$(2,2)$, $K_{G(2,2)}({\bf j}-{\bf 1})=2,2,1$, respectively, which match the coefficients in \eqref{eq:voln=m=2}. 
\end{example}


\begin{figure}[ht]
    \centering
    \includegraphics[scale=0.8]{fpsacm2n2.pdf}
%    \[
%\ytableausetup{smalltableaux}
%\ytableaushort{12,34,56} \qquad \ytableaushort{13,{*(yellow)2}4,56}\qquad \ytableaushort{12,35,{*(yellow)4}6}  \qquad \ytableaushort{13,{*(yellow)2}5,{*(yellow)4}6} \qquad \ytableaushort{14,25,{*(yellow)3}6}.
%\]
    \caption{Objects counted by $K_{G(2,2)}({\bf j}-{\bf 1})$ for different ${\bf j}$: certain integer flows on $G(2,2)$ (thick line segments carry two units of flow and with the sink and the edges adjacent to it omitted as they carry no flow), the SYT of shape $(2,2,2)$ with descents highlighted in yellow, 
    %(two tableaux have $(5,6)$ as its last row, two have $(4,6)$ and one has $(3,6)$)
    and tuples of generalized Dyck paths.}
    \label{fig:SYT3by2}
\end{figure}


% \begin{remark}
% The number $K_{G(n,m)}({\bf j}-{\bf 1})$ is also the number of SYT of shape $(m+1) \times n$ where the first  row has values $(1,j_n+2, j_n +j_{n-1}+3,\ldots,j_n+\cdots + j_2+n)$. 
% \end{remark}


% \begin{example}
% For example, consider the case when $m=2$ and $n=3$. Then the $\textbf{j}$'s for which $K_G(j_1-\textup{out}_1, \dots, j_N-\textup{out}_N, 0)>0$ are $(6,0,0)$, $(5,1,0)$, $(5,0,1)$, $(4,2,0)$, $(4,1,1)$, $(4,0,2)$, $(3,3,0)$, $(3,2,1)$, $(3,1,2)$, $(2,4,0)$, $(2,3,1)$, $(2,2,2)$. These correspond to the following Dyck paths:

% Add picture.

% And 
% \begin{align*}
% A_{3,2}(6,0,0)&=A_{3,2}(5,1,0)=A_{3,2}(4,2,0)=A_{3,2}(5,0,1)=A_{3,2}(4,1,1)=5,\\
% A_{3,2}(3,3,0)&=A_{3,2}(3,2,1)=4,\\
% A_{3,2}(2,4,0)&=A_{3,2}(2,3,1)=A_{3,2}(4,0,2)=A_{3,2}(3,1,2)=2,\\
% A_{3,2}(2,2,2)&=1 
% %\quad A_{3,2}(5
% %{(6, 0, 0): 5, (5, 1, 0): 5, (4, 2, 0): 5, (3, 3, 0): 4, (2, 4, 0): 2, (5, 0, 1): 5, (4, 1, 1): 5, (3, 2, 1): 4, (2, 3, 1): 2, (4, 0, 2): 2, (3, 1, 2): 2, (2, 2, 2): 1}
% \end{align*}
% %See \Cref{fig:coeffsKGjs}
% % \begin{figure}
% %     \includegraphics[]{figures_volume/coeffsKGjs32.pdf}
% %     \caption{Table of numbers $A_{3,2}(j_1,j_2,j_3)$.}
% %     \label{fig:coeffsKGjs}
% % \end{figure}
% \end{example}



% \begin{example}
% \[
% 5 \frac{a_1^6}{6!} + 5 \frac{a_1^5}{5!}  + \cdots  2 \frac{a_1^3a_2a_3^2}{3!2!} + \frac{a_1^2a_2^2a_3^2}{2!2!2!}  = \det \begin{bmatrix}
%         \frac{1}{2}{a_1^2} & \frac{1}{3!}{a_1^3} & \frac{1}{4!}a_1^4\\
%        a_1+a_2  & \frac{1}{2}(a_1+a_2)^2 & \frac{1}{3!}(a_1+a_2)^3\\
%          a_1+a_2+a_3 & \frac{1}{2}(a_1+a_2+a_3)^2& \frac{1}{3!}(a_1+a_2+a_3)^3
%     \end{bmatrix}
% \]
% \end{example}

From the rectangular tableaux interpretation above and a result in the next section (\Cref{lem:numtermslidskii}) we get the following result.

\begin{corollary}
The number of different (first) last rows of SYT of shape $n^{m+1}$ is equal to the Fuss--Catalan number $F_{n,m}=\frac{1}{nm+1}\binom{(m+1)n}{n}$. 
\end{corollary}




We give another interpretation of $K_{G(n,m)}({\bf j} - {\bf 1})$ in terms of tableaux which is an analogue of \cite[Corollary 15.4]{AP} for shifted SYT of staircase shape and the associahedron.

\begin{definition}
    Given a composition $\mathbf{j}=(j_1,\ldots,j_n)$ of $mn$ that dominates $m\bf{1}$ and an index $1\leq i \leq n$, let $\Lambda_\mathbf{j}^i$ be the set of partitions $\lambda^i=(\lambda^i_1, \lambda^i_2, \ldots)$ of $\sum_{k=1}^i j_i$ such that $\lambda^i_k=m$ for all $k\leq i$, and $\lambda^i_k \leq m$ for all other parts.
\end{definition}

\begin{lemma}\label{lem:KGproductSYT}
    We have that $K_{G(n,m)}(\mathbf{j}-\mathbf{1})=\sum_{(\lambda^1, \ldots, \lambda^n)\in \Lambda^1 \times \cdots \times \Lambda^n} \prod_{k=1}^n \textup{SYT}(\lambda^k/\lambda^{k-1})$ where $\lambda^0$ is empty.
\end{lemma}

\begin{proof}[Proof sketch]
By \Cref{prop:SYT-to-dyck} and taking the transpose, $K_{G(n,m)}({\bf j} - {\bf 1})$ counts  SYT of shape $(m+1)^n$ where the $(m+1)th$ column has values $(j_1+1,j_1+j_2+2,\ldots,j_1+\cdots +j_{n-1}+n-1,n(m+1))$. By removing this fixed column and reindexing the resulting tableaux to have entries in $[nm]$, this is also the number of  SYT of shape $n \times m$ where the entries in the first $k$ rows are in $\{1,\ldots,\sum_{i=1}^k j_i\}$. Each such tableau can be decomposed into skew tableaux having entries in $[\sum_{k=1}^i j_i]\setminus [\sum_{k=1}^{i-1} j_i]$ giving the desired formula.
\end{proof}

\begin{example}
Let $n=m=3$, and $\mathbf{j}=(5,3,1)$. Then $\Lambda^1_\mathbf{j}=\{(3,2),(3,1,1)\}$, $\Lambda^2_\mathbf{j}=\{(3,3,2)\}$ and $\Lambda^3_\mathbf{j}=\{(3,3,3)\}$. Therefore, we have that $K_{G(n,m)}(\mathbf{j}-\mathbf{1})$ is
\[
\textup{SYT}\bigl(\raisebox{-3pt}{\text{\tiny $\yng(3,2)$}}\bigr)\cdot \textup{SYT}\bigl(\raisebox{-3pt}{\text{\tiny $ \young(::\hfil,\hfil\hfil) $}}\bigr) \cdot \textup{SYT}({\text{\tiny $\yng(1)$}}) +\textup{SYT}\Bigl(\raisebox{-6pt}{\text{\tiny $ \yng(3,1,1)$}}\Bigr)\cdot \textup{SYT}(\raisebox{-3pt}{\text{\tiny $ \yng(2,1)$}}) \cdot  \textup{SYT}\left({\text{\tiny $ \yng(1)$}}\right)=5\cdot 3 \cdot 1+ 6\cdot 2 \cdot 1 = 27.\]
\end{example}

We finish the section with a determinant formula for the generating polynomial of the numbers $K_{G(n,m)}({\bf j}-\mathbf{1})$. This is an analogue of Postnikov's result for the number of shifted staircase SYT with prescribed diagonal \cite[Theorem 15.1]{AP}.


\begin{corollary} \label{cor:det of gen poly Kgs}
For positive integers $n$ and $m$ and nonnegative integers $a_i\geq 0$ we have that 
%the numbers $K_{G(n,m)}({\bf j}-\mathbf{1})$ 
%of SYT of shape $n\times (m+1)$ where the $(m+1)$th column has values $(j_1+1,j_1+j_2+2,\ldots,j_1+\cdots + j_{n-1}+n-1,n(m+1))$ 
%satisfy
\[
\sum_{{\bf j}} K_{G(n,m)}({\bf j}-\mathbf{1})   \frac{a_1^{j_1}}{j_1!}\cdots \frac{a_n^{j_n}}{j_n!}  \,=\, \det \left[ \frac{(a_1+\cdots + a_{i})^{j-i+m}}{(j-i+m)!} \right]_{i,j=1}^n.
\]
\end{corollary}

\begin{proof}
This follows from \Cref{thm:lidskii vol for PSnm} and the determinant formula for the volume of $\PS_n^m(\aaa)$ derived from \eqref{eq:kreweras number lp}.
%and the interpretation for $A_{n,m}({\bf j})=K_{G(n,m)}({\bf j}-{\bf 1})$ in \Cref{eq:SYT to sum of KGs}.
\end{proof}


\begin{example}
Continuing \Cref{ex:running ex m=n=2}: 
 \(
2\frac{a_1^4}{4!} + 2\frac{a_1^3a_2}{3!1!} + 1\frac{a_1^2a_2^2}{2!2!} = \det \begin{bmatrix}
\frac{1}{2}{a_1^2} & \frac{1}{3!}{a_1^3}\\
a_1+a_2  & \frac{1}{2}(a_1+a_2)^2
\end{bmatrix}.
\)


% \[
% 5 \frac{a_1^6}{6!} + 5 \frac{a_1^5}{5!}  + \cdots  2 \frac{a_1^3a_2a_3^2}{3!2!} + \frac{a_1^2a_2^2a_3^2}{2!2!2!}  = \det \begin{bmatrix}
%         \frac{1}{2}{a_1^2} & \frac{1}{3!}{a_1^3} & \frac{1}{4!}a_1^4\\
%        a_1+a_2  & \frac{1}{2}(a_1+a_2)^2 & \frac{1}{3!}(a_1+a_2)^3\\
%          a_1+a_2+a_3 & \frac{1}{2}(a_1+a_2+a_3)^2& \frac{1}{3!}(a_1+a_2+a_3)^3
%     \end{bmatrix}
% \]
\end{example}


\subsection{About combinatorial proofs of the volume formula} \label{sec: combinatorial proof volume formulas}

We now use the different interpretations of $K_{G(n,m)}(\mathbf{j}-\mathbf{1})$ to give a combinatorial proof of equations~\eqref{eq:volume formula case 1} and~\eqref{eq:lidskii vol for PSnm} for $\mathbf{a}=\mathbf{1}$ and $n=2$, i.e., we will show that \begin{equation}\label{eq:combinatorialvolume}
\SYT(n^m) \cdot \prod_{i = 1}^m i!(n+i)^{n-m-1+i}=\sum_{{\bf j}} \binom{mn}{j_1,\ldots,j_n}  K_{G(n,m)}({\bf j}-{\bf 1}),\end{equation}
where the sum is over compositions $\mathbf{j}$ of $mn$ that dominate $m\bf{1}$. 

\begin{lemma}\label{lem:numtermslidskii}
For $\mathbf{a}=(1,\ldots,1)$  the number of terms of the Lidskii formula for $\mathcal{F}_{G(n,m)}$ equals the Fuss--Catalan number $F_{n,m}=\frac{1}{nm+1}\binom{(m+1)n}{n}$.
\end{lemma}

\begin{proof}
Such $\textbf{j}$'s can be thought of as the lengths of the horizontal segments in $m$-Dyck paths (starting from the top right corner). It is known that such $m$-Dyck paths are counted by Fuss--Catalan numbers \cite{stump2018catalandfuss}.
\end{proof}


\begin{lemma}\label{lem:productrewritten}
   We have that $ \prod_{k=1}^m k!(2+k)^{1-m+k} = \sum_{i=0}^m (i+1)\binom{m}{i}.$ 
\end{lemma}

\begin{proof}[Proof sketch]
    One can show that $ \prod_{k=1}^m k!(2+k)^{1-m+k} = (m+2)2^{m-1}$ by induction on $m$. Note that $(m+2)2^{m-1}$ is equal to the number of parts among all compositions of $m+1$ (see, e.g., A001792 in the OEIS). We can partition compositions by their number of parts, say $i$. The number of parts in all compositions with $i$ parts is $i\binom{m}{i-1}$. So $\prod_{k=1}^m k!(2+k)^{1-m+k} = \sum_{i=1}^{m+1}i\binom{m}{i-1}$, and thus the result holds.  
\end{proof}

%\ar{Should we attempt higher values of $n$, here is the previous statement in more general form:
%\begin{lemma}
 %   $$\prod_{k=1}^m k! (n+k)^{n-m-1+k} = \prod_{l=1}^{n-1} (m+l+1)^l(l+1)^{m-l}$$
%\end{lemma}}

\begin{lemma}\label{lem:distributionofpaths}
    We have that $K_{G(2,m)}(2m-i-1, i-1)=\frac{i+1}{m+1}\binom{2m-i}{m}$ for $0\leq i \leq m$. 
\end{lemma}

\begin{proof}[Proof sketch]
The (multi-parameter) Fuss--Catalan numbers $A_{m-i}(2,i+1):=\frac{i+1}{m+1}\binom{2m-i}{m}$ are known to satisfy the recurrence $A_{m-i}(2,i+1)=A_{m-i}(2,i)+A_{m-i-1}(2,i+1)+\ldots+A_0(2,m)$, i.e., the recurrence given in \Cref{lem:recurrenceKG}.
\end{proof}

With \Cref{lem:distributionofpaths}, it is easy to directly check that equation~\eqref{eq:combinatorialvolume} holds when $n=2$. We now give a combinatorial interpretation for it.

\begin{theorem}
The volume of $PS_2^m(1,1)$ is 
$\textup{SYT}(2^m) \prod_{k=1}^m k!(2+k)^{1-m+k}$ where $\textup{SYT}(2^m)=C_m$, the $m$th Catalan number.
\end{theorem}

\begin{proof}

 Let us understand the left-hand side of equation~\eqref{eq:combinatorialvolume} first. By \Cref{prop:SYT-to-dyck}, we know that $\textup{SYT}(2^m)=\#\mathcal{D}_{m-1,2}$. For each path in each set of paths, elongate each horizontal step by one (including horizontal steps of length 0). Let $\{P'_0, P'_1, \ldots, P'_{m-1}\}$ be one of the resulting sets of paths. Then we have that $P'_i$ is an $m$-Dyck path that is $(i+1)$-stepping. Note that adding an $m$-Dyck path $P^*$ to this set such that $P^*$ is above or equal to $P'_0$ everywhere would yield a set of paths that is in $\mathcal{D}_{m,2}$. From \Cref{lem:productrewritten}, we know that $\prod_{k=1}^m k!(2+k)^{1-m+k} = \sum_{i=0}^m (i+1)\binom{m}{i}$. We can think of the right-hand side as counting the number of elements in compositions of $m+1$, and splitting this according to the number of parts. Now associate the number of parts to the path $P''$ with horizontal steps $2m-i$ and $i$ (from the top right corner), and add $(i+1)\binom{m}{i}$ copies of $P''$ to every set $\{P'_0, P'_1, \ldots, P'_{m-1}\}$ above such that this new path is above or equal to $P'_0$. For the sets where it is not possible to add $P''$, distribute those copies of $P''$ evenly among the $K_{G(2,m)}(2m-i-1,i-1)$ sets where it is possible to add it. (Note this is by \Cref{m-Dyck path interpretation}.) We now count how many copies of each set of paths in $\mathcal{D}_{m,2}$ we have obtained by doing this process. For a set of paths $\{Q_0, Q_1, \ldots, Q_m\}\in \mathcal{D}_{m,2}$ where $Q_0$ has horizontal steps of length $2m-i$ and $i$ for some $0\leq i\leq m$, this set will be counted $(i+1)\cdot\binom{m}{i}\cdot{C_m}/{K_{G(2,m)}(2m-i-1,i-1)}$. By \Cref{lem:distributionofpaths}, this yields $\binom{2m-i}{i}$ just as in the right-hand side.
\end{proof}

\begin{example}
    Let $n=2$, $m=3$. The left-hand side of equation~\eqref{eq:combinatorialvolume} is $C_3 \prod_{k=1}^3 k!(2+k)^{1-3+k}$ where $C_3$ corresponds to the sets of paths in $\mathcal{D}_{2,2}$ shown in \Cref{fig:SYT3by2}. We now elongate each horizontal step by one to obtain the following sets of paths in the top of \Cref{fig:n2example1}. 

    \begin{figure}[ht]
\centering
    \includegraphics[width=0.95\textwidth]{examplen2dyckpaths.pdf}

    \vspace{0.3cm}
    \includegraphics[width=0.75\textwidth]{examplen2dyckpaths2.pdf}



%  \begin{center}
%      \begin{ytableau}
%        1 & 4 \\
%        2 & 5 \\
%        3 & 6 \\
%    \end{ytableau} \quad \quad \quad \quad\begin{ytableau}
%        1 & 3 \\
%        2 & 5 \\
%        4 & 6 \\
%    \end{ytableau}\quad \quad \quad \quad\begin{ytableau}
%        1 & 3 \\
%        2 & 4 \\
%        5 & 6 \\
%    \end{ytableau} \quad \quad \quad \quad\begin{ytableau}
%        1 & 2 \\
%        3 & 5 \\
%        4 & 6 \\
%    \end{ytableau}\quad \quad \quad \quad\begin{ytableau}
%        1 & 2 \\
%        3 & 4 \\
%        5 & 6 \\
%    \end{ytableau}
%  \end{center}
  \caption{Top: Sets in $\mathcal{D}_{2,2}$ where each horizontal step is elongated by 1.  Bottom: Dyck paths with horizontal steps $7-i$ and $i-1$ for $1\leq i \leq 4$ associated to compositions.}
      \label{fig:n2example1}
\end{figure}

Moreover, $\prod_{k=1}^3 k!(2+k)^{1-3+k}=20$ counts the number of elements in the compositions of 4, namely one composition with one element $(4)$, three compositions with two elements $(3,1)$, $(1,3)$, $(2,2)$, three with three elements $(2,1,1), (1,2,1), (1,1,2)$, and one with four $(1,1,1,1)$. To each of these  composition, we associate the Dyck path with horizontal steps of lengths $7-i$ and $i-1$ where $i$ is the number of elements in that composition as in the bottom of \Cref{fig:n2example1}. 

%    \begin{figure}[ht]
%  \begin{center}
    %\includegraphics[width=0.85\textwidth]{figures_superset/examplen2dyckpaths2.pdf}
    %\end{center}
    %\caption{Dyck paths with horizontal steps of lengths $7-i$ and $i-1$ for $1\leq i \leq 4$ associated to compositions.}
   %   \label{fig:n2example3}
%\end{figure}
We add those paths (with multipliers) to the sets of paths at the top of \Cref{fig:n2example1} if doing so yields a set of paths in $\mathcal{D}_{3,2}$. For example, the first path in the bottom of \Cref{fig:n2example1} can be added to each set in the top, and since there is one composition with one element, we count the resulting sets of paths one times each. The third path in the bottom can only be added to the third, fourth and fifth sets in the top. Since there are three compositions with three elements, we want the total contribution to be $5\cdot3\cdot3$, but as we only add this path to three sets, we count the resulting sets 15 times each. %Finally, the fourth path in \Cref{fig:n2example3} can only be added to the last set of \Cref{fig:n2example1}. Since there is one composition with four elements, we want the total contribution to be $5\cdot 1 \cdot 4$, but as we only add this path to one set, we count the resulting set 20 times.

      On the right-hand side, possible $\mathbf{j}$'s need to be such that $j_1\geq 3$ and $j_1+j_2=6$, namely $(3,3)$, $(4,2)$, $(5,1)$ and $(6,0)$. Recall that $K_G(\mathbf{j}-\mathbf{1})$ counts the number of sets in $\{P_0, P_1, P_2, P_3\}\in \mathcal{D}_{3,2}$ where $P_0$ has horizontal steps of lengths $j_1$ and $j_2$. Such sets are counted with multiplicity $\binom{6}{j_1,j_2}$, namely $20$, $15$, $6$ and $1$ for our different $\mathbf{j}$'s.
      %counts the number of integer flows in $\mathcal{F}_{G(n,m)}(\mathbf{j}-\mathbf{1})$, and where each flow is associated to a set of 3 non-crossing lengthening $3$-Dyck paths of \Cref{fig:n2example2}.  
%    \begin{figure}
%  \begin{center}
    %\includegraphics[width=0.24\textwidth]{figures_superset/exampleKG33.pdf}
    %\includegraphics[width=0.24\textwidth]{figures_superset/exampleKG42.pdf}
    %\includegraphics[width=0.24\textwidth]{figures_superset/exampleKG51.pdf}
    %\includegraphics[width=0.24\textwidth]{figures_superset/exampleKG60.pdf}
    %\end{center}
    %\caption{Dyck paths corresponding to the $\mathbf{j}$'s.}
    %  \label{fig:n2example2}
%\end{figure}
\end{example}

% \begin{conjecture}
%     To prove the volume formula for $n=3$.
% \end{conjecture}

% \begin{proof}
%     I think the same ideas hold for $n=3$, but formulas get nastier. I claim that the number of sets of $m-1$ Dyck paths compatible with the path $(j_1,j_2,3m-j_1-j_2)$ (where $j_1\geq m$ and $j_1+j_2\geq 2m$) is $$A(m,j_1,j_2):=(3m+1-j_1-j_2)\left(\frac{2m+1-j_1}{(m+1)^2}\binom{j_1}{m}\binom{j_1+j_2-m}{m} + \frac{1}{m}\binom{j_1}{m+2}\binom{j_1+j_2-m-2}{m-1}\right).$$ To show that this is correct, one would have to show that the recursion $$A(m,j_1,j_2)=\sum_{k_1=m-1}^{\min\{j_1-1,3m-3\}} \sum_{k_2=\max\{2m-2-k_1,0\}}^{\min\{j_1+j_2-2-k_1,3m-3-k_1\}}  A(m-1,k_1,k_2)$$ holds. (Maybe easier to show equivalence to another recursion that would also need to be proven: $$A(m,j_1,j_2)=A(m,j_1,j_2-1)+\sum_{k_1=m-1}^{j_1-1} A(m-1,k_1, j_1+j_2-k_1-2).$$ The other missing ingredient for the proof would be to show that $$(m+2)2^{m-1}(m+3)^23^{m-2}=\sum_{k_1=m}^{3m}\sum_{k_2=\max\{2m-k_1,0\}}^{3m-k_1} D(m,k_1,k_2)$$ or equivalently that $$\prod_{k=1}^m k!(k+3)^{k-m+2}=\sum_{k_1=m}^{3m}\sum_{k_2=\max\{2m-k_1,0\}}^{3m-k_1} D(m,k_1,k_2)$$ where $$D(m,j_1,j_2)=\frac{(m+1)!(3m+1-j_1-j_2)}{(3m-j_1-j_2)!(j_1+j_2-2m)!}\left(\frac{(m+2)(2m+1-j_1)}{m+1}\binom{j_1+j_2-m}{j_2}+(j_1+j_2-2m)\binom{j_1+j_2-m-2}{j_2}\right).$$ With those two facts proven (I have checked them computationally, but didn't have time to actually prove them), the proof would follow the same outline as for $n=2$.
% \end{proof}
    
% \end{example}


With the second interpretation of $K_{G(n,m)}(\mathbf{j}-\mathbf{1})$ in \Cref{lem:KGproductSYT}, it is easy to directly prove the Lidskii formula when $n=2$.

\begin{theorem}
$$C_m \prod_{k=1}^m k!(2+k)^{1-m+k}=\sum_{\mathbf{j}} \binom{2m}{j_1,j_2}K_G(\mathbf{j}-\mathbf{1}).$$
\end{theorem}

\begin{proof}
    Consider $\mathbf{j}=(2m-j_2,j_2)$ for some $0\leq j_2 \leq m$. Then $\Lambda^1_{\mathbf{j}}=\{(m,m-j_2)\}$ and $\lambda^2_{\mathbf{j}}=\{(m,m)\}$. Thus \begin{align*}
        K_{G(n,m)}(\mathbf{j}-\mathbf{1})&=\textup{SYT}(m,m-j_2)\times \textup{SYT}((m,m)/(m,m-j_2))
        % &= \textup{SYT}(m,m-j_2)\times \textup{SYT}(j_2)\\
        % &=\frac{(2m-j_2)!}{\frac{(m+1)!}{j_2+1}(m-j_2)!} \times \frac{j_2!}{j_2!}\\
        =\frac{j_2+1}{m+1}\binom{2m-j_2}{m}
    \end{align*}
    by using the {\em hook length formula} \cite[Corollary 7.21.6]{EC2}. Therefore, we have that 
\begin{align*}
    \frac{1}{C_m} &\sum_{j_2=0}^m \binom{2m}{j_1,j_2}K_G(2m-j_2-1,j_2-1)=\frac{1}{C_m} \sum_{\mathbf{j}} \binom{2m}{j_1,j_2} \frac{j_2+1}{m+1}\binom{2m-j_2}{m}\\
    &=\sum_{j_2=0}^m(j_2+1)\binom{m}{j_2}=\prod_{k=1}^m k!(2+k)^{1-m+k}
\end{align*}
where the last line follows by \Cref{lem:productrewritten}.
\end{proof}



\section{Lattice point formulas in terms of tableaux}


We give lattice point formulas for $\PS_n^m(\aaa)$ and $\PS_n^m(\aaa,\bb)$. Although there are Lidskii formulas for lattice points of flow polytopes, the internal vertices with zero flow of $G(n,m)$, can make these formulas be alternating and also they do not cover net flows like $(\aaa,{\bf 0},-\bb,\ldots)$. Instead, we use Stanley's theory of {\em marked order polytopes} (see \cite[Section 3]{Pitman_Stanley_1999},\cite{LMStD1}), since $\PS_n^m(\aaa)$ and $\PS_n^m(\aaa,\bb)$ are marked order polytopes of the poset ${\bf n}\times {\bf (m+1)}$ with last  $n$-chain marked, and ${\bf n}\times {\bf (m+2)}$ with first and last $n$-chains marked, respectively.  
% \textcolor{blue}{The number of terms of the volume formula for the skew case for $m=1$ is the sequence $2, 6, 21, 80, 322, 1348, 5814$ which is \cite[\url{https://oeis.org/A121988}{A121988}]{oeis}}.

% \begin{theorem}
% \[
% \#(PS_n^1({\bf a} \cap \mathbb{Z}^n) = \sum_{{\bf j}} \bbinom{a_1+1}{j_1}\binom{a_2}{j_2}\cdots \binom{a_n}{j_n},
% \]
% where the sum is over compositions of $n$ ${\bf j}=(j_1,\ldots,j_n)$ such that $\sum_{i=1}^k j_i \geq k$.
% \end{theorem}

% \begin{theorem}
%    \begin{equation} \label{eq:Ehrhart formula from order cones}
%   \#(PS_n^m({\bf a}) \cap \mathbb{Z}^{nm}) = \sum_{{\bf j}} \sum_{T \in \mathcal{L}(Q_{n,m+1}), j_k = h_k-h_{k-1}} \prod_{i=1}^n \bbinom{a_i -d_i(T)+1}{j_i},
%   \end{equation}
%   where the sum is over compositions ${\bf j}$ of $mn$ such that $\sum_{i=1}^k j_i \geq km$ for $k=1,\ldots,n-1$.
% \end{theorem}

% \begin{proof}
% Let $Q_{n,m+1} = {\bf n} \times {\bf (m+1)}$, the product of an $n$-chain and an $(m+1)$-chain with elements:
% \[
% Q_{n,m+1}:=\{ \alpha_{i,1} < \cdots < \alpha_{i,n}, i=1,\ldots,m+1, \alpha_{1,j} < \cdots < \alpha_{m,j}, j=1,\ldots,n\}.
% \]
% Let $C$ be the distinguished chain $t_1<\cdots <t_n$ with $t_j = \alpha_{m+1,j}$. Then $\mathcal{C}_C(Q_{n,m+1},{\bf a})$ is integrally equivalent to $PS_n^m({\bf a})$.

% By \cite[Theorem 5]{Pitman_Stanley_1999}, we have that 
%  \[
%   \#(PS_n^1({\bf a}) \cap \mathbb{Z}^{nm}) = \sum_{T} \prod_{j=1}^n \bbinom{a_j -d_j(T)+1}{h_j-h_{j-1}-1},
%   \] 
%   where the sum is over linear extensions $T$ of $Q_{n,m+1}$, $h_j$ is the position of the element $t_j=\alpha_{m+1,j}$ in $T$ and $d_i$ is the number of descents on the segment of the word $w(T)$ between positions $h_{i-1}$ and $h_i$. 

%   Consider a linear extension $T=a_1\cdots a_{n(m+1)}$ of $Q_{n,m+1}$. If $a_{h_k}= \alpha_{m+1,k}$, i.e. $h_k$ is the position of $t_k=\alpha_{m+1,k}$ in $\pi$, then $1 \leq h_1 < \cdots < h_n = (m+1)n$ and $h_k\geq (m+1)k$. If wet let $j_k=h_k-h_{k-1}$, with $h_0=0$ then ${\bf j}=(j_1,\ldots,j_n)$ are exactly the compositions appearing on the sum on the RHS of \eqref{eq:Ehrhart formula from order cones}.
%   \ahm{Can we see the descents from the $K_{G(n,m)}({\bf j}-{\bf out})$?}
% \end{proof}






% \begin{example}
% For $n=2$ and $m=2$, consider the poset $Q_{2,3}$ with the labeling on \Cref{fig:PS to poset} and distinguished chain $C=5<6$. This poset has the following five linear extensions with elements of $C$ in {\bf bold}
% and descents underlined: 
% \[
% 1234{\bf 5}{\bf 6}, \quad 1\underline{3}24{\bf 5}{\bf 6}, \quad 123\underline{{\bf 5}}4{\bf 6},\quad 1\underline{3}2\underline{{\bf 5}}4{\bf 6}, \quad 13\underline{{\bf 5}}24{\bf 6}
% \]
% These linear extensions give rise to the following formula
% \[
%  \#(PS_2^2(a_1,a_2) \cap \mathbb{Z}^{4}) = \bbinom{a_1+1}{4} + \bbinom{a_1}{4} + \bbinom{a_1+1}{3}\bbinom{a_2}{1} +  \bbinom{a_1}{3}\bbinom{a_2}{1} + \bbinom{a_1+1}{2}\bbinom{a_2}{2}.
% \]
% We compare this formula with the Lidskii formulas for $PS_2^2({\bf a})$.
% \begin{align*}
%    \#(PS_2^2(a_1,a_2) \cap \mathbb{Z}^{4}) &= (a_1 +1)(a_2 +1)+(a_1 +1) \binom{a_2+1}{2} + \binom{a_1+1}{2} + 3\binom{a_1+1}{2}(a_2+1) + \\ 
%    &\binom{a_1+1}{2}\binom{a_2+1}{2}+ 3\binom{a_1+1}{3} + 2\binom{a_1+1}{3}(a_2+1) + 2\binom{a_1+1}{4}\\
%    &= 2\bbinom{a_1+1}{4} + 2\bbinom{a_1+1}{3}a_2 + \bbinom{a_1+1}{2}\bbinom{a_2}{2} - \bbinom{a_1+1}{2}a_2-\bbinom{a_1+1}{3}.
% \end{align*}
% \end{example}

% \begin{figure}
% \includegraphics[]{figures/PS2posetQnm.pdf}
%     \caption{Illustration of the Pitman--Stanley polytope coming from a poset $Q_{n,m+1}$.}
%     \label{fig:PS to poset}
% \end{figure}

We state the formulas in terms of rectangular SYT. Given a SYT $T$ of shape $\lambda$, a {\em (natural) descent} of $T$ is a value $i$ of $T$ such that $i+1$ occurs strictly above $i$ in $T$ \cite{MO}. Note that there is a more common notion of descents of a tableau
%: a value $i$ such that $i+1$ occurs strictly below $i$ in $T$ 
\cite[Section 7.19]{EC2}.

\subsection{Straight shape case}

Given a standard Young tableau  $T$ of shape $n^{m+1}$  with last row $c_1<c_2<\cdots<c_n=(m+1)n$. For $i=1,\ldots,n$, let $d_i(T)$ be the number of descents of $T$ between and including $c_{i-1}$ up to $c_i$ (where $c_0=0$). The following result is an application of a general result of marked order polytopes \cite[Theorem 5]{Pitman_Stanley_1999}, and it implies the volume formula \eqref{eq:lidskii vol for PSnm}.

\begin{theorem} \label{thm:Ehrhart formula from order cones tableaux version}
   \begin{equation} \label{eq:Ehrhart formula from order cones tableaux version}
  \#(PS_n^m({\bf a}) \cap \mathbb{Z}^{nm}) =  \sum_{T \in SYT(n^{m+1})} \prod_{i=1}^n \bbinom{a_i -d_i(T)+1}{c_i-c_{i-1}-1},
  \end{equation}
  where $c_1<c_2<\cdots<c_n=(m+1)n$ is the last row of $T$ and $d_i(T)$ are as defined above.
\end{theorem}




\begin{example}
For $n=2$ and $m=2$, consider the tableaux of shape $(2,2,2)$ in \Cref{fig:SYT3by2}
with descents sets $\varnothing, \{2\}, \{4\}, \{2,4\},\{3\}$, respectively. From the last row of each tableau, the associated compositions are $(4,0), (4,0),(3,1),(3,1),(2,2)$, and descent statistics $(d_1,d_2)$ are $(0,0), (1,0),(0,1), (1,1), (0,1)$. This gives rise to the formula for $\#(PS_2^2(a_1,a_2) \cap \mathbb{Z}^{4})$ being
\begin{multline*}
 %\#(PS_2^2(a_1,a_2) \cap \mathbb{Z}^{4}) 
  \bbinom{a_1+1}{4} + \bbinom{a_1}{4} + \bbinom{a_1+1}{3}\bbinom{a_2}{1} +  \bbinom{a_1}{3}\bbinom{a_2}{1} + \bbinom{a_1+1}{2}\bbinom{a_2}{2}.
\end{multline*}
\end{example}


\begin{example}
Consider the SYT $T$ in \eqref{ex:SYT m=3, n=6} where $m=3$ and $n=6$ and  whose descents are highlighted in yellow.
From the last row of $T$, the associated composition is ${\bf j}=(6,2,2,6,2,0)$ and $T$ has descents $\{3,{\bf 7},8,{\bf 10},{\bf 13},15,17,{\bf 20}\}$ with $(d_1,d_2,d_3,d_4,d_5,d_6)=(1,2,1,3,1,0)$. The contribution of this tableau in \eqref{eq:Ehrhart formula from order cones tableaux version} is 
\(
\bbinom{a_1-1+1}{6} \bbinom{a_2-2+1}{2}\bbinom{a_3-1+1}{2}\bbinom{a_4-3+1}{6}\bbinom{a_5-1+1}{2}
\).
\end{example}


% \begin{figure}[h!]
% \includegraphics[]{figures/PS2posetQnm.pdf}
%     \caption{Illustration of the Pitman--Stanley polytope coming from a poset $Q_{n,m+1}$.}
%     \label{fig:PS to poset}
% \end{figure}

The Ehrhart polynomial $\PS^1_n(t\aaa)$  is known to be positive in $t$ \cite[Corollary 10]{Pitman_Stanley_1999} which can be seen from the case $m=1$ of \eqref{eq:Ehrhart formula from order cones tableaux version} since $d_i \leq 1$. For general $m$, we don't have this restriction so our formula does not imply positivity for  $\PS^m_n(t\aaa)$. However, calculations up to $m,n \leq 8$ suggest positivity for the latter.


\begin{conjecture}
As a polynomial in $a_i$, we have that $\#(\PS_n^m(\aaa)\cap Z^{mn})$ is in $\mathbb{N}[{\bf a}]$. In particular, $\PS_n^m({\bf a})$ is Ehrhart positive.    
% For each fixed ${\bf j}$ the inner sum on the RHS of \eqref{eq:Ehrhart formula from order cones} is a polynomial in $\mathbb{N}[{\bf a}]$.    
\end{conjecture}



\subsection{Skew shape case}

Given $\aaa$ and $\bb$ in $\mathbb{Z}^n_{\geq 0}$, let $\alpha_i=\sum_{j=1}^i a_j$ and $\beta_i = \sum_{j=1}^i b_j$. Let $\SYT_{\aaa,\bb}(n^{m+2})$ be the set of SYT of shape $n^{m+2}$ such that the first and last row have the same relative order as the numbers $\alpha_1,\ldots,\alpha_n$ and $\beta_1,\ldots,\beta_n$. We denote this relative order by $\pi(T)=(\pi_1,\ldots,\pi_{2n})$. Note that in the generic case where $a_i>0$ and $b_i>0$, then there are Catalan ($\SYT(n,n)=C_n$) many different sets $\SYT_{\aaa,\bb}(n^{m+2})$.

Consider a SYT $T$ of shape $n^{m+2}$ with entries $1=c_1<c_2<\cdots<c_{2n}=n(m+2)$ in the first and last row of $T$. For $i=1,\ldots,2n$, let $d_i(T)$ be the number of descents of $T$ between and including $c_{i-1}$ up to $c_i$ (where $c_0=0$). The following result was sketched for $m=1$ in the arxiv version of \cite{Pitman_Stanley_1999}.

\begin{theorem} \label{thm:Ehrhart formula skew shape}
 %  \begin{equation} \label{eq:Ehrhart formula skew shape}
 \( \#(PS_n^m({\bf a},{\bf b}) \cap \mathbb{Z}^{nm}) =  \sum_{T \in \SYT_{\aaa,\bb}(n^{m+2})} \prod_{i=1}^{2n} \bbinom{\pi_i-\pi_{i-1} -d_i(T)+1}{c_i-c_{i-1}-1},
 \)
%  \end{equation}
  where $1=c_1<c_2<\cdots<c_{2n}=n(m+2)$ are the entries in the first and last row of $T$, $d_i(T)$  are as defined above, $(\pi_i)$ is the relative order of $\alpha_i$s and $\beta_i$s from $T$ where $c_0=\pi_0=0$.
\end{theorem}

From the lattice point formula above, we can extract a volume formula for $\PS_n^m(\aaa,\bb)$.

\begin{corollary} \label{cor:eq:vol formula skew shape}
\(
   %\label{eq:vol formula skew shape}
 \vol PS_n^m({\bf a},{\bf b})  =  \sum_{T}\binom{mn}{c_1-c_0-1,\ldots,c_{2n}-c_{2n-1}-1} \prod_{i=1}^{2n} (\pi_i-\pi_{i-1})^{c_i-c_{i-1}-1}\),
  where the sum is over $T$ in $\SYT_{\aaa,\bb}(n^{m+2})$; $c_i$, $d_i(T)$, and $(\pi_i)$ are the same as in \Cref{thm:Ehrhart formula skew shape}.
\end{corollary}


\begin{example}[{\cite[pp. 25-26]{Pitman_Stanley_1999}}]
For $n=2$ and $m=1$, we have five SYT of shape $2^3$ in \Cref{fig:SYT3by2}.
From the order of the entries on the first and last row, the first four tableaux correspond to the ordering $\beta_1<\beta_2<\alpha_1<\alpha_2$ and the last one to the ordering $\beta_1<\alpha_1<\beta_2<\alpha_2$. This gives
%The descents of the tableaux are $\varnothing$, $\{4\}, \{2\},\{2,4\}$ and $\{3\}$. This gives
\[
 \#(PS_2^1({\bf a},{\bf b}) \cap \mathbb{Z}^{2}) = \begin{cases} A &\text{ if } \alpha_1>\beta_2\\
 B &\text{ if } \alpha_1 \leq \beta_2 
 \end{cases}, \quad  \vol PS_2^1({\bf a},{\bf b})  = \begin{cases} A' &\text{ if } \alpha_1>\beta_2\\
 B' &\text{ if } \alpha_1 \leq \beta_2 
 \end{cases},
\]
where $A = \bbinom{\alpha_1-\beta_2+1}{2} + \bbinom{\alpha_1-\beta_2+1}{1}\bbinom{\alpha_2-\alpha_1}{1} + \bbinom{\beta_2-\beta_1}{1}\bbinom{\alpha_1-\beta_2+1}{1} + \bbinom{\beta_2-\beta_1}{1}\bbinom{\alpha_2-\alpha_1}{1}$, $
 B = \bbinom{\alpha_1-\beta_1+1}{1}\bbinom{\alpha_2-\beta_2+1}{1}$,
$A' = \binom{2}{2} (\alpha_1-\beta_2)^2  + \binom{2}{1,1} (\alpha_1-\beta_2)(\alpha_2-\alpha_1) + \binom{2}{1,1} (\beta_2-\beta_1)(\alpha_1-\beta_2) + \binom{2}{1,1}(\beta_2-\beta_1)(\alpha_2-\alpha_1)$, and 
$B' = \binom{2}{1,1}(\alpha_1-\beta_1)(\alpha_2-\beta_2)$.
% {\small 
% \begin{align*}
% A &= \bbinom{\alpha_1-\beta_2+1}{2} + \bbinom{\alpha_1-\beta_2+1}{1}\bbinom{\alpha_2-\alpha_1}{1} + \bbinom{\beta_2-\beta_1}{1}\bbinom{\alpha_1-\beta_2+1}{1} + \bbinom{\beta_2-\beta_1}{1}\bbinom{\alpha_2-\alpha_1}{1}\\
% B &= \bbinom{\alpha_1-\beta_1+1}{1}\bbinom{\alpha_2-\beta_2+1}{1},\\
% A' &= \binom{2}{2} (\alpha_1-\beta_2)^2  + \binom{2}{1,1} (\alpha_1-\beta_2)(\alpha_2-\alpha_1) + \binom{2}{1,1} (\beta_2-\beta_1)(\alpha_1-\beta_2) + \binom{2}{1,1}(\beta_2-\beta_1)(\alpha_2-\alpha_1)\\
% B' &= \binom{2}{1,1}(\alpha_1-\beta_1)(\alpha_2-\beta_2).
% \end{align*}
% }

\end{example}

% \begin{example}
% For $n=3$ and $m=1$ there are $42$ tableaux of shape $3^3$. From the relative order of the entries in the first and last row, they break into five groups of sizes $21,12,4,4,1$, respectively. 

% % with representatives:
% % \begin{align*}
% % \ytableaushort{abc,def}:& \quad \ytableaushort{134,268,579}, \ldots  & 
% % \ytableaushort{abd,cef}:& \quad 
% % \ytableaushort{136,{2}{5}8,{4}{7}9},\ldots &
% % % \ytableaushort{136,{*(yellow)2}{*(yellow)5}8,{*(yellow)4}{*(yellow)7}9},\ldots &
% % \ytableaushort{acd,bef}:& \quad  \ytableaushort{146,257,389},\ldots\\
% % \ytableaushort{abe,cdf}:& \quad \ytableaushort{137,258,469}, \ldots &
% % \ytableaushort{ace,bdf}:& \quad \ytableaushort{147,258,369},
% % \end{align*}

% % The tableau in the second group has descents $2,4,5,7$, corresponds to the linear extension $\underline{1}{\bf 4}\underline{2}{\bf 7}{\bf 5}\underline{3}{\bf 8}69$ and it would contribute to \eqref{eq:Ehrhart formula skew shape} the term
% % \[
% % \bbinom{\beta_2-\beta_1}{1}\bbinom{\beta_3-\alpha_1-1}{1}\bbinom{\alpha_3-\alpha_2}{1} = (\beta_2-\beta_1)(\beta_3-\alpha_1-1)(\alpha_3-\alpha_2).
% % \]
% \end{example}



\acknowledgements{We thank   Luis Ferroni, Alex Fink, Rafael Gonz\'alez D'L\'eon, Fu Liu, Avery St. Dizier, and Martha Yip for helpful comments and suggestions.}

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