\section{A tableau version of multiline queues}\label{sec:tableau}
In this section we introduce some new \emph{queue tableaux} which are in bijection with multiline queues.
The tableaux are 
similar to the permuted basement tableaux; however, our definition of 
attacking boxes is different, and our definition of inversion triples is
different.

Let $\mu=(\mu_1,\dots,\mu_n)$ be a composition with  $\mu_i\in \{0,1,\dots, k\}$.
The \emph{diagram} $D=D_{\mu}$ associated to $\mu$ is a 
 sequence of $n$ columns of boxes where the $i$th column contains  $\mu_i$ boxes (justified to the bottom).
 Meanwhile the \emph{augmented diagram} $\tilde{D} = \tilde{D}_{\mu}$ is $D_{\mu}$ 
 augmented 
 by a \emph{basement} consisting of $n$ boxes in a row just below these 
 columns, see 
	\cref{fig:attacking}.
 We number the rows of $\tilde{D}$ from bottom to 
top (starting from the basement in row $0$) and the columns from left to right (starting from column $1$). Abusing notation slightly,
we often use $D$ or $\tilde{D}$ to refer to the collection of boxes in $D$ or $\tilde{D}$.
We use $(i,j)$ to refer to the box  in column $i$ and row $j$ (if $\mu_i<j$ that box is empty). 
For a box $x$, we denote by $d(x)$ the box directly below it.

Note that we will always be working with a diagram associated to a partition $\lambda$.

\begin{defn}\label{def:attacking}
	Let $D=D_{\lambda} $ be the diagram of shape $\lambda$ for partition $\lambda$, and let $(i,j)\in D_{\lambda}$. The boxes attacking $(i,j)$ in the augmented diagram are % We say that two boxes are \emph{attacking} if any of the following holds
	 (see \cref{fig:attacking} (a)):
\begin{itemize}
\item$(i',j)$ where $i\neq i'$,% are in the same row,
\item $(i',j-1)$ where $i'>i$,% are in adjacent rows,
\item $(i',j-1)$ where $i'<i$ such that $\lambda_i=\lambda_{i'}$.

\end{itemize}
\end{defn}
Note that our definition of attacking boxes differs from that in \cite{HHL3,A} due to the third condition.

%, meaning that $\ell(\sigma)$ is maximal such that 
%	$\lambda_{\sigma(1)} \leq \lambda_{\sigma(2)} \leq 
%	\dots \leq \lambda_{\sigma(n)}$.
%(Recall that $\ell(\sigma)$ is the number of inversions in $\sigma$.)
Given a partition $\lambda=(\lambda_1,\dots,\lambda_n)$ and a 
permutation $\sigma\in S_n$, we say that 
an \emph{augmented filling} of shape $\lambda$ and \emph{basement} $\sigma$ is 
a filling of the boxes of $\tilde{D}_{\lambda}$ with integers in $[n]$, where 
the basement is filled from right to left with $\sigma_1,\ldots,\sigma_n$. 
We say that 
a permutation $\sigma\in S_n$ is \emph{maximal with respect to $\lambda$} if 
whenever $\lambda_i=\lambda_j$ for $i=j$, we have that 
$\sigma_{n+1-i}<\sigma_{n+1-j}$.  



We use the notation $\phi: \tilde{D}_{\lambda}\to [n]$ to denote an augmented filling.
Given a filling $\phi$, we say that a box $x$ is \emph{restricted} if the labels of $x$ and $d(x)$ are equal, i.e. if 
$\phi(d(x))=\phi(x)$.

Note that this definition of an augmented filling is consistent with the skyline fillings used in \cite{HHL3}; it is equivalent to 
the definition of the same object in \cite{A}, though \cite{A} uses  English (rather than French) notation for diagrams.

% An \emph{diagram} of type $\mu$, where $\mu$ is a compositions with $n$ parts $, is a bottom-justified set of $n$ columns with column $i$ consisting of $\mu_i+1$ boxes. The bottom-most row is the \emph{basement}. 

\begin{figure}[!ht]
  \centerline{\includegraphics[height=1in]{attacking.pdf}}
\centering
	\caption{(a) A tableau of shape $\lambda=(4,3,3,3,2,1,1,1,0)$ is shown, with the grey boxes representing the basement. The boxes attacking $x$ are: $w$ (due to the first condition of \cref{def:attacking}), 
	$z$ (due to the second one), and 
	$y$ (due to the third condition).
	The box $v$ is not attacking $x$, and $v=d(w)$. (b) The black box belongs to the leg and the grey boxes belong to the arm of the box labeled $x$.}
\label{fig:attacking}
 \end{figure}

\begin{defn}
	Let $\lambda=(\lambda_1,\dots,\lambda_n)$ be a partition, 
	%$\mu$ some composition obtained by 
	%rearranging the parts of $\lambda$, 
	and let $\sigma\in S_n$ be maximal with respect to $\lambda$.
	 A \emph{queue tableau} of shape $\lambda$ and type $\sigma$ is an augmented filling $\phi:\tilde{D}_{\lambda}\to [n]$ with basement $\sigma$ such that no two attacking boxes contain the same entry. We let $\QT_{\lambda}^{\sigma}$ denote the set of all queue tableaux of shape $\lambda$ and type $\sigma$.
\end{defn}

%For our purposes, we assume $\lambda$ is a partition, and $\inc(\lambda)$ is the anti-partition obtained by reading $\lambda$ from right to left.


\begin{defn}\label{def:weight}
	Let $\lambda=(\lambda_1,\dots,\lambda_n)$ be a partition, 
	and let $\sigma\in S_n$ be maximal  with respect to $\lambda$.
	Let $T\in \QT_{\lambda}^{\sigma}$ with filling $\phi:D_{\lambda}\to [n]$. The \emph{weight} of $T$ is
\[
	\wt(T)=q^{\maj(T)}t^{\coinv(T)}\prod_{x\in D_{\lambda}:\phi(d(x))\neq \phi(x)} 
	\frac{1-t}{1-q^{\leg(x)+1}t^{\arm(x)+1}},
\]
where the various statistics are defined as follows.

\noindent $\bullet$ For $x=(i,j)$, $\leg(x)=\lambda_i - j$ is the number of boxes above $x$ in its column. 

	\noindent $\bullet$ The major index is given by 
	\[
	\maj(T)=\sum_{x\in D_{\lambda}: \phi(d(x))<\phi(x)} \leg(x)+1.
	\]

\noindent $\bullet$ For $x=(i,j)$, 
	\begin{align*}
		\arm(x)&=|\{(i',j-1) \in D\ :\ i'>i,\ \lambda_{i'}<\lambda_i\}| \\
		&+ |\{(i',j) \in D\ :\ i'<i,\ \lambda_{i'}=\lambda_i,\ (i',j) \text{ is not restricted}\}|
	\end{align*} 
is the number of boxes to the right of $x$ in the row below it, contained in columns shorter than its column, plus the number of unrestricted boxes to the 
	left of and in the same row as $x$, contained in columns of the same length as $x$'s column.
	
	In \cref{fig:attacking} (b), the black box shows the leg of box $x$, while the grey boxes show the arm (assuming that none of the grey boxes to the left of $x$ are restricted).

	A \emph{type A triple} is a triple of boxes $(x, d(x),y)$
	such that the columns containing $x$ and $y$ are of the same length, 
	with $\phi(d^{-1}(y))\neq \phi(y)$ and 
	 $\phi(x)>\phi(d^{-1}(y))$.

	A \emph{type B triple} is a triple of boxes $(x, d(x), y)$ where 
	$y$ is to the right of and in the same row as $d(x)$, and 
	 the column containing $y$ is shorter than the column containing $x$.
	 See \cref{fig:inversion}.

\begin{figure}[!ht]
  \centerline{\includegraphics[height=1.3in]{inversion_triples.pdf}}
\centering
\caption{Type A and Type B triples, which are non-inversion triples 
	whenever the values $\{\phi(d(x)), \phi(x), \phi(y)\}$ 
	are strictly increasing when read counterclockwise in Type A, and 
	clockwise in Type B.}
\label{fig:inversion}
 \end{figure}

	A type A or B triple is a \emph{non-inversion triple}
	if $\phi(y)<\phi(d(x))<\phi(x)$ or $\phi(d(x))<\phi(x)<\phi(y)$ or $\phi(x)<\phi(y)<\phi(d(x))$, 
	see  \cref{fig:inversion}.

	\noindent $\bullet$ $\coinv(T)$ is the number of \emph{non-inversion triples}. 
\end{defn}

\begin{remark}
Note that in our definition, Type B triples are defined the same way
	as in \cite{HHL3, A}, but the Type A triples are different and are adapted precisely to correspond to statistics in the MLQs. 
When $\lambda$ has distinct parts, we do not have Type A triples, and in this case the weight we associate to our tableau and the resulting formula for Macdonald polynomials is essentially the one given by Lenart \cite{Lenart} (who gave a formula for $P_{\lambda}$ only in the case that $\lambda$ has distinct parts). To generalize that formula to arbitrary partitions, one needs the Type A triples.
	
	Note also that our arm is defined so as to not count restricted boxes, whereas the usual definition of arm does count restricted boxes. 
\end{remark}


\begin{proposition}\label{prop:tableauxformula}
	Let $\mu=(\mu_1,\dots,\mu_n)$ be a composition, and 
	let $\lambda$ be the partition obtained from $\mu$ by rearranging its parts in decreasing order.
	Choose $\sigma\in S_n$ maximal with respect to $\lambda$ such that  
	$\mu_{\sigma(1)} \leq \mu_{\sigma(2)} \leq 
	\dots \leq \mu_{\sigma(n)}$.
	Then
\[
	F_{\mu} = \sum_{T\in\QT_{\lambda}^{\sigma}} \wt(T)x^T.
\]
where $x^T=\prod_{y\in D_{\lambda}}x_{\phi(y)}$ is the monomial in $x_1,\ldots,x_n$ where the power of $x_i$ is the number of boxes in $D_{\lambda}$ whose entry is $i$.
\end{proposition}

\cref{prop:tableauxformula} gives a tableaux formula for 
the polynomials $F_{\mu}$ (and hence for the Macdonald polynomials
$P_{\lambda} = \sum_{\mu: \dec(\mu) = \lambda} F_{\mu}$) which is equivalent 
to the multiline queue formula we gave earlier.

In \cref{fig:queueTableaux}, we illustrate how both the queue tableaux and the permuted basement tableaux in \cite{A}
%\Comment{need to say WHOSE definition of permuted basement tableau we're using here since we didn't define them} 
can be used to compute $F_{(0,1,2,2)}$. Note that the sums of the weights are the same, and in particular, the sum of the weights of the third and fourth permuted basement tableaux equals the weight of the third queue tableau.

\begin{figure}[!ht]
  \centerline{\includegraphics[width=\textwidth]{queueTableaux0122.pdf}}
\centering
\caption{The three queue tableaux of type $\mu=(0,1,2,2)$ and the four permuted basement tableaux of type $\sigma=(3,4,2,1)$ and shape $\lambda=(2,2,1,0)$. The total weight for both is $x_2x_3^2x_4^2+(x_1x_2x_3^2x_4+x_1x_2x_3x_4^2)\frac{t(1-t)}{1-q t^2}$.}
\label{fig:queueTableaux}
 \end{figure}

%	\Comment{Shouldn't the $\inc(\mu)$ above and below be a $\dec(\mu)$ instead? turning $\mu$ into a partition? maybe we should use $\mu^+$ for that}

To prove \cref{prop:tableauxformula},
we show that there is a direct weight-preserving bijection 
between 
$\MLQ(\mu)$ 
and $\QT_{\lambda}^{\sigma}$ 
	where  $\lambda$ is the partition obtained from $\mu$ by rearranging its parts in decreasing order,
	and 
	 $\sigma\in S_n$ has 
	 the longest length such that  
	$\mu_{\sigma(1)} \leq \mu_{\sigma(2)} \leq 
	\dots \leq \mu_{\sigma(n)}$.
Our bijection is the following. 

	\begin{definition}
		Suppose $\mu$ is a composition with maximal entry $L$ 
		and let $Q\in\MLQ(\mu)$. 
	Choose $\lambda$ and $\sigma$ as in 
\cref{prop:tableauxformula}.
	Let $T$ be an augmented filling of shape $\lambda$ with basement labeled by $\sigma$ from right 
		to left as usual. Let $i_1,\ldots,i_{A}$ be the columns containing the string of linked balls of type $1\leq A\leq L$ that begin from the ball at column $i_1$ in row 1 of $Q$. 
		Label the boxes of the column of $T$ with $i_1$ in the basement 
		by $i_1,\ldots,i_A$ from bottom to top. Let $\Tab(Q)$ denote the resulting tableau,
see \cref{fig:queuetableau}.
	\end{definition}
\begin{figure}[!ht]
  \centerline{\includegraphics[height=1in]{Q-tableau.pdf}}
\centering
	\caption{$\Tab(Q)$, where $Q$ is 
	the multiline queue from \cref{fig:MLQ_example}.}
\label{fig:queuetableau}
 \end{figure}

\begin{lemma}
Let $Q\in\MLQ(\mu)$, 
	and choose $\lambda$ and $\sigma$ as in 
\cref{prop:tableauxformula}.
	Then $\Tab(Q)\in\QT_{\lambda}^{\sigma}$. 
	Moreover this map is a bijection from 
	$\MLQ(\mu)$ to $\QT_{\lambda}^{\sigma}$.
\end{lemma}

\begin{proof}
The first part was already proved in the definition of $\Tab(Q)$. The second part follows from the third non-attacking condition, that if there are two boxes with label $c$ in row $r$ and $r+1$ respectively, and they are in columns of the same length, then they must be directly on top of each other.
\end{proof}


\begin{proof}[Proof of \cref{prop:tableauxformula}]
We claim that the filling $\Tab(Q)$ obtained from an MLQ in this way is non-attacking. 

	First, if a ball labeled $j$ is directly above a ball labeled $i$ in $Q$ in row $r$ and column $c$, then either $j<i$, or $j=i$ in which case the two balls are paired. There are two boxes containing the label $c$ in rows $r$ and $r+1$ respectively. If $j<i$, the box in row $r+1$ is to the right of the box in row $r$ since all columns corresponding to label $j$ are by construction to the right of all columns corresponding to label $i$. If $j=i$, then both boxes labeled $c$ are in the same column, and thus non-attacking in both cases.

	That the bijection is weight-preserving follows from \cref{lem:stats} below, which in turn
	follows from the definitions.
\end{proof}


%\begin{conjecture}
%We can split the permuted basement tableaux $\PB_{\inc(\mu)}^{\sigma}$ into classes, whose total weights sum to the weight of a single corresponding tableau $T\in\QT_{\inc(\mu)}^{\sigma}$.
%\end{conjecture}


%Not necessary
%\begin{lemma}
%For a composition $\mu$, if $\sigma_1^{-1}\inc(\mu)=\sigma_2^{-1}\inc(\mu)$ then $\QT_{\inc(\mu)}^{\sigma_1}=\QT_{\inc(\mu)}^{\sigma_2}$.
%\end{lemma}


%The following lemma lists some properties of the queue tableaux and the statistics defined on them, which by construction are set to match the corresponding statistics on the multiline queues.

\begin{lemma}\label{lem:stats}
\begin{enumerate}
\item Let $x$ be in row $r$ and column $j$, where $L$ is the largest part of $\lambda$. Then $\leg(x)+1=r+i-L$.
\item Let $U(r,j)$ be the set of unrestricted entries in row $r$ and columns of length $j$. Then the contribution $\prod_{x\in U(r,j)} \frac{1-t}{1-q^{\leg(x)+1}t^{\arm(x)+1}}$ matches the contribution of the balls of type $j$ in the corresponding row $L-r$ of the MLQ.
\item The co-inversions of type B count the number of balls skipped of lower labels. The co-inversions of type A count the number of balls skipped of the same label in the corresponding MLQ.
\end{enumerate}
\end{lemma}


\begin{remark}\label{rem:queue}
	Our queue tableau are the same as permuted basement \cite{A, thesis}
tableau, and their weights agree, when $\mu$ is a composition with all parts distinct.


%We denote the set of permuted basement tableaux of shape $\mu$ and basement $\sigma$ by $\PB_{\mu}^{\sigma}$. 
%To distinguish between the two definitions, we denote by $\coinv_{PB}$ and $\arm_{PB}$ the statistics of co-inversions and arms that correspond to the permuted basement tableaux, and by $\wt_{PB}$ the weight of a permuted basement tableau.

Any non-attacking filling of a queue tableau is automatically non-attacking as a filling of a permuted basement tableau. Moreover, when the parts of $\mu$ are distinct, all non-attacking permuted basement fillings are also non-attacking according to \cref{def:attacking}, so the two sets of tableaux are equal.

When the parts of $\mu$ are distinct, the definitions of arm agree on both sides; moreover, 
	there are no triples of type A, so the coinversion statistics match 
as well.
%Let $T\in \QT_{\inc(\mu)}^{\sigma}$ be a queue tableau, and let $T'\in\PB_{\inc(\mu)}^{\sigma}$ be the permuted basement tableau with the same filling. When the parts of $\mu$ are distinct, neither $T$ nor $T'$ has triples of type A, so both $\coinv(T)$ and $\coinv_{PB}(T')$ are obtained from non-inversions of type B: since the sets of these coincide in the two types of tableaux, the co-inversion statistics match. Moreover, the definition of $\arm(x)$ for $x\in T$ and $\arm_{PB}(x)$ for $x\in T'$ also match when the parts of $\mu$ are distinct. Thus $\wt(T)=\wt_{PB}(T')$.
\end{remark}

