\section{Decorated forests}\label{sect2_pw_trees}

In this section we will generalize the construction of \cite{foissy_2011}. We
will start by defining some forests called biplane that are labeled by certain
lists of integers. We will construct a bijection between these packed forests
and packed words thanks to a decomposition of packed words through global
descents and removal of maximums. The recursive structure of forests can then be
understood as a chaining of operations generating the elements of
$\WQSym$. This will allow us to construct a basis of $\TPrim$ by characterizing
a subfamily of biplane trees.

\subsection{Decompositions of packed words}

\begin{defi} \label{global_descent} A \textbf{global descent} of a packed word
  $w$ is a position $c$ such that all the letters before or at position $c$ are
  greater than all letters after position $c$.
\end{defi}

\begin{ex}
  The global descents of $w = 54664312$ are the positions 5 and 6. Indeed, all letters of $54664$
  are greater than the letters of $312$ and this is also true for $546643$ and $12$.
\end{ex}

\begin{defi} \label{irreducible} A packed word $w$ is \textbf{irreducible} if it has no global
  descent.
\end{defi}

% \begin{ex}
%   The word $w' = 21331$ is irreducible.
% \end{ex}
% Recall that $u\gcdot v$ denotes the left-shifted concatenation of $u$ and $v$.

\begin{lem} \label{gd_fact} Each word~$w$ admits a unique factorization as
  $w = w_1\gcdot w_2\gcdot\dots\gcdot w_k$ such that $w_i$ is irreducible for all $i$.
\end{lem}

\begin{ex}
  The global descent decomposition of $54664312$ is $21331\gcdot 1\gcdot 12$.
  The word $n\cdot n-1\cdot...\cdot 1$ has $1\gcdot 1\gcdot ...\gcdot 1$ as global descent decomposition.
\end{ex}

\begin{defi} \label{phi} Fix $n \in \NN$ and $w \in \PW_n$. We write $m \eqdef \max(w) + 1$. For any
  $p>0$ and any subset~$I \subseteq [1,\dots, n+p]$ of cardinality~$p$,
  $\phi_I(w)=u_1\dots u_{n+p}$ is the packed word of length $n+p$ obtained by inserting $p$
  occurences of the letter $m$ in $w$ so that they end up in positions $i \in I$. In other words
  $u_i = m$ if $i\in I$ and $w$ is obtained from $\phi_I(w)$ by removing all occurrences of $m$.
\end{defi}

\begin{ex} $\phi_{2,4,7}(1232) = 1424324$ and $\phi_{1,2,3}(\epsilon)=111$.
\end{ex}

Let $\PW_n^I$ denote the set of packed words of size $n$ whose maximums are in positions
$i\in I$. This way $\phi_I(w)\in \PW_{n+p}^I$. The following lemma is immediate.

% \begin{defi}
%   The \textbf{diminished word} of an non empty packed word $w$ is the packed word $u$ obtained by
%   removing the maximum letters $m = max(w)$. (\emph{i.e.} $\exists I, w = \phi_I(u)$)
% \end{defi}

\begin{lem} \label{phi_bij} Let $n \in \NN$ and $p>0$, for any $I \subseteq [1,\dots, n+p]$,
  $\phi_I$ is a bijection from~$\PW_{n}$ to the~$\PW_{n+p}^I$.
  
  Moreover, for any $W\in\PW_\ell$ where~$\ell>0$ there exists a unique pair
  $(I,w)$ where $I\subseteq [1\dots \ell]$ and $w$ is packed, such that $W = \phi_I(w)$.
\end{lem}

\begin{defi} \label{ins} Let $u, v \in \PW$ with $v \neq \epsilon$. By~\cref{phi_bij}, there
  is a unique pair $(I, v')$ such that $v=\phi_I(v')$. We denote by $I'$ the set
  obtained by adding $|u|$ to the elements of~$I$. We define
  $u\ins v = \phi_{I'}(u\gcdot v')$. In other words, we remove the maximum letter
  of the right word, perform a left shifted concatenation and reinsert the
  removed letters as new maximums.
\end{defi}

\begin{ex}
  $2123\ins \red{3}\blue{22}\red{3}\blue{12} = \phi_{1+4, 4+4}(4345\blue{2212}) =
  4345\red{6}\blue{22}\red{6}\blue{12}$.
\end{ex}

% \begin{lem} \label{phi_fact} Let $w$ be a packed word. Write $w = u \ins
%   \phi_I (v)$ where $u$ is of maximal length. Then writing
%   $I = [i_1, \dots, i_p]$ and $v = v_1\gcdot\dots\gcdot v_r$, this factorisation
%   is the only one such that either $i_1 \leq |v_1|$ or $I = [1, \dots, p]$ and $v=\epsilon$.
% \end{lem}
\begin{lem} \label{phi_fact} Let~$w$ be an irreducible packed word. There exists
  a unique factorization of the form $w=u\ins\phi_I(v)$ which maximizes the size of
  $u$. In this factorization
  \begin{itemize}
  \item either $v=\epsilon$ and $I = [1, \dots, p]$ for some $p$;
  \item or the factorization $v=v_1\gcdot\dots\gcdot v_r$ of $v$ into
    irreducibles satisfies the inequalities $i_1 \leq |v_1|$, and
    $(\sum|v_i| + |I|) + 1 - i_p \leq |v_r|$.
  \end{itemize}
\end{lem}

\begin{ex} Here are some decompositions according to~\cref{phi_fact}:
  \begin{alignat*}{2}
    21331 &= 1\ins\phi_{2,3}(11) &
    1231 &= \epsilon \ins \phi_3(121)\\
    1233 &= 12 \ins \phi_{1,2}(\epsilon) & 
    111 &= \epsilon \ins \phi_{1,2,3}(\epsilon) \\
    543462261 &= (1 \gcdot 212) \ins \phi_{1,4}(11 \gcdot 1)
    \rlap{ $ = (3212) \ins \phi_{1,4}(221)$}
  \end{alignat*}
\end{ex}
% \begin{proof}
%   Let $w$ be irreducible, $m$ its maximum, and let $(I, w')$ be the unique pair such that
%   $w=\phi_I(w')$ according to~\cref{phi_bij}.  By~\cref{gd_fact}, we write
%   $w' = w_1'\gcdot w_2' \gcdot\dots\gcdot w_k'$, the unique decomposition into irreducibles. Let
%   $\ell$ be such that $w_{\ell}'$ is the last factor which is entirely before the first removed
%   maximum, then with $r=k-\ell$ we can rewrite $w'$ as
%   $(u_1\gcdot \dots\gcdot u_\ell)\gcdot(v_1\gcdot \dots\gcdot v_{r})$. Now we get $I'$ by
%   substracting $|u_1\gcdot \dots\gcdot u_\ell|$ to all parts of $I$ and we obtain
%   $w=u_1\gcdot \dots\gcdot u_\ell \ins \phi_{I'}(v_1\gcdot \dots\gcdot v_r)$ with
%   $i_1' \leq |v_1|$ or $w' = u_1\gcdot \dots\gcdot u_\ell$ by definition of $\ell$.
  
%   The decomposition is unique because the decomposition of $w'$ is unique and it is the only
%   choice of $\ell$ to obtain the inequality $i_1' \leq |v_1|$ if $v_1$ exists ($r\neq0$).
% \end{proof}

% \begin{rem}
%   In~\cref{phi_fact} the inequality $i_1' \leq |v_1|$ means that $v_1$ is the first factor where a
%   maximum was removed just before or inside. In a symmetric way, $v_r$ is the last factor where a
%   maximum was removed just after or inside (which is always true otherwise $w$ would not be
%   irreducible) and it can be formalized as $(\sum|v_i| + |I|) + 1 - i_p \leq |v_r|$.
% \end{rem}

\subsection{Forests from decomposed packed words}

We now apply recursively the decomposition of the former section to construct a
bijection between packed words and a certain kind of trees that we now define. 
\begin{defi} An unlabeled \textbf{biplane tree} is an ordered tree
  (sometimes also called a planar) whose children are organized in a
  pair of two (possibly empty) ordered forests, which we call the left
  and right forests.
\end{defi}

\begin{ex} The biplan trees
  $\scalebox{0.5}{\input{figures/arbres_pw/arbre_biplan_ll}}$,
  $\scalebox{0.5}{\input{figures/arbres_pw/arbre_biplan_lr}}$ and
  $\scalebox{0.5}{\input{figures/arbres_pw/arbre_biplan_rr}}$ are different.
  Indeed in the first case, the left forest contains two trees and the right
  forest is empty, in the second case both forests contain exactly one tree
  while in the third case we have the opposite of the first case. Here is an example
  of a bigger biplane tree where the root has two trees in both left and right
  forests \scalebox{0.5}{\input{figures/arbres_pw/arbre_biplan}}.
\end{ex}

\begin{rem}
  These biplan trees are counted by the sequence A006013 in OEIS.
\end{rem}

In our construction we will deal with labeled biplane trees where the
labels are sorted lists of positive integer. For a labeled biplane
tree, we denote by $\Node(x, f_\ell, f_r)$ the tree whose root is labeled
by $x$ and whose left (resp. right) forest is given by $f_\ell$
(resp. $f_r$). We also denote by~$[t_1, \dots t_k]$ a forest of $k$
trees.

\begin{ex}
  $\Node((1),\ [],[]) =$ \scalebox{0.5}{\input{figures/arbres_pw/arbre1_lbl}}, and
  $\Node((1,3),\ [],[\Node((1),\ [],[])]) =$ \scalebox{0.5}{\input{figures/arbres_pw/arbre212_lbl}}.
\end{ex}

We now apply recursively the decompositions of~\cref{gd_fact,phi_fact} to get an algorithm which
takes a packed word and returns a biplane forest where nodes are decorated by lists of integers:
\begin{defi} \label{def:construction}
The forest~$F(w)$~(resp. tree~$T(w)$) associated to a packed word (resp. a non empty
    irreducible packed word) $w$ are defined in a mutual recursive way as follows:
  \begin{itemize}
  \item $F(\epsilon) = []$ (empty forest),
  \item for any packed word $w$, let
    $w_1\gcdot w_2\gcdot\dots\gcdot w_k$ be the global descent decomposition
    of $w$, then $F(w) \eqdef [T(w_1), T(w_2), \dots, T(w_k)]$.
  \item for any non empty irreducible packed word $w$, we define
    $T(w) \eqdef \Node(I, F(u), F(v))$ where $w=u\ins\phi_I(v)$ and $u$ is of
    maximal length.
  \end{itemize}
\end{defi}

\begin{ex}
  Let $w = 876795343912$, the decomposition of~\cref{gd_fact} gives $w = w_1\gcdot w_2$ with
  $w_1 = 6545731217$ and $w_2 = 12$. Now, we decompose $w_1$ and $w_2$
  using~\cref{phi_fact} as
   \[
     w_1 = 3212 \ins \phi_{1,6}( 3121 )= (1 \gcdot 212) \ins \phi_{1,6} (1
     \gcdot 121),
     \quad\text{and}\quad
     w_2 = 1 \ins \phi_1(\epsilon).
   \]
   It gives the following forest:
  \begin{align*}
    F(876795343912) & = [T(6545731217),\ T(12)] \\
%                    & = [\Node((1,6), F(3212), F(3121)),\
%                      \Node((1),F(1),F(\epsilon))]\\
                    & =
                      \scalebox{0.6}{\input{figures/arbres_pw/arbre_construct1}}
                      \scalebox{0.6}{\input{figures/arbres_pw/arbre_construct2}} \\ 
                    & =
                      \scalebox{0.5}{\input{figures/arbres_pw/arbre876795343912_1}}
                      =
                      \scalebox{0.5}{\input{figures/arbres_pw/arbre876795343912}}.
  \end{align*}
  
  As we can see in this example, in order to simplify the notation, we do not
  write the label when it is the list $1$.
%
  We now characterize the trees obtained this way:
\end{ex}

\begin{defi} \label{forest_def} Let $t$ be a labeled biplane tree. We
  write $t = \Node(I, f_\ell, f_r)$ where ${I = [i_1, \ldots, i_p]}$,
  $f_\ell = [\ell_1, \ldots, \ell_g]$ and $f_r = [r_1, \ldots, r_d]$, which is depicted as follows:
  \begin{equation*}
  	t = \scalebox{0.8}{\input{figures/arbres_pw/arbre}}.
  \end{equation*}
  
  The \emph{weight} of $t$ is recursively defined by
  $\omega(t) = p + \sum_{i=0}^{g}\omega(\ell_i) + \sum_{j=0}^{d}\omega(r_j)$. In particular, if
  $t$ is a leaf then $\omega(t) = p$. The \emph{right-weight} of $t$ is defined by
  ${\omega_r(t) = p + \sum_{j=0}^{d}\omega(r_j)}$. We say that $t$ is a \textbf{packed tree}
  if it satisfies:
  \begin{itemize}
  \item If there are no right children ($d=0$) then $i_k = k$ for all $k$.
  \Item Otherwise:
    \begin{equation} \label{eq:forest_def}
      \left\{
        \begin{array}{rcl}
          1 \leq &i_1 &\leq \omega(r_1),\\
          1 \leq &\omega_r(t) + 1 - i_p &\le \omega(r_d).
        \end{array}
      \right.
    \end{equation}
  \item $f_\ell$ and $f_r$ are packed forests (\emph{i.e.} lists of packed trees).
  \end{itemize}
\end{defi}

For the rest of the article we denote the set of packed forests of weight $n$ by $\PForest_n$
and the set of packed trees of weight $n$ by $\PTree_n$. We also denote by $\PForest_n^I$ the
set of packed forests that satisfy~\cref{eq:forest_def} for $I = (i_1, \ldots, i_p)$ with
$0 <i_1< \ldots< i_p$. Finally we denote the set of packed trees of weight
$n$ with an empty left forest  by $\PParticular_n$.

There is a unique packed forest of weight 1, namely \scalebox{0.5}{\input{figures/arbres_pw/arbre1}},
here are the packed forests of weight 2:\scalebox{0.5}{\input{figures/arbres_pw/arbre12}},
    \scalebox{0.5}{\input{figures/arbres_pw/arbre21}},
    \scalebox{0.5}{\input{figures/arbres_pw/arbre11}}.
    We show below the packed forests of weight 3:

\noindent
    \scalebox{0.4}{\input{figures/arbres_pw/arbre123}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre132}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre213}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre231}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre312}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre321}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre122}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre212}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre221}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre112}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre121}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre211}},
    \scalebox{0.4}{\input{figures/arbres_pw/arbre111}}.

% \begin{lem} \label{bij} Packed trees are in bijection with irreducible packed words and packed
%   forests are in bijection with packed words.
% \end{lem}

The following theorem is a generalisation of the construction of \cite{foissy_2011} for $\FQSym$
and permutations to $\WQSym$ and packed words.
\begin{theorem} \label{thm:bij} For all $n\in\NN$ we have the three following
  equalities : % \todo{Theorem 18: it seems that for the extended abstract, Lemma
    % 17 could be omitted (and the first line of the proof of Theorem 18 could be
    % revised accordingly) to reduce some redundancy.}
  \begin{equation*}
    \dim(\WQSym_n) = \#\PForest_n
    \quad\text{and}\quad
    \dim(\Prim_n) = \#\PTree_n
    \quad\text{and}\quad
    \dim(\TPrim_n) = \#\PParticular_n
  \end{equation*}
\end{theorem}

\begin{proof}
  The construction of \cref{def:construction} defines a bijection from
  packed words to packed forests which restrict to a bijection from
  irreducible packed words to packed trees. Thanks to \cref{left_prod}
  this proves the first two equalities. Recall that a basis of
  primitive elements is given by~\cref{brace} as ordered trees
  decorated by totally primitive elements. If we consider the label
  $I$ together with the right forest of each node as decoration, we
  get that packed trees are in bijection with planar trees decorated
  by $I$ and an element of $\PForest^I$ that is an element
  of~$\PParticular$.
\end{proof}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "primitive_wqsym"
%%% End:
