\section*{Introduction}

The varied zoo of combinatorial Hopf algebras is much better understood when one
considers the extra algebraic structures that each algebra can have. In this
light, operad related theories are very useful. Some important examples are the
Hopf algebras of non-commutative and quasi-symmetric functions related to the
theory of free Lie algebras~\cite{NCSF1}. More recently, the Hopf algebra of
binary trees was identified as the free dendriform algebra on one
generator~\cite{LodRon_PBT}.

Closed related examples include the algebras $\FQSym$ of permutations of
Malvenuto-Reutenauer~\cite{MalReu} and the Hopf algebra $\WQSym$ of surjections
or, equivalently, ordered set partitions~\cite{Hivert_thesis}. These two can be
seen as noncommutative versions of the algebra of quasi-symmetric
functions. Though the first one is trivially self-dual, it is only by a deep
theorem of Foissy~\cite{foissy_2007} that one can show that the second one is
too. In particular, until Vargas's work~\cite{Vargas_thesis}, no concrete
isomorphism was known.

The first study of $\WQSym$ structure is due to
Bergeron-Zabrocki~\cite{berzag}. They showed that it is free and
co-free. Independently, Novelli-Thibon endowed it with a bidendriform bialgebra
structure~\cite{novthi_2006}. Recall that a dendriform algebra is an abstraction
of a shuffle algebra where the product is split in two half-products. If the
coproduct is also split, and certain compatibilities hold, one gets the notion
of bidendriform bialgebra~\cite{foissy_2007}.

Building on the work of Chapoton and Ronco~\cite{ronco_2000,chapoton_2002},
Foissy~\cite{foissy_2007} showed that the structure of a bidendriform bialgebra
is very rigid. In particular, he defined a specific subspace called the space of
totally primitive elements, and showed that it characterizes the whole
structure. This does not only re-prove the freeness and co-freeness, as well as
the freeness of the primitive lie algebra, but also shows that the structure of
a bidendriform bialgebra depends only on its Hilbert series (the series of
dimensions of its homogeneous components). In particular, any such algebra is
isomorphic to its dual. However, Foissy's isomorphism is not fully explicit and
depends on a choice of a basis of the totally primitive elements. To this end,
one needs an explicit basis of the totally primitive elements. Foissy described
such a construction for $\FQSym$~\cite{foissy_2011}. Our long term goal is to
effectively apply Foissy's construction to $\WQSym$ in order to build an
explicit isomorphism respecting the bidendriform structure. With this objective
in mind, we provide an explicit basis called the totally primitive elements
using a bijection with certain families of trees.

% \bigskip

We begin with a background section presenting two rigidity structure theorems
that prove, among other things, the self-duality of any bidendriform bialgebra
(\cref{brace,prim_tot}). We then define the notion of packed word as well as the
specific basis of~$\WQSym$, which will be the starting point of our
combinatorial analysis (\cref{half_prod,left_coprod,right_coprod}).

\cref{sect2_pw_trees} is devoted to the combinatorial construction of biplane
forests (\cref{forest_def}) which are our first key ingredient. They record a
recursive decomposition of packed words according to their global descents
(\cref{gd_fact}) and positions of the maximum letter (\cref{phi_fact}). We show
that the cardinalities of some specific sets of biplane trees match the
dimensions of primitive and totally primitive elements (\cref{thm:bij}).

Finally in \cref{sect3_Pbasis} we construct a new basis of $\WQSym$ which
contains a basis for the primitive and totally primitve elements
(see~\cref{thm:P}). To do so we decompose the space of totally primitive
elements as a certain direct sum which matchs the combinatorial decomposition of
packed words (\cref{tot_stable}).


%\todo{remerciements}

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