 
% 10 Sept 2004

%\input{intseries.preamble}

\documentclass[12pt]{amsart}
\usepackage[all]{xy}
%\addtolength{\hoffset}{-2cm}

%\addtolength{\textwidth}{3cm}

%\addtolength{\marginparwidth}{-1cm}


%preamble
\swapnumbers
\newtheorem{thm}[subsection]{Theorem}
\newtheorem{prop}[subsection]{Proposition}
\newtheorem{lemma}[subsection]{Lemma}
\newtheorem{cor}[subsection]{Corollary}
\theoremstyle{remark}
\newtheorem{rem}[subsection]{Remark}


% DEBUT DES MACROS LOCALES


\def\d{\succ}
\def\g{\prec}

\def\DD{\Delta}
\def\aa{\alpha}
\def\bb{\beta}
\def\cc{\gamma}
\def\dd{\delta}

\def\Prim{\operatorname{Prim}}
\def\Hom{\operatorname{Hom}}
\def\Id{\mathrm{Id}}

\def\oo{\omega}
\def\PP{{\mathcal P}}
\def\vect{\mathtt{Vect }}
\def\t{\otimes}

%Arbres

\def\arbreA{\xymatrix@R=3pt@C=3pt{
&& \\
&*{}\ar@{-}[ur] \ar@{-}[ul] \ar@{-}[d]     &\\
&&
}}

\def\arbreBA{\xymatrix@R=2pt@C=2pt{
&&&&\\
&&&*{}\ar@{-}[ul] & \\
&&*{}\ar@{-}[uurr] \ar@{-}[uull] \ar@{-}[d]     &&\\
&&&&
}}

\def\arbreAB{\xymatrix@R=2pt@C=2pt{
&&&&\\
&*{}\ar@{-}[ur] &&& \\
&&*{}\ar@{-}[uurr] \ar@{-}[uull] \ar@{-}[d]     &&\\
&&&&
}}

\def\arbreBB{\xymatrix@R=2pt@C=2pt{
&&&&\\
&&&& \\
&&*{}\ar@{-}[uurr] \ar@{-}[uull] \ar@{-}[d] \ar@{-}[uu]     &&\\
&&&&
}}

\def\arbreABC{\xymatrix@R=1pt@C=1pt{
&&&&&&\\
&*{}\ar@{-}[ur] &&&&& \\
&&*{}\ar@{-}[uurr] &&&&\\
&&&*{}\ar@{-}[uuurrr] \ar@{-}[uuulll] \ar@{-}[d] &&&\\
&&&&&&
}}

\def\arbreBAC{\xymatrix@R=1pt@C=1pt{
&&&&&&\\
&&&*{}\ar@{-}[ul] &&& \\
&&*{}\ar@{-}[uurr] &&&&\\
&&&*{}\ar@{-}[uuurrr] \ar@{-}[uuulll] \ar@{-}[d] &&&\\
&&&&&&
}}

\def\arbreACA{\xymatrix@R=1pt@C=1pt{
&&&&&&\\
&*{}\ar@{-}[ur] &&&&*{}\ar@{-}[ul] & \\
&&&&&&\\
&&&*{}\ar@{-}[uuurrr] \ar@{-}[uuulll] \ar@{-}[d] &&&\\
&&&&&&
}}

\def\arbreCAB{\xymatrix@R=1pt@C=1pt{
&&&&&&\\
&&&*{}\ar@{-}[ur] &&& \\
&&&&*{}\ar@{-}[uull] &&\\
&&&*{}\ar@{-}[uuurrr] \ar@{-}[uuulll] \ar@{-}[d] &&&\\
&&&&&&
}}


\def\arbreCBA{\xymatrix@R=1pt@C=1pt{
&&&&&&\\
&&&&&*{}\ar@{-}[ul] & \\
&&&&*{}\ar@{-}[uull] &&\\
&&&*{}\ar@{-}[uuurrr] \ar@{-}[uuulll] \ar@{-}[d] &&&\\
&&&&&&
}}

\def\arbreBAdecore{\xymatrix@R=2pt@C=2pt{
&&&&\\
&&&*{}\ar@{-}[ul] &\epsilon(i+1) \\
&&*{}\ar@{-}[uurr] \ar@{-}[uull] &&\\
&&\epsilon(i)&&
}}

\def\arbreABdecore{\xymatrix@R=2pt@C=2pt{
&&&&\\
\epsilon(i)&*{}\ar@{-}[ur] &&& \\
&&*{}\ar@{-}[uurr] \ar@{-}[uull]      &&\\
&&\epsilon(i+1)&&
}}

% FIN DES MACROS LOCALES

\begin{document}

\author[J.-L. Loday]{Jean-Louis Loday}
\address{Institut de Recherche Math\'ematique Avanc\'ee\\
    CNRS et Universit\'e Louis Pasteur\\
    7 rue R. Descartes\\
    67084 Strasbourg Cedex, France}
\email{loday@math.u-strasbg.fr}
\urladdr{www-irma.u-strasbg.fr/{$\sim$}loday/}
\title{Inversion of integral series enumerating  planar trees}
%\alttitle{}
\subjclass[2000]{}
\keywords{Integer sequence, generating series, planar tree, excluded pattern, operad, Koszul duality}

%\dedicatory{}
\date{\today}

\begin{abstract}
We consider an integral series $f(X,t)$ which depends on the choice of a set $X$ of labelled planar rooted trees. We
prove that its inverse with respect to composition is of the form $f(Z,t)$ for another set $Z$ of trees, deduced from
$X$. The proof is self-contained, though inspired by the Koszul duality theory of quadratic operads. In the same vein we give a conceptual proof for the formulas giving the coefficients of the inverse with respect to composition of the generic formal power series.
\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 53 \rms (2005), Article~B53d\hfill}
\def\thepage{}
%
%

\section{Introduction} \label{S:int}

Let $I$ be a finite set of indices. Let $Y_n\times I^n$ be the set of planar binary rooted trees whose $n$ vertices are
 labelled by elements in the index set $I$. Let $X$ be a subset of $Y_2\times I^2$ and let $Z$ be its complement.
Define $X_n$ as the subset of $Y_n\times I^n$ made of labelled trees whose local patterns are in $X$. In other
words, a tree is in $X_n$ if for every pair of adjacent vertices the subtree defined by this pair is in $X$. By
convention
$X_0=Y_0\times I^0$ and $X_1=Y_1\times I$. From the definition of $X_n$ it follows immediately that $X_2=X$.
The set $Z$ determines similarly a sequence $Z_n$.

The alternating generating series of $X$ is by definition
\begin{equation*}f(X,t) := \sum_{n\geq 0} (-1)^{n+1} (\# X_{n}) t^{n+1} = -t + (\# I)t^2 -  (\# X)t^3 +\cdots \ .
\end{equation*}
\noindent {\bf Theorem.} {\it If $Z$ is the complement of $X$, i.e.,
$X \sqcup Z= Y_2\times I^2$, then the generating series of $X$ and $Z$ are inverse to each other with respect to composition:
$$f(X, f(Z,t)) = t .$$
}

For some choices of $I$ and $X$ the integer sequence $(\# X_{n})_{n\geq 0}$ appear in the data base ``On-line Encyclopedia of Integer sequences!" \cite {Sloane},
but for some others they do not.

 Here is an application of this theorem.
Given an integer sequence ${\underline a}=(a_0, \ldots, a_n, \ldots)$, it is often interesting to know a combinatorial
 interpretation of these numbers, that is, to know a family $X_n$ of combinatorial objects such that $a_n = \# X_n$.
The theorem provides a solution for some integer sequences as follows. Suppose that the inverse with respect to composition
of the alternating series of ${\underline a}$ gives an integer sequence ${\underline b}$ which can be interpreted
combinatorially by labelled trees. Then the integer sequence ${\underline a}$ admits also such an interpretation, see \ref{Examples}.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL JEAN-LOUIS LODAY}{\SMALL INVERSION OF INTEGRAL SERIES ENUMERATING PLANAR TREES}
%
%


Our proof of the theorem consists in constructing a chain complex whose Poincar\'e series is exactly
 $f(X, f(Z,t))$. Then we prove that this chain complex is acyclic (i.e., the homology groups are 0 except $H_1$ which
is of dimension 1) by reducing it to the sum of subcomplexes which
turn out to be augmented chain complexes of standard simplices. Hence the Poincar\'e series is $t$.

Our proof is self-contained but the idea of considering this particular chain complex is inspired by the theory of quadratic operads. Indeed the
choice of
$X$ determines a certain type of algebras, i.e., a certain quadratic operad, and the choice of $Z$ gives the ``dual
operad" in the Koszul duality sense cf.~\cite{G-K}. Then the chain complex is the Koszul complex attached to this dual  pair of
operads. So our main theorem gives a large family of Koszul operads.

We give all the details for the case of binary trees, but this method can be generalized to planar trees. We outline the  case of $k$-ary trees. A surprising consequence is the following property of the Catalan numbers $c_n$. The series $h(t) = \sum_{n\geq 0}(-1)^{n+1}c_nt^{3n+1}$ is its own inverse with respect to composition: $h(h(t))=t$.

The formula for the inverse of the generic formal power series is well-known. The coefficients which show up are the numbers of the planar trees of a given type. In the last section we give a conceptual proof of this formula by using Koszul duality of an elementary operad.

\bigskip

After the release of the first version of this paper, I was informed by Prof.~I.~Gessel that his student S.F.~Parker obtained the same result by combinatorial methods in her thesis (unpublished). A far reaching generalization of our result has been obtained subsequently by R.~Bacher in \cite{B} using a different technique.

\section{Labelled trees}
\subsection{Planar binary rooted trees}
Denote by $Y_n$ the set of {\it planar binary rooted trees} of degree $n$, that is, with $n$ vertices (with valency $2+1$):
\begin{displaymath}
Y_0 = \{\  \vert \ \}\  , \quad Y_1=\big\{ \vcenter{\arbreA}\big\}\  , \quad
{Y_2=\Big\{ L:= \vcenter{\arbreAB}\ ,\  {R:=\vcenter{\arbreBA} }}\Big\}
\end{displaymath}
\begin{displaymath}
{Y_3=\Bigg\{ \vcenter{\arbreABC}}\ ,\  {{}\vcenter{\arbreBAC }},\  {{}\vcenter{\arbreACA }},\  {{}\vcenter{\arbreCAB }},\  {{}\vcenter{\arbreCBA }}\Bigg\}
\end{displaymath}

Observe that the end of the leaves and of the root are not considered as vertices. This notion of vertex is sometimes referred to as ``internal vertex'' in the literature.

The number of elements in $Y_n$ is the so-called {\it Catalan number} $c_n=\frac {(2n)!}{n!(n+1)!}, $ cf.~\ref{Examples} (b). Let $I$ be a
 finite set of indices. By definition a {\it labelled tree} is a planar binary rooted tree such that
each vertex is labelled by an element of $I$. These elements need not be distinct. Therefore the set of
labelled trees of degree $n$ is in bijection with $Y_n\times I^n$.

An element of $Y_2\times I^2$ is either of the form $(L; i_1,
i_2)$ or of the form $(R; i_1, i_2)$:
$$\xymatrix@R=2pt@C=2pt{
*{}&&*{}&&&&\\
&\ar@{-}[ur]\ar@{-}[ul] i_1&&& &\\
&&&&&\\
&&\ar@{-}[uuurrr] \ar@{-}[uul] \ar@{-}[d] i_2    &&&\\
&&*{}&&&
}\qquad  \qquad
\xymatrix@R=2pt@C=2pt{
*{}&&&*{}&&*{}&\\
&&&&\ar@{-}[ul] \ar@{-}[ur] i_2 && \\
&&&&&&\\
&&&\ar@{-}[uur] \ar@{-}[uuulll] \ar@{-}[d] i_1    &&&\\
&&&*{}&&&.
}$$

Let $X$ be a subset of $Y_2\times I^2$ and let $Z$ be its complement. We define a subset $X_n$ of  $Y_n\times I^n$ as
 follows.  A pair of adjacent vertices in the labelled tree $y$ determines a subtree of degree $2$, called a
\emph {local pattern}. The labelled tree $y$ is in $X_n$ if and only if all its local patterns belong to $X$. In
other words we exclude all the trees which have a local pattern which belongs to $Z$. It is clear that $X_2=X$. By
convention we define
$X_0=Y_0\times I^0$ and $X_1=Y_1\times I$.

The alternating generating series of $X$ is determined by the integer sequence $(\# X_n)_{n\geq 0}$ as follows:
\begin{equation*}f(X,t) := \sum_{n\geq 0} (-1)^{n+1} (\# X_{n}) t^{n+1} = -t + (\# I)t^2 -  (\# X)t^3 +\ldots \ .
\end{equation*}

If, instead of $X$, we start with $Z$, then we get another family  $Z_n$. For $n=2$, $Z_2$ is the complement of $X_2$, but this property does not hold for higher $n$'s.

\begin{thm} \label{THM}  If $Z$ is the complement of $X$, i.e., $X \sqcup Z= Y_2\times I^2$, then the generating series
of
$X$ and
$Z$ are inverse to each other with respect to composition:
$$f(X, f(Z,t)) = t .$$
\end{thm}
The proof is given in the next section.

\subsection{Examples}\label{Examples}  We list a few interesting examples of integer sequences and their dual which appear in the study of quadratic operads (cf. ~\cite{L3}). The notation is as follows: the sequence $(a_0, \cdots , a_n, \cdots )$ is such that $a_n = \#X_n$ and $f(t)= \sum_{n\geq 0}(-1)^{n+1}a_nt^{n+1}$.
The dual sequence is  $(b_0, \cdots , b_n, \cdots )$ where $b_n = \#Z_n$ and $g(t)= \sum_{n\geq 0}(-1)^{n+1}b_nt^{n+1}$.

Observe that $a_0 = 1$, $a_1 = \# I$, $a_2 = \#X$ and $0\leq a_2\leq 2(a_1)^2$. In the following examples  we can write $g(t)$ as a rational function, hence we get a
 combinatorial interpretation of the integer sequence $\underline a$ whose alternating series $f(t)$ is determined by the functional equation $g(f(t))=t$.
\medskip

\noindent (a) $(1, 1,1, \ldots, 1, \ldots )$ versus itself.
\begin{itemize}
\item $I=\{1\}$, $X= \{L\}$ and $Z=\{R\}$.
\item $f(t)=g(t) = \frac {-t}{1+t}$.
\end{itemize}

\noindent (b) $(1, 1, 2, 5, 14, 42, 132, \cdots, c_n=\frac{(2n)!}{(n+1)! n!}, \ldots )$ versus $(1,1,0, \ldots , 0, \ldots $).
\begin{itemize}
\item  $I=\{1\}, Z=\emptyset$,  $X=Y_2$.
\item $g(t) = -t+t^2$.
\item We get the well known functional equation for the generating series of the Catalan numbers $c(t):= \sum_{n\geq 0} c_nt^n$,
\[ tc(t)^2 - c(t) +1 = 0. \]
\end{itemize}

\noindent (c)  $(1, 2, 6, 22, 90, \cdots, 2C_{n}, \ldots )$ versus $(1,2,2, \ldots , 2, \ldots $).
\begin{itemize}
\item$C_n$ is the super Catalan number (also called Schr\"oder number), that is, the number of planar trees with $n+1$ leaves.
\item $I=\{1,2\}$, $Z=\{(L;1,1), (R;2,2)\}$ and $X$ has 6 elements.
\item It is immediate to see that $Z_n$
has only two elements: the left comb indexed by $1$'s and the right comb indexed by $2$'s. Therefore
$g(t) = \frac {-t+t^2}{1+t}$. On the other hand, one can show that, for $n\geq
2$, there is a bijection between the elements of $X_n$ and two copies of the set of planar trees with $n+1$ leaves (see \cite{L-R2} for a variant of this result). The theorem gives the well known functional equation for
the generating series of the super Catalan numbers $C(t):= \sum_{n\geq 0} C_nt^n$,
\[ tC(t)^2 +(1-t)C(t) -1 = 0. \]
\end{itemize}

\noindent (d)  $(1, 2, 6, 21,80, \ldots )$ versus $(1,2,2,1,0,\ldots, 0 , \ldots )$.
\begin{itemize}
\item $I=\{1,2\}$, $Z=\{(L;2,1), (R;1,2)\}$ and $X$ has 6 elements.
\item It is immediate to see that $Z_3$
has only one element and that $Z_n$ is empty for $n\geq 4$. Hence $g(t)=-t+2t^2-2t^{3}+t^4$.
\item This example and the previous one show that the integer sequence determined by $X$ does not depend only on the number of elements of $I$ and $X$.
\end{itemize}

\noindent (e)  $(1, 2, 7, 31, 154, \ldots )$ versus $(1,2,1,1,\ldots, 1 , \ldots )$.
\begin{itemize}
\item Let $I=\{1,2\}$, $Z=\{(L;1,1)\}$ and $X$ has 7 elements.
\item It is immediate to see that for $n\geq 2$,
$Z_n$ has only one element: the left comb indexed by $1$'s. Hence  $g(t)= \frac {-t+t^2+t^3}{1+t}$.
\end{itemize}

\noindent (f)  $(1, 3, 17, 121, 965, \cdots )$ versus $(1,3,1,1,\ldots, 1 , \ldots )$, and \\
\indent $(1, k, 2k^2-1, 5\, 3^k -5k+1\cdots, ?, \cdots )$ versus $(1,k,1,1,\ldots, 1 , \ldots )$.
\begin{itemize}
\item $I=\{1,\cdots , k\}$, $Z=\{(L;1,1)\}$ and $X$  has $2k^2-1$ elements.
\item It is immediate to see that, for $n\geq 2$,  $Z_n$ has only one element.
Hence $g(t)= \frac {-t+(k-1)(1+t)t^2}{1+t}$.
\end{itemize}

%\noindent (g) $(1, 3, 13, 67, 381, \cdots )$ versus $(1,3,5,7,\ldots, 2n-1,\ldots )$

\noindent (g)  $(1, 3, 14, 80, 510, \cdots )$ versus $(1,3,4,5,\ldots, n+2,\ldots )$.
\begin{itemize}
\item I=$\{1,2,3\}$, $Z= \{(L;1,1), (L;2,1), (R;2,2), (R;3,3)\}$, $X$ has $14$ elements.
\item One checks that $Z_n$ is made of $(n+1)+1$ elements. Hence $g(t)=\frac{t(-1+t+t^2)}{(1+t)^2}$.
\end{itemize}

\noindent (h)  $(1, 4, 23, 156, 1162, \cdots )$ versus $(1,4,9,16,\ldots, (n+1)^2,\ldots )$.
\begin{itemize}
\item I=$\{\nwarrow, \nearrow, \searrow, \swarrow \}$, in the following we write $Rij$ in place of $(R;i,j)$:
\[ Z= \left\{
\begin{array}{ccc}
R\nwarrow \nwarrow  & R\nearrow \nwarrow  & L\nearrow \nearrow   \\
R\swarrow \nwarrow  & R\searrow \nwarrow  & L\searrow \nearrow  \\
R\swarrow \swarrow  & L\searrow \swarrow  & L\searrow \searrow   \\
\end{array}\right\}
\]
\item We have shown in \cite[Proposition~4.4]{A-L} that  $Z_n= (n+1)^2$, hence $g(t)=\frac{t(-1+t)}{(1+t)^3}$.
\item The first sequence has been given a different combinatorial interpretation in terms of connected non-crossing configurations in \cite{Flajolet}.
\end{itemize}

\noindent (i)  $(1, 9, 113, \cdots )$ versus $(1,9,49,\ldots,  )$.
\begin{itemize}
\item $I$ is a set of $9$ indices denoted
$ \begin{array}{ccc}
\nwarrow  & \uparrow  & \nearrow  \\
 \leftarrow  & \circ  & \rightarrow  \\
 \swarrow  & \downarrow  & \searrow  \\
\end{array}
$
and $Z$ is made of the following 49 elements (indexed by the cells of $\Delta^2\times \Delta^2$):

\[ \begin{array}{ccccccc}
R\nwarrow \nwarrow  & R\nearrow \nwarrow  & L\nearrow \nearrow  & R\nearrow \uparrow  & R\nwarrow \uparrow  & R \uparrow \nwarrow & R\uparrow \uparrow \\
R\swarrow \nwarrow  & R\searrow \nwarrow  & L\searrow \nearrow  & R\searrow \uparrow  & R\swarrow \uparrow  & L\downarrow \nwarrow  & R\downarrow \uparrow  \\
R\swarrow \swarrow  & L\searrow \swarrow  & L\searrow \searrow  & R\searrow \downarrow  & L\swarrow \downarrow  & L\downarrow \swarrow  & L\downarrow \downarrow  \\
R\swarrow \leftarrow  & R\searrow \leftarrow  & L\searrow \rightarrow  & R\searrow \circ  & R\swarrow \circ  & L\downarrow \leftarrow  & R\downarrow \circ  \\
R\nwarrow \leftarrow  & R\nearrow \leftarrow  & L\nearrow \rightarrow  & R\nearrow \circ  & R\nwarrow \circ  & L\uparrow \leftarrow  & R\uparrow \circ  \\
R\leftarrow \nwarrow  & L\rightarrow \nwarrow  & L\rightarrow \nearrow  & R\rightarrow \uparrow  & L\leftarrow \uparrow  & L\circ \nwarrow  & L\circ \uparrow  \\
R\leftarrow \leftarrow  & R\rightarrow \leftarrow  & L\rightarrow \rightarrow  & R\rightarrow \circ  & R\leftarrow \circ  & L\circ \leftarrow  & R\circ \circ  \\
\end{array}
\]

\item Unfortunately we do not know how to compute the number of elements in $Z_n$. This example is strongly related to dendriform trialgebras \cite{L-R1} and motivated by the  ennea-algebras \cite {Leroux}.
\end{itemize}

Added after the release of the first version: a thorough study of this example has been performed in \cite{B}.

\section{Koszul complex and the Theorem}
Only elementary homological algebra methods are used in the proof. The reader may find them in standard textbooks on homological algebra such as, for instance, \cite{Bbki}.

\subsection{Koszul complex}

Given a planar binary rooted tree $y\in Y_n$, one  numbers the leaves from left to
right by $0, \ldots , n$. Accordingly, one numbers the vertices by $1, \ldots, n$, the $i$th
vertex being in between the leaves $i-1$ and $i$. So a decoration is a map $\epsilon$ from
$\{1,\ldots, n\}$ to $I$. A vertex of $y$ is said to be a \emph{cup} if it is directly
connected to two leaves (no intermediate node). In the following example $z$ has a cup at
vertex $1$ and vertex $3$:
\[ \arbreACA \]
The grafting of two treees $y$ and $y'$ is the new tree $y\vee y'$ obtained from $y$ and $y'$ by joining the roots to a new vertex and adding a new root. For instance, the above tree is the grafting $\vcenter{\arbreA} \vee \vcenter{\arbreA}$.

We define a chain complex ${\mathcal K}_* = ({\mathcal K}_n , d)_{n>0}$ over the field ${\mathbb K}$ as follows. The
space of $(n+1)$-chains is
$$ {\mathcal K}_{n+1} := \bigoplus {\mathbb K}[Z_n \times X_{i_0} \times \cdots \times  X_{i_n}]$$
where the sum is over all $(n+1)$-tuples $(i_0, \cdots , i_n)$, where $i_j\geq 0$. The boundary map $d :
{\mathcal K}_{n+1}\to {\mathcal K}_{n}$ is of the form $d= \sum_{i=1}^n (-1)^i d_i$, where
$d_i$ sends a basis vector to a basis vector or $0$ according to the following rule.

Let $z\in Z_n$ and $x_j\in X_{i_j}$. If the $i$th vertex of $z$ is not a cup, then
$d_i(z;x_0,\ldots , x_n):=0$. If the $i$th vertex of $z$ is a cup, then
$$d_i(z;x_0,\ldots
, x_n):= (d_i(z);x_0,\ldots , x_{i-1}\vee_{\epsilon (i)} x_{i}, \ldots , x_n)$$
where $d_i(z)$ is the labelled tree obtained from $z$ by deleting the $i$th node
(replace it by a leaf), and where $\vee_{\epsilon (i)} $ means the grafting with ${\epsilon
(i)}$ as the decoration of the new node. If it happens that the labelled tree $x_{i-1}\vee_{\epsilon (i)} x_{i}$ contains a pattern in $Z$, then we put $d_i(z;x_0,\ldots , x_n):=0$.

\begin{lemma} $d^2=0$.
\end{lemma}
\begin{proof} Let $\omega=(z;x_0,\ldots, x_n)$. It is sufficient to prove that $d_id_j =
d_{j-1}d_i$ for $i<j$ (presimplicial relation). If $i<j-1$, then the actions of $d_i$ and
$d_j$ on $\oo$  are sufficiently far apart so that they commute (the indexing $j-1$
comes from the renumbering). In the case $j=i+1$ we will prove that $d_id_{i+1} (\omega)=0=
d_{i}d_i (\omega)$. We are, locally in $z$, in one of the following two situations:
\[ \arbreBAdecore \qquad \qquad \arbreABdecore\]
In the first situation $d_id_i (\omega)=0$ because the $i$th vertex is not a cup. If $i+1$ is not a cup, then
$d_id_{i+1} (\omega)=0$ because $d_{i+1} (\omega)=0$. If $i+1$ is a cup, then
$d_id_{i+1} (\omega)=0$ because one of the entries of $d_id_{i+1} (\omega)$ is $a\vee_{\epsilon (i)}
(b\vee_{\epsilon (i+1)} c)$ which has a local pattern in  $Z$ and so is $0$ in $X_l$.

The proof
is similar in the second situation.\end{proof}

The chain complex ${\mathcal K}_*$ is called the \emph{Koszul complex} of $X$ (see
Section~\ref{S:op} for an explanation of this terminology).

\subsection{Extremal elements}
By definition a basis vector $\omega=(z;x_0,\ldots,\break x_n)$ of  ${\mathcal K}_n$ is an \emph{extremal element}
if there does not exist a basis vector $\omega '$ such that $d_i(\omega ') = \omega$ for
some $i$.

\begin{prop}\label{extremal}
For each extremal element $\omega$ with $k$ cups, the basis vectors $d_{i_1}\cdots
d_{i_r}\omega$ span a subcomplex ${\mathcal
K}_{\omega}$  of $\mathcal K$ which is isomorphic to the augmented chain complex of the
standard simplex $\Delta ^{k-1}$.
\end{prop}

\begin{proof}  Let $\omega=(z;x_0,\ldots, x_n)$ be an extremal element.  The graded subvector space of ${\mathcal K}_*$ spanned by the
elements $d_{i_1}\cdots
d_{i_r}\omega$ is stable by $d$ and so forms a subcomplex.

Let us now prove the isomorphism. We claim that $d_{i_1}\cdots  d_{i_r}\omega$ is
non-zero if and only if the indices
$i_j$ are such that the vertices ${i_j}$ are cups. Indeed the ``only if"
case is immediate. In the other direction: if $d_{i_1}\cdots  d_{i_r}\omega\ne 0$, then this would say that there is an $l$, such that the vertex $l$ is  a cup and
$d_l(\oo)=(d_l(z); \ldots, (a\vee_u b)\vee_v c, \ldots)$ with $(R; u,v)$   in $Z$, or $d_l(\oo)=(d_l(z); \ldots, a\vee_u( b\vee_v c, \ldots)$ with $(L; u,v)$   in $Z$. So we could construct ${\widehat \oo}= (\widehat z; \ldots, a, b, c, \ldots)$ so that
$d_l({\widehat \oo})= \oo$, and $\omega$ would not be extremal.

We construct a bijection between the cells of $\Delta ^{k-1}$ and the set of non-zero vectors $\{
d_{i_1}\cdots  d_{i_r}\omega\}$ by sending the $j$th vertex  (number $j-1$) of $\Delta^{k-1}$ to
$d_{i_1}\ldots \widehat{d_{i_j}}\ldots d_{i_k}\omega$ where $i_j$ is the $j$th cup of $x$. It is
immediate to verify that the boundary map in the chain complex of the standard simplex
corresponds to the boundary map $d$ by this bijection. Observe that, under this bijection, the
big cell of the simplex is mapped to $\oo$ and the generator of the augmentation space is mapped to  $d_{i_1}\ldots   d_{i_k}\omega$.
\end{proof}

\begin{prop}\label{sum}
The chain complex ${\mathcal K}_*$ is isomorphic to $\bigoplus _{\omega}{\mathcal K}_
{\omega}$ where the sum is taken over all the extremal elements $\omega$.
\end{prop}

\begin{proof} Let us show that any basis vector belongs to ${\mathcal K}_
{\omega}$ for some extremal element $\omega$. If $\omega$ is extremal, then the Proposition holds. If
not, then there exists an element ${\omega}_1$ such that $d_i({\omega}_1)=\omega$ for
some
$i$, and so on. The process stops after a finite number of steps because $(z;\vert , \ldots, \vert )$ is extremal.

Now it is sufficient to prove that, if a basis vector belongs to ${\mathcal K}_{\omega}$ and
to ${\mathcal K}_{\omega'}$, then $\omega = \omega '$.

Let $\omega=(z;x_0,\ldots, x_n)$ and $\omega'=(z';x_0',\ldots, x_n')$. If
$d_i(\oo)=d_j(\oo')\ne 0$, then $i$ is a cup of $z$, $j$ is a cup of $z'$ and $d_i(z)=d_j(z')$. If
$i< j$, then there exists $\bar\oo$ such that $d_j(\bar \oo) = \oo$, $d_i(\bar \oo)=\omega '$, and
therefore $\oo$ is not extremal. So we have $i=j$.

If $d_i(\oo)=d_i(\oo')\ne 0$, then it is of the form $(\bar z; \ldots, a\vee_{\epsilon (i)} b,
\ldots )$. But the element $(z; \ldots, a, b,\ldots )$, where $z$ is the labelled tree obtained from
$\bar z$ by replacing the $i$th leaf by a cup and putting $\epsilon(i)$ as a decoration, is
the only element such that $d_i(\oo)=(\bar z; \ldots, a\vee_{\epsilon (i)} b,
\ldots )$. Hence $\oo = \oo '$.

So we have proved that any basis vector belongs to one and only one subcomplex of the form ${\mathcal K}_
{\omega}$. \end{proof}

\begin{rem} In order to visualize these two proofs it is helpful to think of the element $\omega=(z;x_0,\ldots, x_n)$ as a single graph (with a ``horizon") obtained by gluing the $x_j$'s to the leaves of $z$. The horizon indicates where to cut to get the $x_j$'s back. The operator $d_j$, where $j$ is the number of a cup, consists in lowering the horizon under the relevant node.

Example with $n=3$ and two cups in $z$:
$$
\xymatrix@R=3pt@C=3pt{
&&*{}&&*{}&*{}  &      &*{}&*{}&&*{}&*{}     &*{}&&*{}&*{}&      &*{}& \\
&&&*{}\ar@{-}[ul]\ar@{-}[ur]&&  &   &&&*{}\ar@{-}[ul]\ar@{-}[ur]&&       &&*{}\ar@{-}[ul]\ar@{-}[ur]&*{}&&*{} && \\
x_i&&&&*{}\ar@{-}[ul]\ar@{-}[ur]\ar@{-}[d]&   &  &&*{}\ar@{-}[ul]\ar@{-}[ur]\ar@{-}[d]&&&    &*{}\ar@{-}[ul]\ar@{-}[ur]\ar@{-}[d]&&&&*{}\ar@{-}[ul]\ar@{-}[ur]\ar@{-}[d] && \\
\ar@{.}[rrrrrrrrrrrrrrrrr]&&&&*{}& & &&*{}&&& &*{}&&&*{}&*{}  &&\text{horizon} \\
&&&&& & &&&&& &&&&& && \\
&&&&&     &     &*{}\ar@{-}[uulll]\ar@{-}[uur]&&&&     &&&*{}\ar@{-}[uull]\ar@{-}[uurr]&&*{} && \\
z&&&&&  & &&&&& &&&&& && \\
&&&&& & &&&&*{}\ar@{-}[uulll]\ar@{-}[uurrrr]\ar@{-}[d]& &&&&& && \\
&&&&& & &&&&*{}& &&&&& && \\
&&&&& & &&&&& &&&&& && \\ }
$$
\end{rem}

\begin{cor}\label{acyclicity}
For any choice of $X$ the Koszul complex ${\mathcal K}_*$ is acyclic.
\end{cor}
\begin{proof} By Propositions~\ref{sum} and \ref{extremal} the homology of the Koszul complex is trivial since the standard simplex
is contractible. There is only one exception in dimension $1$ since the subcomplex
corresponding to the extremal element $\oo = (\vert ;\vert )$ is ${\mathbb K}$  in dimension $1$. So we have $H_n({\mathcal
K}_*) = 0$ for $n>1$ and $H_1({\mathcal
K}_*) = {\mathbb K}$. \end{proof}

\begin{prop}\label{Pseries}
The  Poincar\'e series of the Koszul complex ${\mathcal K}_*$ is equal to $f(Z,f(X,t))$.
\end{prop}

\begin{proof} Let us call $w= n + i_0 + \cdots + i_n$ the \emph{weight} of an element $\oo\in Z_n\times X_{i_0}\times
\cdots \times X_{i_n}$. From the definition of $d_i(\oo)$ we see that the weight of $d_i(\oo)$ is also $w$. Therefore
the Koszul complex is the direct sum of subcomplexes ${\mathcal K}_*^{(w)}$ made of all the elements of weight
$w$. For a fixed weight $w$ the complex ${\mathcal K}_*^{(w)}$ is finite, beginning with ${\mathbb K}[Z_w\times (X_0)^{w+1}]$,
ending with
${\mathbb K}[Z_0\times X_w]$. More generally one has ${\mathcal K}_n^{(w)}=\bigoplus {\mathbb K}[Z_n\times X_{i_0}\times \cdots
\times X_{i_n}]$ where the sum is over all the $(n+1)$-tuples $(i_0,\ldots , i_n)$ such that $n + i_0 +
\cdots +i_n = w$.

Let $a_n:= \#X_n$ and $b_n := \#Z_n$ so that $f(X,t)=  \sum_{n\geq 1} (-1)^{n+1} a_n t^{n+1}$ and
 $f(Z,t)= \sum_{n\geq 1} (-1)^{n+1} b_n t^{n+1}$. From the explicit description of
${\mathcal K}_n^{(w)}$ we check that the Euler-Poincar\'e characteristic of
${\mathcal K}_*^{(w)}$ is precisely the coefficient of $(-1)^wt^{w+1}$ in the expansion of
$$ \sum_{n\geq 1} (-1)^{n+1} b_n \big(  \sum_{m\geq 1} (-1)^{m+1} a_m t^{m+1}\big)^n\ .$$
Therefore the Poincar\'e series $\sum_{w\geq 0}(-1)^{w}\chi({\mathcal K}_*^{(w)})t^{w+1}$ is equal to\\
$f(Z,f(X,t))$.
\end{proof}



\subsection{End of the proof of Theorem~\ref{THM}}
By Proposition~\ref{Pseries} it suffices to show that the Poincar\'e series of ${\mathcal K}_*$ is $t$.
The Poincar\'e series of a complex is the same as the Poincar\'e series of its homology. Since the homology of
${\mathcal K}_*$ is 0, except in weight 0 where it is ${\mathbb K}$ by Corollary~\ref{acyclicity}, the Poincar\'e series is $t$. \hfill $\square$


\section{Operadic interpretation.}\label{S:op}
\subsection{Algebraic operad} The free associative algebra over the vector space $V$ is the tensor algebra $T(V)$ equipped with the concatenation product. If $V$ is generated by the elements $x_1, \ldots , x_k$, then $T(V)$ is nothing but the algebra of noncommutative polynomials over the $x_i$'s. Let us consider $T$ as a functor $T: \vect \to \vect$. The inclusion $V\to T(V)$ is given by a transformation of functors $\iota : \Id \to T$ and the classical composition of polynomials gives a transformation of functors $\cc : T\circ T \to T$. Observe that the triple $(T, \cc, \iota)$ is a monoid in the category of endofunctors of $\vect$.

By definition an \emph{algebraic operad} is a monoid $(\PP, \cc, \iota)$ where $\PP$ is an endofunctor of $\vect$, and $\cc: \PP\circ \PP\to \PP$, $\iota : \Id\to  \PP$ are transformations of functors. Any algebraic operad $\PP$ defines a notion of algebra as follows. A $\PP$-algebra is a vector space $A$ equipped with a map $\cc_A : \PP(A)\to A$ compatible with $\cc$ and $\iota$. For instance, $\PP(V)$ is a $\PP$-algebra. It has the property of being free over $V$.

In this paper we consider only operads of the form
$$\PP(V) := \bigoplus_n {\PP}_n \t V^{\t n}.$$
They are called \emph{regular operads}. For instance, in the associative example described above we have $As_n = {\mathbb K}$. For more details on operads and on the Koszul duality theory for operads the reader can consult \cite{G-K}, \cite{L1}, \cite{F}.

\subsection{Algebraic operads based on labelled trees} Let $I$ be a finite set of indices,  $X$ be a subset of $Y_2\times I^2$ and $Z$  its complement.
Over the field ${\mathbb K}$ we define a type of algebras, denoted $\PP$, as follows. There is one
binary operation $\circ_i$ for any $i\in I$ and the relations are
$$(x\circ_i y)\circ_j z = 0 \hbox{ if } (L;i,j)\in Z\hbox{ and }
x\circ_i ( y\circ_j z )= 0 \hbox{ if } (R;i,j)\in Z.
$$
It is immediate to check that the free algebra of type $\PP$ on one generator admits
$X_{n-1}$ as a basis of the homogeneous part of degree $n$, $n\geq 1$. The generator is
the unique element of $X_0$, that is, $\vert $ . So the operad $\PP$ determined by this type
of algebras is a regular operad such that $\PP_n={\mathbb K}[X_{n-1}]$.

Reversing the roles of $X$ and $Z$, that is, taking the elements of $X$ as relations, gives
rise to a new regular operad $\mathcal Q$ such that ${\mathcal Q}_n={\mathbb K}[Z_{n-1}]$.

\begin{lemma} \label{thedual}
The Koszul dual operad of $\PP$ is $\mathcal Q$, that is, $\PP^! = \mathcal Q .$
\end{lemma}

\begin{proof} Recall from \cite{G-K}, (see \cite{L1} or \cite{L2} for a short survey and \cite{F} for details) that the dual operad $\PP^!$ of the
regular operad $\PP$ is constructed as follows. The generating operations are the
same. The space of relations is made of the elements $\sum \alpha_{ij} (x\circ_i y)\circ_j z
+ \sum \beta_{ij} x\circ_i ( y\circ_j z )$ (for some scalars $\alpha_{ij}$ and $\beta_{ij}$) which are orthogonal to the relations of $\PP$ for
the inner product $\langle -,-\rangle$ defined on the linear generators by
\begin{eqnarray}
\langle (x\circ_i y)\circ_j z\ ,\ (x\circ_i y)\circ_j z\rangle = 1, \\
\langle x\circ_i ( y\circ_j z )\ ,\ x\circ_i ( y\circ_j z )\rangle= -1 \\
\langle -,-\rangle= 0\qquad  {\rm otherwise.}
\end{eqnarray}

One immediately checks that the vector space generated by $X$ is orthogonal to the vector
space generated by $Z$, and therefore the Koszul dual of $\PP$ is $\mathcal Q$. \end{proof}

\begin{thm}\label{duality}
The operads $\PP$ and $\mathcal Q$ are Koszul operads.
\end{thm}
\begin{proof} The Koszul duality of $\PP$ is equivalent to the acyclicity of the Koszul complex of
$\PP$, which is $(\PP^{!*}(\PP(V)), \delta)$. Since $\PP$ is regular, it is sufficient to check the acyclicity for $V={\mathbb K}$.  Since
$\PP^!={\mathcal Q}$ the chains of the Koszul complex of $\PP$ are the same as the chains
of the Koszul complex of $X$ constructed in the first section. A careful checking of the
construction of $\delta$ shows that $\delta = d$.

So we can apply Corollary~\ref{acyclicity} and the proof is completed.\end{proof}

\subsection{Poincar\'e series}
 The Poincar\'e series of a binary regular operad $\PP$ is defined as
$$f^{\PP}(t) : = \sum _{n\geq 1} (-1)^n
\dim \PP_n\ t^n\ .$$
Hence, for the operad $\PP$ defined by $X$, one has $f^{\PP}(t)= f(X,t)$ and the functional equation of Theorem~\ref{THM} is the functional equation
$$f^{\PP^!}(f^{\PP}(t))= t$$
 proved in \cite{G-K} for Koszul binary quadratic operads. A similar formula holds for any Koszul quadratic operad (not necessarily binary), cf.~\cite{F}, \cite{V2}.

In this paper we exploit only the Poincar\'e series property of Koszul operads. There are many other applications like constructing homotopy algebras (cf.~\cite{G-K}) and computing the homology of the associated partition complex (cf.~\cite{V3}).

\section{Generalization}
There is no reason to restrict oneself to binary trees, that is, to binary operads. One can
start with planar rooted trees. In this framework we choose a set of indices for each integer $k\geq 2$. The functional equation is now in two variables because any operation determines two integers: the number of  variables on which it acts and the number of generating operations used to form it (in the binary case the number of variables is equal to the number of generating operations plus one). See~\cite[Section~9]{V3} for the operadic interpretation.  In this section we give some examples of a particular case: the vertices of the trees have valency $k+1\geq 2+1$ for a fixed integer $k$.

\subsection{$k$-ary planar trees}
Let $Y_n^{(k)}$ be the set of planar rooted trees with $n$ nodes, each vertex being of valency $k+1$. The number of
leaves of such a tree is $(k-1)n+1$. The case $k=2$ is the one treated in the first part. Let $I$ be a set of indices and
let $Y_n^{(k)}\times I^n$ be the set of labelled trees. Choose a subset $X$ of $Y_2^{(k)}\times I^2$ and let $Z$ be its
complement. As before we define $X_n\subset Y_n^{(k)}\times I^n$ to be the subset made of labelled trees whose
local patterns belong to $X$.

In order to state the Theorem we need to introduce the following series. Let ${\underline a} = (a_0, \ldots,
a_n,\ldots )$ be a sequence of numbers (we will always have $a_0=1$). Define the (lacunary) series $f^{(k)}$ and
$g^{(k)}$ as follows:
$$
f^{(k)}({\underline a}, t) := \sum _{n\geq 0}(-1)^{n+1} a_n t^{(k-1)n+1} = -t + a_1t^k-a_2t^{2k-1} +\cdots
$$
$$
g^{(k)}({\underline a}, t) := - \sum _{n\geq 0}(-1)^{(k+1)n} a_n t^{(k-1)n+1} = -t +
(-1)^ka_1t^k- a_2t^{2k-1} + \cdots
$$
Observe that when $k$ is even $f^{(k)}= g^{(k)}$ and when $k$ is odd all the signs in $g^{(k)}$ are $-$ .
When $k=2$, one has $f^{(2)}= g^{(2)}= f$ as defined in Section~2. The series $f^{(k)}(X,t)$ and $g^{(k)}(X,t)$ are obtained
by taking $a_n= \#X_n$.

\begin{thm}\label{THMdeux}  Let $X$ be a subset of  $Y_2^{(k)}\times I^2$ and let $Z$ be its
complement, i.e., $X \sqcup Z= Y_2^{(k)}\times I^2$. Then the following functional equation holds:

$$g^{(k)}(Z,f^{(k)}(X,t)) = t .$$
\end{thm}
The proof is along the same lines as the proof of Theorem~\ref{THM} and we leave it to the diligent reader to work it out.

There is an operadic interpretation of this result, which involves the notion of $k$-ary algebras. The
relevant generalization of Koszul duality theory for quadratic algebras (not just binary) can be found in \cite{F}.

It would be interesting to study the analogous question with operads replaced by props as in \cite{V1}, \cite{V2}.

\subsection{Examples}
The integer sequences involved in this case are of the form
\begin{displaymath}
(1, \underbrace{0, \ldots, 0}_{k-2}, a_1, \underbrace{0, \ldots, 0}_{k-2}, a_2, \underbrace{0, \ldots, 0}_{k-2}, a_3,
0, \ldots, )
\end{displaymath}
with $a_1 = \# I, a_2= \# X$, so  $0\leq a_2\leq k(a_1)^2$. We denote such a lacunary sequence by
$(1; a_1; a_2; \cdots ; a_n; \cdots )_k$ .
\medskip

\noindent (a) $(1;  1; k;\frac{k(3k-1)}{2}; \frac{k(8k^2-6k+1)}{3}; \cdots )_k$ versus $(1; 1; 0; \cdots ; 0; \cdots )_k$ .

Let $c_n^{(k)}$ be the number of $k$-ary trees with $n$ nodes. Taking $I=\{1\}$, $X=Y_2^{(k)}$ and $Z=\emptyset$ we get $g^{(k)}(\emptyset,t)=-t+(-1)^kt^k$ and $f^{(k)}(Y_2^{(k)},t)=\sum_{n\geq 0}(-1)^{n+1}c_n^{(k)}t^{(k-1)n+1}$. So this last series, denote it $y$, satisfies the functional equation $-y+ (-1)^ky^k = t$.
\medskip


\noindent (b)  $(1;  1; 2; 5; \cdots ; c_n ; \cdots )_3$ versus  $(1;  1; 1; \cdots ; 1; \cdots )_3$ .

Take $I={1}$, $X$ has two elements and $Z$ has one element. The set $X_n$ has $c_{n+1}$ elements and $Z_n$ has one element. This case is related to the notion of totally associative ternary algebras and partially  associative ternary algebras studied in \cite {Gnedbaye}.
\medskip

\noindent (c) $(1;  1; 2; 5; \cdots ; c_n ; \cdots )_4$ versus itself.

Let $k=4$,  $I=\{1\}$. The set $X$ is made of two elements of $Y_2^{(4)}$ and $Z$ is made of the other two. It is clear that the sets $X_n$ and $Z_n$ are in bijection with the planar binary trees of degree $n$. As a consequence of Theorem~\ref{THMdeux} the series $h(t) = \sum_{n\geq 0}(-1)^{n+1}c_nt^{3n+1}$ satisfies $$h(h(t)) = t.$$
 Of course this result can also be proved by direct computation from the expression
$c(t):= \sum_{n\geq 0}c_nt^{n}=\frac{1-\sqrt{1-4t}}{2t}$.


\section{Inversion of the generic formal power series}

Let $f(t)= t + a_1t^2 + \cdots + a_nt^{n+1}+\cdots $ be the generic formal power series and let $g(t)= t + b_1t^2 + \cdots + b_nt^{n+1}+\cdots $ be its inverse with respect to composition. The coefficient $b_n$ is a polynomial in the coefficients $a_1, \ldots, a_n$. Explicitly we get
$$
\begin{array}{rcl}
b_1 &=& -a_1,\\
b_2 &=&2a_1{}^2 -a_2,\\
b_3 &=&-5a_1{}^3+5a_1a_2 -a_3,\\
b_4 &=&14a_1{}^4-21a_1{}^2a_2 +6a_1a_3+3{a_2}^2-a_4,
\end{array}
$$
and more generally
$$b_n =\sum _{i_1+2i_2+\cdots +ni_n}(-1)^{i_1+i_2+\cdots +i_n}c_{i_1\cdots i_n}a_1{}^{i_1} a_2{}^{i_2} \ldots a_n{}^{i_n}\ ,$$
where the coefficient $c_{i_1\cdots i_n}$ is the number of planar rooted trees having $i_k$ vertices with valency $(k+1)+1$ (cf.~\cite{Stanley}). Observe that it is also the number of cells of the $(n-1)$-dimensional associahedron $\mathcal {K}^{n-1}$ of the form $(\mathcal {K}^{0})^{i_1}\times \cdots \times \mathcal (\mathcal {K}^{n-1})^{i_n}$.

This result can be proved purely combinatorially, however it has a simple proof in the spirit of this paper, i.e., via Koszul operads. It gives a conceptual explanation for the appearance of the numbers of planar rooted trees of a certain form.

First, we oberve that it is sufficient to prove this result when the coefficients $a_n$ are integers, since we know a priori that $b_n$ is a polynomial in the $a_i$'s. Second, consider the algebras defined by $a_n$ $(n+1)$-ary operations (with no symmetry) and with relations: any nontrivial composite is $0$. It is clear that the (regular) operad $\mathcal P$ associated to these algebras is such that ${\mathcal P}_n = a_n {\mathbb K}$ since there are no operations but the generating ones. Since the operad ${\mathcal P}$ is nilpotent by construction, its dual ${\mathcal P}^!$ is the free operad over the same generators. Therefore a linear generator of ${\mathcal P}_n^!$ is determined by a planar rooted tree whose vertices are labelled by the generators of the ${\mathcal P}_k$'s :

$$\xymatrix@R=3pt@C=3pt{
*{} \ar@{-}[dr]&&*{} \ar@{-}[dl] &*{} \ar@{-}[ddd]&*{} \ar@{-}[dr] &*{} \ar@{-}[d]&\ar@{-}[dl]&&*{} \ar@{-}[dddlllll]  \\
&\mu_1\ar@{-}[ddrr] & & & &\mu_3 \ar@{-}[ddll]    & & &  \\
& & & &   & & &  &\\
& & &\mu_2 \ar@{-}[d]&   & & &  &\\
& & &*{} &   & & &  &
}$$
where $\mu_1 \in \PP_2, \mu_2 \in \PP_4, \mu_3 \in \PP_3$.

It follows from this description that
$$\dim {\mathcal P}_n^! =\sum _{i_1+2i_2+\cdots +ni_n}c_{i_1\cdots i_n}a_1{}^{i_1} \ldots a_n{}^{i_n}\ .$$
 Since the operad ${\mathcal P}^!$ is quadratic and free, it is a Koszul operad, that is, the Koszul complex is acyclic (cf. Fresse \cite{F}). Computing the Euler-Poincar\'e characteristic of this complex gives a formula entertwining the generating series of ${\mathcal P}$ and of ${\mathcal P}^!$. For a general Koszul quadratic operad this has been unraveled explicitly by B.~Vallette in \cite[Section~9]{V2}. In the particular case at hand it takes precisely the form $g(f(t))=t$.

\bigskip

Special thanks to Mamuka Jibladze for discussions on the topic of this section.


%Bibliography


\begin{thebibliography}{99}

\bibitem[A-L]{A-L}
M.~Aguiar and J.-L.~Loday, \emph{Quadri-algebras},  J. Pure Appl. Alg. {\bf 191}  (2004),  no. 3, 205--221.

\bibitem[B]{B}
R.~Bacher, \emph{On generating series of complementary planar trees}, S\'eminaire Lotharingien Combin. {\bf 53}, to appear;
\texttt{arXiv:math.CO/0409050.}

\bibitem[Bbki]{Bbki}
N.~Bourbaki, \emph{
\'El\'ements de math\'ematique.
Alg\`ebre. Chapitre 10. Alg\`ebre homologique}.
Masson, Paris, 1980. vii+216 pp.

\bibitem[F-N]{Flajolet} P.~Flajolet, M.~Noy, \emph{Analytic combinatorics of non-crossing configurations},  Discrete Math. {\bf 204} (1999),  no. 1-3, 203--229.

\bibitem[F]{F}
B.~Fresse, \emph{Koszul duality of operads and homology of
partition posets},   Homotopy theory: relations with algebraic geometry, group cohomology,  and algebraic $K$-theory,   115--215, Contemp. Math., 346, Amer. Math. Soc., Providence, RI,  2004.

\bibitem[G-K]{G-K}
V.~Ginzburg, M.M.~Kapranov, \emph{Koszul duality for operads},
Duke Math. J. {\bf 76} (1995), 203-272.

\bibitem[Gn]{Gnedbaye} A.V.~Gnedbaye, \emph{
 Op\'erades des alg\`ebres $(k+1)$-aires}.
  Operads: Proceedings of Renaissance Conferences (Hartford, CT/Luminy,  1995),   83--113,
 Contemp. Math., 202, Amer. Math. Soc., Providence, RI,  1997.

\bibitem[Le]{Leroux}
Ph.~Leroux, \emph{Ennea-algebras}, J. Algebra {\bf 281} (2004), no. 1, 287--302.

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

\bibitem[L2]{L2}
J.-L.~Loday, \emph{Dialgebras}, in:
 ``Dialgebras and related operads", Springer Lect. Notes in Math.
1763, (2001), 7--66.

\bibitem[L3]{L3}
J.-L.~Loday, \emph{Scindement d'associativit\'e et alg\`ebres de Hopf}, Proceedings of the Conference in honor of Jean Leray, Nantes 2002, S\'eminaire et Congr\`es (SMF) 9 (2004), 155--172.

\bibitem[L-R1]{L-R1}
J.-L.~Loday, M.~Ronco, \emph{Trialgebras and families of polytopes}, Homotopy theory: relations with algebraic geometry, group cohomology,  and algebraic $K$-theory,   369--398, Contemp. Math., 346, Amer. Math. Soc., Providence, RI,  2004.

\bibitem[L-R2]{L-R2}
J.-L.~Loday, M.~Ronco, \emph{On the structure of cofree Hopf algebras}, J. reine angew. Math. (2005), to appear.

\bibitem[Sl]{Sloane} N.J.A.~Sloane,
\emph{An online version of the encyclopedia of integer sequences},
\texttt{http://akpublic.att.com/$\sim$njas/sequances/ol.thm}

\bibitem[St]{Stanley} R.P. Stanley, Enumerative combinatorics. Vol. 1. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge,  1997.

\bibitem[V1]{V1}
B.~Vallette, \emph{
 Koszul duality for PROPs}, C.R.Acad.Sci Paris {\bf 338} (2004), 909--914.

\bibitem[V2]{V2}
B.~Vallette, \emph{A Koszul duality for props}, to appear in Trans.  Amer. Math. Soc.

\bibitem[V3]{V3}
B.~Vallette, \emph{Homology of generalized partition posets}, to appear in J. Pure Appl. Alg.

\end{thebibliography}

\end{document}