\documentclass[11pt]{article}
\input{/Users/nicolascurien/Dropbox/Macros-bibli/macros-english2}
\newcommand{\pp}{\ensuremath{\sqsubset}}
\newcommand{\ppld}{\ensuremath{\sqsubset_{LD}}}
\newcommand{\rev}{\ensuremath{\textrm{\textup{rev}}}}
\newtheorem{exo}{Exercise}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prperty}[theorem]{Property}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{exe}[theorem]{Example}
\newtheorem{open}{Open Question}
\newcommand{\rf}{\ensuremath{\mathfrak{R}}}
\newcommand{\m}{\mathcal{M}}
\newcommand{\T}{\mathcal{T}}
\renewcommand{\P}[1]{\mathbb{P}\left[#1\right]}
\newtheorem{rek}[theorem]{Remark}
\renewcommand{\sh}{\ensuremath{\textrm{\textup{sh}}}}
\renewcommand{\rg}{\ensuremath{\cyclearrowright}}
\usepackage{enumerate}
\def\llbracket{[\hspace{-.10em} [ }
\newcommand{\e}{\mbox{e}\hspace{-.34em}\mbox{\i}}
\renewcommand{\e}{\mathfrak{e}}
\def\rrbracket{ ] \hspace{-.10em}]}
\usepackage{amsmath}
%\usepackage{palatino}
\title{Metric Geometry}
\date{}
\author{}
\begin{document}
%\maketitle
\setcounter{section}{0}
\section{Galton-Watson Trees}
\begin{exo}[Catalan number]
\begin{enumerate}
\item Show that there exists a bijection between the set $\mathcal{B}_{n}$ of rooted, oriented binary trees with $2n$ edges and the set $\mathbf{A}_{n}$ of rooted, oriented (general) trees with $n$ edges.
\item The generating function of $\mathcal{B}_{n}$ is by definition 
$$ B(z) = \sum_{n\geq 0} z^{2n}\# \mathcal{B}_{n}.$$
Show that $B$ satisfies $B(z)=1+z^2 B(z)^2,$ or equivalently $zB(z)= z (1 +(zB(z))^2)$.
\item Apply Lagrange inversion formula (or solve the equation) to find 
$$ \# \mathcal{B}_{n} = {\frac{1}{n+1}} {2n \choose n} .$$
\end{enumerate}
\end{exo}

A \emph{Cayley tree} is a labeled tree with $n$ vertices without any orientation nor distinguished point. In other words it is a spanning tree on $\mathbb{K}_{n}$, the complete graph over $n$ vertices. See figure below. 
\begin{figure}[h]
\begin{center}
\includegraphics[height=3cm]{spanning}
\end{center}
\end{figure}
\begin{exo} Let $T$ be a (rooted, oriented) Galton-Watson tree with Poisson(1) offspring distribution. We denote by $|T|$ the number of edges of $T$ and put 
$$ P(z) = \sum_{n\geq 0} \mathbb{P}(|T|=n) z^n.$$
\begin{enumerate}
\item Show that $P = \mathrm{e}^{-1}\exp ( zP).$
\item Apply Lagrange Inversion Theorem to get 
$$ \mathbb{P}(|T|=n-1) = \frac{n^{n-1}\mathrm{e}^{-n}}{n!}, \mbox{ for all } n \geq 1.$$

\item Let $T_{n}$ be a Galton-Watson tree with Poisson(1) offspring distribution conditioned to have $n$ vertices. Then assign the labels $\{1, ... ,n\}$ uniformly at random to the vertices of $T_{n}$ and forget the ordering and the root of $T_{n}$. Show that the resulting unordered labeled tree is uniform over the set $\mathcal{C}_{n}$ of Cayley trees over $\{1, ... ,n\}$. Deduce 
$$ \# \mathcal{C}_{n} = n^{n-2}.$$
\end{enumerate}
\end{exo}

\noindent \textbf{Lagrange Inversion Theorem}.  Let $\phi(u) = \sum_{k\geq 0} \phi_{k} u^k$ be a power series of $\mathbb{C}[[u]]$ with $\phi_{0}\ne0$. Then, the equation $y=z\phi(y)$ admits a unique solution in $\mathbb{C}[[z]]$ whose coefficients are given by $$y(z)=\sum_{n=1}^\infty y_{n} z^n, \hspace{2cm} \mbox{with }y_{n}= \frac{1}{n}[u^{n-1}]\phi(u)^n,$$
where $[u^{n-1}]\phi(u)^n$ stands for the coefficient in front of $u^{n-1}$ in $\phi(u)^n$.
\begin{exo}[Proof of Lagrange Inversion Theorem]
\begin{enumerate}
\item Show that the coefficients of $y$ as a series of $z$ are determined by the coefficients of $\phi$ and the equation $y=z\phi(y)$ in $\mathbb{C}[[z]]$.
\item Assume that $\phi$ is a polynomial function. \begin{enumerate} \item Show that $y$ is analytic around $0$. \item Using Cauchy formula, show that $$n[z^n]y=ny_{n}= \frac{1}{2i\pi}\int_{ \mathcal{C}} \frac{y'(z)dz}{z^n}, \hspace{0.5cm} \mbox{ where }\mathcal{C} \mbox{ is a small anticlockwise contour around }0.$$
\item With a change of variable, prove the Lagrange Inversion Theorem in this case. \end{enumerate}
\item Deduce the general case.
\end{enumerate}
\end{exo}

\begin{exo}* Who are these charming gentlemen ?

\begin{figure}[h]
\begin{center}
\includegraphics[height=5.5cm]{galton}
\includegraphics[height=5.5cm]{watson}
\includegraphics[height=5.5cm]{bienayme} \\ \ \\ 
\includegraphics[height=5.5cm]{cayley}
\includegraphics[height=5.5cm]{borchardt}
\includegraphics[height=5.5cm]{catalan}
\end{center}
\end{figure}

Note that the fourth one already had a cell-phone.
\end{exo}

\nocite{FS09}
\nocite{Ald98}

\bibliographystyle{alpha}
\bibliography{/Users/nicolascurien/Dropbox/Macros-Bibli/bibli}



\end{document}