\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P11}{19}{2012}

\usepackage{amsmath, amssymb, amsthm, verbatim}
\usepackage{amsfonts}
%\usepackage{auto-pst-pdf}
\usepackage{pstricks,pst-node,pst-tree}
%\usepackage{pst-tree}

\def \P{\mathcal{P}}
\def \l{\ell}
\def \Psq{\mathcal{P}_{\rm sq}}
\def \Z{\mathbb{Z}}
\def \N{\mathbb{N}}
\def \F{\mathcal{F}}
\def \T{\mathcal{T}}
\def \M{\mathcal{M}}
\def \sl{\mathfrak{sl}}
\def \cal {\mathcal}
\def \tmu{\tilde\mu}
\def \({\left( }
\def \){\right)}
\def \t{\tilde}
\def \lr{\Leftrightarrow}
\DeclareMathOperator{\Tab}{Tab}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\chv}{ch}

\theoremstyle{definition}
\newtheorem{defi}{Definition}[section]
\newtheorem{lemma}[defi]{Lemma}
\newtheorem{claim}[defi]{Claim}

\newtheorem{thm}[defi]{Theorem}
\newtheorem{rem}[defi]{Remark}
\newtheorem{example}[defi]{Example}
\newtheorem{cor}[defi]{Corolary}
\newtheorem{conj}[defi]{Conjecture}

\title{Partitions, Kostka polynomials and pairs of trees}
\author{Eliana Zoque\\
\small University of California, Riverside\\
\small \texttt{elizoque@math.ucr.edu}}
\date{\dateline{Dec 15, 2010}{Dec 23, 2011}{Jan 6, 2012}\\ 
\small Mathematics Subject Classification: 05A15}


\begin{document}
\maketitle 

\begin{abstract}
Bennett et al.\ \cite{BCDM} presented a recursive algorithm to create a family of partitions from one or several partitions. They were mainly interested in the cases when we begin with a single square partition or with several partitions with only one part. The cardinalities of those families of partitions are the Catalan and ballot numbers, respectively. In this paper we present a non-recursive description for those families and prove that the generating function of the size of those partitions is a Kostka number. We also present bijections between those sets of partitions and sets of trees and forests enumerated by the Catalan an ballot numbers, respectively.
\end{abstract}



\section*{Introduction}
The Catalan numbers appear in a wide variety of settings, including
representation theory. While studying the category of finite
dimensional representations of the affine Lie algebra associated to
$\mathfrak{sl}_2$ and trying to develop a theory of highest weight
categories, Chari and Greenstein (\cite{CG1,CG2}) found that that
one of the results required  would be to prove that a certain module
$\cal M_{\ell}$  for the ring of symmetric functions of
$\ell$ variables was free,  with rank given by the $\ell^{th}$
Catalan number.

The module $\cal M_{\ell}$ is generated by a family of polynomials
$\mathbf{ p}_\mu$ indexed by partitions with exactly $\ell$ parts. An
algorithm is presented in \cite{BCDM} which at the
$\ell^{th}$ stage generates a particular subset (denoted $\cal
P^\ell$) of the set of all partitions with $\ell$ parts. It is
proved by purely algebraic methods that this subset has cardinality
equal to the $\ell^{th}$ Catalan number and it is conjectured that
the set $\{\bold p_{\mu}:\mu\in\cal P^\ell\}$ is a basis for $\cal
M_{\ell}$. Chari and Greenstein also present a more general algorithm which gives rise to
subsets of partitions $\cal P^\ell_m$  with cardinality equal to the
ballot numbers $b_{\ell,m}$.

Chari and Loktev \cite{CL11} define modules $M_{k,\xi}$ for the ring of symmetric functions in $n$ variables and generated by polynomials ${\mathbf p}({\mathbf r}),{\mathbf r}\in\Z_+^{\xi_2}\times\dots\times\Z_+^{\xi_{n+1}}$. They use the theory of global Weyl modules of the current algebra of $\sl_{n+1}$ to prove that $M_{k,\xi}$ is free and has a graded basis where the number of elements of a given grade is the coefficient of the corresponding power of $q$ of a certain Kostka polynomial, and show that it can be identified with a multiplicity space in the ring of polynomials in $k$ variables. For $n=1$, $\xi=(\l+m-1,\l),\,k=2\l+m-1$ and $M_{k,\xi}$ is precisely $\cal M_{\ell,m}$. All their results were proved using algebraic rather than combinatorial methods, and for $n>1$ there is no conjecture regarding a set of generators for $M_{k,\xi}$.

In this paper we present a combinatorial approach to the results of Chari-Greenstein.
As a consequence, we are able to recover their results and also to improve them in two directions. Thus we can give a non-recursive description of elements of the set $\cal P^\ell_m$ in terms inequalities. We can prove that the generating function of the size of the partitions in $\P^\l_m$ is a certain Kostka polynomial. We do this by exhibiting an explicit bijection between this subset and a set of standard tableaux with two columns.

To make the connection with the module $\cal M_{\ell,m}$,  we note that that it admits a grading  by the non-negative integers given by the total degree of the polynomials and in fact the rank of
$\bold p_\mu$ is exactly the  size of $\mu$. Thus our result together with the results of Chari and Loktev
suggest that the polynomials $\bold p_\mu$ form a free basis for $\cal M_{\ell,m}$.

The paper is organized as follows. In Section 1 we recall the
algorithm defined in \cite{BCDM} and state our main results: Theorems \ref{notilde}, \ref{KostkaPol} and \ref{tilde}. Sections \ref{ineq} and \ref{kostka} are
devoted to proving these results. In Section 4, we  present an
explicit bijection between $\cal P^\ell$ and the set of rooted trees
with $\ell$ vertices and similar results for $\cal P^\ell_m$. We
conclude the paper with a very brief description of the
representation theory of affine algebras which motivated this paper.
The interested reader is referred to \cite{BCDM} and \cite{CL} for a
more detailed exposition.


\subsection*{Acknowledgements} The author is grateful to M.\ Bennett, V. Chari, R.J.\ Dolbin and N.
Manning for posing the questions and for useful discussions and suggestions, and to the anonymous referee for interesting remarks and references.

\section{Notation}\label{notation}

In this section we will present the relevant notation, as well as
some Theorems taken from \cite{BCDM}.

Let $\N$ be the set of non-negative integers. Let $[n]=\{1,\dots, n\}$ for any positive integer $n$.

By a partition $\lambda$ we  mean a weakly decreasing sequence
$$\lambda=(\lambda_1,\lambda_2,\dots,\lambda_n, \dots),\quad \lambda_1\geq\lambda_2\geq\dots\geq\lambda_n\geq\dots$$ of non-negative integers such that finitely many of the $\lambda_i$ (known as the parts of $\lambda$) are strictly positive. The number of parts is the length of $\lambda$ denoted by $l(\lambda)$. If a partition has length $n$ we can write it as the finite sequence $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_n)$. We denote the set of all partitions by $\P$.

Given a partition $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_n)$ of length $n$
%, set
%$$\lambda\setminus\{\lambda_n\}= (\lambda_1,\dots,\lambda_{n-1}),$$
and and positive integer $\lambda_{n+1}\leq \lambda_n$ set
$$\lambda\cup(\lambda_{n+1})=(\lambda_1,\lambda_2,\dots,\lambda_n,\lambda_{n+1}).$$

Given a set of partitions $S$ of length $n$, let $\M(S)$ be the set of all partitions of length $n+1$
obtained by adding an extra part to a partition in $S$:
$$\M(S)=\{\lambda\cup(j)\,:\,0< j\leq \lambda_{n},\,\mu\in S\}.$$

For $k, n\in\Z^+$, let $\P^{n,k}$ be the set of partitions of length $n$ where no part is bigger than $k$, i.e.
$$\P^{n,k}=\{\lambda\in\P\,:\,l(\lambda)=n,\,\lambda_1\le k\}.$$
We can regard a partition $\lambda\in\P^{n,k}$ as a weakly decreasing function $\lambda:[n]\to[k],\,i\mapsto \lambda_i$, so we can write $\lambda(i)=\lambda_i.$

Let $\tau:\P^{n,k}\to\P^{n,k}$ (or $\tau_{k}$, if confusion arises) be the complement of $\lambda$ with respect to $(n^{k+1})$, i.e.,
$$\tau(\lambda_1,\cdots,
\lambda_n)=(k+1-\lambda_n,\cdots, k+1-\lambda_1).$$ As a map
$[n]\to[k]$, $\tau(\lambda)$ is equal to the composition
$\gamma_{k}\circ\lambda\circ\gamma_n$, where for every positive
integer $m$, $\gamma_m:[m]\to [m]$ is an order-reversing bijection of order two
defined by $i\mapsto m+1-i$.

Fix $m\in\Z^+$, and
define subsets $\P^{\l}_m\subset\P^{\l,\l+m-1}$ by
\begin{gather*}
\P^1_m=\P^{1,m}=\{\{j\}: 1\le j\le m\},\\
%\P^\l_{m,\rm dir}=\{\mu\cup(j)\,:\,0< j\leq
%\mu_{\l-1},\,\mu\in\P^{\l-1}_m\}\subset\P^{\l,\l+m-1},\\
%\P^\l_\tau(\Omega_m)=\tau_{\l+m-1}\(\P^\l_{\rm d}(\Omega_m)\),\\
\P^\l_m=\M(\P^{\l-1}_m)\cup\tau_{\l+m-1}(\M(\P^{\l-1}_m)).
\end{gather*}
Also set $\P^\l=\P^\l_1$.

\begin{example}
$\P^1_3=\{(1),(2),(3)\},\,\M(\P^1_3)=\{(1^2),(21),(2^2),(31),(32),(3^2)\}$ and \\
$\P^2_3=\{(1^2),(21),(2^2),(31),(32),(3^2),(42),(43),(4^2)\}$.
\end{example}
\begin{example}
$\P^1=\{(1)\}$, $\P^2=\{(1^2),(2^2)\}$, $\P^3=\{(1^3),(2^21),(2^3),(32^2),(3^3)\}$, $\P^4=$ \\
$\{(1^4), (2^2 1^2), (2^31), (32^21), (3^31), (2^4), (32^3), (42^3), (3^32), (43^22), (3^4), (43^3), (4^23^2), (4^4)\}$
\end{example}

The following theorem provides a non-recursive definition of the partitions in $\P^\l.$
\begin{thm}\label{notilde}
$\mu\in\P^\l$ if and only if $\mu:[\l]\to[\l]$ is decreasing and satisfies the
following conditions for every $i\in[\l]$:
\begin{enumerate}
\item[(i)] If $\mu(i)>i$ then $\mu(\mu(i))> i$. \item[(ii)]  If
$\mu(i)<i$ then $\mu(\mu(i))< i$.
\end{enumerate}
\end{thm}
In Theorem \ref{tilde} we provide a similar characterization for the partitions in $\P^\l_m.$

The ballot numbers are defined by
$$b_{\l,m}={{2\l+m}\choose{\l}}-{{2\l+m}\choose{\l-1}}.$$
The following Theorem is proved in \cite{BCDM}.

\begin{thm}[\cite{BCDM}, Section 3.1]\label{thm2} For $\l,m\in\Z^+$, we have  $$|\P^\l_m|=b_{\l,m-1}.$$
\end{thm}
In Section \ref{kostka} we prove a stronger result:
\begin{thm}\label{KostkaPol}
$$\sum_{\mu\in\P^\l_m}q^{|\mu|}=K_{(2^\l1^{m-1})(1^{2\l+m-1})}(q)$$
where the size of a partition $\mu=(\mu_1,\,\mu_2,\,\dots,\,\mu_\l)$, denoted by $|\mu|$ is the sum of its parts $\mu_1+\mu_2+\dots+\mu_\l$ and the right-hand side is a Kostka polynomial.
\end{thm}


\section{A non-recursive characterization using inequalities}\label{ineq}

In this section we provide a non-recursive description of the elements of
$\P^\l_m$ using inequalities.
\begin{comment}
\subsection{Inequalities for $\boldsymbol{\P^\l(\lambda)}$}

\begin{thm}\label{sq}
Let $\l\geq k$, $\lambda\in\Psq^k$ and $\mu\in\P^\l$. Then $\mu\in\P^\l(\lambda)$ if and only if there
exists $b\in[\l-k+1]$ so that:
\begin{enumerate}
\item[(i)] $\mu(b)=b+k-1,\,\mu(b+k-1)=b$. \item[(ii)]
 If $1\leq i< b$ then $\mu(\mu(i))>i$. \item[(iii)] If
$b+k-1< i\leq \l$ then $\mu(\mu(i))<i$.
\item[(iv)] If $\t\lambda\in\Psq^k$ is defined by
$\t\lambda(i)=\mu(b+i-1)-b+1,\,1\leq i\leq k$ then $\t\lambda\in\{\lambda,\tau(\lambda)\}.$
\end{enumerate}
\end{thm}

\begin{rem}
It is clear that, given $\mu\in\P^\l$, if there exist $b$ and $k$
satisfying conditions (i)-(iii) they are unique since $b$ and
$b+k-1$ are the smallest and largest fixed points of
$\mu\circ\mu:[\l]\to[\l]$. We will prove in Lemma \ref{existence}
that they do exist for every $\mu\in\P^\l$.

Also, notice that Theorem \ref{thm1}(ii) is a direct consequence
of condition (iv) in Theorem \ref{sq}.
\end{rem}

Before proving Theorem \ref{sq} we prove the following
\begin{lemma}\label{ii-iii}\ \begin{enumerate}\item
$\mu\in\P^\l$ satisfies (i), (ii) and (iii) for $b$ if and only if
$\tau_\l(\mu)$ satisfies (i), (ii) and (iii) for $b'=\l-k-b+2.$
\item If  $\t\lambda\in\Psq^k$ is defined as in (iv), i.e.,
$$\t\lambda(i)=\mu(b+i-1)-b+1,\,1\leq i\leq k$$ and $\t{\lambda'}\in\Psq^k$ is defined similarly for $\tau_\l(\mu)$ and $b'$,
i.e., $$\t{\lambda'}(i)=\tau_\l(\mu)(b'+i-1)-b'+1,\,1\leq i\leq k$$
then $\tau_k\big(\t\lambda\big)=\t{\lambda'}$.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $\ mu^*=\tau_\l(\mu)$. Then
$$\ mu^*(t)=\gamma(\mu(\gamma(t)))$$
where $\gamma=\gamma_\l$, i.e., $\gamma:\Z\to\Z,\,x\mapsto \l+1-x$. $\gamma$ is an
order-reversing bijection satisfying
$\gamma(b')=b+k-1$ and $\gamma(b)=b'+k-1$.

If $\mu$ satisfies (i), then
$\ mu^*(b')=\gamma(\mu(\gamma(b')))=\gamma(\mu(b+k-1))=\gamma(b)=b'+k-1$
and similarly, $\ mu^*(b'+k-1)=b'.$ This is condition (i) for
$\ mu^*.$

Assume that $\mu$ satisfies (ii) for $b$, that is,
$$1\leq i<b\Rightarrow i<\mu(\mu(i)).$$%=\gamma(\mu^*_{\gamma(\mu_t)})=\gamma(\ mu^*_{\ mu^*_{\gamma(t)}})$$
Therefore
$$\gamma(b)< \gamma(i)\leq\gamma(1)\Rightarrow \gamma(i)>\gamma(\mu(\mu(i))),$$
or equivalently,
$$b'+k-1< \gamma(i)\leq\l\Rightarrow \gamma(i)>\gamma(\mu(\mu(i))).$$
If we set $i'=\gamma(i)$ then $i=\gamma(i')$ and
$$b'+k-1< i'\leq\l\Rightarrow i'>\gamma(\mu(\mu(\gamma(i')))).$$
This is precisely (iii) for $\ mu^*,\,b',\,i'$ since
$$\ mu^*(\ mu^*(i'))=\ mu^*(\ mu^*(\gamma(i)))=\gamma(\mu(\gamma(\ mu^*(\gamma(i)))))
=\gamma(\mu(\mu(\gamma(i')))).$$
The other implications in (a) are similar.

The proof of (b) is a straight forward calculation. It suffices to
prove that $\t{\lambda'}(i)+\t\lambda(k+1-i)=k+1,\,1\leq i\leq k$.
In fact:
$$\t{\lambda'}(i)+\t\lambda(k+1-i)=(\tau_\l(\mu)(b'+i-1)-b'+1)+(\mu(b+(k+1-i)-1)-b+1)$$
$$=\gamma(\mu(\gamma(b'+i-1)))+\mu(b+k-i)-b-b'+2$$
$$=\gamma(\mu(b+k-i))+\mu(b+k-i)+k-\l=\l+1-\mu(b+k-i)+\mu(b+k-i)+k-\l=k+1.$$
\end{proof}

\begin{proof}[Proof of Theorem \ref{sq}] First we prove that $\mu\in\P^\l(\lambda)$ implies (i)-(iv).
We proceed by induction on $\l$. If $\l=k$ then  $b=1$, conditions
(ii) and (iii) are vacuum, and $\mu\in\P^\l(\lambda)$ if and only
if $\mu\in\{\lambda,\tau_\l(\lambda)\}$, which is precisely
condition (iv) since $\lambda'=\mu$.

For the inductive step assume that $\l>k$ and $\mu\in\P^\l(\lambda)$, say
$$\mu\in \{\nu\cup(j)\,|\,1\leq j\leq \nu(\l-1)\}\cup\{\tau_{\l}\nu\cup(j)\,|\,1\leq j\leq \nu(\l-1)\}$$
where $\nu\in\P^{\l-1}(\lambda)$ satisfies conditions (i)-(iv) for
$b'$, $1\leq b'\leq \l-k$. If $\mu=\nu\cup(j)$, then take $b=b'$. The
only thing that we have to check is (iii) for $i=\l$ which in this
case reads $\mu(\mu(\l))<\l$, but every part of $\nu$, and
therefore of $\mu$, is less than $\l$.

If $\mu=\tau_{\l}\nu\cup(j)$ then it follows from Lemma \ref{ii-iii}
and the previous paragraph that $\mu$ satisfies (i)-(iv) for
$b=\l-k-b'+2.$

Now we prove that (i)-(iv) imply that $\mu\in\P^\l(\lambda)$. If
$\l=k$ then we must have $b=1$,(i) means that $\mu\in\Psq^k$, (ii)
and (iii) are vacuum, and (iv) means that $\mu\in\{\lambda,
\tau_\l(\lambda)\}$.

If $\l>k$ then $\mu$ is not a square partition since $\mu(\l)=1$
and $\mu(1)=\l$ imply $\mu(\mu(\l))=\l$ and $\mu(\mu(1))=1$,
forcing $b=1$ and $b+k-1=\l$ and therefore
$\l-1=k-1$, a contradiction. So we consider the cases
$\mu(\l)\neq1$ and $\mu(1)\neq\l$.

If $\mu(1)<\l$ then $\mu=\nu\cup(\mu(\l))$ where by the induction
hypothesis $\nu\in\P^{\l-1}(\lambda)$ and therefore
$\mu\in\P^{\l}(\lambda).$

If $\mu(1)=\l$ and $\mu(\l)>1$ then $\ mu^*=\tau_\l(\mu)$ satisfies
$\ mu^*(\l)=1,\,\ mu^*(1)<\l$, %so $\nu\setminus\{\nu_\l\}\in\P^{\l-1}(\lambda)$.
and by Lemma \ref{ii-iii}, $\ mu^*$ satisfies (i)-(iv) for
$b'=\l-k-b+2$. So we can apply the previous paragraph to conclude
that $\ mu^*\in\P^\l(\lambda)$ and therefore $\mu\in\P^\l(\lambda)$.
\end{proof}

Now we use these results to provide an alternative proof of the following

\begin{lemma}[Theorem \ref{thm1}(iii), \cite{BCDM} Proposition 2.6 (ii)]\label{existence}
Let $\mu\in\P^\l$ for some $\l\in\N$. Then $\mu\in\P^\l(\lambda)$
for some $\lambda\in\Psq^k,\, k\geq1$.
\end{lemma}

\begin{proof}
We are to prove that for every $\mu\in\P^\l$ there exist $b$ and
$k$ satisfying the conditions in Theorem \ref{sq}.
$\mu\circ\mu:[\l]\to[\l]$ is increasing since $\mu$ is decreasing.
It has a fixed point since the sequence $j_1,\,j_2\dots$ defined
by $j_1=1,\,j_{m+1}=\mu(\mu(j_m))$ is increasing and must
stabilize. Let $b$ be the smallest fixed point of $\mu\circ\mu$.
Clearly $\mu(b)$ is another fixed point of $\mu\circ\mu$. We claim
that it is the largest one. Assume that $a>\mu(b)$ is another
fixed point for $\mu\circ\mu$, then so is
$\mu(a)\leq\mu(\mu(b))=b$. The minimality of $b$ implies
$\mu(a)=b$, but this is impossible since $\mu(\mu(a))=a>\mu(b).$

Set $k=\mu(b)-b+1$, so $\mu(b)=b+k-1$ and condition (i) is
satisfied. If $1\leq t< b$ then $\mu(\mu(t))\leq\mu(\mu(b))=b$,
but the inequality cannot occur since $b$ is the smallest fixed
point of $\mu\circ\mu$. This proves condition (ii), and (iii) is
proved similarly. Defining $\lambda\in\Psq^k$ as in condition (iv) we get that $\mu\in\P^\l(\lambda)$
\end{proof}

\end{comment}
%\subsection{Inequalities for $\boldsymbol{\P^\l_m}$}\

As before, we regard elements of  $\P^\l_m$ as weakly decreasing
functions $\mu:[\l]\to[\l+m-1]$. Here $\tau=\tau_{m+\l-1}$ so
$\tau(\mu)=\gamma_{m+\l-1}\circ\mu\circ\gamma_\l$.

We define $$t:[\l]\times[\l+m-1]\to [\l],\, t(r,s)=\begin{cases}
s&\text{if }s<r,\\r&\text{if }r\leq s\leq m+r-1,\\s-m+1&\text{if
}s>m+r-1.
\end{cases}$$
$t$ has the effect of ``compressing" a $\l\times(\l+m-1)$ rectangle
into an $\l\times\l$ square. For example, if $\l=5,\,m=3$, the
values of $t(r,s)$ are shown in Figure \ref{t}, where $r$ and $s$
are displayed vertical and horizontally, respectively.

\begin{figure}[h]
\begin{center}\setlength{\unitlength}{0.5mm}\begin{picture}(70,70)
{\color{gray}
\multiput(0,5)(0,10){6}{\line(1,0){70}}
\multiput(0,5)(10,0){8}{\line(0,1){50}}}
\multiput(3,7)(0,10){5}{1}
\multiput(13,7)(0,10){3}{2}
\multiput(23,7)(0,10){2}{3}
\put(33,7){4}

\multiput(63,7)(0,10){5}{5}
\multiput(53,17)(0,10){4}{4}
\multiput(43,27)(0,10){3}{3}
\multiput(33,37)(0,10){2}{2}

\multiput(3,47)(10,0){3}{1}
\multiput(13,37)(10,0){3}{2}
\multiput(23,27)(10,0){3}{3}
\multiput(33,17)(10,0){3}{4}
\multiput(43,7)(10,0){3}{5}

\put(-5,55){\vector(0,-1){50}} \put(-10,27){$r$}
\put(0,60){\vector(1,0){70}} \put(35,62){$s$}

\thicklines
\put(0,45){\framebox(30,10)}\put(10,35){\framebox(30,10)}
\put(20,25){\framebox(30,10)}\put(30,15){\framebox(30,10)}\put(40,5){\framebox(30,10)}
\end{picture}
\end{center}\caption{$t:[5]\times[7]\to[5]$}\label{t}
\end{figure}

Let $\tilde\mu(i)=t(i,\mu(i))$, i.e., $$\tilde\mu(i)=\begin{cases}
\mu(i)&\text{if }\mu(i)<i,\\i&\text{if }i\leq \mu(i)\leq m+i-1,\\\mu(i)-m+1&\text{if
}\mu(i)>m+i-1.
\end{cases}$$

In general,
$\tilde\mu:[\l]\to[\l]$ is not a partition since it is not weakly
decreasing.
The following properties are easy to prove

\begin{lemma}\label{propt}
\
\begin{enumerate}
\item[(a)] $t(r,s)<r$ if and only if $s<r$, and $t(r,s)>r$ if and only
if $s>r+m-1$. \item[(b)]
$t\circ(\gamma_\l\times\gamma_{\l+m-1})=\gamma_\l\circ\mu.$
\item[(c)] Let $\mu^*=\tau(\mu)$. Then
$\gamma_\l\circ\widetilde{\mu^*}=\t\mu\circ\gamma_{\l}$.
\end{enumerate}
\end{lemma}

\begin{proof}
(a) is clear from the definition. For (b), notice that
\begin{multline*}t(\gamma_\l(r),\gamma_{\l+m-1}(s))\\=\begin{cases}
\l+m-s&\text{if }\l+m-s<\l+1-r\\\l+1-r&\text{if }\l+1-r\leq
\l+m-s\leq m+(\l+1-r)-1\\(\l+m-s)-m+1&\text{if
}\l+m-s>m+(\l+1-r)-1
\end{cases}\end{multline*}
$$=\begin{cases}
\gamma_\l(s-m+1)&\text{if }r+m-1<s\\
\gamma_\l(r)&\text{if }r\leq s\leq m+r-1=\gamma_\l(\mu(r,s))\\
\gamma_\l(s)&\text{if }s<r
\end{cases}$$
The conclusion follows.

(c) follows from Lemma (b) and the definition of $\mu^*$:
$$\gamma_\l\big(\widetilde{\mu^*}(i)\big)=\gamma_\l(t(i,\mu^*(i)))=t(\gamma_\l(i),\gamma_{\l+m-1}(\mu^*(i)))
=t(\gamma_\l(i),\mu(\gamma_{\l}(i)))=\t\mu(\gamma_{\l}(i))$$

\end{proof}

Now we provide a characterization for
$\P^\l_m.$

\begin{thm}\label{tilde}
Let $\mu\in\P^{\l,\l+m-1}.$ Then $\mu\in\P^\l_m$ if and
only if $\tilde\mu$ satisfies the following conditions for every
$i\in[\l]$:
\begin{enumerate}
\item[(i)] If $\tilde\mu(i)>i$ then $\tilde\mu(\tilde\mu(i))> i$.
\item[(ii)]  If $\tilde\mu(i)<i$ then $\tilde\mu(\tilde\mu(i))<
i$.
\end{enumerate}
\end{thm}

First we prove the following:
\begin{claim}\label{tau}
$\mu\in\P^{\l,m+\l-1}$ satisfies (ii) if and only if $\tau(\mu)$
satisfies (i).
\end{claim}

\begin{proof}
Assume that $\mu$ satisfies (ii) and that $\widetilde{\mu^*}(i)>i$
where $\mu^*=\tau(\mu)$. From Lemma \ref{propt} (c) and the fact
that $\gamma_\l$ is order-reversing we see that
$\gamma_\l(i)>\gamma_\l\big(\widetilde{\mu^*}(i)\big)=\t{\mu}(\gamma_\l(i))$
and as a consequence of (i),
$\gamma_\l(i)>\t{\mu}(\t{\mu}(\gamma_\l(i)))$. Applying
$\gamma_\l$ again we get
$i<\gamma_\l(\t{\mu}(\t{\mu}(\gamma_\l(i))))$, but
$\gamma_\l(\t{\mu}(\t{\mu}(\gamma_\l(i))))=\widetilde{\mu^*}(\gamma_\l(\t{\mu}(\gamma_\l(i))))
=\widetilde{\mu^*}\big(\widetilde{\mu^*}(i)\big).$ The conclusion
follows.
\end{proof}

\begin{proof}[Proof of Theorem \ref{tilde}]
First we prove by induction that every $\mu\in\P^\l_m$ satisfies
(i) and (ii). If $\l=1$ then (i) and (ii) are void since
$\t\mu(1)=1.$

Because of Claim \ref{tau} we just have to consider
$\mu=\nu\cup(j),\,1\leq j\leq\nu(\l-1)$ to complete the induction
step. Clearly $\t\mu(i)=\t\nu(i)\in[\l-1]$ for $i\in[\l-1]$, and
the premise of (i) is impossible if $i=\l$, so we just have to
prove that (ii) holds for $i=\l$. But $\tilde\mu(\l)<\l$ implies
$\tilde\mu(\tilde\mu(\l))=\tilde\nu(\tilde\mu(\l))\leq\l-1< \l$
since $\t\nu:[\l-1]\to[\l-1].$

Now we prove that if $\mu\in\P^{\l,m+\l-1}$ is so that $\tilde\mu$
satisfies (i) and (ii), then $\mu\in\P^\l_m$. For $\l=1$
there is nothing to prove since $\P^1_m=\P^{1,m}$. Assume
$\l>1$. It is not possible to have $\t\mu(1)=\l$ and $\t\mu(\l)=1$
since this would contradict (i) and (ii). If $\t\mu(1)=\l$ then if
follows from Lemma \ref{propt} (c) and Claim \ref{tau} that we can
replace $\mu$ by $\tau(\mu)$. Therefore we can assume that
$\t\mu(1)<\l$. From the definition of $t$ if follows that
$\mu(1)<\l+m-1$ and therefore no part of $\mu$ is bigger than
$\l+m-1$. So $\nu=\mu\setminus\mu_\l\in \P^{\l-1,m+\l-2}$ and it
satisfies (i) and (ii). By the induction hypothesis
$\nu\in\P^{\l-1}_m$ and therefore $\mu=\nu\cup(\mu_j)\in
\P^\l_m$.
\end{proof}

One important case is $\P^\l=\P^\l_1$. Since $\t\mu=\mu$ for $m=1$, Theorem \ref{tilde} implies Theorem \ref{notilde}.
The following Lemma provides an alternative characterization of $\P^\l$.
%Clearly $\P^\l(\Omega_1)=\P^\l(\lambda)$ where $\lambda=(1)$ is the only element in $\Psq^1$.
%In this case Lemma \ref{sq} states that $\mu\in\P^\l_1$  if and only if:
\begin{lemma}\label{remlambda1}
A partition $\mu\in\P^{\l,\l}$ belongs to $\P^\l$ if and only if the following conditions are satisfied.
\begin{enumerate}
\item[(i$'$)] There exists a positive integer $b\in[\l]$ so that $\mu(b)=b$,
\item[(ii$'$)]  If $1\leq i< b$ then $\mu(\mu(i))>i$,
\item[(iii$'$)] If $b< i\leq \l$ then $\mu(\mu(i))<i$.
\end{enumerate}
\end{lemma}

\begin{proof}

``(i),(ii) $\Rightarrow$(i$'$),(ii$'$),(iii$'$)":  $\mu\circ\mu:[\l]\to[\l]$ is weakly increasing since $\mu$ is weakly decreasing.
It has a fixed point $b$ since the sequence $j_1,\,j_2\dots$ defined
by $j_1=1,\,j_{m+1}=\mu(\mu(j_m))$ is weakly increasing and must
stabilize. (i) and (ii) imply that $\mu(b)=b$. Since $\mu$ is weakly increasing, $i< b$ (resp.\ $i>b$) implies that
$\mu(i)\geq\mu(b)=b>i$ (resp.\ $\mu(i)\leq\mu(b)=b<i$). and
therefore $\mu(\mu(i))>i$ (resp.\ $\mu(\mu(i))<i$).


``(i$'$),(ii$'$),(iii$'$) $\Rightarrow$ (i),(ii)": If $i\leq b$ then $\mu(i)\geq\mu(b)=b\geq i$.
Therefore $\mu(i)<i$ implies $i>b$ which in turn implies
$\mu(\mu(i))< i$ and similarly $\mu(i)>i$ implies $\mu(\mu(i))>i$.
\end{proof}

\begin{rem}\label{intervals} Similarly, for $\mu\in\P^\l_m$ we can consider the fixed points of
$\tmu$: let
$L=\{i\,|\,\tmu(i)>i\},\,M=\{i\,|\,\tmu(i)=i\},\,H=\{i\,|\,\tmu(i)<i\}$.
We claim that $L,\,M$ and $H$ are (possibly empty) intervals. Assume that $i\in H$
and $j>i$. From Lemma \ref{propt} (a) we have that
$i>\tmu(i)=t(i,\mu(i))$ which implies $i>\mu(i)$ and therefore
$j>i>\mu(i)\geq\mu(j)$. As a consequence $\tmu(j)=\mu(j)$ and $j\in
H$. Similarly, $i\in L$ and $j<i$ imply $j\in L.$ This proves that
$L,\,M$ and $H$ are consecutive intervals in $[\l]$. It is easy to see that $\tmu|_L$ and $\tmu|_H$ are weakly decreasing.
\end{rem}


\section{Kostka polynomials}\label{kostka}

Kostka polynomials appear frequently in combinatorics and representation theory. They arise as the connection coefficients
between the Schur and Hall-Littlewood polynomials:
$$s_{\lambda}=\sum_{\mu} K_{\lambda\mu}(q)P_{\mu}(q).$$

The definition that we use in terms of the charge of a tableaux is due to Lascoux and Sch\"utzenberger (\cite{LS78}).
Let $\Tab(\nu,\mu)$ be the set of semistandard tableaux with shape $\lambda$ and content $\mu$.
For any two partitions $\lambda,\mu$ of the same size, the Kostka polynomial is defined by
$$K_{\nu\mu}(q)=\sum_{T\in\Tab(\nu,\mu)}q^{\ch(T)}$$
where $\ch(T)$ is the charge of $T$ as defined in \cite{LS78,M1995}.
We will recall the definition of $\ch(T)$ where $T\in\Tab(\nu,(1^n)),\,n=|\nu|$, i.e., where $T$ is a standard tableaux.
Let $\pi$ be a permutation in $S_n$, regarded  as a standard word in the letters $1,\,2,\,\dots,\,n$. For any $i\in[n]$ the charge value $\chv(i)$ is defined as follows:
$$\chv(i)=\begin{cases}
0&\text{if }i=1\\\chv(i-1)&\text{if $i$ is to the right of $i - 1$ in $\pi$}\\\chv(i-1)+1&\text{if $i$ is to the left of $i - 1$ in $\pi$}
\end{cases}.$$
The charge of $\pi$, denoted $\ch(\pi)$, is $\sum_{i=1}^n \chv(i).$ If $T$ is a standard tableaux, by reading $T$ from right to left in consecutive rows, starting from the top, we obtain a permutation $\pi(T)$, and charge of $T$ is defined to be $\ch(\pi(T))$.

The main result of this section is that the generating function of the size of the partitions in $\P^\l_m$ is a Kostka polynomial as in Theorem \ref{kostka}. The idea of the proof is to establish a bijection between both $\P^\l_m$ and $\Tab_{((2^\l1^{m-1})(1^{2\l+m-1}))}$ and sets of sequences of non-negative integers satisfying some inequalities. Those integers add up to the size of the partition and the charge of the tableaux, respectively. The following example illustrates the main idea.

\begin{example} The tableaux in $\Tab(2^21,1^5)$, with their respective words and charges are:
\setlength{\unitlength}{1.5pt}
\begin{center}
\begin{picture}(180,60)

\put(-30,40){$T$:}
\multiput(0,30)(40,0){5}{\line(1,0){10}}
\multiput(0,40)(40,0){5}{\line(1,0){20}}
\multiput(0,50)(40,0){5}{\line(1,0){20}}
\multiput(0,60)(40,0){5}{\line(1,0){20}}
\multiput(0,30)(40,0){5}{\line(0,1){30}}
\multiput(10,30)(40,0){5}{\line(0,1){30}}
\multiput(20,40)(40,0){5}{\line(0,1){20}}
\multiput(3,52)(40,0){5}{1}
\put(13,52){2}
\put(3,42){3}
\put(13,42){4}
\put(3,32){5}

\put(53,52){2}
\put(43,42){3}
\put(53,42){5}
\put(43,32){4}

\put(93,52){3}
\put(83,42){2}
\put(93,42){4}
\put(83,32){5}

\put(133,52){3}
\put(123,42){2}
\put(133,42){5}
\put(123,32){4}

\put(173,52){4}
\put(163,42){2}
\put(173,42){5}
\put(163,32){3}


\put(-30,20){$\pi(T)$:}
\put(0,20){21435}
\put(40,20){21534}
\put(80,20){31425}
\put(120,20){31524}
\put(160,20){41523}
\put(-30,10){$\chv$:}
\put(0,10){10212}
\put(40,10){10211}
\put(80,10){10101}
\put(120,10){10201}
\put(160,10){10100}
\put(-30,0){$\ch(T)$:}
\put(0,0){6}
\put(40,0){5}
\put(80,0){3}
\put(120,0){4}
\put(160,0){2}
\end{picture}
\end{center}
Therefore $K(q)_{(2^21,1^5)}=q^6+q^5+q^4+q^3+q^2.$

To calculate the sizes of the partitions in $\P_2^2$, we count the number of boxes per diagonal:
\begin{center}
\begin{picture}(290,50)
\setlength{\unitlength}{1.2pt}
%\put(20,0){\textcolor{magenta}{*}}
%\put(80,0){\textcolor{green}{*}}
%\put(140,0){\textcolor{cyan}{*}}
%\put(200,0){\textcolor{red}{*}}
%\put(260,0){\textcolor{blue}{*}}

\put(5,10){$\mu:$}
\put(20,10){(1,1)}
\put(80,10){(2,1)}
\put(140,10){(2,2)}
\put(200,10){(3,2)}
\put(260,10){(3,3)}

\put(0,0){$|\mu|:$}
\put(25,0){2}
\put(85,0){3}
\put(145,0){4}
\put(205,0){5}
\put(265,0){6}

\thicklines

{\color{gray}
\multiput(20,20)(0,10){3}{\line(1,0){30}}
\multiput(20,20)(10,0){4}{\line(0,1){20}}

\multiput(80,20)(0,10){3}{\line(1,0){30}}
\multiput(80,20)(10,0){4}{\line(0,1){20}}

\multiput(140,20)(0,10){3}{\line(1,0){30}}
\multiput(140,20)(10,0){4}{\line(0,1){20}}

\multiput(200,20)(0,10){3}{\line(1,0){30}}
\multiput(200,20)(10,0){4}{\line(0,1){20}}

\multiput(260,20)(0,10){3}{\line(1,0){30}}
\multiput(260,20)(10,0){4}{\line(0,1){20}}
}

\put(20,20){\line(0,1){20}}\put(30,20){\line(0,1){20}}
\put(20,20){\line(10,0){10}}\put(20,30){\line(1,0){10}}\put(20,40){\line(10,0){10}}

\put(80,20){\line(0,1){20}}\put(90,20){\line(0,1){20}}\put(100,30){\line(0,1){10}}
\put(80,20){\line(10,0){10}}\put(80,30){\line(1,0){20}}\put(80,40){\line(10,0){20}}

\put(140,20){\line(0,1){20}}\put(150,20){\line(0,1){20}}\put(160,20){\line(0,1){20}}
\put(140,20){\line(10,0){20}}\put(140,30){\line(1,0){20}}\put(140,40){\line(10,0){20}}

\put(200,20){\line(0,1){20}}\put(210,20){\line(0,1){20}}\put(220,20){\line(0,1){20}}\put(230,30){\line(0,1){10}}
\put(200,20){\line(10,0){20}}\put(200,30){\line(1,0){30}}\put(200,40){\line(10,0){30}}

\put(260,20){\line(0,1){20}}\put(270,20){\line(0,1){20}}\put(280,20){\line(0,1){20}}\put(290,20){\line(0,1){20}}
\put(260,20){\line(10,0){30}}\put(260,30){\line(1,0){30}}\put(260,40){\line(10,0){30}}

\multiput(12,32)(60,0){5}{{\tiny $\searrow$}}
\multiput(12,42)(10,0){3}{{\tiny $\searrow$}}
\put(8, 37){1}
\put(8, 47){1}
\put(18, 47){0}
\put(28, 47){0}

\multiput(72,42)(10,0){3}{{\tiny $\searrow$}}
\put(68, 37){1}
\put(68, 47){1}
\put(78, 47){1}
\put(88, 47){0}

\multiput(132,42)(10,0){3}{{\tiny $\searrow$}}
\put(128, 37){1}
\put(128, 47){2}
\put(138, 47){1}
\put(148, 47){0}

\multiput(192,42)(10,0){3}{{\tiny $\searrow$}}
\put(188, 37){1}
\put(188, 47){2}
\put(198, 47){1}
\put(208, 47){1}

\multiput(252,42)(10,0){3}{{\tiny $\searrow$}}
\put(248, 37){1}
\put(248, 47){2}
\put(258, 47){2}
\put(268, 47){1}


\end{picture}
\end{center}
Therefore $\sum_{\mu\in\P_2^2}q^{|\mu|}=q^6+q^5+q^4+q^3+q^2.$

It is easy to see that there is a bijection between the charge values (except $0=\chv(1)$) of the words in $\Tab(2^21,1^5)$ and the number of boxes in the diagonals in the partitions in $\P_2^2.$

\end{example}


\begin{proof}[Proof of Theorem \ref{kostka}]


For any partition $\mu$ with $\l$ parts of size at most $\l+m-1$, we regard its Young diagram as contained in an $\l\times(\l+m-1)$ box. Number the $2\l+m-2$ diagonals using numbers between $-\l+1$ and $\l+m-2$, as indicated in Figure \ref{figdiag}. Define $a:\{\mu:l(\mu)=\l,\,\mu_1\le \l+m-1\}\to \N^{2\l+m-2},\,\mu\mapsto(a_{-\l+1},a_{-\l+2},\dots, a_{\l+m-2})$ where $a_i$ the number of boxes if the diagram of $\mu$ in the $i$th diagonal.

\begin{figure}[h]\label{figdiag}
\begin{center}
\setlength{\unitlength}{0.5mm}\begin{picture}(150,60)
{\color{gray} \multiput(10,0)(0,10){6}{\line(1,0){70}}
\multiput(10,0)(10,0){8}{\line(0,1){50}}}
\thicklines
\put(10,0){\line(1,0){20}} \put(30,10){\line(1,0){20}} \put(50,40){\line(1,0){10}}
\put(30,0){\line(0,1){10}} \put(50,10){\line(0,1){30}} \put(60,40){\line(0,1){10}}

\multiput(3,52)(10,0){7}{$\searrow$} \multiput(3,52)(0,-10){5}{$\searrow$}
\put(-2,17){-4} \put(-2,27){-3} \put(-2,37){-2} \put(-2,47){-1}
\put(0,57){0} \put(10,57){1} \put(20,57){2} \put(30,57){3} \put(40,57){4} \put(50,57){5} \put(60,57){6}

\put(90,40){$\l=5,\,m=3$}
\put(90,30){$\mu=(54^32)$}
\put(90,20){$a(\mu)=(1,2,2,3,4,3,2,1,1,0,0)$}

\end{picture}
\end{center}\caption{An example of $a:\{\mu:l(\mu)=\l,\,\mu_1\le \l+m-1\}\to \N^{2\l+m-2}$}
\end{figure}

\begin{lemma}\label{lemmadiag}\
\begin{enumerate}
\item[(a)] A sequence $(a_{-\l+1},a_{-\l+2},\dots, a_{\l+m-2})\in\N^{2\l+m-2}$ is in $a(\{\mu:l(\mu)=\l,\,\mu_1\le \l+m-1\})$ if and only if $a_{-l+1}=1,\,a_{\l+m-2}\in\{0,1\},\,a_{j+1}-a_j\in\{0,1\}$ if $j=0,\dots,m+\l-3$, and $a_{j+1}-a_j\in\{0,-1\}$ if $j=-\l+1,\dots,-1$.
\item[(b)] A sequence $(a_{-\l+1},a_{-\l+2},\dots, a_{\l+m-2})$ satisfying the conditions in part (a) is in $a({\P^\l_m})$ if and only if $a_{-j}>a_{m+j}$ for $j=0,\dots,\l-2.$
\end{enumerate}
\end{lemma}

\begin{proof}
To prove the ``only if" part, recall the definition of the Frobenius symbol of a partition $\mu$ (see \cite{AE}): if its Young diagram has $h$ squares in the diagonal, its Frobenius symbol is defined as
$${d_1,\dots,d_h}\choose{e_1,\dots,e_h}$$
where $d_i$ and $e_i$ are the number of squares to the right of and below, respectively, the $i$th diagonal square. The number of squares in the diagonal of $\mu$ is $a_0$. Since the entries in each of the rows of the Frobenius symbol are weakly decreasing they can be regarded as partitions, and it is easy to see that
$(a_{-1},\dots, a_{-\l})$ and $(a_{1},\dots, a_{\l+m-2})$ are conjugate to $(e_1,\dots,e_h)$ and $(d_1,\dots,d_h)$, respectively.
%$(a_{-1},\dots, a_{-\l})$ and $(a_{1},\dots, a_{\l+m-2})$ are conjugate to the partitions of the Frobenius symbol of $\mu$.
The entries in each of the rows of the Frobenius symbol are distinct and therefore their conjugates satisfy that consecutive parts differ by at most 1 and clearly $a_{-\l+1}=0$. The converse is similar. This proves (a).

For (b), let $\t\mu$ as in section \ref{ineq}.2. Consider $a(\t\mu)=(\t a_{-\l+1},\dots, \t a_{\l-1})$. Clearly $\t a_{-j}=a_{-j}$ and $\t a_{j}=a_{m+j-1}$ for $j=0,\dots,\l-1.$ So we have to prove that $\t\mu$ satisfies the conditions in Theorem \ref{tilde} if and only if $\t a_{-j}>\t a_{j+1}$ for $j=0,\dots,\l-2.$ It is not hard to see that $\tilde a_j=\max\{r\,|\,\t\mu(r)\geq j+r\}$ and  $\tilde a_{-j}=\max\{r\,|\,\t\mu(j+r)\geq r\}$.

Assume that $\t\mu$ satisfies the conditions in Theorem \ref{tilde}. We are to prove that  $\{r\,|\,\t\mu(r)\geq j+1+r\}\subsetneq\{r\,|\,\t\mu(j+r)\geq r\}$. To prove the inclusion, assume on the contrary that there is in an $r$ so that $\t\mu(r)\geq j+1+r>r$ and $\tmu(j+r)< r\leq r+j$, so using the notation in Remark \ref{intervals}, $r\in L$ and $r+j\in H$. Since $L$ and $H$ are intervals containing the lower and higher numbers in $[n]$ and $\tmu$ is weakly decreasing when restricted to those intervals, then $\tmu(j+r)< r$ implies that  $\tmu(\tmu(j+r))\geq \tmu(r)>j+r$, contradicting $\tmu(\tmu(j+r))< r+j$.

This proves that $\t a_{-j}\geq\t a_{j+1}$. If the equality holds, consider $s=\t a_{-j}=\t a_{j+1}$, i.e., $\tmu(j+s)\geq s,\,\tmu(s)\geq j+s+1$ but $\t\mu(j+s+1)< s+1,\,\tmu(s+1)< j+s+2$.
This implies that $\tmu(s)>s$ and $\t\mu(j+s+1)<j+s+1$ so $s\in L$ and $j+s+1\in H.$ Since $\tmu(j+s+1)\leq s$ then $\tmu(\tmu(j+s+1))\geq\tmu(s)\geq j+s+1$, contradicting that $\tmu(\tmu(j+s+1))<j+s+1$.

To prove the converse, assume that $\t a_{j+1}<\t a_{-j}$, i.e., $\max\{r\,|\,\t\mu(r)\geq j+1+r\}\leq\max\{r\,|\,\t\mu(j+r)\geq r\}$ for $j=0,\dots,\l-2$; and we want to prove that the conditions in Theorem \ref{tilde} hold. If $\t\mu(i)>i$, let $j=\t\mu(i)-i-1\geq0$. Then $i\in\{r\,|\,\t\mu(r)\geq j+1+r\}$ so $i\leq\t a_{j+1}<\t a_{-j}$. This implies that $i+1\in\{r\,|\,\t\mu(j+r)\geq r\}$ so $\tmu(\tmu(i))=\tmu(j+i+1)\geq i+1>i.$ That if $\t\mu(i)<i$ then $\tmu(\tmu(i))<i$ is proved analogously.
\end{proof}

Now we establish a bijection between $\Tab_{(2^\l1^{m-1})(1^{2\l+m-1}))}$ and a sequence of non-negative integers.

\begin{lemma}\label{lemmacharge}
For $T\in\Tab(2^\l1^{m-1})(1^{2\l+m-1}))$, let $x_1,\,\dots,\, x_{\l+m-1}$ and $y_1,\,\dots,\,y_{\l}$  be the entries in the first and second columns of  of $T$, respectively, and let $b_1,\,\dots,\, b_{\l+m-1}$ and  $c_1,\,\dots,\,c_{\l}$ and  be their their charge values. Then the following are true:
\begin{enumerate}
\item $b_1=0,\,b_{i+1}-b_{i}\in\{0,1\},\,i=1,\,\dots,\,\l+m-2$, \item $c_1=1,\,c_{i+1}-c_{i}\in\{0,1\},\,i=1,\,\dots,\,\l-1,\,b_i<c_i,\,i=1,\,\dots,\,\l-1$ \item $b_{\l+m-1}-c_\l\in\{0,1\}$.
\end{enumerate}

Conversely, two sequences satisfying these conditions form the list charge values of a tableau in $\Tab_{(2^\l1^{m-1})(1^{2\l+m-1}))}$.
\end{lemma}

\begin{proof}

The word of $T$ is $y_1,x_1,y_2,x_2,\dots,y_\l,x_\l,x_{\l+1},\dots,x_{\l+m-1}$ and that $T$ is standard means that $x_1<x_2<\dots<x_{\l+m-1},\,y_1<y_2<\dots<y_{\l}$ and $x_1<y_1,\dots,x_\l<y_\l$. Clearly $b_1=\chv(1)=0$ and $c_1=\chv(y_1)=1.$ $b_{i+1}\geq b_i$ since $x_{i+1}$ is larger and to the right of $x_i$. If $x_{i+1}=x_i+1$ then  $b_{i+1}=b_i$. If $x_{i+1}>x_i+1$ then $x_i+1=y_j$ for some $j\leq i$ and furthermore $y_j,\,\dots,\,y_{i}$ are precisely the consecutive numbers between $x_i$ and $x_{i+1}$. Therefore $\chv(x_i)+1=\chv(y_j)=\dots=\chv(y_i)=\chv(x_{i+1})$. This proves that $b_{i+1}-b_{i}\in\{0,1\}$. Similar considerations prove $c_{i+1}-c_{i}\in\{0,1\}$. That $b_i>c_i$ follows from the fact that $y_i$ is greater and to the left of $x_i$. Since the $y_\l>x_1,\,\dots,\, x_{\l+m-1},y_1,\,\dots,\, y_{\l+m-1}$ then $b_{\l+m-1}-c_\l\in\{0,1\}$.

For the converse, note that it is possible to reconstruct the word whose charge values are $$c_1,b_1,c_2,b_2,\dots,c_\l,b_\l,b_{\l+1},\dots,b_{\l+m-1}$$ as follows: find all the zeroes, from left to right they correspond to the first numbers $1,2,3,\dots$. Then find the ones and continue on with the next numbers that have not been used and so forth. It is clear that the inequalities for $b_1,\,\dots,\, b_{\l+m-1}$ and  $c_1,\,\dots,\,c_{\l}$ imply those for $x_1,\,\dots,\, x_{\l+m-1}$ and $y_1,\,\dots,\,y_{\l}$ so that we get the word of a standard tableaux.
\end{proof}

To complete the proof of Theorem \ref{KostkaPol}, notice that there is a bijection between the sequences described in Lemmas \ref{lemmacharge} and \ref{lemmadiag} (b): the sequence $(b_1,\,\dots,\, b_{\l+m-1},c_1,\,\dots,\,c_{\l})$ corresponds to the sequence $(c_1,c_2,\dots,c_\l,b_{\l+m-1},b_{\l+m-2},\dots,b_2)\in a(\P^\l_m)$. Under this bijection, a partition $\mu\in\P^{\l}_m$ corresponds to a tableaux of charge $|\mu|$ since $|\mu|$ is equal to the sum of the elements of $a(\mu)$ which in turn is equal to the sum of the charge values of the associated tableaux.
\end{proof}

\begin{example}
Let $\mu$ be the partition in Figure \ref{figdiag}, so $a(\mu)=(1,2,2,3,4,3,2,1,1,0,0)$. We can recover
the standard word with charge values equal to $0,1,0,2,0,2,1,3,1,4,2,3$:
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$i$&1&4&2&7&3&8&5&10&6&12&9&11\\\hline
$\chv(i)$&0&1&0&2&0&2&1&3&1&4&2&3\\\hline
\end{tabular}
\end{center}
This word corresponds to the following standard tableaux:
\begin{center}
\setlength{\unitlength}{0.5mm}\begin{picture}(20,70)
\multiput(0,70)(0,-10){6}{\line(1,0){20}}
\put(0,70){\line(0,-1){70}}\put(10,70){\line(0,-1){70}}\put(20,70){\line(0,-1){50}}
\put(0,0){\line(1,0){10}}\put(0,10){\line(1,0){10}}
\put(1.5,3){11}\put(3,13){9}\put(3,23){6}\put(3,33){5}\put(3,43){3}\put(3,53){2}\put(3,63){1}
\put(11.5,23){12}\put(11.5,33){10}\put(13,43){8}\put(13,53){7}\put(13,63){4}
\end{picture}
\end{center}
\end{example}



\section{Trees, forests and Catalan numbers} \label{bijections}

In this section we will define a bijection between
$\P^\l$ (resp.\ $\P^\l_m$) and a family
enumerated by the Catalan (resp.\ ballot) numbers.
The Catalan numbers appear in various counting problems, see
\cite{Stanley} for a 66 interpretations of the Catalan numbers. Some of these generalize to the ballot numbers.

Consider the set
$\T_\l$ of pairs $(T^-,T^+)$ of rooted trees with a total of
$\l-1$ edges. These pairs are in bijection with trees with $\l$
edges: cutting the rightmost branch from the root creates such a
pair, and viceversa, we can attach a tree as the rightmost subtree
of the root (See Figure \ref{2trees} for an example). Therefore
there are $c_{\l}$ pairs of rooted trees with a total of $\l-1$
edges. We will establish a bijection between $\T_\l$ and $\P^\l$.% in order to prove Theorem \ref{thm1}(i).


\begin{figure}[h]
\begin{center}
\psset{radius=.4mm} \pstree[levelsep=0.9cm]{\TC}{
\pstree{\TC}{\TC\TC\pstree{\TC}{\TC}\TC} \pstree{\TC}{\TC}
\pstree{\TC}{\TC\pstree{\TC}{\TC\TC}\TC} }
$$\mapsto\begin{pmatrix}
\psset{radius=0.4mm} \pstree[levelsep=0.9cm]{\TC}{
\pstree{\TC}{\TC\TC\pstree{\TC}{\TC}\TC} \pstree{\TC}{\TC}
 }&
,
 & \pstree[levelsep=0.9cm]{\TC}{\TC\pstree{\TC}{\TC\TC}\TC}
\end{pmatrix}\in\T_\l$$
%\Bigg(\psset{radius=0.4mm} \pstree[levelsep=0.9cm]{\TC}{
%\pstree{\TC}{\TC\TC\pstree{\TC}{\TC}\TC} \pstree{\TC}{\TC}
% }, \pstree[levelsep=0.9cm]{\TC}{\TC\pstree{\TC}{\TC\TC}\TC} \Bigg)
\end{center}\caption{Cutting a tree in two.}\label{2trees}
\end{figure}



The generalized Catalan numbers are defined by the formula
$C_{k,\gamma}(n)=\frac{\gamma}{nk+\gamma} {{kn+\gamma}\choose{n}}$
(see \cite{GS2006, Chen2008, Stanley}). $C_{k,\gamma}(n)$ is the number of ordered forests
with
 $\gamma$ $k$-ary trees and with total
number of $n$ internal vertices. The ballot numbers are a special
case of the generalized Catalan numbers since $b_{\l,m-1}=
C_{2,m}(\l)$. Therefore $b_{\l,m-1}$ is the number of ordered
forests with
 $m$ binary trees and with total number of $\l$ internal vertices, or equivalently,
 the number of ordered forests with $m$ trees and with total number of $\l$ edges, since there is a
bijection between binary trees with $n$ vertices and rooted trees
with $n$ edges. As before, we can cut non-empty trees to obtain
pairs of trees. We will use this to establish Theorem \ref{thm2}.

\subsection{$\boldsymbol{\P^\l}$ and Trees}
Now we describe how to create an element of $\P^\l$ from a pair
of rooted trees $(T^-,T^+)$. Number the levels of both trees so
that the roots are located in level 1. Starting from the deepest
level and moving up and from left to right, label the vertices of
the odd levels of $T^-$ and the even levels of $T^+$ consecutively
with the numbers $1,2,3\dots$, and label the vertices of the even
levels of $T^-$ and the odd levels of $T^+$ consecutively with the
numbers $\l, \l-1,l-2\dots.$ Then label the roots of $T^\pm$ with
$b^\pm$, where $b\in[\l]$ is the only number that has not been
used so far. To define $\mu:[\l]\to[\l]$ let $\mu(i)$ be the
parent of $i$ (if the parent of $i$ is $b^\pm$, define
$\mu(i)=b$), and $\mu(b)=b$.


\begin{example}\label{ex14} Consider the pair of trees in Figure
\ref{2trees}. After numbering the nodes, we get the pair of trees
in Figure \ref{2labelledtrees}.

\begin{figure}[h]
\begin{center}
\psset{radius=3pt} %\pstree[levelsep=1.2cm]
\pstree[levelsep=35pt]{\TC~{$9^-$}}{
\pstree{\TC~{11}}{\TC~{1}\TC~{2}\pstree{\TC~{3}}{\TC~{14}}\TC~{4}}
\pstree{\TC~{10}}{\TC~{5}}
 } \qquad
 %\pstree[levelsep=1.2cm]
 \pstree[levelsep=35pt]{\TC~{$9^+$}}{\TC~{6}\pstree{\TC~{7}}{\TC~{13}\TC~{12}}\TC~{8}}
\end{center}\caption{A pair of labeled trees}\label{2labelledtrees}
\end{figure}


The corresponding partition is
%Consider the following partition $\mu\in\P^{14}_1$
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$i$&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\\hline
$\mu(i)$&11&11&11&11&10&9&9&9&9&9&9&7&7&3\\\hline
\end{tabular}
\end{center}
%Here $L=\{1,\dots,5\},\,b=6,\,H=\{7,\dots,14\}$. The corresponding pair of trees is
\end{example}


\begin{lemma}
The map $\mu:[\l]\to[\l]$ obtained by this process is a partition in $\P^\l$.
\end{lemma}

\begin{proof}
To simplify the notation, let $L=[b-1],\,H=[\l]\setminus[b].$ We
have to prove that $\mu$ is weakly decreasing and satisfies the
conditions in Lemma \ref{remlambda1}.

It is clear form the construction that $\mu(b)=b$, $i\in L$
implies $\mu(i)\notin L$, and $i\in H$ implies $\mu(i)\notin H$.
Let $1\leq i\leq j<\l$. If $i\in L$ and $j\in H$ then
$\mu(i)\in\{b\}\cup H$ and $\mu(j)\in\{b\}\cup L$. Therefore
$\mu(i)\geq\mu(j).$ Similar considerations hold if one among $i,j$
is equal to $b$. Assume that $i,j\in L$. Then either $i$ is
located at a level deeper than $j$, or they are in the same level
but $i$ is to the left of $j$, and the same is true about their
parents. But their parents $\mu(i),\mu(j)\in\{b\}\cup H$, and
therefore $\mu(i)\geq\mu(j)$. A similar argument works if we
assume $i,j\in H$.

The conditions in Lemma \ref{remlambda1} say
\begin{enumerate}
\item[(i)] $\mu(b)=b.$
\item[(ii)] $i\in L\Rightarrow\mu(\mu(i))>i.$
\item[(iii)] $i\in H\Rightarrow\mu(\mu(i))<i.$
\end{enumerate}

(i) follows from the construction of $\mu$. If $i\in L$ then
either $\mu(\mu(i))$ is two levels above $i$ and therefore
$\mu(\mu(i))>i$, or $\mu(i)=b$, so $\mu(\mu(i))=b>i$. Similar
considerations work if $i\in H.$
\end{proof}

The process can be reversed: for $\mu\in\P^\l$ let $b$ be its
fixed point, and $L,\,H$ as before. We define a pair of trees
$(T^-,T^+)$ with $i\in([l]\setminus\{b\})\cup\{b^-,b^+\}$
as vertex set. The root of $T^\pm$ is $b^\pm$, and the edges are
drawn according to the following rules:
\begin{enumerate}
\item  If $i\in[l]\setminus\{b\}$ and $\mu(i)\neq b$, we draw an
edge $i\to\mu(i)$. \item If $i\in L$ and $\mu(i)=b$, we draw an
edge $i\to b^+$. \item If $i\in H$ and $\mu(i)=b$, we draw an edge
$i\to b^-$.
\end{enumerate}
The vertices in $L$ (resp.\ $H$) are organized increasingly
(resp.\ decreasingly) from left to right. This procedure creates a
bijection between $\T_\l$ and  $\P^\l$


\begin{example}
The following are the $14=C_4$ pairs of rooted trees with 3 edges.

\bigskip
 \psset{radius=2pt}
 \pstree[levelsep=0.5cm]{\Tcircle{}} \
{\pstree[levelsep=0.5cm]{\Tcircle{} }{ \pstree{ \Tcircle{} }{
\Tcircle{} \Tcircle{}}} }
 \qquad
 \pstree[levelsep=0.5cm]{\Tcircle{}
}\ {\pstree[levelsep=0.5cm]{\Tcircle{} }{ \pstree{ \Tcircle{} }{
\Tcircle{}}\Tcircle{}}}
 \qquad \pstree[levelsep=0.5cm]{\Tcircle{}
}\ {\pstree[levelsep=0.5cm]{\Tcircle{} }{
         \Tcircle{}
        \pstree{ \Tcircle{} }{
                     \Tcircle{}}}}
\qquad \pstree[levelsep=0.5cm]{\Tcircle{} } \ \
{\pstree[levelsep=0.5cm]{\Tcircle{} }{
        \pstree{ \Tcircle{} }{
        \pstree{ \Tcircle{} }{
                     \Tcircle{}
                              }
                    }}}
\qquad \pstree[levelsep=0.5cm]{\Tcircle{} }\
{\pstree[levelsep=0.5cm]{\Tcircle{} }{\Tcircle{}
        \Tcircle{}\Tcircle{}}}
 %\newline \bigskip
  \qquad 
{\pstree[levelsep=0.5cm]{\Tcircle{} }{
        \pstree{ \Tcircle{} }{
        \pstree{ \Tcircle{} }{
                     \Tcircle{}
                              }
                    }}}\ \pstree[levelsep=0.5cm]{\Tcircle{} } \qquad \qquad
 \pstree[levelsep=0.5cm]{\Tcircle{} }{
        \pstree{ \Tcircle{} }{
                     \Tcircle{}\Tcircle{}
                              }}\
  %      \pstree[levelsep=0.5cm]{\Tcircle{}}
 
 \bigskip
 
  \pstree[levelsep=0.5cm]{\Tcircle{} }{
        \pstree{ \Tcircle{} }{
                     \Tcircle{}
                              }}\
        \pstree[levelsep=0.5cm]{ \Tcircle{} }{\Tcircle{}}
 \qquad \pstree[levelsep=0.5cm]{ \Tcircle{} }{\Tcircle{}}\
 \pstree[levelsep=0.5cm]{\Tcircle{} }{
        \pstree{ \Tcircle{} }{
                     \Tcircle{}
                              }}
 \qquad \pstree[levelsep=0.5cm]{\Tcircle{} }{
         \Tcircle{}}\
        \pstree[levelsep=0.5cm]{ \Tcircle{} }{
                     \Tcircle{}\Tcircle{}
                              }
\qquad \pstree[levelsep=0.5cm]{\Tcircle{} }{\pstree{ \Tcircle{}
}{
                     \Tcircle{}
                              }
        \Tcircle{}}\ \pstree[levelsep=0.5cm]{\Tcircle{}}
%\newline\bigskip
\, \qquad
 {\pstree[levelsep=0.5cm]{\Tcircle{} }{
         \Tcircle{}
        \pstree{ \Tcircle{} }{
                     \Tcircle{}}}}\ \pstree[levelsep=0.5cm]{\Tcircle{} }
\quad\qquad \pstree[levelsep=0.5cm]{ \Tcircle{} }{
                     \Tcircle{}\Tcircle{}
                              }\  \pstree[levelsep=0.5cm]{\Tcircle{} }{
         \Tcircle{}}
\qquad {\pstree[levelsep=0.5cm]{\Tcircle{} }{\Tcircle{}
        \Tcircle{}\Tcircle{}}}\ \pstree[levelsep=0.5cm]{\Tcircle{} }
%\end{center}

%\caption{The 14 rooted trees with 3 edges}
%\end{figure}

%\psset{radius=1mm} \pstree[levelsep=0.5cm]{\Tcircle{}
%}{\pstree{\Tcircle{} }{ \pstree{ \Tcircle{} }{ \Tcircle{}
%\Tcircle{}}} }\quad \pstree[levelsep=0.5cm]{\Tcircle{}
%}{\pstree{\Tcircle{} }{ \pstree{ \Tcircle{} }{
%\Tcircle{}}\Tcircle{}}}
% \quad\pstree[levelsep=0.5cm]{\Tcircle{}
%}{\pstree{\Tcircle{} }{
%         \Tcircle{}       \pstree{ \Tcircle{} }{ \Tcircle{}}}}
%\quad\pstree[levelsep=0.5cm]{\Tcircle{} }{\pstree{\Tcircle{} }{
 %       \pstree{ \Tcircle{} }{
%        \pstree{ \Tcircle{} }{                    \Tcircle{}} }}}
%\quad\pstree[levelsep=0.5cm]{\Tcircle{} }{\pstree{\Tcircle{}
%}{\Tcircle{}
%        \Tcircle{}\Tcircle{}}}
%                    \quad a\pstree[levelsep=0.5cm]{\Tcircle{} }{
%        \pstree{ \Tcircle{} }{
%                     \pstree{ \Tcircle{} }{\Tcircle{}}
 %                             }       \Tcircle{}}
%\quad\pstree[levelsep=0.5cm]{\Tcircle{} }{
%        \pstree{ \Tcircle{} }{
%                     \Tcircle{}\Tcircle{}                              }
%        \Tcircle{}}
%                    \quad\pstree[levelsep=0.5cm]{\Tcircle{} }{
%        \pstree{ \Tcircle{} }{                     \Tcircle{}}
 %       \pstree{ \Tcircle{} }{\Tcircle{}}
 %                   }
%\quad\pstree[levelsep=0.5cm]{\Tcircle{} }{
%         {\Tcircle{}}
%        \pstree{ \Tcircle{} }{
 %                    \pstree{ \Tcircle{} }{\Tcircle{}}                  } }
%\quad\pstree[levelsep=0.5cm]{\Tcircle{} }{
%         \Tcircle{}
%        \pstree{ \Tcircle{} }{
%                     \Tcircle{}\Tcircle{}                        }}
%\quad\pstree[levelsep=0.5cm]{\Tcircle{} }{\pstree{ \Tcircle{} }{
%                     \Tcircle{}                              }
%        \Tcircle{}\Tcircle{}}
%\quad\pstree[levelsep=0.5cm]{\Tcircle{} }{\Tcircle{}
%        \pstree{ \Tcircle{} }{
%                     \Tcircle{}                              }\Tcircle{}}
%\quad\pstree[levelsep=0.5cm]{\Tcircle{} }{\Tcircle{}
%        \Tcircle{}\pstree{ \Tcircle{} }{
 %                    \Tcircle{}                             }}
%\quad\pstree[levelsep=0.5cm]{\Tcircle{} }{\Tcircle{}
%        \Tcircle{}\Tcircle{}\Tcircle{}}
\bigskip
The following are the labeling of the nodes following the
algorithm described before, and the corresponding partitions.
These are in fact the 14 partitions in $\P^4_1.$
\bigskip

%\begin{figure}[h]\label{c4part}
 \pstree[levelsep=30pt]{\Tcircle{$2^-$}} \
{\pstree[levelsep=30pt]{\Tcircle{$2^+$} }{ \pstree{ \Tcircle{1} }{
\Tcircle{4} \Tcircle{3}}} }
 $\mu=(2,2,1,1)$\qquad\qquad
 \pstree[levelsep=30pt]{\Tcircle{$3^-$}
}\ {\pstree[levelsep=30pt]{\Tcircle{$3^+$} }{ \pstree{ \Tcircle{1} }{
\Tcircle{4}}\Tcircle{2}}}$\mu=(3,3,3,1)$
 \\ \pstree[levelsep=30pt]{\Tcircle{$3^-$}
}\ {\pstree[levelsep=30pt]{\Tcircle{$3^+$} }{
         \Tcircle{1}
        \pstree{ \Tcircle{2} }{
                     \Tcircle{4}}}}$\mu=(3,3,3,2)$
\qquad\qquad \pstree[levelsep=30pt]{\Tcircle{$3^-$} }\
{\pstree[levelsep=30pt]{\Tcircle{$3^+$} }{
        \pstree{ \Tcircle{2} }{
        \pstree{ \Tcircle{4} }{
                     \Tcircle{1}
                              }
                    }}}\ $\mu=(4,3,3,2)$\\
\qquad  \pstree[levelsep=30pt]{\Tcircle{$4^-$} }\
{\pstree[levelsep=30pt]{\Tcircle{$4^+$} }{\Tcircle{1}
        \Tcircle{2}\Tcircle{3}}}\ $\mu=(4,4,4,4)$
\qquad\qquad
{\pstree[levelsep=30pt]{\Tcircle{$2^-$} }{
        \pstree{ \Tcircle{3} }{
        \pstree{ \Tcircle{1} }{
                     \Tcircle{4}
                              }
                    }}}\ \pstree[levelsep=30pt]{\Tcircle{$2^+$} }\ \quad
                    $\mu=(3,2,2,1)$\
\\\\
 \pstree[levelsep=30pt]{\Tcircle{$3^-$} }{
        \pstree{ \Tcircle{4} }{
                     \Tcircle{1}\Tcircle{2}
                              }}\
        \pstree[levelsep=30pt]{\Tcircle{$3^+$}}\ \quad $\mu=(4,4,3,3)$
 \qquad\qquad \pstree[levelsep=30pt]{\Tcircle{$3^-$} }{
        \pstree{ \Tcircle{4} }{
                     \Tcircle{1}
                              }}\
        \pstree[levelsep=30pt]{ \Tcircle{$3^+$} }{\Tcircle{2}}\ \quad $\mu=(4,3,3,3)$
\\\\
 \qquad \pstree[levelsep=30pt]{ \Tcircle{$2^-$} }{\Tcircle{3}}\
 \pstree[levelsep=30pt]{\Tcircle{$2^+$} }{
        \pstree{ \Tcircle{1} }{
                     \Tcircle{4}
                              }}\ \quad $\mu=(2,2,2,1)$
 \qquad\qquad \pstree[levelsep=30pt]{\Tcircle{$3^-$} }{
         \Tcircle{4}}\
        \pstree[levelsep=30pt]{ \Tcircle{$3^+$} }{
                     \Tcircle{1}\Tcircle{2}
                              }\ \quad $\mu=(3,3,3,3)$\
\\\\
\qquad \pstree[levelsep=30pt]{\Tcircle{$2^-$} }{\pstree{
\Tcircle{4} }{
                     \Tcircle{1}
                              }
        \Tcircle{3}}\ \pstree[levelsep=30pt]{\Tcircle{$2^+$}} \ \quad $\mu=(4,2,2,2)$\ \qquad\qquad
 {\pstree[levelsep=30pt]{\Tcircle{$2^-$} }{
         \Tcircle{4}
        \pstree{ \Tcircle{3} }{
                     \Tcircle{1}}}}\ \pstree[levelsep=30pt]{\Tcircle{$2^+$} }\ \quad $\mu=(3,2,2,2)$ %!!!!!
                    \qquad\qquad
 \\\pstree[levelsep=30pt]{ \Tcircle{$2^-$} }{
                     \Tcircle{4}\Tcircle{3}
                              }\  \pstree[levelsep=30pt]{\Tcircle{$2^+$} }{
         \Tcircle{1}}\ \quad $\mu=(2,2,2,2)$
\qquad {\pstree[levelsep=30pt]{\Tcircle{$1^-$} }{\Tcircle{4}
        \Tcircle{3}\Tcircle{2}}}\ \pstree[levelsep=30pt]{\Tcircle{$1^+$} } \ \quad $\mu=(1,1,1,1)$
%\caption{The 14 partitions in $\P^4(1)$.}
%\end{figure}
\end{example}

%\psset{radius=1mm} \pstree[levelsep=30pt]{\Tcircle{3'}
%}{\pstree{\Tcircle{3} }{ \pstree{ \Tcircle{4} }{ \Tcircle{1}
%\Tcircle{2}}} }  $\mu=(4,4,3,3)$\qquad
% \pstree[levelsep=30pt]{\Tcircle{2'}
%}{\pstree{\Tcircle{2} }{
%        \pstree{ \Tcircle{4} }{
%                     \Tcircle{1}
%                              }
%        \Tcircle{3}
%                    }}  $\mu=(4,2,2,2)$
%\pstree[levelsep=30pt]{\Tcircle{2'} }{\pstree{\Tcircle{2} }{
%         \Tcircle{4}
%        \pstree{ \Tcircle{3} }{
%                     \Tcircle{1}
%                              }
%                    }}  $\mu=(3,2,2,2)$
%\qquad \pstree[levelsep=30pt]{\Tcircle{2'} }{\pstree{\Tcircle{2} }{
%        \pstree{ \Tcircle{3} }{
%        \pstree{ \Tcircle{1} }{
%                     \Tcircle{4}
%                              }
%                    }}}  $\mu=(3,2,2,1)$
% \pstree[levelsep=30pt]{\Tcircle{1'} }{\pstree{\Tcircle{1}
%}{\Tcircle{4}
%        \Tcircle{3}\Tcircle{2}}}  $\mu=(1,1,1,1)$
%\qquad
 %                   \pstree[levelsep=30pt]{\Tcircle{3'} }{
 %       \pstree{ \Tcircle{2} }{
 %                    \pstree{ \Tcircle{4} }{\Tcircle{1}}
 %                             }
 %       \Tcircle{3}
 %                   }  $\mu=(4,3,3,2)$
%
%\pstree[levelsep=30pt]{\Tcircle{2'} }{
%        \pstree{ \Tcircle{1} }{
%                     \Tcircle{4}\Tcircle{3}
%                              }
%        \Tcircle{2}
%                    }  $\mu=(2,2,1,1)$
%\qquad \pstree[levelsep=30pt]{\Tcircle{2'} }{
%        \pstree{ \Tcircle{1} }{
%                     \Tcircle{4}
%                              }
%        \pstree{ \Tcircle{2} }{\Tcircle{3}}
%                    }  $\mu=(2,2,2,1)$

%\pstree[levelsep=30pt]{\Tcircle{3'} }{
%         {\Tcircle{2}}
%        \pstree{ \Tcircle{3} }{
%                     \pstree{ \Tcircle{4} }{\Tcircle{1}}
%                              }
%                    }  $\mu=(4,3,3,3)$
%\qquad \pstree[levelsep=30pt]{\Tcircle{2'} }{
%         \Tcircle{1}
%        \pstree{ \Tcircle{2} }{
%                     \Tcircle{4}\Tcircle{3}
%                              }
 %                   } $\mu=(2,2,2,2)$

 %\pstree[levelsep=30pt]{\Tcircle{3'} }{\pstree{ \Tcircle{1}
%}{
%                     \Tcircle{4}
%                              }
%        \Tcircle{2}\Tcircle{3}} $\mu=(3,3,3,1)$
%\qquad \pstree[levelsep=30pt]{\Tcircle{3'} }{\Tcircle{1}
%        \pstree{ \Tcircle{2} }{
%                     \Tcircle{4}
%                              }\Tcircle{3}}  $\mu=(3,3,3,2)$
%\qquad \pstree[levelsep=30pt]{\Tcircle{3'} }{\Tcircle{1}
%        \Tcircle{2}\pstree{ \Tcircle{3} }{
%                     \Tcircle{4}
%                              }} $\mu=(3,3,3,3)$
%\qquad \pstree[levelsep=30pt]{\Tcircle{4'} }{\Tcircle{1}
%        \Tcircle{2}\Tcircle{3}\Tcircle{4}} $\mu=(4,4,4,4)$
\bigskip
Now we want to describe the action of $\tau:\P^\l\to\P^\l$.
$\tau$ replaces the label $i$ by $\l+1-i$, except $b^-$ and $b^+$
which are replaced by $(\l+1-b)^+$ and $(\l+1-b)^-$, respectively.
The two trees exchange positions and the levels that contained the
increasing sequence $1,2,3,\dots$ now contain the decreasing
sequence $\l,\l-1,\l-2,\dots$ and viceversa.



\begin{example} Consider the partition in Example \ref{ex14}:
$$\mu=(11,11,11,11,10,9,9,9,9,9,9,7,7,3)$$
$$\tau(\mu)=(12,8,8,6,6,6,6,6,6,5,4,4,4,4)$$
Their corresponding pairs of trees are shown in Figure
\ref{extau}.
\end{example}
\begin{figure}[h]
\begin{center}
\psset{radius=1mm} \pstree[levelsep=1.1cm]{\TC~{$9^-$}}{
\pstree{\TC~{11}}{\TC~{1}\TC~{2}\pstree{\TC~{3}}{\TC~{14}}\TC~{4}}
\pstree{\TC~{10}}{\TC~{5}}
 }\quad
 \pstree[levelsep=0.9cm]{\TC~{$9^+$}}{\TC~{6}\pstree{\TC~{7}}{\TC~{13}\TC~{12}}\TC~{8}}
\end{center}
\begin{center}\psset{radius=1mm}\pstree[levelsep=1.1cm]{\TC~{$6^+$}}{\TC~{9}
\pstree{\TC~{8}}{\TC~{2}\TC~{3}}\TC~{7}}\quad
 \pstree[levelsep=0.9cm]{\TC~{$6^-$}}{
\pstree{\TC~{4}}{\TC~{14}\TC~{13}\pstree{\TC~{12}}{\TC~{1}}\TC~{11}}
\pstree{\TC~{5}}{\TC~{10}}
 }
\end{center}
\caption{The action of $\tau$}\label{extau}
\end{figure}



\subsection{$\boldsymbol{\P^\l_m}$ and forests}\label{ssec-forests}

%Now we define a bijection between $\P^\l_m$ and a family enumerated by ballot numbers.
Now we describe how to associate to $\mu\in\P^\l_m$ a
$m$-tuple of (possibly empty) pairs of rooted trees.

The roots of the pairs of trees are going to be $\{b^-\,|\,b\in
M\}\cup \{b^+\,|\,b\in M\}$. The vertices that are not roots are
going to be $L\cup H.$ The edges are drawn according to the
following rules:
\begin{enumerate}
\item  If $i\in L\cup H$ and $\mu(i)\notin M$, we draw an edge $i\to\tmu(i)$.
\item If $i\in L$ and $\tmu(i)=b\in M$, we draw an edge $i\to b^+$.
\item If $i\in H$ and $\tmu(i)=b\in M$, we draw an edge $i\to b^-$.
\end{enumerate}
Now we pair the trees with roots $b^-,\,b^+\,(b\in M)$, and we say
that this pair is the $(m-\mu(b)+b)$-th one. Clearly $b\in M$
implies $m-\mu(b)+b\in[m]$ by the definition of $t$, and if $b<b'$
then $m-\mu(b)+b<m-\mu(b')+b'$, so different pairs have different
positions between 1 and $m$.


\begin{example}  Consider the following partition $\mu\in\P^{24}_4$:
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$i$&1&2&3&4&5&6&7&8&9&10&11&12\\\hline
$\mu(i)$&22&22&22&21&21&21&21&20&17&17&17&16\\\hline
\end{tabular}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$i$&13&14&15&16&17&18&19&20&21&22&23&24\\\hline
$\mu(i)$&16&15&15&15&14&14&13&12&6&3&3&3\\\hline
\end{tabular}
\end{center}
Here, $L=\{1,\dots,12\},\,M=\{13,14,15\},\,H=\{16,\dots,24\}$ and $\tmu:[24]\to[24]$ is
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$i$&1&2&3&4&5&6&7&8&9&10&11&12\\\hline
$\tmu(i)$&19&19&19&18&18&18&18&17&14&14&14&13\\\hline
\end{tabular}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$i$&13&14&15&16&17&18&19&20&21&22&23&24\\\hline
$\tmu(i)$&13&14&15&15&14&14&13&12&6&3&3&3\\\hline
\end{tabular}
\end{center}

This map determines 6 trees:

\bigskip
\begin{center}
\psset{radius=1mm} \pstree[levelsep=1.2cm,
treesep=0.5cm]{\TC~{$13^-$}}{
\pstree{\TC~{19}}{\TC~{1}\TC~{2}\pstree{\TC~{3}}{\TC~{24}\TC~{23}\TC~{22}}}}
\pstree[levelsep=1.2cm,treesep=0.5cm]{\TC~{$13^+$}}{\TC~{12}}
\pstree[levelsep=1.2cm, treesep=0.5cm]{\TC~{$14^-$}}{
\pstree{\TC~{18}}{\TC~{4}\TC~{5}\pstree{\TC~{6}}{\TC~{21}}\TC~{7}}
\pstree{\TC~{17}}{\TC~{8}} } \pstree[levelsep=1.2cm,
treesep=0.5cm]{\TC~{$14^+$}}{\TC~{11}\TC~{10}\pstree{\TC~{9}}{\TC~{20}}}
\pstree[levelsep=1.2cm, treesep=0.5cm]{\TC~{$15^-$}}{\TC~{16}}
\TC~{$15^+$}
\end{center}

The pairs with  $13^\pm,\, 14^\pm$ and $15^\pm$ as roots are the
first, third and fourth, respectively, while the second pair is
empty. These 4 pairs of trees correspond to a forest with 4 trees
and total number of 24 edges:

\begin{center}
\psset{radius=1mm} $T_1=$\pstree[levelsep=0.9cm, treesep=0.4cm]{\TC}{
\pstree{\TC}{\TC\TC\pstree{\TC}{\TC\TC\TC}}
\pstree{\TC}{\TC}
 } $T_2=$\pstree[levelsep=0.9cm, treesep=0.4cm]\TC \ \quad
 $T_3=$\pstree[levelsep=0.9cm, treesep=0.4cm]{\TC}{
\pstree{\TC}{\TC\TC\pstree{\TC}{\TC}\TC}
\pstree{\TC}{\TC}\pstree{\TC}{\TC\TC\pstree{\TC}{\TC}}
 }
 $T_4=$\pstree[levelsep=0.9cm, treesep=0.4cm]{\TC}{\TC\TC}
\end{center}
\end{example}

Clearly the process can be reversed, and to every forest with $m$
trees and with total number of $\l$ edges we can associate an
element of $\P^\l_m$.

\section{Representations of $\sl_{n+1}$ and global Weyl modules}

Let $\l,\,m$ be non-negative integers and set $k=2\l+m-1$. Let
$$\Lambda_k=\mathbb{Z}[x_1,\dots,x_k]^{S_k}$$ be the ring of symmetric functions.
%Given a partition with $\mu=(\mu_1,\dots,\mu_\l)$ of length $\l$ let $\rm{comp}(\mu)\subset\mathbb{Z}_+^\l$  be the set of
%compositions in the $S_\l$ orbit of the partition $\mu$ of length $\l$ $(\mu_1,\dots,\mu_l)$.
Let $\rm{comp}(\mu)\subset\mathbb{Z}_+^\l$  be the set of compositions in the $S_\l$ orbit of the partition $\mu$ of length $\l$.
Following \cite{BCDM}, define polynomials
$$\bold{p}_{\mu}(x_1,\dots,x_{2\l})
=\sum_{\mu^*\in\rm{comp}(\mu)}(x_1^{\mu^*_1}-x_2^{\mu^*_1})\dots(x_{2\l-1}^{\mu^*_\l}-x_{2\l}^{\mu^*_\l})$$

Let $\mathcal{M}_{\l,m}$ be the $\Lambda_k$-submodule of $\mathbb{C}[x_1,\dots,x_k]$ spanned by the polynomials $\{\bold{p}(\mu)\,|\,\mu\in\mathbb{Z}_+^\l\}$. This module was studied in \cite{BCDM,CG1, CG2, CL, CL11} in connection with the category of finite-dimensional representations of the current algebra of $\sl_2$.

The following conjecture was posed by Bennet et al.
\begin{conj}[\cite{BCDM}]
$\mathcal{M}_{\l,m}$ is a free $\Lambda_k$-module with basis $\{\bold{p}_\mu\,|\,\mu\in\P^\l_m\}$.
\end{conj}
In \cite{BCDM} the conjecture was verified for all $m$ if $\l= 1,\,2$ and for $\l= 3,\, 4$ for
$m = 1,\, 2$.

For example, when $m=1,\,\l=2$ then $\P_1^2=\{(1,1),(2,2)\}$, $\bold{p}_{(1,1)}(x_1,x_2,x_3,x_{4})=(x_1-x_2)(x_3-x_4)$ and $\bold{p}_{(2,2)}(x_1,x_2,x_3,x_{4})=
(x_1^2-x_2^2)(x_3^2-x_4^2)$. For $\mu\in\Z_+^2$ we have that, up to a factor of 2 if $\mu_1=\mu_2,$
$$\bold{p}_{\mu}(x_1,x_2,x_3,x_{4})=
(x_1^{\mu_1}-x_2^{\mu_1})(x_3^{\mu_2}-x_4^{\mu_2})+(x_1^{\mu_2}-x_2^{\mu_2})(x_3^{\mu_1}-x_4^{\mu_1})$$
That $\bold{p}_{\mu}$ is generated by $\bold{p}_{(1,1)}$ and $\bold{p}_{(2,2)}$ can be proved using that $\bold{p}_{(1,1)}$ is a factor of $\bold{p}_{\mu}$,  $\bold{p}_{(2,2)}=(x_1+x_2)(x_3+x_4)\bold{p}_{(1,1)}$ and $\sum_{i<j}x_ix_j-(x_1+x_2)(x_3+x_4)=x_1x_2+x_3x_4.$

The following theorem was recently proved by Chari and Loktev.
\begin{thm}[\cite{CL11}]
%Chari and Loktev \cite{CL11} have established that
$\mathcal{M}_{\l,m}$ is a free $\Lambda_k$-module graded module and the generating function of the degree of the generators is the Kostka polynomial $K_{(2^\l1^{m-1})(1^{2\l+m-1})}$.
\end{thm}

Thus our results prove that the polynomials $\{\bold{p}(\mu)\,|\,\mu\in\P^\l_m\}$ have the right degree. It remains to prove that they are indeed a free basis. Chari and Loktev's conventions are slightly different from ours since we work with the transpose partitions.

Schur's duality establishes a correspondence between irreducible representations of $\mathfrak{gl}_n$ and Young diagrams with at most $n$ rows.
%The duality formula for Kostka polynomials (\cite{SW}, Theorem 7.1) establishes a connection between our Kostka polynomial in Theorem \ref{KostkaPol} and another one with the transpose partition:
%$$K_{(\l+m-1, \l)(1^{2\l+m-1})}(q)=q^{{2\l+m-1}\choose2}K_{(2^\l1^{m-1})(1^{2\l+m-1})}(q^{-1}).$$
Kostka polynomials appear in \cite{CL} in connection to the graded character ${\rm ch}_q$ of modules over the loop algebra $\mathfrak{sl_2}[q]$: Let $V(r)$ be the irreducible $\mathfrak{sl_2}$-module with highest weight $r$. Then
\begin{equation*}\label{sl}
{\rm ch}_q\left(V(1)^{\otimes k}\right)=\sum_{\substack{\l,m\geq 0\\2\l+m-1=k}}K_{(2^\l1^{m-1})(1^{2\l+m-1})}(q){\rm ch}(V(m)).\end{equation*}
(Once again, our conventions are different than the ones in their paper). This formula has a generalization to $\sl_{n+1}$. It would be interesting to find a free basis for $M_{k,\xi}$ when $\xi$ has parts longer than 2. The results of Chari and Loktev in \cite{CL11} indicate the number of generators and their degree in terms of Kostka polynomials, but there is no conjecture regarding a free basis.

The right-hand side of Theorem \ref{KostkaPol} can be rewritten using $q$-binomial coefficients as
$${{2\l+m}\choose{\l}}_q-{{2l+m}\choose{\l-1}}_q$$
This is the $\sl_2$ case of a formula expressing the Kostka polynomial as a sum over generalized $q$-binomial coefficients. In the language of \cite{S} or of \cite{War2004}, these generalized q-binomials are called antisymmetric supernomials.

This poses some questions:

 In the $\sl_2$ case one would expect to find set $R_m^\l$ in such a way that $R_m^\l-R_{m+2}^{\l-1}=P_m^\l.$
More importantly, in the $\sl_2$ case, there should also be a bijection between the partitions in $\P_m^\l$ and the path description of the $\sl_2$ case of the Kostka polynomial given by \cite{NY}, possibly in a way similar to the  bijection in Secion 3. The generating function of Kostka in terms of such paths is precisely what gives rise the the above-mentioned formula for the Kostka polynomials.

 A bijection in the $\sl_2$ case could provide with an important clue as to how to generalize the set $\P_m^\l$ to $\sl_n$. This could ultimately lead to a new combinatorial description of the general Kostka polynomial, and may also shed light on the problem of constructing a free basis of $\M_{k,\xi}$ for $\xi$ having parts exceeding 2.

\begin{thebibliography}{10}

\bibitem{AE} G.~Andrews and K.~Eriksson, {\em Integer partitions} Cambridge University Press, Cambridge, 2004.

\bibitem{BCDM} M.~Bennett, V.~Chari, R.~J.~Dolbin and N.~Manning, {\em Square Partitions and Catalan Numbers}, preprint, ArXiv0912.4983.

\bibitem {CG1} V.~Chari and J.~Greenstein, {\em Current algebras, highest weight categories and quivers}, Adv. in Math.
{\bfseries216} (2007), no. 2, 811--840.

\bibitem{CG2} V.~Chari and J.~Greenstein, {\em A family of Koszul algebras arising from finite-dimensional representations of simple Lie algebras},
 Adv. in Math.  {\bfseries 220}  (2009),  no. 4, 1193--1221.

\bibitem{CL} V.~Chari and S.~Loktev, {\em Weyl, Demazure and fusion modules for the current algebra of $\mathfrak{sl}_{r+1}$.} Adv. Math. 207 (2006), no. 2, 928--960.

\bibitem{CL11} V.~Chari and S.~Loktev, {\em An application of global Weyl modules of $\sl_{n+1}[t]$ to invariant theory}, preprint, arXiv:1104.4048.

\bibitem{Chen2008} R.~Chen, {\em A refinement of the formula for $k$-ary trees and the Gould-Vandermonde's convolution}, Electron. J. Combin. {\bfseries 15} (2008), no. 1.

\bibitem{GS2006} I.~Gessel and S.~Seo, {\em A refinement of Cayley's formula for trees.  } Electron. J. Combin.  {\bfseries11}(2)  (2006),  \#R27.

\bibitem{HP} P.~Hilton and J.~Pedersen, \emph{Catalan numbers, their generalization and their uses}, Math. Intell. \textbf{13} (1991) 64--75.

\bibitem{LS78} A.~Lascoux and M.~P.~Sch\"utzenberger, {\em Sur une conjecture de H.O. Foulkes}, CR Acad. Sci.
Paris 286A (1978), 323--324.

\bibitem{M1995} I.G.~Macdonald, {\em Symmetric functions and Hall polynomials}, Second edition, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1995.

\bibitem{NY} A.~Nakayashiki and Y.~Yamada, {\em Kostka polynomials and energy functions in
    solvable lattice models}, Selecta Math. (N.S.) 3 (1997), 547--599.)

\bibitem{S} A.~Schilling, {\em $q$-Supernomial coefficients: From riggings to ribbons}, Birkhauser Boston, Cambridge, MA, 2002, pp. 437--454

\bibitem{SW} A.~Schilling and S.O.~Warnaar, {\em Inhomogeneous lattice paths, generalized Kostka polynomials and A$_{n-1}$ supernomials}, Comm.\ Math.\ Phys.\ 202 (1999), no.\ 2, 359--401.

\bibitem{Stanley} R.~Stanley, {\em Enumerative Combinatorics}, Vol.~2, Cambridge University Press, 1999.

\bibitem{War2004} S.O.~Warnaar, {\em The Bailey lemma and Kostka polynomials}, J.~Algebraic Combin. 20 (2004), no. 2, 131--171.

\end{thebibliography}

\end{document}
