\documentclass[12pt,reqno]{amsart}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{tikz}
\usetikzlibrary{arrows,backgrounds,decorations,positioning,fit,petri}
%\usepackage{ntheorem}
\usepackage{color}
%\usepackage{multirow}
%\usepackage{abstract}
%\usepackage{pdflscape}

%================================================================

%================================================================

\textheight 240mm
\textwidth 160mm
\hoffset -14mm
\voffset -26mm

%================================================================

\numberwithin{equation}{section}

%================================================================

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{prc}[theorem]{Proposition/Conjecture}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{note}[theorem]{Note}
\newtheorem{exercise}[theorem]{Exercise}

%================================================================

%================================================================

\def\hs{\hbox to 3mm{}}
\def\hhs{\hbox to 5cm{}}
\def\bs{\bigskip}
\def\bbss{\vskip 6mm}
\def\NN{\mathbb{N}}
\def\ss{\smallskip}
\def\ep{\varepsilon}
\def\A{\mathcal{A}}
\def\B{{\cal B}}
\def\C{\mathbb{C}}
\def\X{\mathbb{X}}
\def\X{\Xi}
\def\Z{{\cal Z}}
\def\H{\mathcal{H}}
\def\F{{\sym F}}
\def\N{{\sym N}}
\def\M{{\cal M}}
\def\MS{\mathbf{MS}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\Hom{{\rm Hom}}
\def\tp{\tilde p}
\def\binomial#1#2{\begin{pmatrix}#1 \cr #2 \end{pmatrix}}
\def\pointir{\unskip . --- \ignorespaces}
\def\mref#1{(\ref{#1})}
\def\tcr#1{\textcolor{red}{#1}}
\def\tcb#1{\textcolor{blue}{#1}}
\def\tcg#1{\textcolor{green}{#1}}
\def\scal#1#2{\langle #1 | #2 \rangle}
\def\kd#1#2{\delta{#1#2}}
\def\ncs#1#2{#1\langle\langle #2\rangle\rangle}
\def\rncs#1#2{#1^{\rm rat}\langle\langle #2\rangle\rangle}
\def\ncp#1#2{#1\langle #2\rangle}
\def\func#1#2{{\cal F}(#1,#2)}
\def\MQS{\mathbf{MQSym}}
\def\prim{\mathrm{Prim}}
\def\wmat{\mathrm{WMat}}
\def\ot{\otimes}
\def\qed{$\hfill\square$}

%================================================================

%================================================================


\begin{document}

\title{A word Hopf algebra based on the selection/quotient principle}
\author[G\'erard H.\,E. Duchamp, Nguyen Hoang-Nghia, 
and Adrian Tanasa]
{G\'erard H.\,E. Duchamp$^{1}$, Nguyen Hoang-Nghia$^{1}$, 
and Adrian Tanasa$^{1,2}$}
\thanks{\noindent\hskip-10pt{\tt gerard.duchamp@lipn.univ-paris13.fr}\newline
{\tt nguyen.hoang@lipn.univ-paris13.fr}\newline
{\tt adrian.tanasa@ens-lyon.org}}

\address{$^{1}$LIPN - Institut Galil\'ee - Universit\'e Paris 13, Sorbonne Paris Cit\'e, CNRS UMR 7030,
99 avenue Jean-Baptiste Cl\'ement, F-93430 Villetaneuse, France,\newline
\indent
$^{2}$Horia Hulubei National Institute for Physics and Nuclear Engineering,\\
P.O.B. MG-6, 077125 Magurele, Romania}


\date{}

\begin{abstract}
We define a Hopf algebra structure on the vector space spanned by packed words using a selection/quotient coproduct. 
We show that this algebra is free on its irreducible packed words. 
We also compute the Hilbert series of this Hopf algebra, and we investigate its primitive elements.
    %        This paper introduces a Hopf algebra structure (modelled after matroids) on the linear span of the set of packed words with selection/quotient coproduct. Using the notion of irreducible element, we prove that $\wmat$ is free as an algebra.
\end{abstract}
\maketitle

\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 68 \rms (2013), Article~B68c\hfill}
\def\thepage{}

\section{Introduction}

In algebraic combinatorics, one often associates algebraic structures with various sets of combinatorial objects. Such structures are, for example, Hopf algebras on trees, graphs, tableaux, matroids, words, etc.

A first type of combinatorial Hopf algebra structure is constructed using the selection/quotient principle. This simply means that the comultiplication is of the form
\begin{equation}\label{eq:type1} \Delta(S) =
\underset{\text{conditions}} {\sum_{A \subseteq S\\ +}} S[A] \otimes S/_A ,
\end{equation} 
where $S[A]$ is a substructure of $S$ and $S/_A$ is a quotient.

Examples of such Hopf algebras are the Connes--Kreimer Hopf algebra of Feynman graphs, underlying the combinatorics of perturbative renormalization in quantum field theory \cite{Con-Kre2} or in non-commutative Moyal quantum field theory \cite{tanasa-kreimer}, \cite{tanasa-vignes-tourneret} (the interested reader may also consult \cite{tanasa2}, \cite{Tan12} for some short reviews of these algebras). For the sake of completeness, let us also mention that similar Hopf algebraic structures have been proposed for quantum gravity spin-foam models,
see \cite{Markopoulou}, \cite{tanasa3}.

Matroid theory has been introduced by Whitney in \cite{whitney}. A structure of matroid Hopf algebra is defined in \cite{schmi}, where the product is given by the direct sum operation and the coproduct is given by the selection/quotient principle mentioned above. 

A second type of combinatorial Hopf algebra structure relies on the 
selection/com\-ple\-ment principle. This means that the comultiplication is of the form
%
\begin{equation}\label{eq:type2}
\Delta(S) = \underset{\text{conditions}} {\sum_{A \subseteq S\\ +}} 
 S[A] \otimes [S-A].
\end{equation} 

Examples of such Hopf algebras are the Loday--Ronco Hopf algebra of planar binary trees \cite{Lod-Ron2} or the Hopf algebra of matrix quasi-symmetric functions $\MQS$ \cite{NCSFVI}.

It would thus be interesting to find Hopf algebraic structures on words with a comultiplication not of type \eqref{eq:type2}, but of type \eqref{eq:type1}. This is the issue we address in this paper.

In this article, we introduce a new Hopf algebraic structure, which we call $\wmat$, on the set of packed words with product given by the shifted concatenation and coproduct given by such a selection/quotient principle. 
Each letter $x_j, j\geq 1$, can be seen 
as the infinite column vector with $1$ at the $j^{th}$ place and all other entries zero. $\wmat$ has the zero column, $x_0$, as a special element. 
In graph theory, it would correspond to the self-loop. Using the notion of irreducible element, we prove that $\wmat$ is free as an algebra. 

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL G\'ERARD H.\,E. DUCHAMP, NGUYEN HOANG-NGHIA, AND ADRIAN TANASA}{\SMALL 
A WORD HOPF ALGEBRA BASED ON THE SELECTION/QUOTIENT PRINCIPLE}
%
%

%=====================================================

%=====================================================

\section{Algebra structure}
\subsection{Definitions}

Let $X$ be an infinite totally ordered alphabet $\{x_i\}_{i \geq 0}$ and $X^*$ be the set of words with letters 
in the alphabet $X$. 

A word $w$ of length $n=|w|$ is a mapping $i\mapsto w[i]$ from 
$\{1,2,\dots,|w|\}$ to $X$. For a letter $x_i\in X$, the partial degree $|w|_{x_i}$ is the number of times the letter $x_i$ occurs in the word $w$. We have
\begin{equation}
	|w|_{x_i}\ =\sum_{j=1}^{|w|} \delta_{w[j],x_i}.
\end{equation}
For a word $w\in X^*$, we define the alphabet $Alph(w)$ as the set of its letters, while $IAlph(w)$ denotes the set of indices in $Alph(w)$. 
In symbols,
\begin{equation}
Alph(w)=\{x_i: |w|_{x_i}\not=0\}\ ;\ IAlph(w)=\{i\in \NN: |w|_{x_i}\not=0\}.
\end{equation}
The upper bound $sup(w)$ is the supremum of $IAlph(w)$, i.e., 
\begin{equation}
sup(w) = sup_{\,\mathbb{N}} (IAlph(w)).
\end{equation}
We denote the empty word by $1_{X^*}$, and we put $sup(1_{X^*}) = 0$. 

\ss
Let us define the substitution operators. Let $w=x_{i_1} \dots x_{i_m}$ and $\phi : IAlph(w) \longrightarrow \mathbb{N}$, with $\phi(0)=0$. 
We then have
\begin{equation}\label{eq:subs}
S_\phi(x_{i_1} \dots x_{i_m}) = x_{\phi(i_1)} \dots x_{\phi(i_m)}.
\end{equation} 

Next we define the pack operator of a word $w$. Let $\{j_1 ,j_2, \dots ,j_k \} = IAlph(w)\setminus \{0\}$ with $j_1 < j_2 < \dots < j_k$ and define
$\phi_w$ as 
\begin{equation}\label{eq:packedword}
\phi_w(i) = \begin{cases} m,& \mbox{ if } i = j_m ,\\ 
0,& \mbox{ if } i = 0. \end{cases}
\end{equation}                                                 
The corresponding packed word, denoted by $pack(w)$, is $S_{\phi_w}(w)$. A word $w \in X^*$  is said to be \textit{packed} if $w = pack(w)$.

\begin{example}
Let $w = x_1 x_1 x_5 x_0 x_4$.
Then we have $pack(w) = x_1 x_1 x_3 x_0 x_2$.
\end{example}

\begin{remark}
The presence of the letter $x_0$ dramatically influences the 
picture since there is an infinite number of distinct packed words of weight $m$ (here, the weight is the sum of the indices), which are obtained by
adding multiple copies of the letter $x_0$.
\end{remark}

\begin{example}
The packed words of weight 2 are $x_0^{k_1} x_1 x_0^{k_2} x_1 x_0^{k_3}$, with $k_1, k_2, k_3 \geq 0$.
\end{example}

The operator $pack: X^* \longrightarrow X^*$ is idempotent ($pack \circ pack = pack$). By linear extension, it defines a projector. 
The image, $pack(X^*)$, is the set of packed words.

\medskip
Let $u,v$ be two words. We define the shifted concatenation $*$ by 
\begin{equation}u*v = uT_{sup(u)}(v),\end{equation} 
where, for $t \in \NN$, $T_t(w)$ denotes the image of $w$ by $S_\phi$ for $\phi(n) = n+t$ if $n>0$ and $\phi(0) = 0$ (that is, all letters are reindexed except $x_0$). It is straightforward to check that, in the case the words are packed, the result of a shifted concatenation is a packed word.

\begin{definition}
Let $k$ be a field. We define the vector space $\mathcal{H} = span_{k}(pack(X^*))$. This space is endowed with a product (on the words) given by 
 \begin{align*}\mu : &\mathcal{H} \otimes \mathcal{H} \longrightarrow \mathcal{H}, \\ & u \otimes v \longmapsto u*v.\end{align*}
\end{definition}

\begin{remark}
The product above is similar to the shifted concatenation for permutations (see \cite{NCSFVI}). 
Moreover, if $u$ and $v$ are two words in $X^*$, then $sup(u*v) = sup(u) + sup(v)$. 
\end{remark}

\begin{proposition}
$(\mathcal{H},\mu,1_{X^*})$ is an associative algebra with unit.
\end{proposition}
\begin{proof}
Let $u,v,w$ be three words in $\mathcal{H}$. We have
\begin{align}
(u*v)*w  = (uT_{sup(u)}(v))T_{sup(u*v)}(w)  = u(T_{sup(u)}(v)(T_{sup(u) +sup(v)})(w)) = u* (v*w).
\end{align}

Thus, $(\mathcal{H},\mu)$ is associative. On the other hand, for all $u \in pack(X^*)$, we have 
\[u*1_{X^*}  = uT_{sup(u)}(1_{X^*}) = u1_{X^*} = u\ ,\]
and
\[1_{X^*}*u  = (1_{X^*})T_{sup(1_{X^*})}(u)  = (1_{X^*})u = u\ .\]
Now observe that $pack(1_{X^*})=1_{X^*}$. This is in fact obvious 
from the fact that $1_{X^*} = 1_\mathcal{H}$.
We conclude that $(\mathcal{H},\mu,1_{X^*})$ is an associative algebra
with unit.
\end{proof}

As already announced in the introduction, we call this algebra $\wmat$.

\begin{remark}
The product is non-commutative, for example: $x_1*x_1x_1 \neq x_1x_1*x_1$.
\end{remark}

Let $w = x_{k_1} \dots x_{k_n}$ be a word and $I \subseteq \{1,2, \dots, n\}$. 
The subword $w[I]$ is defined as $x_{k_{i_1}} \dots x_{k_{i_l}}$, where
$I=\{i_1,i_2,\dots,i_l\}$ with $i_1<i_2<\dots<i_l$.
A further notation that we shall use from here on is $I+J$ for the
disjoint union of the two sets $I$ and $J$.

\begin{lemma}\label{lm:subword}Let $u,v$ be two words, and $I \subset 
\{1,2,\dots, |u|\}$ and $J\subset \{|u|+1,|u|+2,\dots, |u|+|v|\}$. 
Then we have 
\begin{equation}\label{eq:mor1}pack(u*v[I+J]) = pack(u[I])*pack(v[J']),
\end{equation} 
where $J'$ is the set $\{i-|u|:i\in J\}$.
\end{lemma}

\begin{proof}
By direct computation, we have 
\begin{equation}\label{eq:prod}
 pack(u*v[I+J]) = pack(uT_{sup(u)}(v)[I+J]) = pack(u[I]T_{sup(u)}(v)[J]). 
\end{equation}
Furthermore, we have 
$sup(u[I])\leq sup(u)$, and this, together with \eqref{eq:prod}, leads to
\begin{align}
pack(u[I]T_{sup(u)}(v)[J]) =  pack(u[I]T_{sup(u[I])}(v[J'])) = pack(u[I])*pack(v[J']). 
\end{align}
\end{proof}

\begin{theorem}
Let $k\langle X\rangle $ be equipped with the shifted concatenation. The mapping pack \begin{equation}
k\langle X\rangle  \xrightarrow{pack} \mathcal{H}
\end{equation} 
is a homomorphism of associative algebras with unit.
\end{theorem}

\begin{proof}
By using Lemma~\ref{lm:subword} with $I=\{1,2, \dots, |u|\}$ and 
$J = \{|u|+1,|u|+2, \dots, |u|+|v|\}$, the assertion of the theorem
follows immediately.
\end{proof}

\subsection{$\wmat$ is a free algebra}\label{sec:freealg}

$\wmat$ is, by construction, the algebra of the monoid $pack(X^*)$, therefore to check that 
$\wmat$ is a free algebra, it is sufficient to show that $pack(X^*)$ is a free monoid on its letters. 
In the following diagram, a free monoid is a pair $(F(X),j_X)$ where $F(X)$ is a monoid, 
$j_X : X \rightarrow F(X)$ is a mapping such that 
for all $M \in Mon$ and all $f : X \rightarrow M$ there exists a unique
$f_X \in Hom(F(X),M)$ such that $f = f_x \circ j_X$.

\begin{center}
\begin{tikzpicture}
\node (set) at (0,0) {Set};
\node (monoids) [right = 3cm of set] {Monoids};
\node (X) [below=1cm of set] {$X$};
\node (M) [below=1cm of monoids] {$\mathcal{M}$};
\node (F) [below=2.5cm of monoids] {$F(X)$};
\draw (5,-.5) to (-2,-.5);
\draw (1.5,1) to (1.5,-4);
\draw[->] (X) to node [above] {$f$} (M);
\draw[->] (X) to node[below] {$j_X$} (F);
\draw[->,dotted] (F) to node [right]{$f_X$} (M);
\end{tikzpicture}
\end{center}

Here we use an ``internal" characterization of free monoids in terms of irreducible elements.

\begin{definition}\label{def:irrword}
A packed word $w$ in $pack(X^*)$ is called an irreducible word 
if and only if it cannot be written in the form $w = u*v$, 
 where $u$ and $v$ are two non trivial packed words.
\end{definition}

\begin{example}
The word $x_1x_1x_1$ is an irreducible word. The word $x_1x_1x_2$ is a reducible word because 
it can be written as $x_1x_1x_2 = x_1x_1 *x_1$.
\end{example}

\begin{proposition}
If $w$ is a packed word, then $w$ can be written uniquely as 
$w = v_1*v_2*\dots *v_n$, where $v_i$ are non-trivial irreducible words, 
$1\leq i \leq n$.
\end{proposition}

\begin{proof}
The $i^{th}$ position of word $w$ is called an admissible cut if $sup(w[1\dots i]) = inf(w[i+1 \dots |w|]) - 1$ or $sup(w[i+1 \dots |w|]) = 0$, where $inf(w)$ is the infimum of $IAlph(w)$. 

Since the length of word is finite, we may write $w = v_1* v_2* \dots v_n$, 
with $n$ maximal and $v_i$ non-trivial, $1\leq i \leq n$.

We assume that one word can be written in two ways 
\begin{equation}\label{eq:irre1} w = v_1* v_2* \cdots * v_n\end{equation} 
and 
\begin{equation}\label{eq:irre2} w = v'_1* v'_2* \cdots * v'_m.\end{equation}

Denoting by $k$ the first number such that $v_k \neq v'_k$, without loss of generality we may suppose that $|v_k|<|v'_k|$. From Equation~\eqref{eq:irre1}, the $k^{th}$ position is an admissible cut of $w$. From Equation~\eqref{eq:irre2}, the $k^{th}$ position is not an admissible cut of $w$. 
Thus, we obtain a contradiction. 
Hence, we have $n=m$ and $v_i=v'_i$ for all $1\leq i \leq n$.
\end{proof}

We thus conclude that $pack(X^*)$ is free as monoid with the packed words as a basis.

%=====================================================

%=====================================================

\section{Bialgebra structure}
  
We now give the definition of the coproduct and prove that the coassociativity property holds.

\begin{definition}
For $A \subset X$, we define $w/A = S_{\phi_A}(w)$ with 
$${\phi_A}(i) = \begin{cases} i,& \mbox{ if } x_i \not\in A,\\ 
0,& \mbox{ if } x_i \in A.\end{cases}$$
For a word $u$, we define $^w/_u = {}^w/_{Alph(u)}$.
\end{definition}

\begin{definition}\label{def:coprod}
The coproduct of $\H$ is given by \begin{equation}\label{eq:coprod}\Delta(w) = \sum_{I+J=\{1,\dots ,|w|\}}pack(w[I]) \otimes pack(w[J]/_{w[I]}), 
\quad \text{for all } w \in \H. \end{equation} 
\end{definition}

\begin{example}
We have
\begin{multline*}
\Delta(x_1x_2x_1) = x_1x_2x_1 \otimes 1_{X^\ast} + x_1 \otimes x_1x_0 + x_1 \otimes x_1^2 + x_1 \otimes x_0x_1 + x_1x_2 \otimes x_0\\
 + x_1^2 \otimes x_1 + x_2x_1 \otimes x_0 + 1_{X^\ast}\otimes x_1x_2x_1.
\end{multline*}
\end{example}

Next, we prove coassociativity.

Let $I=\{i_1,i_2,\dots,i_n\}$ and $I_1 =\{j_1,j_2,\dots,j_k\} \subseteq 
\{1,2,\dots, |I|\}$, and let $\alpha$ be the mapping 
\begin{align}
\alpha:  I & \longrightarrow \{1,2,\dots, n\},\notag\\  i_s & \longmapsto s.
\end{align}

\begin{lemma}\label{lm:coprod1}
Let $w \in X^*$ be a word, $I$ be a subset of $\{1,2,\dots, |w|\}$, and 
$I_1 \subset \{1,2, \dots, \break|I|\}$. 
Then we have
 \begin{equation}\label{eq:coprod1} pack(w[I])[I_1] = S_{\phi_{w[I]}}(w[I'_1]),\end{equation} where $I'_1$ is $\alpha^{-1}(I_1)$ and $\phi_{w[I]}$ is the packing map of $w[I]$ that is given in \eqref{eq:packedword}.
\end{lemma}

\begin{proof}
Using the definition of the packing map $\phi_{w[I]}$, we can directly check that 
Equation~\eqref{eq:coprod1} holds.
\end{proof}

\begin{lemma}
\label{lm:coprod2}
Let $w,w_1,w_2 \in X^*$ be words and $\phi$ be a strictly increasing map from $IAlph(w)$ to $\mathbb{N}$.
Then
\begin{equation}pack(S_{\phi}(w)) = pack(w)
\label{eq:1}
\end{equation}
and
\begin{equation}\label{eq:quotionpack}
S_{\phi}(^{w_1}/_{w_2})= {}^{S_{\phi}(w_1)}/_{S_{\phi}(w_2)}.
\end{equation}
\end{lemma}

\begin{proof}
In order to prove \eqref{eq:1}, we observe that
\begin{equation} \label{eq:3}
pack(S_{\phi}(w))  = S_{\phi_0}(S_{\phi}(w))= S_{\phi_0\circ\phi}(w),
\end{equation}
where $\phi_0$ is the packing map which is given in \eqref{eq:packedword}.
Note that both $\phi$ and $\phi_0$ are strictly increasing maps. 

We write $I=IAlph(w) = \{j_1,j_2,\dots,j_k\}$, $j_1 < j_2 < \dots <j_k$, 
and $j'_i = \phi(j_i)$, $i=1,2,\dots, k$, so that the image set $\phi(I)$
is given by
$\phi(I) = \{j'_1,j'_2,\dots,j'_k  \}$ with $j'_1 < j'_2 < \dots < j'_k$. From the definition of $\phi_0$, we have $\phi_0(j'_i) = i = \phi_0(j_i)$. This leads to
\begin{equation}
S_{\phi_0\circ\phi}(w) = S_{\phi_0}(w) = pack(w),
\end{equation}
from which \eqref{eq:1} follows in combination with \eqref{eq:3}.

Now we turn to the proof of \eqref{eq:quotionpack}.
Let $I_2 = Alph(w_2)$ and $I'_2 = Alph(S_{\phi}(w_1))$.
Using this notation, the left-hand side of
\eqref{eq:quotionpack} becomes
\begin{equation}\label{eq:LHSquotionpack}
S_{\phi}(^{w_1}/_{w_2}) = S_{\phi}(S_{\phi_{I_2}}(w_1)) = S_{\phi\circ\phi_{I_2}}(w_1),
\end{equation}
and the right-hand side becomes
\begin{equation}
\label{eq:RHSquotionpack}
{}^{S_{\phi}(w_1)}/_{S_{\phi}(w_2)}
= S_{\phi_{I'_2}}(S_{\phi}(w_1)) = S_{\phi_{I'_2}\circ\phi}(w_1).
\end{equation}

With $x_i \in Alph(w_1)$, there are two cases:
\begin{itemize}
\item[1.] If $x_i \in I_2$, then $\phi_{I_2}(i)=0$ and $\phi\circ\phi_{I_2}(i)=0$ since $\phi$ is a strictly increasing map.
On the other hand, $\phi(i) \in I'_2$, and this implies $\phi_{I'_2}\circ\phi(i)=\phi_{I'_2}(\phi(i))=0$.
\item[2.] If $x_i \not\in I_2$, then $\phi_{I_2}(i)=i$ and $\phi\circ\phi_{I_2}(i)=\phi(i)$.
On the other hand, since $\phi$ is a strictly increasing map, 
we have $\phi(i) \not\in I'_2$, and $\phi_{I'_2}\circ\phi(i) = \phi(i)$.
\end{itemize}

Thus, we have $\phi\circ\phi_{I_2}(i) = \phi_{I'_2}\circ\phi(i)$. Using this result and \eqref{eq:LHSquotionpack} and \eqref{eq:RHSquotionpack}, 
we arrive at \eqref{eq:quotionpack}.
\end{proof}

\begin{lemma} \label{lm:coprod3}
Let $w$ be a word in $\mathcal{H}$, and $I,J,K$ be three
mutually disjoint subsets of $\{1,2, \dots, |w|\}$.
Then
\begin{equation}
\frac{^{w[K]}/_{w[I]}}{^{w[J]}/_{w[I]}} = {}^{w[K]}/_{w[I+J]}.
\end{equation}
\end{lemma}

\begin{proof}
Using Lemma~\ref{lm:coprod2}, we have
\begin{multline*}
\frac{^{w[K]}/_{w[I]}}{^{w[J]}/_{w[I]}} = {}^{S_{\phi_I}(w[K])}/_{S_{\phi_I}(w[K])} =
 S_{\phi_I}(^{w[K]}/_{w[J]})\\
  = S_{\phi_I}(S_{\phi_J}(w[K])) = S_{\phi_I \circ \phi_J}(w[K]) =  ^{w[K]}/_{w[I+J]}.
\end{multline*}
\end{proof}

\begin{proposition}
The vector space $\mathcal{H}$ endowed with the coproduct \eqref{eq:coprod} is a coassociative coalgebra with co-unit. The co-unit is given by 
$$\epsilon(w) = \begin{cases} 1,& \mbox{ if } w = 1_\H,\\
0,& \mbox{ otherwise}.  \end{cases}$$ 
\end{proposition}

\begin{proof}
We first prove the coassociativity of the coproduct \eqref{eq:coprod}, 
that is, 
\begin{equation}\label{eq:coass}
(\Delta \otimes Id)\circ \Delta(w) = (Id \otimes \Delta)\circ\Delta(w).
\end{equation}
The left-hand side \eqref{eq:coass} can be written
in the form
\begin{align}\notag
& (\Delta \otimes Id)\circ \Delta(w) =  \sum_{I+J = \{1,\dots, |w|\}}
\Bigg(\sum_{I_1+I_2 = \{1, \dots, |I|\}} pack(pack(w[I])[I_1]) \\
\notag
&\kern6.5cm\otimes  pack(^{pack(w[I][I_2])}/_{pack(w[I][I_1])})\Bigg)
 \otimes pack(^{w[J]}/_{w[I]})\\
\notag
&\kern1cm 
= \sum_{I+J = \{1,\dots, |w|]} \left(\sum_{I'_1+I'_2 = I} pack(S_{\phi}(w[I'_1])) \otimes  pack(^{S_{\phi}(w[I'_2])}/_{S_{\phi}(w[I'_1])}) \right) 
 \otimes pack(^{w[J]}/_{w[I]})\\
&\kern1cm
s
 =  \sum_{I'_1+I'_2+J = \{1,\dots, |w|\}} pack(w[I'_1]) \otimes pack(^{w[I_2]}/_{w[I'_1]})  \otimes pack(^{w[J]}/_{w[I_1+I_2]}).
\label{eq:LHSassc}
\end{align}
The right-hand side of \eqref{eq:coass} can be written as
\begin{align}\notag
& (Id \otimes \Delta)\circ \Delta(w) \\
\notag
&\kern.9cm
= 
\sum_{I+J=\{1,\dots, |w|\}} pack(w[I])\otimes \left(\sum_{J_1+J_2=\{1,\dots, |J|\}} pack(pack(^{w[J]}/_{w[I]}))[J_1]) \right. \notag\\
\notag 
&\kern5cm \left. \otimes pack(^{pack(^{w[J]}/_{w[I]})[J_2]}/_{pack(^{w[J]}/_{w[I]})[J_1]}))\right) \\
\notag
&\kern.9cm
 = \sum_{I+J=\{1,\dots, |w|\}} pack(w[I])\otimes \left(\sum_{J'_1+J'_2=J} pack(^{w[J'_1]}/_{w[I]})\otimes pack(S_{\phi}(^{^{w[J'_2]}/_{w[I]}}/_{{w[J'_1]}/_{w[I]}}))\right)\\
\notag
&\kern.9cm
 = \sum_{I+J=\{1,\dots, |w|\}} pack(w[I])\otimes \left(\sum_{J'_1+J'_2=J} pack(^{w[J'_1]}/_{w[I]})\otimes pack(^{w[J'_2]}/_{w_{[I+J'_1]}})\right)\\
&\kern.9cm
 = \sum_{I+J'_1+J'_2=\{1,\dots, |w|\}} pack(w[I])\otimes pack(^{w[J'_1]}/_{w[I]}) \otimes pack(^{w[J'_2]}/_{w_{[I+J'_1]}}).
\label{eq:RHSassc}
\end{align}
Comparing \eqref{eq:LHSassc} and \eqref{eq:RHSassc}, 
we conclude that the coproduct \eqref{eq:coprod} is coassociative.

We now claim that
\begin{equation}\label{eq:counit}
(\epsilon \otimes Id)\circ \Delta(w) = (Id \otimes \epsilon)\circ\Delta(w), \end{equation} for all words $w \in \mathcal{H}$.
In order to establish this claim, 
we rewrite the left-hand side of \eqref{eq:counit} as
\begin{multline*}
(\epsilon \otimes Id)\circ \Delta(w)  =(\epsilon \otimes Id)\left(\sum_{I+J=\{1,\dots, |w|\}}pack(w[I]) \otimes pack(w[J]/w[I]) \right)\notag\\
 = \sum_{I+J=\{1,\dots, |w|\}}\epsilon(pack(w[I])) \otimes pack(w[J]/w[I]) = 1_\H \otimes pack(w) = pack(w),
\end{multline*}
 and the right-hand side as
\begin{multline*}
 (Id \otimes \epsilon)\circ\Delta(w) =(Id \otimes \epsilon)\left(\sum_{I+J=\{1,\dots, |w|\}}pack(w[I]) \otimes pack(w[J]/w[I]) \right)\notag\\
 = \sum_{I+J=\{1,\dots, |w|\}}pack(w[I]) \otimes \epsilon(pack(w[J]/w[I])) = pack(w) \otimes 1_\H = pack(w).
\end{multline*}
Consequently, the triple $(\mathcal{H},\Delta,\epsilon)$ is a
coassociative coalgebra with co-unit.
\end{proof}

\begin{remark}
This coalgebra is not cocommutative. For example, we have 
\begin{align*}
T_{12} \circ \Delta (x_1^2) & = T_{12} (x_1^2 \otimes 1_\H + 2 x_1 \otimes x_0 + 1_\H \otimes x_1^2) \\ & = x_1^2 \otimes 1_\H + 2 x_0 \otimes x_1 + 1_\H \otimes x_1^2 \neq \Delta(x_1^2),
\end{align*}
where the operator $T_{12}$ is given by $T_{12}(u\otimes v) = v \otimes u$.
\end{remark}


\begin{lemma}
Let $u,v$ be two words. Furthermore, let $I_1 +J_1 = \{1,2,\dots, |u|\}$ and
$I_2 + J_2 = \{|u|+1,|u|+2,\dots ,|u|+|v|\}$. Then
\begin{equation}\label{eq:mor2}
pack(^{u*v[J_1+J_2]}/_{u*v[I_1+I_2]}) = pack(^{u[J_1]}/_{u[I_1]}) * pack(^{v[J'_2]}/_{v[I'_2]}),
\end{equation} where $I'_2$ is the set $\{k-|u|:k\in I_2\}$ and $J'_2$ is the set $\{k-|u|:k\in J_2\}$.
\end{lemma}

\begin{proof}
We have
\begin{align*}
 pack(^{u*v[J_1+J_2]}/_{u*v[I_1+I_2]}) &= pack(S_{\phi_{I_1+I_2}}(u*v[J_1+J_2]))\\
& = pack(S_{\phi_{I_1+I_2}}(uT_{sup(u)}(v)[J_1+J_2])) \notag\\
& = pack(S_{\phi_{I_1}+\phi_{I_2}}(u[J_1]T_{sup(u)}(v)[J_2]))\\
&= pack(S_{\phi_{I_1}}S_{\phi_{I_2}}(u[J_1]T_{sup(u)}(v[J'_2]))) \notag\\
 &= pack(S_{\phi_{I_1}}(u[J_1])S_{\phi_{I_2}}(T_{sup(u)}(v[J'_2])))\\
&= pack(^{u[J_1]}/_{u[I_1]})T_{sup(^{u[J_1]}/_{u[I_1]})}pack(S_{\phi_{I'_2}}(v[J'_2])) \notag\\
 &= pack((^{u[J_1]}/_{u[I_1]})*pack(^{u[J'_2]}/_{u[I'_2]}).
\end{align*}
\end{proof}

\begin{proposition}
For any words $u,v$ in $\mathcal{H}$, we have
\begin{equation} \Delta(u*v) = \Delta(u)*^{\otimes 2} \Delta(v).\end{equation}
\end{proposition}

\begin{proof}
We have
 \begin{align}
 \Delta&(u*v)  %\sum_{I+J=\{1, \dots, |u|+|v|\}} pack(u*v[I]) \otimes pack(^{u*v[J]}/_{u*v[I]})\notag\\
= \sum_{\substack{I_1 + I_2 = I \\ J_1 + J_2 = J \\I_1,J_1 \subset \{1,\dots, |u|\}\\I_2,J_2 \subset \{|u|+1,\dots, |u|+|v|\}}} \left(pack(u * v[I_1+I_2])\right)  \otimes\left( pack(^{(u*v[J_1+J_2]}/_{(u*v[I_1+I_2]})\right)\notag\\
%&=\sum_{\substack{I_1+J_1 = \{1,\dots, |u|\}\\I'_2+J'_2 = \{1,\dots, |v|\}}} \left(pack(u[I_1])*pack( v[I_2])\right) \otimes\left( pack((^{u[J_1]}/_{u[I_1]})*(^{u[J'_2]}/_{u[I'_2]}))\right)\notag\\
%&=\sum_{\substack{I_1+J_1 = \{1,\dots, |u|\}\\I'_2+J'_2 = \{1,\dots, |v|\}}} \left(pack(u[I_1])*pack( v[I_2])\right) \otimes\left( pack(^{u[J_1]}/_{u[I_1]})*pack(^{u[J'_2]}/_{u[I'_2]})\right)\notag\\
&=\sum_{\substack{I_1+J_1 = \{1,\dots, |u|\}\\I'_2+J'_2 = \{1,\dots, |v|\}}} \left(pack(u[I_1])\otimes pack(^{u[J_1]}/_{u[I_1]})\right)*\left(pack( v[I_2]) \otimes pack(^{u[J'_2]}/_{u[I'_2]})\right)\notag\\
&=\left(\sum_{I_1+J_1 = \{1,\dots, |u|\}} pack(u[I_1])\otimes pack(^{u[J_1]}/_{u[I_1]})\right)\notag \\
&\kern4cm
 *\left(\sum_{I'_2+J'_2 = \{1,\dots, |v|\}} pack( v[I_2]) \otimes pack(^{u[J'_2]}/_{u[I'_2]})\right)\notag\\ 
=& \Delta(u) *^{\otimes 2} \Delta(v).
\notag
\end{align}
\end{proof}

Since $\mathcal{H}$ is graded by word length, 
we have the following theorem.

\begin{theorem}
$(\mathcal{H},*,1_\H,\Delta,\epsilon)$ is a Hopf algebra.
\end{theorem}

\begin{proof}
This follows from the above results.
\end{proof}

For $w\neq 1_\H$, the antipode is given by the recursion
\begin{equation}
S(w) = -w - \sum_{I+J =\{1,\dots, |w|\}, I,J\neq \emptyset} S(pack(w[I]))*pack(^{w[J]}/_{w[I]}).
\end{equation}

%=====================================================

%=====================================================

\section{Hilbert series of the Hopf algebra $\wmat$}

In this section, we compute the number of packed words with length $n$ and supremum $k$. It is the same as the number of cyclically ordered partitions of an $n$-element set. Using the formula for Stirling numbers of the second kind (see \cite{Co74}), we obtain an explicit formula for the number of packed words with length $n$, which we denote by $d_n$.  

\begin{definition} The Stirling number of the second kind $S(n,k)$ counts the number of set partitions of an $n$-element set into precisely $k$ blocks. 
They are given by the recurrence
$$
S(n+1,k) = S(n,k-1) + kS(n,k),\quad \text{for $0<k\leq n$,}
$$
and initial conditions $S(0,0)=1$ and $S(n,0)=0$ for $n>0$.
\end{definition}

We may define a word without $x_0$ by its positions, 
meaning that, if a word $w=x_{i_1}x_{i_2}\dots x_{i_n}$ has length $n$ and 
alphabet $IAlph(w) = \{1,2,\dots,k\}$, then this word can be determined from the list 
$\{S_1,S_2,\dots,S_k\}$, where $S_i$ is the set of positions of $x_i$ in the word $w$, with $1 \leq i \leq k$. It is straightforward to check that $(S_i)_{1\leq i \leq k}$ is a partition of $\{1,2, \dots, n\}$.

We may divide the set of packed words with length $n$ and supremum $k$ into two parts: \textit{``pure"} packed words (which have no $x_0$ in their alphabet), denoted by $pack_{n,k}^+(X)$, and packed words which have $x_0$ in their alphabet, denoted by $pack_{n,k}^0(X)$. It is obvious that
\begin{equation}
d(n,k) = \# pack_{n,k}^+(X) + \# pack_{n,k}^0(X).
\end{equation}
We now compute the cardinality of these two sets separately.

Consider a word $w \in pack_{n,k}^+(X)$.
Clearly, we have $IAlph(w) = \{1,2,\dots,k\}$. This word is determined by $\{S_1,S_2,\dots,S_k\}$, where $S_i$ is the set of positions of $x_i$, for $1\leq i \leq k$. It is obvious that:
\begin{enumerate}
\item $S_i \neq \emptyset$, for all $i \in \{1,2,\dots,k\}$;
\item $\bigsqcup_{1 \leq i \leq k} S_i = \{1,2,\dots,n\}$.
\end{enumerate}

\noindent
Note that (1) and (2) hold even for $w = 1_\H$.

Thus, the cardinality of packed words with length $n$ and supremum $k$
equals
\begin{equation}\label{eq:d+}
d^+(n,k)=\# pack_{n,k}^+(X) = S(n,k)k!.
\end{equation}

Similarly, a 
word $w \in \# pack_{n,k}^0(X)$ can be determined by $\{S_0,S_1,S_2,\dots,S_k\}$ where $S_i$ is the set of positions of $x_i$, for $0\leq i \leq k$. 
In this case, we have
\begin{equation}\label{eq:d0}
d^0(n,k)=\# pack_{n,k}^0(X) = S(n,k+1)(k+1)!.
\end{equation}

The number of packed words with length $n$ and supremum $k$ is then the
sum of these two numbers, namely
\begin{equation}\label{eq:dnk1}
d(n,k) = d^+(n,k) + d^0(n,k) = S(n,k)k! + S(n,k+1)(k+1)! = S(n+1,k+1)k!.
\end{equation}

Using {\sl Maple}, we computed the first few values of $d(n,k)$. 
They are displayed in Table~\ref{tab:dnk}.
Note that the values of  Table~\ref{tab:dnk} correspond to those of the triangular array $A028246$ in \cite{sloane}.


\begin{table}[!ht]
\begin{center}
\begin{tabular}{cc|rrrrrrrrr}\hline
 &&\multicolumn{9}{c}{$k$}\\
&&0&1&2&3&4&5&6&7&8\\\cline{1-11}
&{0}&1&0&0&0&0&0&0&0&0\\
&{1}&1&1&0&0&0&0&0&0&0\\
&{2}&1&3&2&0&0&0&0&0&0\\
&{3}&1&7&12&6&0&0&0&0&0\\
$n$&{4}&1&15&50&60&24&0&0&0&0\\
&{5}&1&31&180&390&360&120&0&0&0\\
&{6}&1&63&602&2100&3360&2520&720&0&0\\
&{7}&1&127&1932&10206&25200&31920&20160&5040&0\\
&{8}&1&255&6050&46620&166824&317520&332640&181440&40320\\\cline{1-11}
\end{tabular}
\vskip6pt
\caption{Values of $d(n,k)$ given by the explicit formula \eqref{eq:dnk1} and computed with {\sl Maple}.\label{tab:dnk}}
\end{center}
\end{table}

\begin{remark}
 Formulas \eqref{eq:d+} and \eqref{eq:d0} imply that the 
 packed words of length $n$ and supremum $k$ without, respectively with, $x_0$ 
 are in bijection with the ordered partitions of $\{1,2,\dots,n\}$ into $k$ 
blocks, respectively into $k+1$ blocks. Therefore formula \eqref{eq:dnk1} implies that the set of packed words of length $n$ with supremum $k$ is in bijection with the circularly ordered partitions of $n+1$ elements into $k+1$ blocks.
 \end{remark}

The number $d_n$ of all packed words of length $n$ is then given by 
\begin{align}\label{eq:dn}
&d_n =\sum_{k=0}^{n} d(n,k)= \sum_{k=0}^n S(n+1,k+1)k!.
\end{align}
Using again {\sl Maple}, we computed the values listed in Table~\ref{tab:dn}.

\begin{table}[!ht]
\begin{center}
\begin{tabular}{c|rrrrrrrrrrrr|}\hline
$n$&0&1&2&3&4&5&6&7&8&9&10\\\hline
$d_n$&1&2&6&26&150&1082&9366&94586&1091670&14174522&204495126\\\hline
\end{tabular}
\vskip6pt
\caption{Some value of $d_n$ by the formula \eqref{eq:dn}.\label{tab:dn}}
\end{center}
\end{table}

The number of packed words is the sequence 
$A000629$ in
\cite{sloane}, where it is also mentioned that this sequence corresponds to 
the sequence of ordered Bell numbers multiplied by two 
(except for the $0$th term).

The ordinary and exponential generating functions of our sequence are also given in \cite{sloane}, while 
the ordinary generating function is given by 
the formula $\sum_{n\ge 0} \frac{2^n n! x^n}{\prod_{k=0}^n (1+k x)}$. 
The exponential generating function
is given by $\frac{e^x}{2-e^x}$. Below we provide the proof of the latter fact.

\ss
First, recall that 
the exponential generating function of the ordered Bell numbers 
(see, for example, page $109$ of \cite{flaj}) is
\begin{equation}\label{eq:pt2}
\frac{1}{2-e^x} = \sum_{n\geq 0 } \sum_{k = 0}^n S(n,k)k! \frac{x^n}{n!}.
\end{equation}
By differentiating both sides of this equation with respect to $x$, 
we obtain
\begin{equation}\label{eq:pt3}
\frac{e^x}{2-e^x} = \sum_{n\geq 1 } \sum_{k = 1}^n S(n,k)k! \frac{x^{n-1}}{(n-1)!}.
\end{equation}
Combining \eqref{eq:dn} and \eqref{eq:pt3}, we get 
\begin{equation}\label{eq:egfdn}
\frac{e^x}{2-e^x} = \sum_{n\geq 0 } \sum_{k = 0}^n S(n+1,k+1)k! \frac{x^{n}}{n!} = \sum_{n\geq 0 } d_n \frac{x^{n}}{n!},
\end{equation}
as claimed in \cite{sloane}.

\bigskip
We now investigate the combinatorics of irreducible packed words (see Definition \ref{def:irrword}).
First, we notice that there are still infinitely many 
irreducible packed words of weight $m$, and again they are
obtained by adding multiple copies of the letter $x_0$.

\begin{example}
The word $x_1x_0^kx_1x_0^kx_1$ (with $k$ an arbitrary positive integer) 
is an irreducible packed word of weight $3$.
\end{example}

Let us denote by $i_n$ the number of irreducible packed words of length $n$. 
Then we have
\begin{equation}
i_n =  \sum_{\substack{j_1+ \dots + j_k =n\\j_l \neq 0}}(-1)^{k+1} d_{j_1} \dots d_{j_k}.
\end{equation}

Using {\sl Maple}, we computed the first values of $i_n$.
They are displayed in Table~\ref{tab:irr}.

\begin{table}[!ht]
\begin{center}
\begin{tabular}{crrrrrrrrrrrr}\hline
n&0&1&2&3&4&5&6&7&8&9&10\\\hline
$i_n$ &1 &2 &2 &10 &66 &538 &5170 &59906 &704226 &9671930 &145992338 \\\hline
\end{tabular}
\vskip6pt
\caption{The ten first values of the number of irreducible packed words
\label{tab:irr}}
\end{center}
\end{table}

Note that this sequence does not appear in Sloane's On-Line Encyclopedia of Integer Sequences \cite{sloane}.

\section{Primitive elements of $\wmat$}

We emphasize that this Hopf algebra, although graded, is not cocommutative and thus the primitive
elements do not generate the whole algebra but only the sub-Hopf algebra on which $\Delta$ is 
cocommutative (the largest subalgebra on which 
the 
Cartier--Quillen--Milnor--Moore theorem holds).

We denote by $Prim(\wmat)$ the algebra generated by the primitive elements of $\H$.

\ss
We recall the following result.

\begin{lemma}\label{lm:graded}
Let $V^{(1)}$ and $V^{(2)}$ be two graded vector spaces,
\begin{equation}
V^{(i)} = \oplus_{n\geq 0} V_n^{(i)} ,\ i = 1, 2.
\end{equation}                                           
Furthermore,
let $\phi \in  Hom^{gr} (V^{(1)} , V^{(2)} )$, that is,
$\phi (V^{(1)}_n ) \subseteq V_n^{(2)})$ for all $n \geq 0$.
Then $Ker(\phi)$ is graded.
\end{lemma}

We then obtain the following property of $Prim(\wmat)$.
\begin{proposition}
$Prim(\wmat)$ is a Lie subalgebra of $\wmat$, graded by the word's length.
\end{proposition}

\begin{proof}
We define the mapping 
\begin{eqnarray}
\Delta^+:  & \wmat  \longrightarrow \wmat \otimes \wmat \notag\\
& \begin{cases} 1_\H & \longmapsto 0, \\ h & \longmapsto \Delta(h) - 1_\H \otimes h -h \otimes 1_\H .\end{cases}
\end{eqnarray}
This mapping is graded. Using Lemma~\ref{lm:graded}, 
we infer $Prim(\wmat) = Ker(\Delta^+)$. 
Thus, the subalgebra $Prim(\wmat)$ is graded.
\end{proof}

%Let $\wmat_n$ be the subalgebra generated by the packed words of length $n$, $n \geq 0$. We may see an element $P$ of this subalgebra as a polynomial of packed words of length $n$.

%\begin{equation}
%P = \sum_{w \in \wmat_n} \left\langle P|w\right\rangle w.
%\end{equation} 

Let us now compute the dimensions of the first few spaces $Prim(\wmat)_n$:
\begin{itemize}
 \item 
For $n=1$, 
a basis is formed by the primitive elements $x_0$ and $x_1$. 
Then one can check that the primitive elements of length $1$ have the form $ax_0 + bx_1$, with $a$ 
and $b$ scalars. 
%

\item
For $n=2$, a basis is formed by the primitive elements $x_0 x_1 - x_1 x_0$ and $x_1 x_2 - x_2 x_1$. 
Then one can check that all the primitive elements of length $2$ 
have the form $a(x_0 x_1 - x_1 x_0 ) + b(x_1 x_2 - x_2 x_1)$, with $a$ and $b$ scalars.
This is seen by explicitly solving a system of $4$ equations with $d_2=6$ variables.
\end{itemize}

Nevertheless, the explicit calculations quickly become lengthy. 
For example, for $n=3$, 
we have to solve a system of $22$ equations with $26$ variables. 

%=====================================================

%=====================================================


\bigskip     
To conclude, let us give some a posteriori explanations on the choice of the
name ``$\wmat$" for our algebraic structure.
We have defined here a Hopf algebra on some set of words with a selection/quotient coproduct rule in the spirit of graphs  \cite{Con-Kre2} and matroid Hopf algebras \cite{schmi}. We could thus call our algebra $\mathrm{WGraph}$ or $\wmat$. We prefer the name $\wmat$, since matroids are more general structures than graphs.

On the other hand, the "W" in our name simply refers to the fact 
that we have a Hopf algebra with basis indexed by a subset $X$ of the free
monoid $\NN^\ast$. 
Let us say that, at this point, there is no polynomial realization of $\wmat$ 
(as is is the case for $WSym$ or $WQSym$ or the Connes--Kreimer Hopf algebras on trees; see \cite{pol-rel} and the references therein).

This actually seems to us to be an important perspective for future work related to the 
new Hopf algebra proposed in this paper.
 
\section*{Acknowledgements}
%The quality of this paper was greatly enhanced by the gracious assistance of Prof. G??erard H.E. Duchamp
%and Adrian Tanasa, reading teachers, who have taught me most of what I know about this. 
We thank Jean-Yves Thibon for various discussions and suggestions.
The authors acknowledge a 
Universit\'e Paris 13, Sorbonne Paris Cit\'e BQR grant.
A.~Tanasa was supported by
the grants \hbox{PN 09 37 01 02} and CNCSIS Tinere Echipe 77/04.08.2010.\break
G.~H.\,E.~Duchamp was supported by the grants ANR BLAN08-2\_332204 (Physique Combinatoire) and PAN-CNRS~177494 (Combinatorial Structures and Probability Amplitudes).

%=====================================================

%=====================================================

\addcontentsline{toc}{section}{References}

\begin{thebibliography}{99}

\bibitem{Co74} \textsc{L. Comtet}, \textit{Advanced Combinatorics: The Art of Finite and Infinite Expansions}, Presses Universitaires de France, Paris, 1974.

\bibitem{Con-Kre2} \textsc{A. Connes} and \textsc{D. Kreimer}, {\it Renormalization in quantum field theory and the Riemann--Hilbert problem I: The Hopf algebra structure of graphs and the main theorem}, Commun. Math. Phys. \textbf{210} (2000), 249--273.

\bibitem{NCSFVI} \textsc{G. H. E. Duchamp, F. Hivert} and \textsc{J.-Y. Thibon}, 
{\it Noncommutative functions VI: Free quasi-symmetric functions and related algebras}, 
 Internat. J. Algebra Comput. {\bf 12} (2002), 671--717.

\bibitem{flaj} \textsc{P. Flajolet} and \textsc{R. Sedgewick}, {\it Analytic Combinatorics}, Cambridge University Press, 2009.

\bibitem{pol-rel} \textsc{L. Foissy, J.-C. Novelli} and \textsc{J.-Y. Thibon}, 
{\it Polynomial realizations of some combinatorial Hopf algebras}, 
J. Noncomm. Geom (in press); {\tt ar$\chi$iv:1009.2067}.

\bibitem{Lod-Ron2} \textsc{J.-L. Loday} and \textsc{M. O. Ronco}, {\it Hopf algebra of the planar binary trees}, Adv. Math. \textbf{139} (1998), 293--309.

\bibitem{Markopoulou} \textsc{F. Markopoulou}, \textit{Coarse graining in spin foam models}, Class. Quant. Grav. {\bf 20} (2003), 777-800.

\bibitem{schmi} \textsc{W. Schmitt}, \textit{Incidence Hopf algebras}, J. 
Pure Appl. Algebra \textbf{96} (1994), 299--330. 

\bibitem{sloane} \textsc{N. J. A. Sloane}, \textit{The On-Line Encyclopedia of Integer Sequences}, available at:\newline {\tt http://www.oeis.org}.

\bibitem{tanasa-kreimer} \textsc{A. Tanasa} and \textsc{D. Kreimer},  
\textit{Combinatorial Dyson--Schwinger equations in noncommutative field theory}, 
J. Noncomm. Geom. {\bf 7} (2013), 255--289.

\bibitem{tanasa-vignes-tourneret} \textsc{A. Tanasa} and \textsc{F. Vignes-Tourneret}, 
\textit{Hopf algebra of non-commutative field theory}, 
J. Noncomm. Geom. {\bf 2} (2008), 125--139.

\bibitem{tanasa2} \textsc{A. Tanasa}, \textit{Combinatorial Hopf algebras in (noncommutative) quantum field theory}, Rom.\ J.\ Phys.\  {\bf 55} (2010), 
1142--1155.

\bibitem{tanasa3} \textsc{A. Tanasa}, \textit{Algebraic structures in quantum gravity}, Class.\ Quant.\ Grav.\  {\bf 27} (2010), 095008, 16~pp.

\bibitem{Tan12} \textsc{A. Tanasa}, \textit{Some combinatorial aspects of quantum field theory}, S\'em. Lothar. Combin. {\bf 65} (2012), Article~B65g, 30~pp.

\bibitem{whitney} \textsc{H. Whitney}, \textit{On the abstract properties of linear dependence}, Amer. J. Math. {\bf 57} (1935), 509--533.

\end{thebibliography}



\end{document}
