\documentclass[reqno,12pt]{amsart}
\usepackage{amsmath,amssymb}
\usepackage{latexsym}
\usepackage{graphicx}

\textheight20cm \textwidth14.6cm \hoffset-1cm \voffset-.0cm

\newcommand{\PP}{\mathcal{P}}
\newcommand{\PQ}{\mathcal{Q}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\sym}{\mathfrak{S}}
\newcommand{\Set}{\operatorname{Set}}

\newcommand{\pl}{\operatorname{PreLie}}
\newcommand{\OU}{\operatorname{OU}}
\newcommand{\ass}{\operatorname{Assoc}}
\newcommand{\com}{\operatorname{Comm}}
\newcommand{\dend}{\operatorname{Dend}}
\newcommand{\NAP}{\operatorname{NAP}}

\newcommand{\un}{\mathbf{1}}

\newcommand{\ndom}{\operatorname{End}}
\newcommand{\Hom}{\operatorname{Hom}}

\newcommand{\sous}{\curvearrowleft}
\newcommand{\under}{\backslash}

\newcommand{\arb}[1]{\includegraphics[height=5mm]{a#1.eps}}
\renewcommand{\tt}[1]{\mathtt{#1}}

\newtheorem{theorem}{Theorem}[section] 
\newtheorem{proposition}[theorem]{Proposition} 
\newtheorem{conjecture}[theorem]{Conjecture} 
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{definition}{Definition}
 
\newtheorem{remark}[theorem]{Remark} 
\newtheorem{example}[theorem]{Example} 
\newtheorem{problem}[theorem]{Problem} 
\newtheorem{algorithm}[theorem]{Algorithm} 

%\newenvironment{proof}{\begin{trivlist}\item{\bf{Proof.}}}
%  {\hfill\rule{2mm}{2mm}\end{trivlist}}

\begin{document}

\title{Operads and Algebraic combinatorics of trees}
\author{F. Chapoton}
\date{}


\begin{abstract}
  This text is an introduction to operads from a combinatorial point
  of view. We give the definition, several examples of operads and the
  construction of a group from each operad.
\end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 58 \rms (2008), Article~B58c\hfill}
\def\thepage{}
%
%


\section{Introduction}

Combinatorics is concerned with finite objects, and considers problems
such as enumerating some finite sets or finding bijections between
different sets. Algebraic combinatorics could be defined as the
reciprocal application of methods and ideas of algebra to
combinatorics or the other way round. Since the pioneering work of
Rota ``on the foundations of combinatorial theory'', these subjects
have become an active and central piece of mathematics.

Up to now, most of the algebraic structures used in algebraic
combinatorics have been well-established and classical notions of
algebra. One of the main streams is the use of associative algebras
and their representation theory, where combinatorial objects appear
typically as labelling sets for some basis, or in a description of
some modules. For instance, partitions, as considered in number
theory, play an important role in representation theory of symmetric
groups, general linear groups and many related algebras.

Similarly, there has been recently a lot of activity on relations
between Hopf algebras and combinatorial objects. One salient point of
these works is the appearance of new kinds of combinatorial entities,
such as different kinds of trees, in an algebraic context.

The present text would like to advocate for the potential use in
combinatorics of a more recent algebraic notion, which is called an
operad. This notion has first been introduced in algebraic topology in
the early 1970's (Boardman--Vogt, May \cite{bovo,may}) for the study
of loop spaces.  There was a ``renaissance'', a renewed interest in
operads, in the 1990's, with the Koszul duality theory introduced by
Ginzburg and Kapranov \cite{ginzkapr} and also in relation with
moduli spaces of curves \cite{renaissance}. More recently, the theory
of operads has seen further developments in many directions. Operads
are useful to describe and work with complicated new kinds of algebras
and algebras up to homotopy.

The idea of an operad is closely related to trees, in a similar sense
that the idea of an associative algebra is related to the notion of words.
Operads could be useful in combinatorics in several ways. First, they
can shed light on some classical combinatorial objects, by endowing
them with new algebraic structures, much like associative algebras do
for partitions. Next, they can provide the setting for very refined
versions of generating series, where the indices are no longer the set
of integers, but some set of combinatorial objects, such as trees of
various sorts. 
 
We have tried to present the theory of operads to a combinatorial
audience, by a specific choice of illustrative examples. The
combinatorialist who already knows something about the combinatorial
theory of species of structures of Joyal \cite{joyal} (which aims at
providing a way to deal with generating series in some universal way)
will see it appear from another point of view.

Let us give some further general references on operads: a general
presentation \cite{bourbaki} and two monographs
\cite{markl_shnider,smirnov}.

This text is the written version of lectures given at the 58th
S\'eminaire Lotha\-ring\-ien de Combinatoire in March 2007. We give several
equivalent definitions of operads, examples of operads based on
combinatorial objects, and explain how one can build a group of
``invertible formal power series'' starting from an operad.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL F. CHAPOTON}{\SMALL OPERADS AND ALGEBRAIC
COMBINATORICS OF TREES}
%
%

\section{Motivation}

This section explains briefly some possible motivations for operads in
combinatorics.

\subsection{Words and permutations}

Let us recall the classical relation between \textbf{words} and \textbf{associativity}. 

An alphabet $A$ is a set of letters $\{a,b,c,\dots\}$. A word $w$ in the alphabet $A$ is a sequence of letters $w=(w_1,w_2,\dots,w_k)$. There is a basic operation on words given by concatenation, which is associative. In fact, the set of words is exactly the free associative monoid on the set $A$. So the study of words naturally takes place in the setting of associative algebras.

Consider now the alphabet $\{a_1,\dots,a_n\}$. Then the set of words
where each letter $a_i$ appears exactly once can be seen as the set of
\textbf{permutations} of $\{1,\dots,n\}$. In a natural sense,
permutations encode all possible operations that can be made with $n$
distinct elements in an associative algebra.

One can find a similar relation between some kinds of trees and some
new kinds of algebraic structures. There is a parallel between
\begin{itemize}
\item  words or permutations $\longleftrightarrow$ associative algebras,
\item  rooted trees $\longleftrightarrow$ pre-Lie algebras,
\item  planar binary trees $\longleftrightarrow$ dendriform algebras.
\end{itemize}

The natural setting of these generalisations is the theory of
\textbf{operads}, which permits to work with different ``types of
algebras.''

\subsection{Partitions}

Integer partitions are classical in combinatorics and are important
too in representation theory.

The Hopf algebra of symmetric functions \cite{macdonald} can be seen
as a description of representations of symmetric groups. To each
integer partition of an integer $n$ correspond an isomorphism class of
modules over the symmetric group $\sym_n$.

The set of planar binary trees has also such a dual nature.

\begin{itemize}
\item  partitions $\longleftrightarrow$ modules over the symmetric groups,
\item  planar binary trees $\longleftrightarrow$ tilting modules on quivers of type A.
\end{itemize}

There is a natural and simple bijection (see \cite{hille}) between
planar binary trees and tilting modules over the following quivers:
\begin{equation}
1 \to 2 \to 3 \to \dots \to n.
\end{equation}

One further hint of the importance of this relation between planar
binary trees and tilting modules is given by the frequent occurrence of
the Tamari lattice in algebraic structures on planar binary trees,
together with the fact that this poset has a natural definition in
terms of tilting modules.

\subsection{Grafting, cutting, pruning, gluing, etc}

Algebraic structures on trees did already appear a long time ago, for
instance in the work of Butcher \cite{butcher} in numerical analysis.

Many new algebraic structures on trees have been introduced more
recently, notably by Connes and Kreimer \cite{conneskreimer}. Among
them, one can find
\begin{itemize}
\item Hopf algebras,
\item Lie algebras,
\item groups,
\item operads.
\end{itemize}

Operads sometimes provide a way to understand all these objects, or at
least they provide a valuable point of view.

\medskip

On the other hand, trees are obviously used everywhere in
combinatorics. For example, there are
\begin{itemize}
\item many posets on some sets of trees \cite{pitman,tamari},
\item different statistics on trees (like on permutations),
\item some bijections or morphisms between trees and permutations,
\item proofs of Lagrange inversion using trees \cite{labelle}.
\end{itemize}

One could also cite the many studies of random trees, and the uses of
the generating series of rooted trees (the Lambert W function
\cite{corless}), for instance in the study of random graphs and
parking functions.

\medskip

In these lectures we will concentrate on two particularly nice kinds
of trees:
\begin{itemize}
\item rooted trees,
\item planar binary trees.
\end{itemize}

For each of them, we will introduce two different operads.


\subsection{Four flavours of operads}

One has to distinguish four kinds of operads: either we work 

\begin{itemize}
\item in the category  of sets  or
\item in the category of vector spaces,
\end{itemize}

and also either with

\begin{itemize}
\item symmetric or labelled (with actions of symmetric groups) or
\item non-symmetric or unlabelled (without actions of symmetric groups)
\end{itemize}
objects.

This second dichotomy corresponds also (in some sense) to non-planar or planar trees.

We will consider examples of operads of all four kinds. Let us present
a summary here:

\begin{itemize}
\item In Set, non-symmetric: Associative, OverUnder
\item In Set, symmetric: Commutative, NAP
\item In Vect, non-symmetric: Dendriform, M (standing for Mould)
\item In Vect, symmetric: pre-Lie
\end{itemize}

\section{Non-symmetric operads}

In this section, the notion of a non-symmetric operad is introduced, first in the
category of sets, then in the category of vector spaces. We give two
different definitions and explain how they are related one to each other.

\subsection{Non-symmetric operads in the category of sets}

Let us consider the category $\Set$ endowed with the Cartesian
product $\times$. In fact, we will consider here only finite sets, but this
is not a necessary condition.

There are two flavours of operads in $\Set$, depending on the presence
or not of actions of symmetric groups. Let us start with the simplest
case, without actions of symmetric groups.

\begin{definition}
A non-symmetric operad $\PP$ in $\Set$ is the data of a set
$\PP(n)$ for each integer $n\geq 1$, of an element $\un$ in $\PP(1)$ and
of composition maps 
\begin{equation}
\gamma : \PP(m)\times \PP(n_1)\times\dots
\times \PP(n_m)\longrightarrow \PP(n_1+\dots+n_m) 
\end{equation}
for all integers $m,n_1,\dots,n_m$. 

These data have to satisfy the
following conditions. 

The element $\un$ is a unit in the following sense:
\begin{align}
\gamma(\un ; p)&=p \\ 
\gamma(p ; \un,\dots,\un)&=p,
\end{align}
for all $p \in \PP(n)$.

The composition maps $\gamma$ satisfy the following associativity condition:
\begin{multline*}
\gamma(\gamma(p;q_1,\dots,q_n) ; r_{1,1},\dots,r_{1,m_1},r_{2,1},\dots,r_{2,m_2},r_{3,1},\dots,r_{n,m_n})\\= \gamma(p ; \gamma(q_1;r_{1,1},\dots,r_{1,m_1}), \dots ,\gamma(q_n;r_{n,1},\dots,r_{n,m_n})).
\end{multline*}
\end{definition}

\begin{figure}
\begin{center}
\includegraphics[scale=0.35]{compo_axiom.eps} 
\caption{Main axiom for composition.
First composing $q$'s and $r$'s then composing $p$ and the
result is the same as first composing $p$ and $q$'s
then composing the result and $r$'s. The common result is symbolically depicted on the right.}
\label{compo_axiom}
\end{center}
\end{figure}

This means that there are two ways to perform composition in Fig.
\ref{compo_axiom}, either starting with several top compositions or
starting with one bottom composition; these two maps should give the
same result. 

One way to recall easily these axioms is to think of the set $\PP(n)$ as
being a set of operations with $n$ (ordered) inputs and one output.
Such an operation can be symbolically depicted as in Fig.
\ref{compo_axiom} by a box with one outgoing and $n$ incoming legs.

Note that non-symmetric operads form a category, with the expected
notion of morphism $f$ from $\PP$ to $\PQ$, given by one map $f_n$ from
$\PP(n)$ to $\PQ(n)$ for each $n$, which have to be compatible with the
composition maps, in the sense that the obvious diagrams must commute.

\subsection{Planar binary trees}

Let us give an example, not the simplest possible but rather a
more interesting one. For this, we need some classical combinatorial
objects.

A \textit{planar binary tree} is a finite
connected and simply connected graph, having only vertices of degree
$1$ or $3$, embedded in the plane, and with a distinguished vertex of
degree $1$ called the root. The other vertices of degree $1$ are
called the leaves. The vertices of degree $3$ will from now on simply
be called vertices.

\begin{figure}
\begin{center}
\includegraphics[scale=0.7]{planar_vide.eps} 
\end{center}
\caption{A planar binary tree.}
\label{planar_vide}
\end{figure}

There is a standard way to draw such trees: leaves are on a horizontal
line on top with a regular spacing and edges are in diagonal
directions.

Given a planar binary tree $T$ with $n$ vertices, one can number its
vertices from $1$ to $n$ in a canonical way, with a recursive
definition. First number the vertices of the left part of the tree
from $1$ to $k-1$, then the bottom vertex with $k$ and the
vertices of the right part of the tree from $k+1$ to $n$.

The number of planar binary trees with $n$ vertices is the Catalan number
\begin{equation}
c_n=\frac{1}{n+1}\binom{2n}{n}.
\end{equation}

Stanley \cite{stanley} has given at least 143 different combinatorial
interpretations of the Catalan numbers, among which one can cite Dyck
paths, planar trees, nonnesting and noncrossing partitions.

Recently, many relations have been found between objects counted by
the Catalan numbers and structures in algebra and representation
theory: quasi-symmetric functions \cite{aval1,aval2}, cluster algebras
\cite{ysystems}, cluster tilting theory \cite{bmrrt}, dual braid
monoid \cite{bessis}, Hopf algebras \cite{lodayronco}, etc.

\subsection{The OverUnder operad}

Here comes the first example of a (non-sym\-met\-ric) operad, called the
OverUnder operad $\OU$ (also called Duplicial operad). It is used by
Frabetti \cite{frabetti} in her work on renormalization with planar
binary trees.

The set $\OU(n)$ is the set of planar binary trees with $n+1$ leaves.

The unit $\un$ in $\OU(1)$ is the only planar binary tree $\arb{1}$
with one vertex.

Composition is given by \textbf{local substitution} at each inner
vertex. One uses the canonical numbering of inner vertices introduced
above. Then given $n$ planar binary trees $S_1,\dots,S_n$, the
composition $\gamma(T;S_1,\dots,S_n)$ is obtained by replacing a
neighbourhood of each vertex $i$ of $T$ by the planar binary tree
$S_i$, identifying the leftmost leaf of $S_i$ with the edge
$\backslash$ emanating from $i$ and the rightmost leaf of $S_i$ with
the edge $/$ emanating from $i$.

\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{compo_OU.eps} 
\end{center}
\caption{Example of composition in the $\OU$ operad.}
\label{compo_OU}
\end{figure}

Figure \ref{compo_OU} displays the composition
\begin{equation}
 \gamma(T;S_1,S_2,S_3).
\end{equation}

One has two simple associative operations on planar binary trees: the over ($/$) and under ($\backslash$) products.

The over product $S/T$ is obtained by grafting the root of $S$ on the leftmost leaf of $T$.

The under product $S\under T$ is obtained by grafting the root of $T$ on the rightmost leaf of $S$.

In addition to being both associative, the over and under products satisfy 
\begin{equation}
(x/y)\under z=x/(y\under z).
\end{equation} 

\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{product_OU.eps} 
\end{center}
\caption{Example for the $/$ and $\backslash$ associative products.}
\label{product_OU}
\end{figure}

\subsection{Alternative axiomatics}

There is an alternative presentation of the notion of a non-symmetric operad.

Instead of being given by $\gamma$ maps, the composition is described
by maps $\circ_i$. The $\gamma$ map is to be thought of as
simultaneous insertion of several objects into one, the $\circ_i$ as
the insertion of just one object into another one.

\begin{enumerate}
\item $\gamma$ maps $\longleftrightarrow$ simultaneous composition,
\item $\circ_i$ map $\longleftrightarrow$ simple composition.
\end{enumerate}

So instead of maps $\gamma$ as before, we are given a collection of
maps $\circ_i$ for all $m$,$n$ and $1 \leq i \leq m$ from
$\PP(m)\times \PP(n) \to \PP(m+n-1)$.

\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{simple_compo.eps} 
\end{center}
\caption{A simple composition $p\circ_i q$.}
\label{simple_compo}
\end{figure}

The $\circ_i$ maps have to satisfy an associativity and a commutativity axiom.

Let $x,y,z$ be in $\PP(m),\PP(n),\PP(p)$ respectively.
\begin{itemize}
\item Associativity \textrm{I} (Disjoint composition): $(x\circ_i
y)\circ_{j+n-1} z=(x\circ_j z)\circ_i y$ for all $x,y,z$ and $i<j$
in $\{1,\dots,m\}$,
\item Associativity \textrm{II} (Nested composition): $(x\circ_i
y)\circ_{j+i-1} z=x\circ_i( y \circ_j z)$ for all $x,y,z$, $i$ in $\{1,\dots,m\}$ and
$j$ in $\{1,\dots,n\}$,
\item Unit: $\un\circ_1 x=x=x\circ_i \un$ for all $m$, $i=1,\dots,m$.
\end{itemize}

The equivalence between the two presentations is obtained by using the
unit $\un$.

In one way, the $\circ_i$ maps can be defined directly from the
$\gamma$ maps:
\begin{equation}
x \circ_i y = \gamma(x;\un,\dots,\un,y,\un,\dots,\un),
\end{equation}
where $y$ is in the $i^{th}$ position.

In the other way, the $\gamma$ maps can be recovered by iteration of the
$\circ_i$ maps:
\begin{equation}
\gamma(p;q_1,\dots,q_n)=(\dots((p \circ_n q_n) \circ_{n-1} q_{n-1})\dots \circ_1 q_1).
\end{equation}

\subsection{The operad of endomorphisms of a set}

If $S$ is a set, one can define the endomorphism operad of $S$
(denoted by $\ndom_S$) as the collection $\ndom_S(n)=\Hom(S^n,S)$
together with the usual composition of multiple maps. For instance,
the simple composition of $f\in \ndom_S(m)$ and $g\in\ndom_S(n)$ at position $i$ is
\begin{equation}
  (f\circ_i g)(s_1,\dots,s_{m+n-1})=f(s_1,\dots,g(s_i,\dots,s_{i+n-1}),\dots,s_{m+n-1}).
\end{equation}

The unit $\un$ is the identity in $\ndom_S(1)$. 

If you are given a morphism from another operad $\PP$ to $\ndom_S$, then
one says that $S$ has the structure of an \textbf{algebra over the
  operad} $\PP$.

For instance, one can show that an algebra over the $\OU$ operad is
exactly a set endowed with two associative operations $/$ and $\under$
satisfying $(x/y)\under z=x/(y\under z)$. This amounts to finding a
presentation of the $\OU$ operad as a quotient of a free operad.

\subsection{The Associative operad}

Here comes another example of a non-symmetric operad, a very simple and essential one.

The set $\ass(n)$ is just a singleton $\{M_n\}$. The unit $\un$ is $M_1$.
The composition is defined by
\begin{equation}
M_m \circ_i M_n = M_{m+n-1}
\end{equation}
or by
\begin{equation}
\gamma(M_n;M_{k_1},\dots,M_{k_n})=M_{k_1+\dots+k_n}.
\end{equation}

This operad has a presentation by generators and relations: it is
generated by $M_2$ and the unique relation is
\begin{equation}
\gamma(M_2;M_2,\un)=\gamma(M_2;\un,M_2).
\end{equation}

This means that a morphism from $\ass$ to $\ndom_S$ is determined by
the image of $M_2$, which is a map from $S\times S \to S$ that has to
be associative in the usual sense.

\subsection{Free operads}

Let us define the free non-symmetric operad generated by a collection of sets
$G=(G_k)_{k \geq 2}$.

A \textit{planar rooted tree} is a finite graph which is a tree, with
a distinguished vertex of degree one (the root), together with an
embedding in the plane. Other vertices of degree one are called leaves.

The set $Free_G(n)$ is the set of planar rooted trees with $n$ leaves
and with labelled inner vertices. Inner vertices must have degree at
least $3$, and vertices of degree $k+1$ must be labelled by elements
of $G_k$ for $k \geq 2$.

The unit $\un$ is the planar rooted tree without any inner vertex,
with just a leaf and a root.

Composition is given by \textbf{grafting} of leaves with roots.

\begin{figure}
\begin{center}
	\includegraphics[scale=0.3]{compo_free.eps} 
\end{center}
\caption{Example of composition in a free operad.}
	\label{compo_free}
\end{figure}

Figure \ref{compo_free} displays the composition
\begin{equation}
\gamma(T;S_1,S_2,S_3)
\end{equation}
 in a free operad.

\subsection{Non-symmetric operads in the category of vector spaces}

Many classical operads can not be defined in the category of sets, but only in the category of vector spaces.

The definition is just the same, 
\begin{itemize}
\item Sets $\PP(n)$ $\longleftrightarrow$ Vector spaces $\PP(n)$,
\item Cartesian product $\times$ $\longleftrightarrow$ tensor product $\otimes$,
\item Disjoint union $\sqcup$ $\longleftrightarrow$ direct sum $\oplus$,
\item maps $\longleftrightarrow$ linear maps.
\end{itemize}


One can go from a non-symmetric operad in Set to a non-symmetric operad in Vect simply by using
the functor ``free vector space over a set''.

The combinatorial aspect can survive if there is a nice basis in each
vector space $\PP(n)$ and a clean description of the composition maps
in these bases.

\subsection{The Dendriform operad}

The dendriform operad $\dend$ has been introduced by Loday
\cite{dialgebras}. The initial motivation was from algebraic topology.

The free dendriform algebra on one generator has a basis indexed by
planar binary trees. It is endowed with an associative product denoted
by $*$, which is the sum of two dendriform products.

Later, Loday and Ronco introduced a Hopf algebra on the free
dendriform algebra on one generator \cite{lodayronco}. This is now
called the Hopf algebra of planar binary trees or Loday-Ronco Hopf
algebra.

The vector space $\dend(n)$ has a basis indexed by planar binary
trees with $n$ vertices. 

The unit $\un$ in $\dend(1)$ is the tree $\arb{1}$.

Composition has a combinatorial description using \textbf{pairs of
  shuffles}, that we will not describe precisely here. In the composition
$T \circ_i S$, one has to identify the left hand side of $S$ with one
specific path in $T$ and the right hand side of $S$ with another path
in $T$. Each of these two identifications is given by a shuffle.

\begin{figure}
\begin{center}
	\includegraphics[scale=0.3]{compo_Dend.eps} 
        \caption{One term in the composition $T \circ_3 S$ in the $\dend$ operad.}
	\label{compo_Dend}
\end{center}
\end{figure}

More recently, it has been shown \cite{anticyclic} that the dendriform
operad has a more refined structure: it is an \textbf{anticyclic
  operad}. For the precise definition of what anticyclic and
cyclic operads are, the reader may consult \cite{getzler_cyclic}.

This implies in particular that there is a natural action of the
cyclic group $\ZZ/{(n+1)\ZZ}$ on the vector space $\dend(n)$. Let us
say a little bit more on this interesting action.

The matrices of the generator of the cyclic group action on $\dend(2)$
and\break $\dend(3)$, in the bases $\left\{\arb{21},\arb{12}\right\}$ and
$\left\{\arb{321},\arb{312},\arb{131},\arb{213},\arb{123}\right\}$,
are as follows:
\begin{equation}
\begin{bmatrix}
-1 & 1\\
-1 & 0\\
\end{bmatrix}
\text{ and }
\begin{bmatrix}
-1 & 0 & 1 & 1 & -1\\
-1 & 0 & 1 & 0 & 0\\
0 & -1 & 0 & 1 & 0\\
-1 & 0 & 0 & 0 & 0\\
0 & -1 & 0 & 0 & 0\\
\end{bmatrix}
\end{equation}

One can see that this action is not given by a permutation of the set
of planar binary trees.

Let us now explain one way to understand this action. There is a
natural map from planar binary trees to rational functions, which goes
as follows.

Let us fix an integer $n$ and $n$ indeterminates $\{u_1,\dots,u_n\}$.

Then a planar binary tree $T$ defines a set of intervals in
$\{1,\dots,n\}$: to each inner vertex corresponds a pair of leaves
(the leftmost and rightmost ones among the leaves that are above
this vertex in $T$) and these leaves enclose an interval.

The planar binary tree $T$ is mapped to
\begin{equation}
\frac{1}{\prod_{I} \sum_{i\in I} u_i},
\end{equation}
where the product runs over the set of intervals defined by $T$.

\begin{figure}
\begin{center}
	\includegraphics[scale=0.7]{planar.eps} 
\end{center}
\caption{A planar binary tree and its standard numbering.}
	\label{planar}
\end{figure}

For example, the planar binary tree shown in Fig. \ref{planar} is mapped to
\begin{equation*}
\frac{1}{(u_1+u_2+u_3)(u_2)(u_2+u_3)(u_1+\dots+u_7)(u_5)(u_5+u_6+u_7)(u_7)}.
\end{equation*}

It is clear that this map is an injective map from the set of planar binary
trees to the set of rational functions: just factorise the fraction to
recover the tree. Less obviously, the associated linear map is also
injective.

All this is related to the work of Ecalle \cite{ecalle} and the notion of
a \textbf{mould}. There exists an operad $M$ introduced in \cite{mould},
whose component $M(n)$ is the field $\QQ(u_1,\dots,u_n)$ of rational
functions in $n$ indeterminates.

\begin{theorem}
  The map introduced above defines an injective map of the Dendriform
  operad into the operad $M$.
\end{theorem}

On the fractions, there is also an action of the cyclic group
$\ZZ/{(n+1)\ZZ}$ given by substitution
\begin{equation}
u_i \mapsto u_{i-1} \text{  and  } u_1 \mapsto -(u_1+\dots+u_n).
\end{equation}

This is compatible with the injection and gives back the cyclic action
on planar binary trees.

\subsection{Non-crossing trees}

One can use this map into fractions to describe a subset of Dend which
is closed under composition. Consider a regular polygon with $n+1$
vertices. Assume that there is a distinguished side called the
\textbf{base}. Recall that a non-crossing tree is a set of diagonals
between vertices of this polygon such that
\begin{itemize}
\item No two of them intersect,
\item all vertices are connected by these diagonals,
\item there are no cycles.
\end{itemize}
We will furthermore assume that it contains the base.

The number of such trees is \cite{noy}
\begin{equation}
\frac{1}{n}\binom{3n-2}{2n-1}.
\end{equation}

\begin{figure}
\begin{center}
	\includegraphics[scale=0.7]{nctree.eps} 
        \caption{A non-crossing tree}
	\label{nctree}
\end{center}
\end{figure}

There is a simple map from non-crossing trees to rational functions. The
fraction is the inverse of the product of terms corresponding to
diagonals. A diagonal is mapped to the sum $\sum_{i\in I} u_i$, where
$I$ is the set of sides of the polygon that are separated from the
base side by the chosen diagonal.

For example, the non-crossing tree shown in Fig. \ref{nctree} is mapped to
\begin{equation*}
\frac{1}{(u_2)(u_2+u_3)(u_1+\dots+u_7)(u_5)(u_6)(u_4+u_5+u_6+u_7)(u_6+u_7)}.
\end{equation*}

There is an operad on non-crossing trees. The unit $\un$ is the unique tree in the $2$-polygon.

Composition is given by \textbf{gluing} the base side of one tree
along a chosen side of the other one, then removing the base in order
to avoid creating a cycle.

By mapping non-crossing trees to fractions (this is injective), one
gets fractions which are in the image of Dend. Hence non-crossing
trees can be seen as a sub-operad of the operad $\dend$.

\section{Symmetric operads}

Symmetric operads are slightly more complicated than non-symmetric operads. Instead of being given a collection of sets indexed by the integers, the underlying data is a \textbf{species}.

\subsection{Species}

The theory of \textbf{species} has been introduced by Joyal
\cite{joyal} as a natural categorical setting for generating functions
and bijections.

\begin{definition}
A species $F$ is a functor from the category of finite sets and
bijections to the category of finite sets.
\end{definition}

This just means that, given a finite set $I$, there is a natural
way to build a set $F(I)$ out of it, without using any specific
properties of the elements of $I$.

This implies that there is a natural action of the bijections of $I$ on $F(I)$. 

Moreover $F$ can be uniquely recovered from the collection $F(\{1,\dots,n\})$ and the action of symmetric groups.


For instance, one has the species $L$ of lists: $L(I)$ is the set of
total orders on $I$. 

Most of the usual labelled combinatorial objects
can be described by species.

For instance, there are species for labelled graphs, for labelled posets, for set partitions, for labelled hypergraphs, and so on.

As a ``technology'', species have been used a lot by the UQAM team in
combinatorics, see for instance the book \cite{bergeron}.

One can define operations on species:

\begin{align*}
(F')(I)&=F(I \sqcup \{\bullet\})\quad&\text{derivative},\\
(F \sqcup G)(I)&=F(I) \sqcup G(I)\quad&\text{disjoint union},\\
(F G)(I) &= \bigsqcup_{I=J \sqcup K} F(J) \times G(K)\quad&\text{product},\\
(F\cdot G)(I) &= F(I) \times G(I)&\quad\text{Hadamard product},\\
(F \circ G)(I) &=\bigsqcup_{\simeq} F(I/{\simeq}) \times \prod_{J
\in I/\simeq} G(J)&\quad\text{composition},
\end{align*}
where $\simeq$ runs over the set of equivalence relations on $I$.


To each species $F$ corresponds an exponential generating series:

\begin{equation}
F(x)=\sum_{n \geq 0} \# F(\{1,\dots,n\}) \frac{x^n}{n!}.
\end{equation}

Each species $F$ can be associated with a symmetric function
\begin{equation}
Z_F=\sum_{n \geq 0} Z_n(F),
\end{equation}
where $Z_n(F)$ is the symmetric function associated with the action of
the symmetric group $\sym_n$ on the set $F(\{1,\dots,n\})$ (see the
standard reference \cite{macdonald} for more on symmetric functions). 

The operations on species correspond to the same operations on
generating functions or symmetric functions. For instance, composition
of species corresponds to plethysm of symmetric functions.

\subsection{Symmetric operads in sets}

\label{def_symm_operad}

A symmetric operad in the category of sets is a species $\PP$ together with a morphism from $\PP \circ \PP$ to $\PP$ which takes the place of the composition map $\gamma$ and should be associative. 

The unit $\un$ is given by a natural system of distinguished elements
in the images of singletons by the functor $\PP$.

This is just an instance of the definition of a monoid in a monoidal category.

If one wants to use the analog of the $\circ_i$ products instead of the $\gamma$ maps, one can give, for all sets $I$, $J$ and $i\in I$, maps
\begin{equation}
  \circ_i : \PP(I)\times\PP(J) \longrightarrow \PP(I\setminus\{i\} \sqcup J)
\end{equation}
that have to satisfy some associativity axioms and naturality
properties, the latter ones being generally obvious in all examples.

One can give an alternative axiomatics of symmetric operads by using
instead of a species $S$ the equivalent data of a collection of sets
$S(n)=S(\{1,\dots,n\})$ with actions of the symmetric groups $\sym_n$.

This becomes heavy, because of \textbf{renumbering}. For instance,
there is an operad on the species $L$ where $L(I)$ is the set of total
orders on $I$. This is the symmetric operad obtained from the
non-symmetric operad $\ass$ by the introduction of free actions of
symmetric groups. The composition $\circ_i$ in $L$ is given by
insertion of a total order as a segment at some point of another one:
\begin{equation}
(b,a,c,f,e,d) \circ_c (u,r,p,s,t,q) = (b,a,u,r,p,s,t,q,f,e,d).
\end{equation}

The same statement would become, after choosing the obvious numberings of $\{a,b,c,d,e,f\}$ and $\{p,q,r,s,t,u\}$:
\begin{equation}
(2,1,3,6,5,4) \circ_3 (6,3,1,4,5,2) = (2,1,8,5,3,6,7,4,11,10,9).
\end{equation}

\subsection{Example: the Commutative operad}

The set $\com(I)$ is just a singleton $\{I\}$ for all non-empty $I$. 

As a species, this is usually called the species of non-empty sets denoted by $E^+$, with generating series $E^+(x)=\exp(x)-1$.

The unit is the unique element in $\com(\{i\})$ for all singletons.

For composition, there is no choice.

Algebras over this operad are just commutative and associative algebras.

\subsection{Rooted trees}

Let us now introduce our second main player, a very well-known kind of tree.

\begin{definition}
  A rooted tree is a finite connected and simply connected graph with
  a distinguished vertex, called the root.
\end{definition}

\begin{figure}
\begin{center}
\includegraphics[height=2cm]{rooted_tree.eps} 
\caption{A rooted tree on the set $\{1,2,3,4,5\}$.}
\label{rooted_tree}
\end{center}
\end{figure}

They are very classical combinatorial objects, going back at least to Cayley.

\begin{proposition}[Classical result (Cayley)]
  There are $n^{n-1}$ distinct rooted trees with vertices $\{1,2,\dots,n\}$.
\end{proposition}

This statement has many proofs, some of them very elegant (see
\cite[Chap. 24]{ziegler} and references therein).

\subsection{The NAP operad}

The $\NAP$ operad has been introduced by Livernet \cite{livernetNAP}.
The name $\NAP$ stands for ``non-associative permutative.''

The set $\NAP(I)$ is the set of rooted trees on $I$. 

The unit is the unique rooted tree on the set $\{i\}$ for any singleton.

Composition $\circ_i$ of a rooted tree $T$ at the vertex $i$ of a rooted tree
$S$ is described as follows.

Consider the forest obtained by removing the vertex $i$ of $S$. Take the disjoint union with $T$. Add an edge between the root of $T$ and all vertices of the forest that were connected to $i$ in $S$.

The root of the result is taken to be the root of $S$ if $i$ is not the root of $S$ and the root of $T$ otherwise.

\begin{figure}
\begin{center}
\includegraphics[height=3cm]{compo_NAP.eps} 
\caption{Example of $\circ_2$ product in $\NAP$ from $\NAP(\{1,2,3,4,5\}) \times \NAP(\{6,7,8,9\})$ to $\NAP(\{1,3,4,5,6,7,8,9\})$.}
\label{compo_NAP}
\end{center}
\end{figure}

An example is given in Figure \ref{compo_NAP}. One simply has to identify the root of $T$ and the vertex $i$ of $S$. The label $i$ disappears.

\subsection{Symmetric operads in vector spaces}

One can play a similar game using vector spaces instead of finite sets. 

A \textbf{vectorial species} is a functor from the category of finite sets and bijections to the category of vector spaces.

Just as before in the case of sets, this is equivalent to the notion
of an $\sym$-module, which is the data of a collection of modules for
all symmetric groups.

Then the same definition as in section \ref{def_symm_operad}, but
considered for vectorial species instead of species, gives a notion of a symmetric operad in the category of vector spaces.

\subsection{Example: the PreLie operad and pre-Lie algebras}

Before explaining the pre-Lie operad, let us say a few words on the
notion of a pre-Lie algebra which is attached to it.

The Pre-Lie operad has been introduced in \cite{prelie}.  But the
notion of a pre-Lie algebra was known long before. It was used by
Gerstenhaber in his study of deformation theory \cite{gerst}. There is
a pre-Lie algebra structure on the Hochschild complex.

It was also used in relation with vector fields on the affine space,
or more generally on spaces endowed with a flat and torsion-free connection,
\textit{i.e.}, an affine structure. The space of sections of the tangent bundle then
has the structure of a pre-Lie algebra.

A pre-Lie algebra is a vector space with a product $\sous$ satisfying
\begin{equation}
  (x \sous y) \sous z -  x \sous (y \sous z)=  (x \sous z) \sous y -  x \sous (z \sous y).
\end{equation}

There are many specific examples of pre-Lie algebras, some of
them more algebraic, others more combinatorial.

For instance, any operad gives a pre-Lie algebra. In the non-symmetric case, the pre-Lie product on the direct sum $\bigoplus_{n} \PP(n)$ is given for $x\in\PP(n)$ and $y\in \PP(m)$ by
\begin{equation}
  x \sous y= \sum_{i=1}^{n} x\circ_i y.
\end{equation}
One can also define a pre-Lie algebra for any symmetric operad, in
a similar way.

Pre-Lie algebras are devices which encode the combinatorics of the ``sum of insertions at all possible
places.''

For instance, one could consider trivalent graphs with three external legs. Then the sum of insertions at all possible vertices defines a pre-Lie product on the vector space spanned by these graphs.

Each pre-Lie algebra gives a Lie algebra, by the formula
\begin{equation}
[x,y]=x \sous y - y \sous x.
\end{equation}

In this way, pre-Lie algebras are some kind of weak associative algebras.

Once we have a Lie algebra, there is a group and a Hopf algebra also.

The commutative Hopf algebra of functions on the group has a nice property: when coordinates are chosen in a nice way, the coproduct is linear on one side.

On a more geometric side, this is related to the notion of a ``group with a left-invariant affine
structure.''

\subsection{The PreLie operad}

Let us now introduce the pre-Lie operad itself.

The set $\pl(I)$ is the set of rooted trees on $I$. 

The unit is the unique rooted tree on the set $\{i\}$ for any singleton.

In a rooted tree, one can orient the edges towards the root.

The composition $\circ_i$ of a rooted tree $T$ at the vertex $i$ of a rooted tree
$S$ is described as a sum over the set of functions from incoming edges at vertex $i$ in $S$ to vertices of $T$. Pick such a function $\phi$.

Consider the forest obtained by removing the vertex $i$ of $S$. Take the disjoint union with $T$.

Add an edge between each vertex of the forest that was connected to $i$ in $S$ and the corresponding vertex of $T$ given by $\phi$.

If the vertex $i$ had an outgoing edge in $S$, connect the other vertex of this edge to the root of $T$.

The root of the result is taken to be the root of $S$ if $i$ is not the root of $S$ and the root of $T$ otherwise.

\begin{figure}
\begin{center}
\includegraphics[height=3cm]{compo_PL.eps} 
\caption{One term in a $\circ_2$ product in $\pl$.}
\label{compo_PL}
\end{center}
\end{figure}

\def\mmm{\kern-.5pt}
Figure~\ref{compo_PL} \mmm displays \mmm one \mmm term \mmm in \mmm a 
\mmm$\circ_2$ \mmm product \mmm in \mmm $\pl$ \mmm from \mmm 
$\pl(\{1,2,3,4,5\}) \times \pl(\{6,7,8,9\})$ to $\pl(\{1,3,4,5,6,7,8,9\})$.


The pre-Lie operad has more structure: it is an anticyclic operad
\cite{anticyclic}. This means that there is natural action of the
symmetric group $\sym_{n+1}$ on the space $\pl(\{1,\dots,n\})$ extending
the action of $\sym_n$.

\medskip

There is a similar ``cyclic'' structure on the operad $\ass$, which is much easier to explain.

Recall that the operad $\ass$ (as a symmetric operad) is based on the
species of lists: $\ass(I)$ is the set of total orders on $I$.

One can uniquely extend a total order on $I$ to a cyclic order on $I \sqcup \{\bullet\}$. Then there is an action of the bigger symmetric group of $I \sqcup \{\bullet\}$ on the set $\ass(I)$.

\medskip

Returning to the pre-Lie case, the action of the bigger symmetric group is not easy to describe. One way is to use the usual injective map from the pre-Lie operad into the Dendriform operad to restrict the cyclic action of the $\dend$ operad.

One can for instance show that the iterated bracket (seen inside the PreLie operad)

\begin{equation}
[[\dots [[n,n-1],n-2],\dots,2],1]
\end{equation}

is (up to sign) in the same orbit as the iterated pre-Lie product 
\begin{equation}
((\dots ((1\sous 2)\sous 3) \dots n-1) \sous n).
\end{equation}


So far, this action is only computable using the operad formalism.
There is no known simpler alternative description.

\section{From operads to groups}

There is a group associated with each operad. This group is defined on
a set of generalised formal power series, which is equipped with a
certain ``composition'' coming from the composition maps of the
operad. The space of functions over this group is a commutative Hopf
algebra, and one can translate everything in the language of Hopf
algebras without difficulty.

We will give the construction and some examples of
particularly nice elements in these groups, some of them being
naturally generating series for some combinatorial objects. References
for this construction are \cite{vdlaan,expon}.

The definition is simpler for non-symmetric operads; let us start with
this case.

Let $\PP$ be a non-symmetric operad in the category of vector spaces. Let
\begin{equation}
\widehat{\PP}=\prod_{n \geq 1} \PP(n).
\end{equation}
As a vector space, this is a completion of the free $\PP$-algebra on
one generator. On this space (seen as a set), there is an associative
product $x \circ y$ which is linear in its left argument. If $x$ is
homogeneous of degree $n$ and $y=\sum_{k \geq 1} y_k$, then
\begin{equation}
x \circ y= \sum_{k_1,\dots,k_n} \gamma(x ; y_{k_1}, \dots, y_{k_n}).
\end{equation}

The $\circ$ product is associative and non-linear in its right
argument. This gives a monoid structure on the set $\widehat{\PP}$.

One can consider the group of invertible elements in this monoid.

The affine subspace of elements $x=\un+\sum_{k \geq 2} x_k$ is a subgroup.

For an operad $\PP$, this will be called the $\PP$-group.

This construction is functorial: a morphism of operads from $\PP$ to $\PQ$ gives a morphism of groups from the $\PP$-group to the $\PQ$-group. 

There is a useful distributivity property between operations in the free $\PP$-algebra and product on the right with an element $G$ of the $\PP$-group:
\begin{equation}
(m(A,B,\dots))G=m(AG,BG,\dots)
\end{equation}
where $A,B,\dots$ are elements in the free $\PP$-algebra and
$m(\dots)$ is the operation in the free $\PP$-algebra induced by an
element $m$ of the operad $\PP$.

For instance, in the case of the Associative operad, the associated
group is just the group of series $f$ in one variable $t$ of the shape
\begin{equation}
f= t+ \sum_{n \geq 2} f_n t^n
\end{equation}
with the group law given by \textbf{composition} of such series. This
group law is of course linear and multiplicative in its left argument:
one has
\begin{equation}
  (f\times g)\circ h = (f\circ h)\times (g\circ h).
\end{equation}

\medskip

In the case of a symmetric operad, the construction is mostly the same.

Let $\PP$ be a symmetric operad in the category of vector spaces. Let
\begin{equation}
\widehat{\PP}=\prod_{n \geq 1} \PP(\{1,\dots,n\})_{\sym_n},
\end{equation}
the product of the coinvariants for the action of the symmetric group. This is the completion of the free $\PP$-algebra on one generator with respect to the filtration by $n$.

There is an associative product $\circ$ on this space, defined by choosing representatives and using the $\gamma$ maps of the operad just as before.

The affine subspace of series where the unit $\un$ has coefficient $1$ is a group.

\subsection{Series of planar binary trees: the OverUnder group}

We give here examples of series in the group associated with the $\OU$ operad.

Let us say that a planar binary tree is a left comb (respectively a right
comb) if it can be written as a power of the tree $\arb{1}$ for the
$/$ product (respectively for the $\backslash$ product). Let us say that a
planar binary tree is a V-shaped tree if it is $\arb{1}$ or can be
written as $\ell/r$ or $\ell\backslash r$ for some left comb $\ell$
and some right comb $r$.

Let us first introduce the sum of all planar binary trees:
\begin{equation*}
\mathtt{A}=\arb{1}+ \arb{12}+\arb{21}+ \arb{123}+\arb{213}+\arb{131}+\arb{312}+\arb{321}+\cdots,
\end{equation*}
and the alternating-sign sum of V-shaped trees
\begin{equation*}
\mathtt{B}=\arb{1}- \arb{12}-\arb{21}+ \arb{123}+ \arb{131}+\arb{321}+\cdots.
\end{equation*}

\begin{theorem}
In the OverUnder group, one has $\mathtt{A}=\mathtt{B}^{-1}$.
\end{theorem}

\begin{proof}

The series $\mathtt{A}$ is easily seen to be the unique solution to
\begin{equation}
\tt{A}=\arb{1}+\tt{A}/\arb{1}+\arb{1}\under \tt{A}+\tt{A}/\arb{1}\under \tt{A}.
\end{equation}
This amounts to saying that a planar binary tree has either zero, one
(left or right) or two subtrees.

Multiplication on the right by $\tt{A}^{-1}$ is distributive with respect
to the over and under products. Hence one gets the following equation:
\begin{equation}
\tt{A}^{-1}=\arb{1}-\arb{1}/\tt{A}^{-1}-\tt{A}^{-1}\under \arb{1}-\arb{1}/\tt{A}^{-1}\under \arb{1}.
\end{equation}
One can check that $\tt{B}$ satisfies this equation. The result
follows by uniqueness.

\end{proof}

This can be generalised, with the same proof, as follows. Let us
introduce a series depending on one parameter $a$ recording the
Narayana statistic on all trees, which is the number of right oriented
leaves (not counting the rightmost leaf):
\begin{equation*}
\mathtt{A}_a=\arb{1}+a\,  \arb{12}+\arb{21}+ a^2\, \arb{123}+a\, \arb{213}+a\,  \arb{131}+a\,  \arb{312}+\arb{321}+\cdots.
\end{equation*}

One can consider the same statistic restricted to V-shaped trees and
with alternating signs:
\begin{equation*}
\mathtt{B}_a=\arb{1}-a\, \arb{12}-\arb{21}+a^2\, \arb{123}+ a\, \arb{131}+\arb{321}+\cdots.
\end{equation*}

\begin{theorem}
  \label{inversion1}
  In the OverUnder group, one has $\mathtt{A}_a=\mathtt{B}_a^{-1}$.
\end{theorem}

\bigskip

Let us now introduce the sum of left combs:
\begin{equation*}
\mathtt{C}=\arb{1}+\arb{12}+ \arb{123}+\cdots,
\end{equation*}
and the sum of right combs:
\begin{equation*}
\mathtt{D}=\arb{1}+\arb{21}+ \arb{321}+\cdots.
\end{equation*}

It follows from Theorem~\ref{inversion1} that the inverse of $\tt{C}$
in the OverUnder group is the alternating version of $\tt{C}$.

One has
\begin{equation}
  \label{relaCD}
  \tt{C}+\tt{C}\under \tt{D}=\tt{D}+\tt{C}/\tt{D}.
\end{equation}
This just means that a V-shaped tree can be decomposed using right
combs and left combs in two different ways.

The \textbf{Tamari lattice} \cite{tamari} is a well-known partial
order on the set of planar binary trees with $n$ vertices. The minimal
element is the left comb tree, the maximal element is the right comb
tree. The covering relations are given by local moves of the shape
$\arb{12}\leq\arb{21}$.

Let us consider the generating function $\mathtt{E}$ for the M{\"o}bius numbers
$\mu(\hat{0},T)$ in the Tamari lattice:
\begin{equation*}
  \mathtt{E}=\arb{1}+ \arb{12}-\arb{21}+ \arb{123}- \arb{213}-\arb{131}+\arb{321}+\cdots.
\end{equation*}

\begin{theorem}
  In the OverUnder group, one has $\mathtt{E}=\mathtt{C}\,\mathtt{D}^{-1}$.
\end{theorem}
The proof uses the formula (\ref{relaCD}) and some known properties of the
Tamari lattices. Details will appear elsewhere.

\bigskip

As there is a map from the OverUnder operad to the Associative operad
(and two maps in the other way), one gets a map from the OverUnder group
to the group of formal power series in one variable.

\smallskip

This map sends a sum of trees $F$ to the series $\sum_{n\geq 1}
f_n t^n$, where $f_n$ is the sum of coefficients of all planar binary trees of
degree $n$ in $F$.

In the other direction, one can map a formal power series in one
variable to a sum of trees by using only left comb trees or right comb
trees.

\begin{equation}
  f=\sum_{n\geq 1} f_n t^n \mapsto F=f_1 \arb{1}+f_2 \arb{12} +f_3 \arb{123} + \cdots.
\end{equation}

\subsection{Series of planar binary trees: the Dendriform group}

Consider again the sum of all planar binary trees, but in a different group:
\begin{equation*}
  \mathtt{A}=\arb{1}+ \arb{12}+\arb{21}+
\arb{123}+\arb{213}+\arb{131}+\arb{312}+\arb{321}+\cdots.
\end{equation*}

In the Dendriform group, $\tt{A}^{-1}$ is the alternating version of
$\tt{A}$. This comes from the fact that $x/(1-x)$ is the functional
inverse of $x/(1+x)$ and the existence of a morphism from the
Associative operad to the Dendriform operad.

The OverUnder group and the Dendriform group share the same underlying set, but they are quite different!

\bigskip

Let us consider now the generating series $\Phi$ for the numbers $\#\{S
\mid S \geq T\}$ in the Tamari lattices:
\begin{equation*}
\Phi=\arb{1}+ 2 \arb{12}+\arb{21}+ 5 \arb{123}+3
\arb{213}+2\arb{131}+2\arb{312}+\arb{321}+\cdots.
\end{equation*}
This can also be seen as a refined generating series for intervals, as
the sum of all coefficients in fixed degree is the total number of
intervals.

There is a similar series for so-called indecomposable intervals,
whose definition we will not recall here:
\begin{equation*}
\Theta=\arb{1}+ \arb{12}+\arb{21}+ 2 \arb{123}+2
\arb{213}+\arb{131}+2\arb{312}+\arb{321}+\cdots.
\end{equation*}

\begin{theorem}
In the Dendriform group, these series satisfy
\begin{equation}
\Theta=\arb{1}+\arb{1}*\Phi \quad\text{ and }\quad \Phi=\Theta+\Phi / \Theta,
\end{equation} 
where $*$ is the associative product in the free dendriform algebra (given by the element $\arb{12}+\arb{21}$ in the Dendriform operad).
\end{theorem}

These equations are proved in a combinatorial way, see \cite{interval_tamari}.

There are nice one-parameter (``quantum'') generalisations of these series, satisfying
\begin{equation}
\Theta=\arb{1}+\arb{1}*\Phi \quad\text{ and }\quad \Phi=\Theta+q \,\Phi / \Theta.
\end{equation} 

\bigskip

As there is a map from the Associative operad to the Dendriform operad, one gets a map from the group of formal power series in one variable to the Dendriform group.

\smallskip

This map sends a series $\sum_{n\geq 1} f_n t^n$ to the sum of planar
binary trees where all trees of degree $n$ have the same coefficient $f_n$.

\begin{multline}
f=\sum_{n\geq 1} f_n t^n\\ 
\mapsto F=f_1 \arb{1}+f_2 (\arb{12} +\arb{21})+f_3 
\Big(\arb{123}+\arb{213}+\arb{131}+\arb{312}+\arb{321} \Big)+\cdots.
\end{multline}

Hence, these series form a sub-group of the Dendriform group.

\bigskip

Recall that we introduced at some point an operad $M$ containing
$\dend$, with $M(n)=\QQ(u_1,\dots,u_n)$.

There is also an associated group, containing the $\dend$ group. Its
elements are formal sums of rational functions in different numbers of
arguments. This is what is called a mould by Ecalle, though he is
using a different group structure and works with more complicated
functions, with $2n$ variables, which do not fit in the present framework.

\subsection{Series of rooted trees: the $\NAP$ group}

Let us introduce the sum of all corollas:
\begin{equation}
\tt{C}=\arb{0}+ \arb{10}+\arb{200}+ \arb{3000}+\arb{40000}+\cdots,
\end{equation}
and the alternating sum of linear trees:
\begin{equation}
\tt{L}=\arb{0}- \arb{10}+\arb{110}- \arb{1110}+\arb{11110}-\cdots.
\end{equation}

\begin{theorem}
In the $\NAP$ group, $\mathtt{C}=\mathtt{L}^{-1}$.
\end{theorem}
The proof uses the functional equation
\begin{equation}
  C=\arb{0}+C \triangleleft \arb{0},
\end{equation}
where $\triangleleft$ is the NAP product on rooted trees; the product
$S \triangleleft T$ is obtained by grafting the root of $T$ on the
root of $S$.

\bigskip

Consider now the series where each rooted tree has weight the inverse of the order of its automorphism group:
\begin{equation}
\tt{A}=\arb{0}+ \arb{10}+\frac{1}{2}\,\arb{200}+ \arb{110}+\frac{1}{6}\,\arb{3000}+\frac{1}{2}\,\arb{1200}+ \arb{2100}+ \arb{1110}+\cdots.
\end{equation}

The inverse of $\tt{A}$ in the $\NAP$ group is the analogous sum
restricted to corollas but with alternating signs:
\begin{equation}
\tt{C}=\arb{0}- \arb{10}+\frac{1}{2}\arb{200}-\frac{1}{6} \arb{3000}+\frac{1}{24}\arb{40000}+\cdots.
\end{equation}
Here the proof is more sophisticated and uses a relationship with some
incidence algebras, see \cite{twohopf}.
 
\bigskip

There are two morphisms from the $\NAP$ group to the
\textbf{multiplicative} group of formal power series: either projects
on corollas or on linear trees. The reader may want to check that this
works in the examples given above.

There is a morphism from the $\NAP$ group to the group of formal power
series for \textbf{composition} given by the sum of the coefficients
of all trees of same degree. This comes from a morphism from $\NAP$ to
the Associative operad.

This is clear in the first example above. In the second example, this
is less obvious. The image of $\tt{A}$ is related to the so-called
Lambert W function which is the functional inverse of $x \exp(x)$.

\subsection{Series of rooted trees: the PreLie group}

The PreLie group has the same underlying set as the $\NAP$ group, but they are distinct.

Consider again the series where each rooted tree has weight the inverse of the order of its automorphism group.
\begin{equation}
\tt{A}=\arb{0}+ \arb{10}+\frac{1}{2}\,\arb{200}+ \arb{110}+\frac{1}{6}\,\arb{3000}+\frac{1}{2}\,\arb{1200}+ \arb{2100}+ \arb{1110}+\cdots.
\end{equation}

Then the inverse of $\tt{A}$ in the PreLie group is the alternating-sign
version of $\tt{A}$. 

The proof goes as follows: first one has to
describe the image of $\tt{A}$ in the $\dend$ group, then compute the
inverse of this image. Details will appear elsewhere.

\bigskip

Consider now the following series
\begin{equation}
\Delta(s,t)=\arb{0}+ (s+t)\,\arb{10}+(s^2+st)\,\arb{200}+ (s^2+2st+t^2)\,\arb{110}+\cdots,
\end{equation}
which is defined by the equation
\begin{equation*}
\Delta=\arb{0}+s\, \Delta \sous \arb{0}+ t\, \arb{0} \sous \Delta.
\end{equation*}

From this equation, it follows that the inverse of $\Delta(s,t)$ in the PreLie group is the alternating-sign version of $\Delta(t,s)$.

One can show that $\Delta$ is related to the statistic ``number of
cycles'' in permutations. 

\bigskip

There is a morphism from the $\pl$ group to the \textbf{multiplicative} group of formal power series, given by projection on corollas.

There is a morphism from the $\pl$ group to the group of formal power series for \textbf{composition}, given by projection on linear trees.

The sum of the coefficients of all trees of same degree defines a morphism from the $\pl$ group to a group of formal power series related to the Witt Lie algebra.

There is a morphism from the $\pl$ group to the $\dend$ group, coming from the morphism from $\pl$ to $\dend$.

\section{Conclusion}

This brief text can not claim to any kind of completeness. We have
forgotten many aspects of operads, focusing on the more combinatorial
ones.

\begin{itemize}
\item There are many more nice operads and morphisms between them.
\item There are many other interesting series in the associated groups.
\item These series over trees can be seen as refined generating series. They can be useful in enumerative problems.
\item There are plenty of interesting Hopf algebras related to these groups.
\item Some of these operads and associated groups are implemented in
  the computer algebra system MuPAD.
\end{itemize}

\bibliographystyle{alpha}
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{BMR{\etalchar{+}}06}

\bibitem[AB03]{aval1}
J.-C. Aval and N.~Bergeron.
\newblock Catalan paths and quasi-symmetric functions.
\newblock {\em Proc. Amer. Math. Soc.}, 131(4):1053--1062 (electronic), 2003.

\bibitem[ABB04]{aval2}
J.-C. Aval, F.~Bergeron, and N.~Bergeron.
\newblock Ideals of quasi-symmetric functions and super-covariant polynomials
  for {$S\sb n$}.
\newblock {\em Adv. Math.}, 181(2):353--367, 2004.

\bibitem[AZ04]{ziegler}
Martin Aigner and G{\"u}nter~M. Ziegler.
\newblock {\em Proofs from {T}he {B}ook}.
\newblock Springer-Verlag, Berlin, third edition, 2004.
\newblock Including illustrations by Karl H. Hofmann.

\bibitem[Bes03]{bessis}
D.~Bessis.
\newblock The dual braid monoid.
\newblock {\em Ann. Sci. \'Ecole Norm. Sup. (4)}, 36(5):647--683, 2003.

\bibitem[BLL98]{bergeron}
F.~Bergeron, G.~Labelle, and P.~Leroux.
\newblock {\em Combinatorial species and tree-like structures}, volume~67 of
  {\em Encyclopedia of Mathematics and its Applications}.
\newblock Cambridge University Press, Cambridge, 1998.
\newblock Translated from the 1994 French original by Margaret Readdy, With a
  foreword by Gian-Carlo Rota.

\bibitem[BMR{\etalchar{+}}06]{bmrrt}
A.~B. Buan, R.~Marsh, M.~Reineke, I.~Reiten, and G.~Todorov.
\newblock Tilting theory and cluster combinatorics.
\newblock {\em Adv. Math.}, 204(2):572--618, 2006.

\bibitem[But72]{butcher}
J.~C. Butcher.
\newblock An algebraic theory of integration methods.
\newblock {\em Math. Comp.}, 26:79--106, 1972.

\bibitem[BV73]{bovo}
J.~M. Boardman and R.~M. Vogt.
\newblock {\em Homotopy invariant algebraic structures on topological spaces}.
\newblock Springer-Verlag, Berlin, 1973.
\newblock Lecture Notes in Mathematics, Vol. 347.

\bibitem[CGH{\etalchar{+}}96]{corless}
R.~M. Corless, G.~H. Gonnet, D.~E.~G. Hare, D.~J. Jeffrey, and D.~E. Knuth.
\newblock On the {L}ambert {$W$} function.
\newblock {\em Adv. Comput. Math.}, 5(4):329--359, 1996.

\bibitem[Cha02]{expon}
F.~Chapoton.
\newblock {Rooted trees and an exponential-like series}, 2002.
\newblock unpublished, arXiv:math.QA/0209104.

\bibitem[Cha05]{anticyclic}
F.~Chapoton.
\newblock On some anticyclic operads.
\newblock {\em Algebr. Geom. Topol.}, 5:53--69 (electronic), 2005.

\bibitem[Cha06]{interval_tamari}
F.~Chapoton.
\newblock Sur le nombre d'intervalles dans les treillis de Tamari.
\newblock {\em S\'eminaire Lotharingien de Combinatoire}, 55:B55f, 2006.
\newblock http://www.citebase.org/abstract?id=oai:arXiv.org:math/0602368.

\bibitem[Cha07]{mould}
F.~Chapoton.
\newblock The anticyclic operad of moulds.
\newblock {\em IMRN}, 2007.
\newblock doi:10.1093/imrn/rnm078.

\bibitem[CK98]{conneskreimer}
A.~Connes and D.~Kreimer.
\newblock Hopf algebras, renormalization and noncommutative geometry.
\newblock {\em Comm. Math. Phys.}, 199(1):203--242, 1998.

\bibitem[CL01]{prelie}
F.~Chapoton and M.~Livernet.
\newblock Pre-{L}ie algebras and the rooted trees operad.
\newblock {\em Internat. Math. Res. Notices}, (8):395--408, 2001.

\bibitem[CL07]{twohopf}
F.~Chapoton and M.~Livernet.
\newblock Relating two Hopf algebras built from an operad.
\newblock {\em IMRN}, rnm131:27, 2007.
\newblock doi:10.1093/imrn/rnm131.

\bibitem[Eca03]{ecalle}
J.~Ecalle.
\newblock A{RI}/{GARI}, la dimorphie et l'arithm\'etique des multiz\^etas: un
  premier bilan.
\newblock {\em J. Th\'eor. Nombres Bordeaux}, 15(2):411--478, 2003.

\bibitem[Fra08]{frabetti}
A.~Frabetti.
\newblock Groups of tree-expanded series.
\newblock {\em Journal of Algebra}, 319(1):377--413, 2008.

\bibitem[FZ03]{ysystems}
S.~Fomin and A.~Zelevinsky.
\newblock {$Y$}-systems and generalized associahedra.
\newblock {\em Ann. of Math. (2)}, 158(3):977--1018, 2003.

\bibitem[Ger64]{gerst}
M.~Gerstenhaber.
\newblock On the deformation of rings and algebras.
\newblock {\em Ann. of Math. (2)}, 79:59--103, 1964.

\bibitem[GK94]{ginzkapr}
Victor Ginzburg and Mikhail Kapranov.
\newblock Koszul duality for operads.
\newblock {\em Duke Math. J.}, 76(1):203--272, 1994.

\bibitem[GK95]{getzler_cyclic}
E.~Getzler and M.~M. Kapranov.
\newblock Cyclic operads and cyclic homology.
\newblock In {\em Geometry, topology, \& physics}, Conf. Proc. Lecture Notes
  Geom. Topology, IV, pages 167--201. Int. Press, Cambridge, MA, 1995.

\bibitem[Hil06]{hille}
L.~Hille.
\newblock On the volume of a tilting module.
\newblock {\em Abh. Math. Sem. Univ. Hamburg}, 76:261--277, 2006.

\bibitem[HT72]{tamari}
S.~Huang and D.~Tamari.
\newblock Problems of associativity: {A} simple proof for the lattice property
  of systems ordered by a semi-associative law.
\newblock {\em J. Combinatorial Theory Ser. A}, 13:7--13, 1972.

\bibitem[Joy86]{joyal}
A.~Joyal.
\newblock Foncteurs analytiques et esp\`eces de structures.
\newblock In {\em Combinatoire \'enum\'erative (Montreal, Que., 1985/Quebec,
  Que., 1985)}, volume 1234 of {\em Lecture Notes in Math.}, pages 126--159.
  Springer, Berlin, 1986.

\bibitem[Lab81]{labelle}
Gilbert Labelle.
\newblock Une nouvelle d\'emonstration combinatoire des formules d'inversion de
  {L}agrange.
\newblock {\em Adv. in Math.}, 42(3):217--247, 1981.

\bibitem[Liv06]{livernetNAP}
M.~Livernet.
\newblock A rigidity theorem for pre-{L}ie algebras.
\newblock {\em J. Pure Appl. Algebra}, 207(1):1--18, 2006.

\bibitem[Lod96]{bourbaki}
J.-L. Loday.
\newblock La renaissance des op\'erades.
\newblock {\em Ast\'erisque}, (237):Exp.\ No.\ 792, 3, 47--74, 1996.
\newblock S\'eminaire Bourbaki, Vol.\ 1994/95.

\bibitem[Lod01]{dialgebras}
J.-L. Loday.
\newblock Dialgebras.
\newblock In {\em Dialgebras and related operads}, volume 1763 of {\em Lecture
  Notes in Math.}, pages 7--66. Springer, Berlin, 2001.

\bibitem[LR02]{lodayronco}
J.-L. Loday and M.~O. Ronco.
\newblock Order structure on the algebra of permutations and of planar binary
  trees.
\newblock {\em J. Algebraic Combin.}, 15(3):253--270, 2002.

\bibitem[LSV97]{renaissance}
J.-L. Loday, J.~D. Stasheff, and A.~A. Voronov, editors.
\newblock {\em Operads: {P}roceedings of {R}enaissance {C}onferences}, volume
  202 of {\em Contemporary Mathematics}.
\newblock American Mathematical Society, Providence, RI, 1997.
\newblock Papers from the Special Session on Moduli Spaces, Operads and
  Representation Theory held at the AMS Meeting in Hartford, CT, March 4--5,
  1995, and from the Conference on Operads and Homotopy Algebra held in Luminy,
  May 29--June 2, 1995.

\bibitem[Mac95]{macdonald}
I.~G. Macdonald.
\newblock {\em Symmetric functions and {H}all polynomials}.
\newblock Oxford Mathematical Monographs. The Clarendon Press Oxford University
  Press, New York, second edition, 1995.
\newblock With contributions by A. Zelevinsky, Oxford Science Publications.

\bibitem[May72]{may}
J.~P. May.
\newblock {\em The geometry of iterated loop spaces}.
\newblock Springer-Verlag, Berlin, 1972.
\newblock Lectures Notes in Mathematics, Vol. 271.

\bibitem[MSS02]{markl_shnider}
M.~Markl, S.~Shnider, and J.~Stasheff.
\newblock {\em Operads in algebra, topology and physics}, volume~96 of {\em
  Mathematical Surveys and Monographs}.
\newblock American Mathematical Society, Providence, RI, 2002.

\bibitem[Noy98]{noy}
M.~Noy.
\newblock Enumeration of noncrossing trees on a circle.
\newblock In {\em Proceedings of the 7th Conference on Formal Power Series and
  Algebraic Combinatorics (Noisy-le-Grand, 1995), Discrete Math.}, volume 180,
  pages 301--313, 1998.

\bibitem[Pit99]{pitman}
Jim Pitman.
\newblock Coalescent random forests.
\newblock {\em J. Combin. Theory Ser. A}, 85(2):165--193, 1999.

\bibitem[Smi01]{smirnov}
V.~A. Smirnov.
\newblock {\em Simplicial and operad methods in algebraic topology}, volume 198
  of {\em Translations of Mathematical Monographs}.
\newblock American Mathematical Society, Providence, RI, 2001.
\newblock Translated from the Russian manuscript by G. L. Rybnikov.

\bibitem[Sta97]{stanley}
R.~P. Stanley.
\newblock {\em Enumerative combinatorics. {V}ol. 1}, volume~49 of {\em
  Cambridge Studies in Advanced Mathematics}.
\newblock Cambridge University Press, Cambridge, 1997.
\newblock With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986
  original.

\bibitem[vdL04]{vdlaan}
P.~van~der Laan.
\newblock {\em Operads. Hopf algebras and coloured Koszul duality}.
\newblock PhD thesis, Universiteit Utrecht, 2004.

\end{thebibliography}

\end{document}
