%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper,12pt,reqno]{amsart}
\usepackage{amsmath,amssymb}
\usepackage[latin1]{inputenc}
\usepackage[dvips]{epsfig}
\usepackage[english,frenchb]{babel}

\textwidth14cm
\voffset-1cm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\CC}{\mathbb{C}}

\newcommand{\UU}{\mathsf{U}}

\newcommand{\bord}{\mathsf{L}}
\newcommand{\Int}{\mathcal{I}}
\newcommand{\Y}{\mathsf{Y}}
\newcommand{\MPhi}{\boldsymbol{\Phi}}
\newcommand{\MTheta}{\boldsymbol{\Theta}}
\newcommand{\MPsi}{\boldsymbol{\Psi}}
\newcommand{\MDelta}{\boldsymbol{\Delta}}
\newcommand{\sym}{\mathfrak{S}}
\newcommand{\forme}{\boldsymbol{A}}
\newcommand{\PL}{\operatorname{PL}}
\newcommand{\sous}{\curvearrowleft}

\newcommand{\gch}{\epsfig{file=gauche.eps,height=2mm}}
\newcommand{\drt}{\epsfig{file=droite.eps,height=2mm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Th\'eor\`eme}[section] 
\newtheorem{proposition}[theorem]{Proposition} 
\newtheorem{conjecture}[theorem]{Conjecture} 
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem{lemma}[theorem]{Lemme} 
\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{Preuve.}}}
%  {\hfill\rule{2mm}{2mm}\end{trivlist}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{document}

\title[Sur le nombre d'intervalles dans les treillis de Tamari]%
{Sur le nombre d'intervalles\\ dans les treillis de Tamari}
\author{F. Chapoton}
\date{}

\setcounter{section}{-1}

\begin{abstract}
  On compte le nombre d'intervalles dans les treillis de Tamari. On
  utilise pour cela une description r\'ecursive de l'ensemble des
  intervalles. On introduit ensuite une notion d'intervalle nouveau
  dans les treillis de Tamari et on compte les intervalles nouveaux.
  On obtient aussi l'inverse de deux s\'eries particuli\`eres dans un
  groupe de s\'eries formelles en arbres.

\vskip10pt
\noindent
{\sc Abstract}.
  We enumerate the intervals in the Tamari lattices. For this, we
  introduce an inductive description of the intervals. Then a notion
  of ``new interval'' is defined and these are also enumerated. As a
  side result, the inverse of two special series is computed in a
  group of tree-indexed series.
\end{abstract}

\maketitle

\selectlanguage{frenchb}

\def\proofname{Preuve}

%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 55 \rms (2006), Article~B55f\hfill}
\def\thepage{}
%
%

\section{Introduction}

Les treillis de Tamari sont des ordres partiels remarquables, li\'es aux
polytopes de Stasheff (associa\`edres). On peut notamment les r\'ealiser
comme l'ordre induit par une forme lin\'eaire particuli\`ere sur
l'ensemble des sommets d'une certaine version du polytope de Stasheff.
Ils ont \'et\'e r\'ecemment g\'en\'eralis\'es par Reading \cite{reading}, qui a
introduit des treillis dits cambriens, associ\'es aux carquois sur les
diagrammes de Dynkin. Dans ce contexte, les treillis de Tamari
correspondent aux carquois de type $\mathbb{A}$ \'equi-orient\'es.

L'objectif principal de cet article est de compter les intervalles
dans les treillis de Tamari. On y parvient en obtenant une description
r\'ecursive compl\`ete de l'ensemble des intervalles. On montre ainsi
l'existence d'une formule close pour le nombre d'intervalles.

Un objectif secondaire est de compter ceux parmi les intervalles qui
ne proviennent pas de treillis de Tamari d'indice inf\'erieur par une
sorte d'``induction''. En termes g\'eom\'etriques, ce sont ceux qui ne
sont pas contenus dans une des facettes du polytope de Stasheff. On
les appelle les intervalles nouveaux, et on d\'emontre aussi une formule
close pour le nombre d'intervalles nouveaux.

Il est assez remarquable que ces nombres d'intervalles et
d'intervalles nouveaux apparaissent aussi ensemble dans l'article
\cite{schaeffer} dont le sujet est l'\'enum\-\'era\-tion de certaines classes
de cartes planes.

Par ailleurs, on calcule l'inverse de deux \'el\'ements particuliers dans
un groupe de s\'eries formelles en arbres li\'e \`a l'op\'erade dendriforme.
Ces s\'eries sont des raffinements de la s\'erie g\'en\'eratrice usuelle des
nombres d'intervalles. La d\'e\-cou\-verte de ces inverses a \'et\'e la cl\'e de
la description r\'ecursive des intervalles.

L'utilisation du syst\`eme de calcul formel \textsf{MuPAD} a \'et\'e
cruciale dans la recherche qui a abouti \`a cet article.

\section{Les treillis de Tamari}

Un \textbf{arbre binaire plan} est un graphe fini plan connexe et
simplement connexe, dont les sommets ont pour valence $1$ ou $3$, muni
d'un sommet de valence $1$ distingu\'e appel\'e la \textbf{racine}. Les
autres sommets de valence $1$ sont appel\'es les \textbf{feuilles}, les
sommets de valence $3$ sont appel\'es \textbf{sommets internes}. On
dessine les arbres binaires plans avec les feuilles en haut et la
racine en bas.

Soit $Y_n$ l'ensemble des arbres binaires plans \`a $n$ sommets
internes. Le cardinal de $Y_n$ est le nombre de Catalan
$c_n=\frac{1}{n+1}\binom{2n}{n}$. Pour $n=1$, il y a un seul arbre
binaire plan, qui sera not\'e $\Y$. Sauf mention explicite du contraire,
on consid\`ere toujours qu'un arbre binaire plan a au moins un sommet
interne. L'utilisation \'eventuelle de l'arbre trivial \`a une feuille,
not\'e $|$, sera toujours explicit\'ee.

Le treillis de Tamari est un ordre partiel sur l'ensemble $Y_n$,
introduit par Tamari \cite{tamari}. Cet ordre partiel est d\'efini comme
suit~: un arbre $T$ est plus grand qu'un arbre $S$ si on peut passer
de $S$ \`a $T$ par une suite d'op\'erations consistant \`a remplacer
localement la configuration $\drt$ par la configuration $\gch$. Le
treillis $Y_1$ a un seul \'el\'ement~: $\Y$. Le treillis $Y_2$ est juste
$\drt \leq \gch$. La figure \ref{tamari} repr\'esente les diagrammes de
Hasse des treillis $Y_3$ et $Y_4$.

%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 SUR LE NOMBRE D'INTERVALLES
DANS LES TREILLIS DE TAMARI}
%
%

\begin{figure}
  \begin{center}
    \scalebox{0.4}{\includegraphics{tamari3rond.eps}}
    \caption{Les treillis de Tamari $Y_3$ et $Y_4$}
    \label{tamari}
  \end{center}
\end{figure}

\subsection{Structures alg\'ebriques}

On d\'efinit des op\'erations $/$ et $\backslash$ sur les arbres binaires
plans (y compris l'arbre trivial $|$)~: $S/T$ est obtenu en
identifiant la racine de $S$ avec la feuille la plus \`a gauche de $T$ ;
$S\backslash T$ est obtenu en identifiant la racine de $T$ avec la
feuille la plus \`a droite de $S$.  Ces op\'erations sont clairement
associatives. Par exemple $\Y/\Y=\gch$ et $\Y\backslash \Y=\drt$.

On consid\`ere l'espace vectoriel gradu\'e $\mathcal{Y}$ ayant pour base
$Y_n$ en degr\'e $n\geq 1$ et l'arbre trivial $|$ en degr\'e $0$. On peut
\'etendre les op\'erations $/$ et $\backslash$ par lin\'earit\'e.

Sur $\mathcal{Y}$, on dispose donc de deux produits associatifs. Un
troisi\`eme produit associatif existe, qui sera not\'e $*$, et qui peut
\^etre d\'efini comme suit~:
\begin{equation}
  S * T =\sum_{S\backslash T \leq U \leq S/T} U,
\end{equation}
o\`u la relation d'ordre est celle du treillis de Tamari. L'arbre
trivial $|$ est une unit\'e pour les trois produits.

On va aussi utiliser l'op\'eration $S \vee T$ d\'efinie par la greffe de
$S$ \`a gauche et de $T$ \`a droite sur les deux feuilles de $\Y$.

Pour plus de d\'etails sur ces structures alg\'ebriques, on renvoie le
lecteur \`a \cite{arithm}.

\section{\'Enum\'eration des intervalles}

Soit $\Int_n$ l'ensemble des intervalles dans le treillis de Tamari
$Y_n$.

En comptant les intervalles dans les premiers treillis de Tamari, on
obtient que les premiers termes de la suite $|\Int_n|$ sont, pour
$n\geq 1$,
\begin{equation*}
  1,3,13,68,399,2530,\text{etc}.
\end{equation*}

Une consultation de l'encyclop\'edie des suites \cite{oeis} m\`ene
imm\'ediatement \`a conjecturer le r\'esultat suivant.
\begin{theorem}
  \label{theo_int}
  Le nombre d'intervalles dans le treillis de Tamari $Y_n$ est 
  \begin{equation}
    |\Int_n|=\frac{2(4n+1)!}{(n+1)!(3n+2)!}.
  \end{equation}
\end{theorem}

\begin{proof}
Il s'agit de calculer la s\'erie g\'en\'eratrice
\begin{equation*}
  \phi=\sum_{n\geq 1} |\Int_n| y^n=y+3 y^2 + 13 y^3 + \dots
\end{equation*}

Pour cela, on introduit un param\`etre suppl\'ementaire. Si $T$ est un
arbre binaire plan dans $Y_n$, on note $\bord(T)$ le nombre de
segments le long du bord gauche de $T$. Par exemple $\bord(\Y)=2$,
$\bord(\gch)=3$ et $\bord(\drt)=2$.

On consid\`ere alors la s\'erie g\'en\'eratrice raffin\'ee
\begin{equation*}
  \Phi=\sum_{n\geq 1}\sum_{[S,T]\in \Int_n} x^{\bord(T)} y^n=x^2 y+(2
  x^3+x^2) y^2 +(5 x^4 +5 x^3 + 3 x^2) y^3 + \dots,
\end{equation*}
o\`u la variable $x$ tient compte compte du param\`etre $\bord$ pour le
maximum $T$ de l'intervalle $[S,T]$. Bien sûr, on retrouve $\phi$ en
posant $x=1$ dans $\Phi$.

On montre de fa\c con combinatoire dans les sections \ref{decomposition},
\ref{description} et \ref{coeur} que $\Phi$ v\'erifie
\begin{equation*}
  \Phi=x^2 y\left(1+\Phi/x\right)
\left(1+\left( \frac{\Phi-\phi}{x-1}\right)\right).
\end{equation*}

En isolant $\phi$ dans un membre, on obtient
\begin{equation*}
  \phi=\Phi+x-1+\frac{1}{y}\left( \frac{1}{x}-\frac{\Phi+1}{\Phi+x}\right),
\end{equation*}
et comme $\phi$ ne d\'epend pas de $x$, le membre de droite est constant
en la variable $x$. Il en r\'esulte que $\Phi$ est d\'etermin\'ee par
l'\'equation diff\'erentielle ordinaire
\begin{equation}
  \label{diffPhi}
  \partial_x \Phi=\frac{(x+\Phi)^2 (1/x^2-y) -1 -\Phi}{1-x+y(x+\Phi)^2}
\end{equation}
et la condition initiale $\Phi=0$ en $x=0$, car tout arbre binaire
plan a au moins deux segments sur son bord gauche.

On en d\'eduit que $\Phi$ v\'erifie l'\'equation alg\'ebrique suivante~:
\begin{multline}
\label{maxi8}
0={x}^{4}{y}^{4}\Phi^{8}+ ( 4\,{y}^{3}{x}^{3}+8\,{x}^{5}{y}^
{4}-{y}^{3}{x}^{4} ) \Phi^{7}+\\ ( -3\,{y}^{2}{x}^{3}+
32\,{y}^{3}{x}^{4}+6\,{y}^{2}{x}^{2}+28\,{x}^{6}{y}^{4}-3\,{x}^{5}{y}^
{3} ) \Phi^{6}+\\ ( 56\,{x}^{7}{y}^{4}+3\,{x}^{6}{y}^{
3}+ ( 108\,{y}^{3}-3\,{y}^{2} ) {x}^{5}-39\,{x}^{4}{y}^{2}+
40\,{y}^{2}{x}^{3}-3\,{x}^{2}y+4\,x y ) \Phi^{5}+\\ ( 1
+70\,{x}^{8}{y}^{4}+25\,{x}^{7}{y}^{3}+ ( 200\,{y}^{3}-9\,{y}^{2}
 ) {x}^{6}-146\,{x}^{5}{y}^{2}+\\ ( 116\,{y}^{2}+21\,y
 ) {x}^{4}-33\,{x}^{3}y+16\,{x}^{2}y-x ) \Phi^{4}+\\
 ( 56\,{x}^{9}{y}^{4}+45\,{x}^{8}{y}^{3}+ ( -6\,{y}^{2}+220
\,{y}^{3} ) {x}^{7}+ ( -254\,{y}^{2}-3\,y ) {x}^{6}+\\
 ( 184\,{y}^{2}+66\,y ) {x}^{5}-77\,{x}^{4}y+ ( -3+20
\,y ) {x}^{3}+3\,{x}^{2} ) \Phi^{3}+\\ ( 28\,{x}
^{10}{y}^{4}+39\,{x}^{9}{y}^{3}+ ( 6\,{y}^{2}+144\,{y}^{3}
 ) {x}^{8}+ ( -231\,{y}^{2}-5\,y ) {x}^{7}+\\ ( 
166\,{y}^{2}+68\,y ) {x}^{6}+ ( -3-67\,y ) {x}^{5}+
 ( 3+8\,y ) {x}^{4} ) \Phi^{2}+\\ ( 8\,{x}^
{11}{y}^{4}+17\,{x}^{10}{y}^{3}+ ( 52\,{y}^{3}+9\,{y}^{2}
 ) {x}^{9}+ ( -y-107\,{y}^{2} ) {x}^{8}+ ( -1+80
\,{y}^{2}+22\,y ) {x}^{7}+\\ ( 1-20\,y ) {x}^{6}
 ) \Phi+{x}^{12}{y}^{4}+3\,{x}^{11}{y}^{3}+ ( 3\,{y}^{
2}+8\,{y}^{3} ) {x}^{10}+ ( y-20\,{y}^{2} ) {x}^{9}+
 ( 16\,{y}^{2}-y ) {x}^{8}.
\end{multline}
En effet, la solution de cette \'equation alg\'ebrique v\'erifie l'\'equation
diff\'erentielle (\ref{diffPhi}) et la condition initiale.

On en d\'eduit par sp\'ecialisation en $x=1$ (et simplification par
factorisation) que $\phi$ v\'erifie l'\'equation alg\'ebrique suivante~:
\begin{multline}
  \label{eqphi}
  {y}^{3}{\phi}^{4}+ \left(4\,{y}+3
    \right)\,{y}^{2} {\phi}^{3}+ \left( 6\,{y}^{2}+17\,{y}+3 \right) y
    {\phi}^{2}\\+ \left( 4\,{y}^{3}+25\,{y} ^{2}-14\,y+1 \right)
    \phi+y\left({y}^{2}+11\,{y}-1\right)=0.
\end{multline}

Pour en d\'eduire les coefficients de $\phi$, on peut utiliser comme
suit les r\'esultats de \cite{schaeffer} dans le cas $a=b=1$. En posant
$\phi=\tau(1-\tau-\tau^2)$ dans (\ref{eqphi}), on obtient que $\tau$
v\'erifie $\tau=y(1+\tau)^4$. On calcule alors les coefficients de
$\phi$ par inversion de Lagrange. Ceci termine la d\'emonstration du
Th\'eor\`eme.
\end{proof}

\section{D\'ecomposition des intervalles}

\label{decomposition}

L'objet de cette section est l'obtention d'une description par
r\'ecurrence sur $n$ des intervalles.

\begin{lemma}
  Il existe une unique d\'ecomposition maximale de chaque arbre binaire
  plan $T$ sous la forme $T_1 / T_2 / \dots / T_k$.
\end{lemma}

\begin{proof}
  Clair, par d\'ecoupe de chaque segment le long du bord gauche.
\end{proof}

Un arbre binaire plan $T$ est dit \textbf{ind\'ecomposable} si sa
d\'ecomposition maximale a un seul terme. Les arbres binaires plans
ind\'ecomposables sont ceux dont le bord gauche est form\'e de deux
segments.

\'Etant donn\'e un arbre binaire plan $T$, on d\'efinit une composition
$c(T)=(c_1,\dots,c_k)$ o\`u $c_i$ est le nombre de sommets internes de
$T_i$ dans la d\'ecomposition maximale de $T$. Par exemple, dans la
figure \ref{exemple}, $c(S)=(2,7)$ et $c(T)=(1,1,2,\break 4,1)$.

Soient $S$ et $T$ deux arbres binaires plans, et soient $(S_i)_i$ et
$(T_i)_i$ leurs d\'ecompositions maximales respectives.

\begin{lemma}
  \label{fusion}
  Si $S\leq T$, alors ou bien la composition $c(S)$ est strictement
  plus grossi\`ere que $c(T)$ ou bien $c(S)=c(T)$ et on a $S_i \leq
  T_i$ pour tout $i$.
\end{lemma}

\begin{proof}
  Il suffit de le montrer lorsque $S$ et $T$ sont reli\'es par une des
  relations \'el\'ementaires locales ($\drt \leq \gch$) qui engendrent
  l'ordre dans les treillis de Tamari.  Si cette relation est utilis\'ee
  dans un des termes de la d\'ecomposition de $T$, la composition $c$ ne
  change pas et l'ordre est respect\'e dans chaque terme, avec
  changement seulement dans un terme.  Si la relation est utilis\'ee \`a
  la liaison entre deux termes, le long du bord gauche, alors il y a
  fusion en un seul terme dans $S$ des deux termes cons\'ecutifs de $T$
  impliqu\'es, donc la composition devient strictement plus grossi\`ere et
  ne peut que le rester.
\end{proof}

\begin{lemma}
  \label{factoriser_ordre}
  Soient $S=S_1/\dots/S_k$ et $T=T_1/\dots/T_k$ deux arbres binaires
  plans. On ne suppose pas que ces d\'ecompositions sont maximales. On
  suppose que $|S_i|=|T_i|$ pour tout $i$. Alors $S \leq T$ si et
  seulement si $S_i \leq T_i$ pour tout $i$.
\end{lemma}

\begin{proof}
  Clairement $S_i \leq T_i$ pour tout $i$ entra\^{\i}ne $S \leq T$.
  Montrons la r\'e\-ci\-proque. Choisissons une cha\^{\i}ne de relations d'ordre
  \'el\'ementaires de $S$ \`a $T$. Si une \'etape de cette cha\^{\i}ne se trouve le
  long du bord gauche \`a la liaison entre deux termes de la
  d\'ecomposition de $T$ fix\'ee, la composition associ\'ee deviendrait
  strictement plus grossi\`ere par le lemme pr\'ec\'edent, donc la
  composition associ\'ee \`a $S$ serait strictement plus grossi\`ere que
  celle de $T$, ce qui contredit l'hypoth\`ese. Donc toutes les \'etapes
  de la cha\^{\i}ne se produisent \`a l'int\'erieur d'un des termes de la
  d\'ecomposition de $T$ fix\'ee et la relation d'ordre se factorise.
\end{proof}

\'Etant donn\'e deux intervalles $J$ et $K$, on peut d\'efinir un nouvel
intervalle $J/K$ avec $\min(J/K)=\min(J)/\min(K)$ et
$\max(J/K)=\max(J)/\max(K)$.

\begin{figure}
  \begin{center}
    \scalebox{0.4}{\includegraphics{decoupage.eps}}
    \caption{Un intervalle dans $Y_9$}
    \label{exemple}
  \end{center}
\end{figure}

\begin{proposition}
  \label{decompo}
  Il existe une unique d\'ecomposition maximale de chaque intervalle $I$
  sous la forme $I_1 / I_2 / \dots / I_k$.
\end{proposition}

\begin{proof}
  Soit $S_1/\dots/S_k$ la d\'ecomposition maximale du minimum $S$ de
  $I$. Par le Lemme \ref{fusion}, la d\'ecomposition maximale du maximum
  $T$ de $I$ est plus fine que celle de $S$. Donc on peut en
  particulier d\'ecomposer le maximum $T$ comme le minimum $S$. Alors,
  chaque terme de la d\'ecomposition de $S$ est plus petit que chaque
  terme de $T$, par le Lemme \ref{factoriser_ordre}.

  Toute autre d\'ecomposition est un grossissement de celle-ci. En
  effet, elle est n\'ecessairement un grossissement pour le minimum $S$.
\end{proof}

Dans l'exemple de la figure \ref{exemple}, la d\'ecomposition maximale a
deux termes, ayant respectivement $2$ et $7$ sommets internes, de haut
en bas.

On appelle \textbf{intervalle ind\'ecomposable} un intervalle dont la
d\'ecomposition maximale a un seul terme. On remarque que les
intervalles ind\'ecomposables sont exactement ceux dont le minimum est
ind\'ecomposable.

\section{Description des intervalles ind\'ecomposables}

\label{description}

\'Etant donn\'e un intervalle $J$ et un segment $s$ du bord gauche de son
maximum $\max(J)$, on peut d\'efinir un nouvel intervalle $\Y *_s J$ o\`u
$\max(\Y *_s J)$ est obtenu en rajoutant \`a gauche une ar\^ete sur
l'ar\^ete $s$ de $\max(J)$ et $\min(\Y *_s J)$ est obtenu en rajoutant \`a
gauche une ar\^ete sur l'ar\^ete racine de $\min(J)$. On peut aussi \'ecrire
$\min(\Y *_s J)=\Y \backslash \min(J)$. Pour justifier que ceci est
bien un intervalle, on a les relations
\begin{equation*}
  \Y \backslash \min(J) \leq \Y \backslash \max(J) \leq \max(\Y *_s J),
\end{equation*}
o\`u la seconde relation est obtenue par une suite de relations
\'el\'ementaires faisant remonter l'ar\^ete la plus \`a gauche le long du bord
gauche de $\max(J)$, jusqu'\`a atteindre le segment $s$.

En particulier, l'\'el\'ement $\min(\Y *_s
J)$ est ind\'ecomposable, donc l'intervalle $\Y *_s J$ est
ind\'ecomposable. Voir la figure \ref{int_indec} pour une illustration
de cette construction.

\begin{figure}
  \begin{center}
    \scalebox{0.4}{\includegraphics{gauchetoute.eps}}
    \caption{Un intervalle ind\'ecomposable}
    \label{int_indec}
  \end{center}
\end{figure}

\begin{proposition}
  \label{indecompo}
  Tout intervalle ind\'ecomposable $I$ est ou bien $[\Y,\Y]$ ou bien de
  la forme $\Y *_s J$ pour un certain intervalle $J$ et un segment $s$
  du bord gauche de $\max(J)$, uniquement d\'etermin\'es.
\end{proposition}

\begin{proof}
  Excluons le cas de l'intervalle $[\Y,\Y]$.

  N\'ecessairement le minimum de $I$ est de la forme $Y \backslash S$
  pour un certain arbre $S$. On peut aussi d\'efinir un arbre $T$ en
  enlevant l'ar\^ete la plus \`a gauche dans le maximum de $I$. 

  Montrons que $S \leq T$. Prenons une cha\^{\i}ne de relations
  \'el\'ementaires de $\min(I)$ \`a $\max(I)$. Dans cette cha\^{\i}ne, certaines
  \'etapes font intervenir l'ar\^ete la plus \`a gauche. Si on enl\`eve ces
  \'etapes, on obtient une cha\^{\i}ne de relations \'el\'ementaires de $S$ \`a
  $T$.

  Donc on peut enlever l'ar\^ete la plus \`a gauche du minimum et du
  maximum de $I$ pour obtenir un nouvel intervalle $J=[S,T]$.

  Pour reconstituer de mani\`ere unique $I$, il suffit de se donner $J$
  et le segment $s$ sur le bord gauche de $\max(J)$ sur lequel se
  trouvait l'ar\^ete enlev\'ee.
\end{proof}




\section{\'Equation fonctionnelle}

\label{coeur}

On d\'eduit de la section pr\'ec\'edente une \'equation fonctionnelle pour $\Phi$.

Soit $\theta$ la s\'erie g\'en\'eratrice des nombres d'intervalles
ind\'ecomposables~:
\begin{equation*}
  \theta=\sum_{n\geq 1}
\underset{\text{ ind\'ec.}}{\sum_{{[S,T]\in \Int_n}}}  y^n=y+2 y^2+8 y^3+41y^4+\dots,
\end{equation*}
et soit $\Theta$ la s\'erie g\'en\'eratrice raffin\'ee correspondante~:
\begin{equation*}
  \Theta=\sum_{n\geq 1}
\underset{\text{ ind\'ec.}}{\sum_{{[S,T]\in \Int_n}}} x^{\bord(T)} y^n=x^2 y+(x^3+x^2)y^2+(2 x^4+3 x^3+3 x^2) y^3 + \dots
\end{equation*}

Alors on a les relations suivantes. Par la d\'ecomposition unique d'un
intervalle en intervalles ind\'ecomposables (Prop. \ref{decompo}), on a
\begin{equation*}
  \Phi=\Theta+\Phi \, \Theta/x.
\end{equation*}

Par la description des intervalles ind\'ecomposables (Prop.
\ref{indecompo}) et la d\'efinition de la fonction $\bord$, on a
\begin{equation*}
  \Theta=x^2 y+ y \,\tilde{\Phi},
\end{equation*}
o\`u $\tilde{\Phi}$ est obtenu est rempla\c cant chaque $x^k$ dans $\Phi$ par
$x^2+\dots+x^{k+1}$. Ceci peut s'\'ecrire
\begin{equation*}
  \Theta=x^2 y+x^2 y \left( \frac{\Phi-\phi}{x-1}\right).
\end{equation*}

On a donc la relation fonctionnelle suivante~:
\begin{equation}
  \label{relaphi}
  \Phi=x^2 y\left(1+\Phi/x\right)
  \left(1+\left( \frac{\Phi-\phi}{x-1}\right)\right).
\end{equation}

\section{S\'eries formelles en arbres binaires plans}

Cette section fait intervenir explicitement des notions alg\'ebriques
plus sophistiqu\'ees~: l'op\'erade dendriforme (due \`a Loday
\cite{lecturenotes}) et le groupe de s\'eries formelles associ\'e. Les
r\'esultats de cette section ne sont pas utilis\'es dans le reste de
l'article. On renvoie le lecteur aux articles \cite{groupes,arithm}
pour la notion d'op\'erade et pour le groupe associ\'e.

Soit $\MPhi$ la s\'erie g\'en\'eratrice des nombres d'intervalles selon leur
maximum~:
\begin{equation*}
  \MPhi=\sum_{n \geq 1} \sum_{ [S,T] \in \Int_n} T=\Y+2\,\gch+\drt+\dots
\end{equation*}
et $\MTheta$ la s\'erie g\'en\'eratrice similaire des intervalles
ind\'ecomposables~:
\begin{equation*}
   \MTheta=\sum_{n \geq 1} 
\underset{[S,T] \text{ ind\'ec.}}{\sum_{{[S, T]\in \Int_n}}} T
=\Y+\gch+\drt+\dots  
\end{equation*}

Par la d\'ecomposition unique en intervalles ind\'ecomposables (Prop.
\ref{decompo}), on a
\begin{equation*}
  \MPhi=\MTheta+\MPhi/\MTheta.
\end{equation*}

Par la description des intervalles ind\'ecomposables (Prop.
\ref{indecompo}), on a
\begin{equation*}
  \qquad \MTheta=\Y+\Y*\MPhi.
\end{equation*}
En effet, l'action du produit \`a gauche par $\Y$ est pr\'ecis\'ement de
faire la somme sur les arbres obtenus en rajoutant un ar\^ete \`a gauche
sur chaque segment du bord gauche.

On a obtenu la proposition ci-dessous.

\begin{proposition}
  On a l'\'equation fonctionnelle suivante~:
  \begin{equation}
    \label{relaF}
    \MPhi=\Y+\MPhi/\Y+\Y*\MPhi+\MPhi/(\Y*\MPhi).
  \end{equation}
  Cette relation caract\'erise la s\'erie $\MPhi$.
\end{proposition}

Ceci a pour cons\'equence les propositions ci-dessous.

\begin{proposition}
  L'inverse de la s\'erie $\Y-\gch$ dans le groupe $\mathsf{G}_{Dend}$ des s\'eries
  formelles en arbres binaires plans est la s\'erie $\Y+\gch \circ_1
  \MPhi$.
\end{proposition}

\begin{proof}
  Par la d\'efinition de la loi de groupe de $\mathsf{G}_{Dend}$, on doit montrer
  \begin{equation*}
    (\Y) \circ_1(\Y+\gch\circ_1 \MPhi)-\big{(}\gch \circ_2(\Y+\gch \circ_1 \MPhi)\big{)} \circ_1(\Y+\gch \circ_1 \MPhi)=\Y.
  \end{equation*}
  Par lin\'earit\'e et comme $\Y$ est une unit\'e pour les compositions
  $\circ$, ceci devient
  \begin{equation*}
    \Y+\gch\circ_1 \MPhi-\gch-\gch\circ_1 (\gch \circ_1 \MPhi)-\gch\circ_2(\gch
    \circ_1 \MPhi)-\big{(}\gch \circ_2(\gch \circ_1 \MPhi)\big{)} \circ_1(\gch \circ_1 \MPhi)=\Y.
  \end{equation*}
  Soit encore
  \begin{equation}
    \label{etape}
    \gch\circ_1 \MPhi=\gch+\gch\circ_1 (\gch \circ_1 \MPhi)+\gch\circ_2(\gch
    \circ_1 \MPhi)+\big{(}\gch \circ_2(\gch \circ_1 \MPhi)\big{)} \circ_1(\gch \circ_1 \MPhi).
  \end{equation}

  Comme on a
  \begin{equation*}
    x \circ_1 (\gch \circ_1 y)=y /x,
  \end{equation*}
  \begin{equation*}
    x \circ_1 (y \circ_1 z)=(x \circ_1 y) \circ_1 z
  \end{equation*}
  et
  \begin{equation*}
    \gch\circ_2 (\gch \circ_1 x)=\gch\circ_1 (\Y * x),
  \end{equation*}
  on peut r\'e\'ecrire l'\'equation (\ref{etape}) comme suit~:
  \begin{equation*}
    \gch\circ_1 \MPhi=\gch\circ_1 (\Y+\MPhi/\Y+\Y*\MPhi+\MPhi/(\Y*\MPhi)).
  \end{equation*}
  Cette \'egalit\'e r\'esulte imm\'ediatement de la relation fonctionnelle
  (\ref{relaF}).
\end{proof}

Consid\'erons maintenant la s\'erie $\MDelta$ d\'efinie par
\begin{equation}
  \MDelta=\sum_{T_1,T_2} (-1)^{t_1+t_2} (t_1+1)\, T_1 \vee  T_2
  =\Y-(2\gch+\drt)+\dots,
\end{equation}
o\`u les sommes portent cette fois sur les arbres binaires plans, y
compris l'arbre trivial $|$, et o\`u on note $t_i$ le nombre de sommets
internes de $T_i$.

\begin{proposition}
  L'inverse de la s\'erie $\MPhi$ dans le groupe $\mathsf{G}_{Dend}$ des s\'eries
  formelles en arbres binaires plans est la s\'erie $\MDelta$.
\end{proposition}

\begin{proof}
  Il s'agit de montrer que $\MPhi \MDelta=\Y$ dans le groupe
  $\mathsf{G}_{Dend}$.  Par la relation (\ref{relaF}), il suffit de
  calculer le produit
  \begin{equation*}
    \left(\Y+\MPhi/\Y+\Y*\MPhi+\MPhi/(\Y*\MPhi)\right)  \MDelta.
  \end{equation*}
  Comme le groupe $\mathsf{G}_{Dend}$ est contenu dans une alg\`ebre
  associative et que la loi de groupe est lin\'eaire \`a gauche, ceci vaut
  \begin{equation*}
    \Y\MDelta+(\MPhi/\Y)\MDelta+(\Y*\MPhi)\MDelta+(\MPhi/(\Y*\MPhi))\MDelta.
  \end{equation*}
  Posons $H=\MPhi\MDelta$. En utilisant la d\'efinition de la loi de
  groupe, on obtient la relation
  \begin{equation}
    \label{relaY}
    H=\MDelta+\sum_{k} (H_k /\Y)\circ_{k+1}\MDelta
    +(\Y*H)\circ_1 \MDelta+\sum_{k} (H_k/(\Y*H))\circ_{k+1}\MDelta,
  \end{equation}
  o\`u on utilise une d\'ecomposition $H=\sum_{k} H_k$ en composantes homog\`enes.

  Cette relation caract\'erise uniquement la s\'erie $H$ par r\'ecurrence.
  Il suffit donc de montrer que $\Y$ v\'erifie (\ref{relaY}) pour
  pouvoir conclure que $H=\Y$. Il faut donc calculer 
  \begin{equation*}
    \MDelta+(\gch)\circ_2 \MDelta+(\gch+\drt)\circ_1 \MDelta
    +(\Y/(\gch+\drt))\circ_2\MDelta.
  \end{equation*}
  
  Ceci vaut
  \begin{multline*}
  \sum_{T_1,T_2} (-1)^{t_1+t_2} (t_1+1)\, T_1 \vee  T_2+
  \sum_{T_1,T_2} (-1)^{t_1+t_2} (t_1+1)\, (\Y * T_1) \vee  T_2\\
  +\sum_{T_1,T_2} (-1)^{t_1+t_2} (t_1+1)\, (T_1 \vee  T_2) / \Y+
  \sum_{T_1,T_2} (-1)^{t_1+t_2} (t_1+1)\, T_1 \vee  (T_2* \Y)\\
  +\sum_{T_1,T_2} (-1)^{t_1+t_2} (t_1+1)\, ((\Y * T_1) \vee  T_2)/\Y+
  \sum_{T_1,T_2} (-1)^{t_1+t_2} (t_1+1)\, (\Y *T_1) \vee  (T_2* \Y).
  \end{multline*}

  En utilisant le fait que
  \begin{equation*}
    \sum_{T \not=|} T = \sum_{S} \Y * S = \sum_{S} S * \Y,
  \end{equation*}
  on change les indices de sommation et on obtient
  \begin{multline*}
  \sum_{T_1,T_2} (-1)^{t_1+t_2} (t_1+1)\, T_1 \vee  T_2
  -\sum_{T_1\not=|,T_2} (-1)^{t_1+t_2} (t_1)\, T_1 \vee  T_2\\
  +\sum_{T_1,T_2} (-1)^{t_1+t_2} (t_1+1)\, (T_1 \vee  T_2) / \Y
  -\sum_{T_1,T_2\not=|} (-1)^{t_1+t_2} (t_1+1)\, T_1 \vee  T_2\\
  -\sum_{T_1\not=|,T_2} (-1)^{t_1+t_2} (t_1)\, (T_1 \vee  T_2)/\Y+
  \sum_{T_1\not=|,T_2\not=|} (-1)^{t_1+t_2} (t_1)\, T_1 \vee T_2.
  \end{multline*}
  On simplifie les termes par paires (1 \& 4), (2 \& 6) et (3 \& 5)~:
   \begin{equation*}
  \sum_{T_1} (-1)^{t_1} (t_1+1)\, T_1 /\Y
  -\sum_{T_1\not=|} (-1)^{t_1} (t_1)\, T_1 /\Y
  +\sum_{T_1,T_2} (-1)^{t_1+t_2} (T_1 \vee  T_2) / \Y.
  \end{equation*}
  On simplifie \`a nouveau~:
   \begin{equation*}
     \Y+\sum_{T_1\not=|} (-1)^{t_1} (t_1)\, T_1 /\Y
  +\sum_{T_1\not=|} (-1)^{t_1+1} T_1 / \Y.
  \end{equation*}
  Ceci donne $\Y$, ce qui termine la d\'emonstration.
\end{proof}

\section{D\'ecoupage en intervalles nouveaux}

Un \textbf{arbre plan} est un graphe fini plan connexe et simplement
connexe, dont les sommets ont une valence diff\'erente de $2$, muni d'un
sommet de valence $1$ distingu\'e appel\'e la \textbf{racine}. Les autres
sommets de valence $1$ sont appel\'es les \textbf{feuilles}, les sommets
de valence diff\'erente de $1$ sont appel\'es \textbf{sommets internes}.
On dessine les arbres plans avec les feuilles en haut et la racine en
bas. Soit $P_n$ l'ensemble des arbres plans \`a $n+1$ feuilles. Les
arbres binaires plans introduits pr\'ec\'edemment sont en particulier des
arbres plans.

\'Etant donn\'es un arbre plan $T$ et, pour chaque sommet interne
$s$ de $T$ de valence $v(s)$, un intervalle $I_s$ dans $Y_{v(s)-2}$,
on peut d\'efinir un intervalle $G(T,(I_s)_s)$ en greffant les minimum
(resp.  les maximum) des intervalles $I_s$ selon le sch\'ema de greffe
fourni par l'arbre plan $T$. La figure \ref{exemple} montre cette
construction pour un arbre plan \`a trois sommets et trois intervalles.

On dit qu'un intervalle est \textbf{nouveau} s'il ne peut pas s'\'ecrire
ainsi de fa\c con non triviale, c'est-\`a-dire s'il n'est pas de la forme
$G(T,(I_s)_s)$ avec $T$ ayant au moins deux sommets internes.

Remarque~: tout intervalle nouveau est ind\'ecomposable. En effet, un
intervalle d\'ecomposable n'est \'evidemment pas nouveau.

On appelle \textbf{d\'ecoupage en nouveaux} de $I$ une \'ecriture de $I$
sous la forme $G(T,(I_s)_s)$ o\`u tous les $I_s$ sont nouveaux.
L'existence d'une telle \'ecriture est claire par la d\'efinition des
intervalles nouveaux.

L'exemple de la figure \ref{exemple} montre un intervalle et son
d\'ecoupage en trois intervalles nouveaux, ainsi que l'arbre plan
associ\'e \`a ce d\'ecoupage.

\begin{lemma}
  \label{descente}
  Soit $K$ un intervalle et $s$ un segment du bord gauche de $\max(K)$. Si
  $\Y *_s K$ est nouveau, alors tout d\'ecoupage en nouveaux de $K$ est
  de la forme $K_1/ \dots / K_k$ o\`u les $K_i$ sont nouveaux.
\end{lemma}

\begin{proof}
  Par l'absurde. Supposons qu'il existe un d\'ecoupage de $K$ d'une
  autre forme. On peut donc en particulier d\'ecrire $K$ par la greffe
  de $K''$ sur une feuille (autre que la feuille gauche) de $K'$ pour
  certains intervalles $K'$ et $K''$. Mais on en d\'eduit alors un
  d\'ecoupage de $\Y *_s K$ sous la forme d'une greffe de $K''$ sur une
  feuille de $\Y *_s K'$. Ceci contredit l'hypoth\`ese.
\end{proof}

\begin{proposition}
  \label{decoupage}
  Tout intervalle $I$ a un unique d\'ecoupage en nouveaux.
\end{proposition}

\begin{proof}
  Il reste \`a montrer l'unicit\'e. On proc\`ede par r\'ecurrence sur $n$, en
  utilisant la description des intervalles obtenue pr\'ec\'edemment.

  Supposons d'abord que l'intervalle $I$ est d\'ecomposable. On choisit
  un d\'e\-cou\-page de $I$ en intervalles nouveaux. Ce d\'ecoupage induit par
  regroupement une d\'e\-composition de $I$. Cette d\'ecomposition est
  n\'ecessairement moins fine que la d\'ecomposition maximale.

  Si elle est strictement moins fine, un des termes admet une
  d\'ecomposition non triviale. Le d\'ecoupage en nouveaux de $I$ induit
  un d\'ecoupage en nouveaux de ce terme. L'intervalle situ\'e \`a la racine
  de ce d\'ecoupage en nouveaux est n\'ecessairement aussi d\'ecomposable.
  Ce qui est absurde, car il est nouveau, donc ind\'ecomposable.
  
  Par cons\'equent, la d\'ecomposition induite par le d\'ecoupage est \'egale
  \`a la d\'ecomposition maximale. Chacun des termes de la d\'ecomposition
  h\'erite alors d'un d\'ecoupage en nouveaux, ces d\'ecoupages sont uniques
  par r\'ecurrence, donc le d\'ecoupage en nouveaux de $I$ est unique. Il
  s'obtient par recollement des d\'ecoupages en nouveaux des termes de
  la d\'ecomposition maximale de $I$.

  \medskip

  \begin{figure}
    \begin{center}
      \scalebox{0.4}{\includegraphics{descente.eps}}
      \caption{D\'ecoupage en nouveaux d'un intervalle ind\'ecomposable}
      \label{fig-desc}
    \end{center}
  \end{figure}

  Supposons maintenant que l'intervalle $I$ est ind\'ecomposable. On
  peut supposer que $I$ n'est pas l'intervalle $[\Y,\Y]$. Il s'\'ecrit
  donc $\Y *_t L$ pour certains $t$ et $L$. On choisit un d\'ecoupage de
  $I$ en intervalles nouveaux. Soit $J$ l'intervalle nouveau situ\'e \`a
  la racine de ce d\'ecoupage.  N\'ecessairement, dans le d\'ecoupage de
  $I$, il n'y a pas d'intervalle nouveau greff\'e sur la feuille de
  gauche de $J$, sinon $I$ serait d\'ecomposable.

  Comme $J$ est nouveau, donc ind\'ecomposable, $J$ s'\'ecrit $\Y*_s K$
  pour certains $s,K$, ou bien $J=[\Y,\Y]$.

  Supposons d'abord que $J$ n'est pas $[\Y,\Y]$. Ce cas assez complexe
  est illustr\'e par la figure \ref{fig-desc}. Par le Lemme
  \ref{descente}, le d\'ecoupage en nouveaux de $K$ est de la forme $K_1
  / \dots /K_k$. On en d\'eduit par recollement de ce d\'ecoupage de $K$
  avec la partie sup\'erieure du d\'ecoupage en nouveaux de $I$ (les
  termes autres que $J$) un d\'ecoupage en nouveaux de $L$.  Ce
  d\'ecoupage en nouveaux de $L$ est unique par r\'ecurrence.

  Donc le d\'ecoupage en nouveaux de $I$ est aussi unique et s'obtient \`a
  partir de celui de $L$ par recollement des morceaux $K_1,\dots,K_k$,
  qui sont les morceaux situ\'es le long du bord gauche entre le segment
  racine et le segment $t$.

  Supposons maintenant que $J$ est l'intervalle $[\Y,\Y]$. Alors $I$
  est de la forme $\Y \backslash L$ pour un certain intervalle $L$, o\`u
  l'op\'eration $\backslash$ sur les intervalles est d\'efinie de mani\`ere
  similaire \`a l'op\'eration $/$. Prenons un autre d\'ecoupage en nouveaux
  de $I$ et soit $J'$ l'intervalle nouveau \`a la racine de ce
  d\'ecoupage. Si $J'$ n'est pas l'intervalle trivial $[\Y,\Y]$, on peut
  facilement construire un d\'ecoupage de $J'$, ce qui est absurde.

  Par cons\'equent, tout d\'ecoupage en nouveaux de $I$ induit un
  d\'ecoupage en nouveaux de $L$, unique par r\'ecurrence. Donc le
  d\'ecoupage en nouveaux de $I$ est unique, obtenu par greffe du
  d\'ecoupage en nouveaux de $L$ sur la feuille droite de l'intervalle
  $[\Y,\Y]$.
\end{proof}

Remarque~: une autre d\'emonstration de la Proposition \ref{decoupage}
peut sans doute \^etre obtenue en utilisant la description g\'eom\'etrique
du treillis de Tamari par le biais d'une forme lin\'eaire sur le
polytope de Stasheff.

\section{R\'esultat auxiliaire}

\label{muriel!}

On va utiliser ici un troisi\`eme type d'arbres. 

Un \textbf{arbre enracin\'e} est un graphe fini connexe et simplement
connexe muni d'un sommet distingu\'e appel\'e la \textbf{racine}. On
dessine les arbres enracin\'es avec la racine en bas, en choisissant un
plongement arbitraire dans le plan. Par convention, on oriente les
ar\^etes de haut en bas.

Un automorphisme d'un arbre enracin\'e $A$ est une permutation de ses
sommets qui fixe la racine et pr\'eserve la relation d'adjacence. On
note $\sigma_A$ le cardinal du groupe d'automorphismes de $A$.

On consid\`ere l'espace vectoriel gradu\'e $\PL$ ayant pour base en degr\'e
$n$ les arbres enracin\'es \`a $n$ sommets.

Cet espace $\PL$ est muni d'un produit bilin\'eaire non-associatif~: si
$A$ et $B$ sont des arbres enracin\'es, on pose
\begin{equation}
  A \sous B = \sum_{s \in A} A \sous_s B,
\end{equation}
o\`u la somme porte sur les sommets de $A$ et $A \sous_s B$ est l'arbre
enracin\'e obtenu en ajoutant, dans l'union disjointe de $A$ et de $B$,
une ar\^ete entre la racine de $B$ et le sommet $s$ de $A$ ; la racine de
$A \sous_s B$ est la racine de $A$.

Soit $\nu$ une s\'erie formelle en une variable $y$. On associe \`a chaque
arbre enracin\'e $A$ une fonction $\nu_A$ d\'efinie r\'ecursivement comme
suit. On \'ecrit $A$ comme la greffe d'arbres
enracin\'es $A_1,\dots,A_k$ (ensemble \'eventuellement vide) sur une
racine et on pose
\begin{equation}
  \nu_{A}= \left(\nu_{A_1} \dots \nu_{A_k}\right) \nu^{(k)},
\end{equation}
o\`u $\nu^{(k)}$ d\'esigne la $k$-i\`eme d\'eriv\'ee de $\nu$ par rapport \`a $y$.
En particulier, on prend comme condition initiale $\nu_\bullet=\nu$
pour l'unique arbre enracin\'e \`a un sommet $\bullet$. On a alors la
propri\'et\'e suivante.


\begin{proposition}
  Pour tous les arbres enracin\'es $A$ et $B$, on a
  \begin{equation}
    \nu_{A \sous B} = (\nu_A)' \nu_B.
  \end{equation}
\end{proposition}

\begin{proof}
  Ceci r\'esulte de la th\'eorie des alg\`ebres pr\'e-Lie, voir \cite{imrn}.
\end{proof}

Consid\'erons maintenant la s\'erie
\begin{equation*}
  \mathsf{\UU}=\sum_{A} \frac{1}{\sigma_A} A,
\end{equation*}
qu'on peut voir comme appartenant \`a un compl\'et\'e de $\PL$. On d\'ecompose
$\UU$ selon le nombre de sommets dans les arbres~:
\begin{equation*}
  \mathsf{\UU}=\sum_{k \geq 0} \frac{\UU_{k+1}}{k!},
\end{equation*}
o\`u le terme $\UU_{k+1}$ est une combinaison lin\'eaire d'arbres \`a $k+1$ sommets.

La proposition ci-dessous montre que la s\'erie formelle en arbres
enracin\'es $\UU$ s'identifie, aux signes pr\`es, \`a l'idempotent introduit
par Livernet \cite{muriel} dans l'\'etude des alg\`ebres pr\'e-Lie.

\bigskip

\begin{proposition}
  Les \'el\'ements $\UU_k$ sont d\'etermin\'es par la r\'ecurrence
  \begin{equation}
  \UU_{k+1}
  =\sum_{\ell=1}^{k} \binom{k-1}{\ell-1} \UU_\ell \sous\UU_{k+1-\ell},    
  \end{equation}
  pour $k\geq 1$ et la condition initiale que $\UU_1$ est l'arbre
  enracin\'e \`a un sommet.
\end{proposition}

\begin{proof}
  Fixons un entier $k$ positif ou nul et un entier $\ell$ strictement
  positif et inf\'erieur ou \'egal \`a $k$.

  Fixons un arbre enracin\'e $A$ \`a $k+1$ sommets, $B$ un arbre enracin\'e
  \`a $\ell$ sommets, $C$ un arbre enracin\'e \`a $k+1-\ell$ sommets,

  Consid\'erons l'ensemble $E_1(A,B,C)$ des triplets $(s,i,j)$ o\`u $s$
  est un sommet de $A$ distinct de la racine, $i$ un isomorphisme
  entre $C$ et le sous arbre de $A$ de racine $s$ et $j$ un
  isomorphisme entre $B$ et le compl\'ementaire de ce sous-arbre de $A$
  (qui est aussi un sous-arbre).

  Alors, cet ensemble $E_1(A,B,C)$ est en bijection avec l'ensemble
  $E_2(A,B,C)$ des couples $(s,\varepsilon)$, o\`u $s$ est un sommet de
  $B$ et $\varepsilon$ un isomorphisme entre $A$ et l'arbre $B \sous_s
  C$. La bijection utilise les isomorphismes pour identifier le sommet
  $s$ de $A$ \`a un sommet $s$ de $B$. On d\'eduit l'isomorphisme
  $\varepsilon $ des deux isomorphismes $i$ et $j$ et r\'eciproquement.

  On a donc une \'egalit\'e $\sum_{E_1(A,B,C)} A = \sum_{E_2(A,B,C)} B \sous_s C $.

  De plus, les groupes d'automorphismes de $B$ et $C$ agissent
  librement sur $E_1(A,B,C)$ et le groupe d'automorphisme de $A$ agit
  librement sur $E_2(A,B,C)$.

  On obtient, avec la convention que le nombre de sommets de
  $A$ est $k+1$, celui de $B$ est $\ell$ et celui de $C$ est
  $k+1-\ell$,
  \begin{align*}
    \frac{\UU_{k+1}}{k!}&=\sum_{A} \frac{1}{\sigma_A} A
    = \frac{1}{k} \sum_{(A,s\in A)} \frac{1}{\sigma_A} A\\
    &=\frac{1}{k} \sum_{\ell=1}^{k} \sum_{(A,B,C)} \sum_{(s,i,j) \in E_1(A,B,C)} \frac{1}{\sigma_A \sigma_B \sigma_C} A\\
    &=\frac{1}{k} \sum_{\ell=1}^{k} \sum_{(A,B,C)} \sum_{(s,\varepsilon)\in E_2(A,B,C)} \frac{1}{\sigma_A \sigma_B \sigma_C} B \sous_s C\\
      &=\frac{1}{k} \sum_{\ell=1}^{k} \sum_{(B,C,s \in B)} \frac{1}{\sigma_B \sigma_C} B \sous_s C\\
      &=\frac{1}{k} \sum_{\ell=1}^{k} \sum_{(B,C)} \frac{1}{\sigma_B \sigma_C} B \sous C\\
      &=\frac{1}{k} \sum_{\ell=1}^{k} \left(\sum_B \frac{1}{\sigma_B} B\right) \sous \left(\sum_C
      \frac{1}{\sigma_C} C\right)\\
      &= \frac{1}{k} \sum_{\ell=1}^{k} \frac{\UU_{\ell}}{(\ell-1)!} \sous
      \frac{\UU_{k+1-\ell}}{(k-\ell)!}.
  \end{align*}
  Ceci termine la d\'emonstration de la proposition.
\end{proof}

\section{\'Enum\'eration des intervalles nouveaux}

Si on compte les intervalles nouveaux dans les premiers treillis de
Tamari, on trouve
\begin{equation*}
  1,1,3,12,56,288,1584,\text{etc.},
\end{equation*}
pour $n \geq 1$.

On est men\'e, par consultation de l'encyclop\'edie des suites d'entiers,
\`a conjecturer le r\'esultat suivant.

\begin{theorem}
  \label{theo_int_nouv}
  Pour $n \geq 2$, le nombre d'intervalles nouveaux dans le treillis de
  Tamari $Y_n$ est
  \begin{equation}
    3 \,\frac{ 2^{n-2} (2n-2)!}{(n-1)!(n+1)!}.
  \end{equation}
\end{theorem}

La preuve est l'objet de la suite de cette section.

A chaque arbre plan $T$, on peut associer un arbre enracin\'e
$\forme(T)$ (la \textbf{forme} de $T$) de la fa\c con suivante~: les
sommets de $\forme(T)$ sont les sommets internes de $T$, les ar\^etes de
$\forme(T)$ sont les ar\^etes entre sommets internes de $T$, la racine
de $\forme(T)$ est le sommet interne de $T$ qui est adjacent \`a la
racine de $T$, voir la figure \ref{forme}.

\begin{figure}
  \begin{center}
    \scalebox{0.4}{\includegraphics{forme.eps}}
    \caption{Un arbre plan et l'arbre enracin\'e associ\'e}
    \label{forme}
  \end{center}
\end{figure}

\medskip

On introduit par commodit\'e une version d\'ecal\'ee de la s\'erie g\'en\'eratrice
des intervalles~:
\begin{equation*}
  \psi=y\phi=\sum_{n\geq 1} |\Int_n| y^{n+1}=y^2+3 y^3 + 13 y^4 + \dots
\end{equation*}
et une s\'erie g\'en\'eratrice similaire pour les intervalles nouveaux~:
\begin{equation*}
  \nu=\sum_{n\geq 1} 
\underset{\text{nouveau}}{\sum_{[S,T]\in\Int_n}} y^{n+1}=y^2+
    y^3 + 3 y^4 + 12 y^5 +\dots
\end{equation*}
On peut d\'eduire de l'\'equation alg\'ebrique (\ref{eqphi}) pour $\phi$ une \'equation
alg\'ebrique pour $\psi$~: 
\begin{multline*}
    {\psi}^{4}+ \left( 4\,y+3 \right) {\psi}
^{3}+ \left( 6\,{y}^{2}+17\,y +3\right) {\psi}^{2} \\+ \left( 
4\,{y}^{3}+25\,{y}^{2}-14\,y+1 \right) \psi+y^2
\left({y}^{2}+11\,{y}-1 \right) =0.
\end{multline*}

On va chercher \`a obtenir une \'equation alg\'ebrique pour $\nu$.

\medskip

Soit $N_n$ le nombre d'intervalles nouveaux dans le treillis de Tamari
$Y_n$. Le d\'ecoupage unique d'un intervalle en intervalles nouveaux
donne la relation suivante~:
\begin{equation}
  \label{nouveau_brut}
  \psi=\sum_{n \geq 1} \sum_{T\in P_n} N_T \,y^{n+1},
\end{equation}
o\`u $P_n$ est l'ensemble des arbres plans \`a $n+1$ feuilles et $N_T$ est
le produit sur l'ensemble des sommets internes $s$ de $T$ des
$N_{v(s)-2}$ ($v(s)$ est la valence de $s$).

Dans cette somme, on regroupe les termes selon la valeur de
$\forme(T)$~:
\begin{equation*}
  \psi=\sum_{A}\sum_{n\geq 1} 
\underset{\forme(T)\simeq A}{\sum_{T \in P_n}}
  N_T \, y^{n+1},
\end{equation*}
o\`u la somme externe porte sur les arbres enracin\'es.

Fixons un arbre enracin\'e $A$ et soit $I$ l'ensemble de ses sommets.
Notons $v_i$ le nombre d'ar\^etes entrantes du sommet $i$. La somme des
$v_i$ vaut $|I|-1$, car chaque sommet sauf la racine a exactement une
ar\^ete sortante.

On a besoin de d\'ecrire l'ensemble des arbres plans de forme isomorphe
\`a $A$. On a un bijection entre d'une part l'ensemble $F_1(A)$ form\'e
par les paires $(T,\gamma)$ o\`u $T$ est un arbre plan et $\gamma$ un
isomorphisme entre $\forme(T)$ et $A$ et d'autre part l'ensemble
$F_2(A)$ form\'e par les paires $((\ell_i)_i,(Z_i)_i)$ o\`u, pour chaque
sommet $i$ de $A$,
\begin{itemize}
\item $\ell_i$ est un nombre sup\'erieur ou \'egal \`a $2$,
\item $Z_i$ est une injection de l'ensemble des ar\^etes entrantes en $i$
  dans l'ensemble $\{1,\dots,\ell_i\}$.
\end{itemize}

La bijection est la suivante~: \`a la paire $(T,\gamma)$, on associe les
nombres $\ell_i$ tels que $\ell_i+1$ est la valence du sommet de $T$
correspondant par $\gamma$ au sommet $i$ de $A$. Par $\gamma$, les
ar\^etes entrantes en $i$ dans $A$ sont envoy\'ees dans l'ensemble des
ar\^etes entrantes du sommet correspondant de $T$, ce qui donne
l'injection $Z_i$ voulue.

R\'eciproquement, si on conna\^{\i}t les nombres $\ell_i$ et les injections
$Z_i$, on peut ais\'ement reconstruire un arbre plan $T$ muni d'une
bijection $\gamma$.

% Un arbre plan $T$ de forme $A$ est uniquement d\'etermin\'e par les
% donn\'ees suivantes~:
% \begin{itemize}
% \item un dessin de $A$ dans le plan~: un ordre total sur les ar\^etes
%   entrantes de chaque sommet de $A$, modulo l'action libre du groupe
%   des automorphismes de $A$.
% \item les valences $\ell_i+1$ dans $T$ de ses sommets internes (en
%   bijection avec les sommets de $A$)
% \item les positions de greffe~: pour chaque $i$, $v_i$
%   entiers distincts dans $\{1,\dots,\ell_i\}$.
% \end{itemize}

Le groupe des automorphismes de $A$ agit librement sur $F_1(A)$. La
contribution de $A$ \`a $\psi$ est donc donn\'ee par
\begin{equation*}
  \frac{1}{\sigma_A} \sum_{(\ell_i)_{i \in I}} \prod_{i \in I} \left( \frac{\ell_i
      !}{(\ell_i-v_i)!} N_{\ell_i-1} \right) y^{n+1},
\end{equation*}
o\`u $n$ est la somme des $\ell_i-1$. En r\'epartissant la variable $y$,
ceci vaut encore
\begin{equation*}
  \frac{1}{\sigma_A} \sum_{(\ell_i)_{i \in I}} \prod_{i \in I} \left(\frac{\ell_i
    !}{(\ell_i-v_i)!} N_{\ell_i-1} y^{\ell_i-v_i}\right),
\end{equation*}
soit
\begin{equation*}
  \frac{1}{\sigma_A} \prod_{i\in I} \left(\sum_{\ell_i \geq 2} \frac{\ell_i
    !}{(\ell_i-v_i)!}N_{\ell_i-1} y^{\ell_i-v_i}\right).
\end{equation*}
On reconna\^{\i}t dans les facteurs de cette formule les d\'eriv\'ees de $\nu$,
on obtient donc
\begin{equation*}
  \frac{1}{\sigma_A} \prod_{i\in I} \nu^{(v_i)}.
\end{equation*}

En utilisant la d\'efinition des fonctions $\nu_A$ comme dans la section
\ref{muriel!}, on peut donc \'ecrire
\begin{equation}
  \label{sommarb}
  \psi=\sum_{A} \frac{1}{\sigma_A} \nu_A=\nu+\nu \nu'+ \nu (\nu')^2 +\frac{1}{2} \nu^2 \nu''+ \dots,
\end{equation}
o\`u la somme porte sur les arbres enracin\'es, 

\medskip

Introduisons une suite de fonctions $(\alpha_k)_{k \geq 1}$ de la
variable $y$. Le terme initial est $\alpha_1=\nu$. Les termes suivants
sont donn\'es pour $k\geq 1$ par la r\'ecurrence
\begin{equation*}
  \alpha_{k+1}
  =\sum_{\ell=1}^{k} \binom{k-1}{\ell-1}\partial_y(\alpha_\ell)\,\alpha_{k+1-\ell}.
\end{equation*}

Alors, par les r\'esultats de la section \ref{muriel!}, l'\'equation
(\ref{sommarb}) \'equivaut \`a
\begin{equation*}
  \psi=\sum_{k \geq 0} \frac{\alpha_{k+1}}{k!}.
\end{equation*}

Introduisons la s\'erie g\'en\'eratrice double
\begin{equation*}
  \MPsi=\sum_{k \geq 0}{\alpha_{k+1}}\frac{z^k}{k!}.
\end{equation*}

La r\'ecurrence d\'efinissant les fonctions $\alpha_k$ se traduit en une
\'equation aux d\'eriv\'ees partielles pour $\MPsi$~:
\begin{equation}
  \label{edp}
  \partial_z \MPsi= (\partial_y \MPsi) \MPsi,
\end{equation}
avec la condition initiale
\begin{equation}
  \label{condi}
  \MPsi\vert_{z=1}=\psi.
\end{equation}

Par cons\'equent, $\Psi$ est solution de l´\'equation alg\'ebrique
\begin{multline*}
 {z}^{4}{\MPsi}^{4}+ \left( 4\,{z} y-8+11\,{z} \right) z^2 {\MPsi}^{3}+ \left( 6\,{z}^{2}{y}^{2}-{z}^
{2}+33\,{z}^{2}y-16\,z y+16-12\,z \right) {\MPsi}^{2}\\+ \left( -8\,{
y}^{2}-2\,z y+1+4\,z{y}^{3}-12\,y+33\,z{y}^{2} \right) \MPsi+11\,{y
}^{3}+{y}^{4}-{y}^{2} =0.
\end{multline*}
En effet, la solution de cette \'equation alg\'ebrique v\'erifie l'\'equation
diff\'erentielle (\ref{edp}) et la condition initiale (\ref{condi}) en
$z=1$. En utilisant la sp\'ecialisation
\begin{equation*}
  \MPsi\vert_{z=0}=\alpha_1=\nu,
\end{equation*}
on d\'eduit de cette \'equation alg\'ebrique pour $\MPsi$ une \'equation
alg\'ebrique pour $\nu$~:
\begin{equation*}
  {y}^{2}-11\,{y}^{3}-{y}^{4}+ \left( -1+12\,y+8\,{y}^{2} \right) \nu
  -16\,  \nu^{2}=0.
\end{equation*}
Donc
\begin{equation*}
 \nu= \frac{1}{32}\left(-1+12\,y+8\,{y}^{2}+\,(1-8\,y)^{3/2}\right).
\end{equation*}
On en d\'eduit imm\'ediatement la formule attendue pour les coefficients
de $\nu$. Ceci d\'emontre le Th\'eor\`eme \ref{theo_int_nouv}.

\bibliographystyle{plain}
\begin{thebibliography}{1}

\bibitem{imrn}
Fr{\'e}d{\'e}ric Chapoton and Muriel Livernet.
\newblock Pre-{L}ie algebras and the rooted trees operad.
\newblock {\em Internat. Math. Res. Notices}, (8)\!\!:395--408, 2001.

\bibitem{groupes}
Fr{\'e}d{\'e}ric Chapoton. 
{Rooted trees and an exponential-like series}.
{\tt ar$\chi$iv\!\!\!:math.QA/0209104}.

\bibitem{schaeffer}
Robert Cori and Gilles Schaeffer.
\newblock Description trees and {T}utte formulas.
\newblock {\em Theoret. Comput. Sci.}, 292(1)\!\!:165--183, 2003.
\newblock Selected papers in honor of Jean Berstel.

\bibitem{tamari}
Samuel Huang and Dov 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{muriel}
Muriel Livernet.
\newblock {A rigidity theorem for preLie algebras}.
\newblock {\em J. Pure Appl. Algebra} 207(1), 1--18, 2006.

\bibitem{lecturenotes}
Jean-Louis 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{arithm}
Jean-Louis Loday.
\newblock Arithmetree.
\newblock {\em J. Algebra}, 258(1)\!\!:275--309, 2002.
\newblock Special issue in celebration of Claudio Procesi's 60th birthday.

\bibitem{reading}
Nathan Reading.
\newblock {Cambrian Lattices}.
\newblock {\em Adv. Math.}, 205(2)\!\!:313--353, 2006.

\bibitem{oeis}
N.~J.~A. Sloane.
\newblock The {O}n-{L}ine {E}ncyclopedia of {I}nteger {S}equences, 2006.
\newblock \tt www.research.att.com/\~{}njas/sequences/\rm.

\end{thebibliography}

\end{document}
