\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$. \item[(iii)] If $b+k-1< i\leq \l$ then $\mu(\mu(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 }sm+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)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+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-1i$ then $\tilde\mu(\tilde\mu(i))> i$. \item[(ii)] If $\tilde\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))b$) implies that $\mu(i)\geq\mu(b)=b>i$ (resp.\ $\mu(i)\leq\mu(b)=bi$ (resp.\ $\mu(\mu(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$. 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 $ja_{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)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)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$, 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