%==================================================
%%% \documentstyle[12pt,fullpageusa]{article}
\documentstyle[11pt]{article}

% Dimensions 
\textwidth 15.5 true cm  % says Quisquater 16x26.5 cm
			% but everything is consistent with 18 instead...

\textheight 23 true cm
\pagestyle{empty}
\topmargin -1.3 true cm
\oddsidemargin .2in

% statements
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}



% Abbrevs
\def\ds{\displaystyle}
\def\Arg{\hbox{\rm Arg}}
\def\FF{{\cal F}}
\def\Fn{{\cal F}_n}
\def\Fmn{{\cal F}_n^{<m>}}
\def\Fnn{{\cal F}_n^{<n>}}
\def\FF{{\cal F}}
\def\eop{\vrule height7pt width 6pt depth 0pt}
\def\GF{{\sc gf}}
\def\Tm{{\bf T}_m}
\def\Rm{{\bf R}_m}


% Goodies
\def\LUO{\leavevmode
{\char'3\kern -.2em\lower 0.666ex\hbox{\char'7}\kern-.125 em\raise0.2ex\hbox{\char'12}}}

\def\Small{\small}  % In case we want footnotes in smallsize instead of footnotesize

\newenvironment{smallit}{\renewcommand{\baselinestretch}{0.87}\par\begin{small}}{\par\renewcommand{\baselinestretch}{1}\par\end{small}}



\title{\bf RANDOM MAPPING STATISTICS}
\author{Philippe Flajolet\\
INRIA Rocquencourt,\\
F--78150 Le Chesnay (France)
\and
Andrew M. Odlyzko\\
AT\&T Bell Laboratories,\\
Murray Hill, NJ 07974 (USA)
}
\date{}

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

\begin{document}

\maketitle

 % Introduction
%%%\input m1.tex

% Methods
%%%\input m2.tex

% Additive parameters
%%%\input m3.tex

% Extremal statistics
%%%\input m4.tex

% Extensions
%%%\input m5.tex

% Conclusion
%%%\input m6.tex

% Bibliography

%%% \frenchspacing
%%% \renewcommand{\baselinestretch}{0.90}


%%% \bibliography{/home/yquem/algo/flajolet/lib/bib/algo}
%%% \bibliographystyle{plain}




%==================================================
\begin{quote}
\begin{smallit}
\noindent
{\bf Abstract.}
Random mappings from a finite set into itself
are either a heuristic or an exact model for a variety of applications in
random number generation,
computational number theory,
cryptography, and the analysis of algorithms 
at large.
This paper introduces a general framework in which
the analysis of about twenty characteristic parameters
of random mappings is carried out:
These parameters are studied
systematically through the use of generating functions and
singularity analysis.
In particular, an open problem of Knuth is solved,
namely that of finding the expected diameter of a
random mapping. The same approach is applicable to a larger class of discrete
combinatorial models and possibilities of automated analysis
using symbolic manipulation systems (``computer algebra'')
are also briefly discussed.
\end{smallit}
\end{quote}

\section{Introduction}

Random maps % of one sort or another
occur in many problems of discrete probability.
Consider for instance the following 
assertions:
\begin{enumerate}
\item Throw $n$ balls into $m$ urns at random.
Then, a proportion of about $e^{-n/m}$ of the urns
will usually be empty. [Hashing].
\item A room contains $23$ persons. It is a good 
idea (the odds are 50.7\% in your favour!)
 to bet that two persons in the room have the same birthdate.
[Birthday paradox].
\item You buy chocolate bars
that contain coupons and there are $n$
different possible coupons. Expect to buy (and possibly eat!)
about $n\log n$ chocolate bars in order to
obtain a full collection.
[Coupon collector problem].
\item When using a middle--square random number generator
(or some other ``randomly'' designed random number generator)
operating with $\ell$ digits, the generator is likely
to cycle after about $2^{\ell/2}$ steps.
[``Random'' random number generators].
\item Pollard's integer factorization algorithm
is likely to find a factor  of 
a composite integer $n$ within $\approx n^{1/4}$ steps.
[Pollard's rho--method].
\item There are $n$ spies that attend a cryptography conference
and leave their hats at the cloakroom.
When the lecture is over, each spy picks up  a hat at
random. Then, there is a probability close
to $e^{-1}$ that nobody has his hat on
his head. [Derangement problem].
% \item There are $n$ persons that go to the opera
% and leave their hats at the cloakroom.
% When the show is over, each person picks up  a hat at
% random. Then, there is a probability close
% to $e^{-1}$ that nobody has his hat on
% his head. [Derangement problem].
\end{enumerate}
These assertions are all classical.
A moment's reflection shows that they
convey some information on (random) functions
from a finite set to a finite set.
We thus let $\Fmn$ denote the collection of all
functions from a finite $n$--set domain to a finite $m$-set
range, and use $\Fn\equiv\Fnn$ to denote the special case
where $m=n$, in which situation we merely consider an arbitrary
function of a finite set into itself.

Situations where we deal with $\Fmn$ are commonly known
as {\sl occupancy problems\/} in discrete probability theory.
Models where we consider random elements
of $\Fn$ are known as {\sl random mappings\/} models.

Assertions~1 and 2 are typical of statistical
properties of random elements of $\Fmn$,
i.e., occupancy problems.
Assertion~1 is typical of a whole range of
problems that present themselves when analyzing
the expected performance of hashing algorithms
\cite{Knuth73}. Assertion~2 is
the classical ``birthday paradox'' and it owes its
celebrity to the rather counterintuitive low
value of $23$.
Assertion~3 constitutes the classical
``coupon collector problem''.
It is slightly more
complicated than the earlier ones,
since now $m$ is itself a random variable in the process.
However, if we look at the probability that
a fixed number $m$ of bars suffice for a full collection,
it reduces to a standard
statistical problem over $\Fmn$.

Assertion~4 brings us closer to
the subject of this paper, since it deals with
the iteration structure
of a finite set into itself.
It is an assertion concerning $\Fmn$ with $m=n=2^\ell$.
What it says in essence is that
a random {\sl mapping\/} $f\in\Fn$ will tend
to ``cycle'' after about $\sqrt{n}$ steps.
As is quite well known, this fact,
combined with an idea of Floyd
for testing random number generators,
gave rise to Pollard's
rho--method \cite{Pollard75}
for integer factoring
(cf.~Assertion~5). This
eventually led to the % discovery \cite{BrPo81} of the factorization
factorization 
of the eighth Fermat number $F_8=2^{2^8}+1$, see \cite{BrPo81}.

The last assertion, number 6, is related to
random permutations which form a special subset
of $\Fn$.

The model of random functions
---where every function from $\Fmn$ or $\Fn$ is
taken equally likely--- may be either ``exact''
(\#\ 1,2,3,6) or ``heuristic'' in which case
(\#\ 4,5) we postulate, on the basis of simulations,
that  % asymptotically
properties of
a special class of functions (e.g. quadratic function
models)
should be asymptotically the same
as properties of
the class of {\sl all\/} functions\footnote{\Small In the case
of Pollard's algorithms and iteration of quadratic functions modulo
integers, a notable advance is due to Bach \cite{Bach89}
who proved recently that---in {\sl initial\/} stages--- quadratic
functions behave asymptotically like random functions.
Bach's result ultimately relies on the Weil--Deligne theorem
establishing the truth of the ``Riemann hypothesis''
for zeta functions of algebraic curves!}.

\smallskip
Our purpose here is to describe a unified framework for
analyzing a number of statistical\footnote{\Small The term ``statistics''
is to be understood in the sense
of discrete probability.}
properties of random mappings.
A probabilistic  problem to be analyzed is first specified symbolically
in terms of a collection of suitable combinatorial constructions.
If this specification succeeds, then
combinatorial theory guarantees that
{\sl generating functions\/} for parameters of interest can be found.
We then recover {\sl asymptotic\/} information
from these generating functions using
{\sl complex analysis\/}, and more precisely,
using the local behaviour of generating functions
around their singularities.

This approach is effective in analyzing a large number of ``decomposable''
parameters of random mappings. With it, we are able to derive in a 
uniform manner a number of results
otherwise obtained by a variety of probabilistic or
combinatorial arguments. 
We also demonstrate the effectiveness of our
approach by solving an open problem of Knuth \cite{Knuth81},
namely that of estimating the expected diameter of
random mappings.


{\sl Note.}
We refer to Knuth's book \cite{Knuth81}
for background information on
random number generators.
Random mappings are the subject
of a vast collection of works;
Mutaf{\v c}iev's survey \cite{Mutafchiev84}
cites 113 references!
For general presentations, we
direct the reader to the classic paper of Harris \cite{Harris60},
the papers by Arney and Bender \cite{ArBe82},
and Stepanov \cite{Stepanov69}.
In this area,
the contribution of the ``Russian school''
which uses essentially probabilistic methods,
as shown by  Kolchin's book {\sl Random Mappings\/} \cite{Kolchin86},
is notable.

For completeness, we mention several recent papers not referenced in \cite{Kolchin86},
namely \cite{Broder85,Delaurentis88,FlKnPi89,Jaworski85,Kalugin88,Pavlov88,Pavlov88a}.
In addition, there is now a growing literature on random mapping patterns,
and we refer to \cite{Mutafchiev88} for a comprehensive list
of references on this subject.

This paper is an (extended!) abstract.
In particular, statements of Section~4
regarding extremal statistics should be taken as preliminary announcements
of results:
Several of the proofs there (Theorems~7,8) are extremely delicate and,
at the time of this writing, have not appeared
in full detail.
% thus corresponding theorems
% should be taken with some caution.
The reader interested in quantitative estimates on random mappings
rather than methodology can proceed directly to the self contained
statements of Theorems 2--8.
\section{Methods}

Any element of $\Fmn$ can be viewed as a word over an
$m$--ary alphabet of length $m$. Thus,
there are $m^n$ mappings from an $n$--set
into an $m$--set. Specializing this
observation, we find that the cardinality
of $\Fn\equiv\Fnn$ is $n^n$.
We are going to rederive this trivial result
by means of generating functions.
If $\{f_n\}_{n\ge0}$ is a sequence of numbers, then
its (exponential) {\sl generating function\/} ({\GF}) is defined
to be
\begin{equation}
f(z)=\sum_{n\ge0} f_n {z^n\over n!}.
\end{equation}
Proceeding in such a simple case as the enumeration
of $\Fn$ via generating functions may seem a complicated detour.
However, it has the advantage of illustrating,
without unnecessary complications, a complete chain in the approach
we propose to follow for appreciably harder problems.
In this way, we shall be able to give a unified presentation of 
a number of problems otherwise treated by a variety of {\sl ad hoc\/}
methods.

As is well known, there are two components
in the use of generating functions.
\begin{description}
\item[{\rm A.}] First, it is classical that a number of
{\sl combinatorial constructions\/} translate directly into
generating function equations. Thus, by properly specifying
a counting problem by means of these constructions,
we are able to derive mechanically a collection
of generating function equations that ---in principle, at least---
solve our problem exactly.
\item[{\rm B.}] Second, the {\sl singularities\/} of generating functions
(now treated as analytic objects) condense most of
the {\sl asymptotic\/} information needed to
recover their coefficients.
\end{description}
We refer to \cite{GoJa83,Stanley86}
for background knowledge related to combinatorial analysis
(Part~A).
General references for asymptotic methods
can be found in \cite{deBruijn81,Olver74}
and our approach follows closely our paper \cite{FlOd90}.

\smallskip
Our treatment of random mappings is based not on the
direct representation of mappings by sequences of choices but
instead on their decomposition as {\sl functional graphs\/}.

\begin{figure}
\vspace*{4.5cm}
%%%\special{psfile=rmaps.ps hoffset=72 voffset=-24} % hscale=0.5 vscale=0.5}

\noindent
\begin{smallit}
{\bf Figure 1.} The functional graph associated to the map
$\varphi(x)=x^2+2\pmod{20}$.
The functional graph comprises two connected components
each containing a cycle of length $2$.
The function $x^2+2\pmod n$ is one of a restricted set
of polynomial functions whose iteration structure
can be precisely described. For general polynomials,
essentially, the only known approach is heuristic
where one postulates that a polynomial
behaves like a random mapping.
(See however \cite{Bach89} for one of the
very few rigorous results in this domain.)
\end{smallit}

\smallskip
\noindent\hrule
\end{figure}

Let $\varphi$ be an element of $\Fn$.
Consider the directed graph whose nodes are
the elements $[1..n]$ and whose edges are
the ordered pairs $\langle x,\varphi(x)\rangle$,
for all $x\in [1..n]$.
If we start from any $u_0$ and keep iterating $\varphi$,
i.e., we consider the sequence $u_1=\varphi(u_0), u_2=\varphi(u_1)\ldots$,
we are going to find, before $n$ iterations,
a value $u_j$ equal to one of $u_0,u_1,\ldots,u_{j-1}$.
In graphical terms, starting from any $u_0$, the iteration structure
of $\varphi$ is described by a simple path  that
connects to a cycle. The length of the 
path (measured by the number of edges) is called the {\sl tail length\/}
of $u_0$ and is denoted by $\lambda(u_0)$.
The length of the cycle (measured by the number
of edges or nodes) is called the 
{\sl cycle length\/} of $u_0$
and is denoted by $\mu(u_0)$.
We also call {\sl rho-length\/} of $u_0$
the quantity $\rho(u_0)=\lambda(u_0)+\mu(u_0)$
which is the length of the non repeating trajectory of
the point $u_0$.

If we now consider all possible starting points $u_0$,
paths exhibit confluence and form into trees;
these trees, grafted on cycles, form components;
finally, a collection of (connected) components
forms a functional graph (see Fig.~1).

\subsection{Combinatorial Enumerations}
Looking at Figure~1, a computer scientist could
be tempted to give a description of 
functional graphs of the following form
\begin{verbatim}
     type    FunGraph   = set(Component);
             Component  = cycle(Tree);
             Tree       = Node * set(Tree);
             Node       = Latom(1).  %Comment: atom of size 1 (labelled)
\end{verbatim}
In other words a functional graph is a {\sl set\/}
of connected components;
a component is a {\sl cycle\/} of trees;
a tree is recursively defined by appending a node
to a {\sl set\/} of trees;
a node is a basic atomic object (of size 1),
and labelled by an integer.

Let us adopt here the convention
that if  $\cal C$ is a class of combinatorial structures,
then  $C_n$ (or $c_n$) denotes the number of elements in the class
which have size $n$ ---i.e., $n$ nodes.
As seen already, we let
$$C(z)=\sum_{n\ge0}C_n{z^n\over n!}$$
denote the corresponding (exponential) generating function.
Thus, we use the same letters or groups of letters
to denote structures ($\cal C$), counting sequences ($C_n$ or $c_n$)
and generating functions ($C(z)$ or $c(z)$).

Recent formalization of the process of combinatorial counting
(see e.g., \cite{GoJa83})
offers the possibility of translating directly
specifications of the type above
into generating function equations. Here,
they  provide for the collection of equations:
\begin{eqnarray}
\hbox{\it FunGraph\/}(z)&=&\exp(\hbox{\it Component\/}(z));\nonumber\\
\hbox{\it Component\/}&=&\log(1-\hbox{\it Tree\/}(z))^{-1};\nonumber\\
\hbox{\it Tree\/}(z)&=&\hbox{\it Node\/}(z)\times\exp(\hbox{\it Tree\/}(z));\nonumber\\
\label{funz}
\hbox{\it Node\/}(z)&=&z.
\end{eqnarray}
Comparison between the formal specification and the
collection of equations reveals
that we have used the translation mechanism
\begin{eqnarray}
{\tt set}&\mapsto&\exp(.)\nonumber\\
{\tt cycle}&\mapsto&\log(1-(.))^{-1}\nonumber\\
\label{transl}
{\tt *}&\mapsto& \times\ \  \hbox{(ordinary product)}
\end{eqnarray}
This mechanism (\ref{transl})
is quite powerful and of course completely general \cite{Foata74}.
We will not attempt here to redo the whole theory that underlies
such derivations. Let us just indicate that
if  ${\cal F}$, ${\cal G}$ and $\cal H$
are three classes of labelled structures
related by ${\cal F}={\cal G}*{\cal H}$,
then the corresponding counting sequences satisfy
$$ f_n=\sum_{k=0}^n {n\choose k} g_k h_{n-k}.
$$
In the equation above,
index $k$ selects the size of the $\cal G$ component
(there are $g_k$ possibilities for this component
and $h_{n-k}$ possibilities for the $\cal H$ component),
and the binomial coefficient represents the
number of ways of distributing labels $[1..n]$ between
the the two components. At the {\GF} level,
this relation on coefficients gives $f(z)=g(z)\cdot h(z)$.
The rule for sets, for instance, follows from
similarly interpreting  the expansion
$$
\exp(g(z))=1+{1\over1!}(g(z))^1+
{1\over2!}(g(z))^2+
{1\over3!}(g(z))^3+
\cdots$$
as meaning that a set over $\cal G$
has either $0$ or $1$ or $2$  or $3$, etc.~elements.


If we abbreviate our generating functions for {\tt FunGraph},
{\tt Component} and {\tt Tree} by $f(z)$, $c(z)$ and
$t(z)$,
we obtain a more readable form
of our basic set of equations (\ref{transl}):
\begin{equation}
\label{transl2}
\left\{
\begin{array}{ccc}
f(z)&=&e^{c(z)}\\
c(z)&=&\ds\log{1\over1-t(z)}\\
t(z)&=&ze^{t(z)}
\end{array}
\right.
\end{equation}
which expresses generating functions of interest in
terms of the implicitly defined tree function $t(z)$.

\smallskip


\begin{smallit}
We briefly digress here to indicate how
exact counting results are hidden behind
such equations. Function $t(z)$ was
considered by Eisenstein and Cayley
(amongst others). The Lagrange inversion theorem furnishes
the number of trees of size $n$ in the form $t_n=n^{n-1}$
(Cayley's theorem);
the same theorem gives the explicit expansion of $f(z)=(1-t(z))^{-1}$,
and one gets as expected $f_n=n^n$.
\end{smallit}
% \renewcommand{\baselinestretch}{1}

\subsection{Asymptotic Analysis}
Probabilistic problems on random mappings are usually more complicated than
the plain enumeration results that we have just discussed.
Fortunately fairly synthetic methods exist
that also permit one to extract directly the asymptotic form
of coefficients of a complicated generating function from its singularities.

These methods take their roots in the work of Darboux
in the last century \cite{Olver74}
and we shall make use here of the approach called 
{\sl singularity analysis\/} which originates in
\cite{Odlyzko82} and \cite{FlOd82},
and which is  exposed by us 
in \cite{FlOd90}.

If we first observe the asymptotic form
of coefficients\footnote{\Small We let as usual $[z^n]\,f(z)$ denote the
coefficient of $z^n$ in the expansion of $f(z)$}
of standard functions
\begin{eqnarray}
\label{three}
{[z^n]} {{1\over 1-3z}}&=&3^n, \\
\label{four}
{[z^n]} {{1\over 1-4z}}&=&4^n, \\
\label{sqrt}
{[z^n]} {{1\over\sqrt{1-4z}}}&\sim&{{4^n\over \sqrt{\pi n}}}, 
\end{eqnarray}
we notice from (\ref{three},\ref{four}) that the location of
a singularity of the function (at ${1\over3}$ or $1\over4$)
determines the dominant exponential behaviour
of its coefficients (as $3^n$ or $4^n$).
Comparison of (\ref{four}) and (\ref{sqrt})
reveals further that a singularity of a square--root type
yields a subexponential factor also of a square root type,
namely  $1/\sqrt{\pi n}$.

\begin{figure}[t]
\vspace*{6cm}
%%%\special{psfile=conf.ps hscale=0.8 vscale=0.8 hoffset=64}

\medskip
\noindent
\begin{smallit}
{\bf Figure 2.}
Two conformal representations by
$$f(z)=(1-z)^{1/2}\ \ \hbox{and}\ \ g(z)=(1-z)^{9/5}$$
of the unit square ${\cal Q}=\{z=x+iy\ |\ -1\le x\le+1,\ -1\le y \le +1\}$.
The two different types of singular behaviours at $z=1$
(left ``angles'' on the diagrams)
are reflected by different growths of coefficients, namely
$$f_n\equiv[z^n]\,f(z)\approx n^{-1-1/2}=n^{-3/2}\ \ \hbox{and}\ \ 
g_n\equiv[z^n]\,g(z)\approx n^{-1-9/5}=n^{-14/5}.$$
\hrule
\end{smallit}
\end{figure}



Our previous observations were based on functions with
Taylor coefficients of a simple explicit form. What is of
interest in our context, is that it is sufficient
to determine local {\sl asymptotic\/} expansions near a singularity,
and such expansions can be ``transferred'' to coefficients
in the same way as before. This is the heart of the method
called singularity analysis in \cite{FlOd90}.
The precise formulation of one of the results
of that paper that we shall need
is as follows:

\begin{theorem}[Singularity Analysis]
\label{singana}
Let $f(z)$ be a function analytic in 
a domain 
$${\cal D}=\{z\ {\bigm|} \ |z|\le s_1,\ |\Arg(z-s)|>{\pi\over2}-\eta\},$$
where $s$, $s_1>s$, and $\eta$ are three positive real numbers. Assume that,
with $\sigma(u)=u^\alpha\log^\beta u$ and $\alpha\not\in\{0,-1,-2,\ldots\}$,
we have
$$f(z)\sim\sigma\bigg({1\over1-z/s}\bigg)
\qquad\hbox{as $z\to s$ in ${\cal D}$.}
$$
Then, the Taylor coefficients of $f(z)$ satisfy
$$[z^n]\,f(z)\sim s^{-n}{\sigma(n)\over n\Gamma(\alpha)}.$$
\end{theorem}

For instance, using Theorem~\ref{singana}, we find:
\begin{eqnarray}
\label{expz}
{[z^n]} {{e^z\over\sqrt{1-4z}}}&\sim&e^{1/4}{{4^n\over \sqrt{\pi n}}},\\
\label{sqrtlog}
{[z^n]} {{\sqrt{{1\over 4z}\log(1-4z)^{-1}}{1\over\sqrt{1-4z}}}}
&\sim&\sqrt{\log n}{{4^n\over \sqrt{\pi n}}}.
\end{eqnarray}
To obtain the first relation (\ref{expz}), observe that the only singularity
of $h(z)=e^z/\sqrt{1-4z}$ is at $z={1\over4}$,
and there $h(z)\sim e^{1/4}/\sqrt{1-4z}$,
the asymptotic form of the coefficients being then given by (\ref{sqrt}).
The second relation (\ref{sqrtlog}) illustrates the variety of singular
behaviours that can be treated by singularity analysis,
and here a $\sqrt{\log}$ on the function transfers into a
$\sqrt{\log}$ on the coefficients.


\paragraph{Random Mappings.}
Let us apply this technology to functions involved in the analysis
of random mappings. We are then required to determine the singularities
of the function $t(z)$ which determines all other functions 
in (\ref{transl2}). We have seen that
\begin{equation}
\label{eqt}
t(z)=z\exp(t(z)),
\end{equation}
which defines $t(z)$ {\sl implicitly}.

\begin{proposition}
The tree function $t(z)$ defined by (\ref{eqt}) is
analytic in the domain $\cal D$
formed by the complex plane slit along $(e^{-1},+\infty)$.
For $z$ tending to $e^{-1}$ in $\cal D$, $t(z)$ admits the singular expansion,
\begin{equation}
\label{singt}
t(z)=1-2^{1/2}\sqrt{1-ez}-{1\over 3}(1-ez)+O\big((1-ez)^{3/2}).
\end{equation}
\end{proposition}

% \renewcommand{\baselinestretch}{0.3}

\begin{smallit}
\noindent
{\bf Proof.}
In fact, implicitly defined functions normally have square root
type singularities. Equation~(\ref{eqt}) is a particular case of the general 
scheme
\begin{equation}
\label{eqf}
F(z,y(z))=0,
\end{equation}
which determines $y(z)$ as a function of $y$.
It is known ---by the {\sl implicit function theorem\/}---
that, if we have a solution
$(z_0,y_0)$ of (\ref{eqf}), then we can
``continue'' it  in a neighbourhood of
$(z_0,y_0)$ provided that
\begin{equation}
\label{impl}
{\partial\over\partial y}
F(z,y)\bigg|_{\scriptstyle z=z_0\atop \scriptstyle y=y_0}\not=0.
\end{equation}
In other words, if $F(z_0,y_0)=0$ and $F_{y}(z_0,y_0)\not=0$,
then a branch of $y(z)$ satisfies $y(z_0)=y_0$,
and that branch is regular at $z_0$.
Observe also that locally, the dependency between $z$ and $y$
is expressed by
\begin{equation}
\label{reg}
(z-z_0)F_z(z_0,y_0)+(y-y_0)F_y(z_0,y_0)\sim 0
\end{equation}
corresponding, as expected, to a locally linear dependence between
$z$ and $y$.

In contrast, if condition (\ref{impl}) ceases to be valid,
then the dependence between $z$ and $y$ assumes the form
\begin{equation}
\label{sing}
(z-z_0)F_z(z_0,y_0)+{1\over2}(y-y_0)^2 
F_{yy}(z_0,y_0)+\hbox{smaller order terms}= 0.
\end{equation}
Solving (\ref{sing}) for $y$, we thus find
between $z$ and $y$ a square--root dependency:
\begin{equation}
\label{sqrtsing}
y\sim y_0\pm \left(2 {F_z(z_0,y_0)\over F_{yy}(z_0,y_0)}\right)^{1/2}
\sqrt{z_0-z}.
\end{equation}

The brief discussion above shows the paradigm of a singularity
analysis of implicitly defined functions
\cite[Chap~V]{Evgrafov66}. The fundamental ideas,
in the realm of asymptotic counting, seem
to go back to P\'olya, and Meir and Moon derived
in this way a number of statistical properties of random trees
(see e.g., \cite{MeMo78}).

In the case of the tree function $t(z)$, we can apply our previous discussion
with $F(z,y)=y-ze^y$. The  singularities
of $t(z)$ are thus amongst numbers $z_0$ which satisfy
the system of two equations in two unknowns,
$$y_0-z_0e^{y_0}=0\ \ \hbox{and}\ \ 1-z_0e^{y_0}=0$$
which provides $y_0=1$ and $z_0=e^{-1}$.
The singularity of $t(z)$ that we need to consider is thus
$z=e^{-1}$;
around this point, the
singular expansion (\ref{singt}) is easily derived
from the model (\ref{sing},\ref{sqrtsing}).~~\eop
\end{smallit}

\smallskip


We can now apply singularity analysis to $t(z)$ and the functions that
depend on it. By Theorem~\ref{singana},
considering functions $t(z),1/(1-t(z))$, etc., 
we find 
\begin{equation}
\label{singf}
\begin{array}{ccccl}
\displaystyle{t_n\over n!}&=&[z^n]\,t(z)&\sim&\ds{e^n\over\sqrt{2\pi n^3}} 
	\\[3mm]
\displaystyle{c_n\over n!}&=&[z^n]\,c(z)&\sim&\ds{e^n\over 2n} 
	\\[3mm]
\displaystyle{f_n\over n!}&=&[z^n]\,f(z)&\sim&\ds{e^n\over\sqrt{2\pi n}}.
\end{array}
\end{equation}
The result concerning $f_n$ is expected, and by a complicated detour, we
have rediscovered Stirling's formula!
In view of Cayley's result that $t_n=n^{n-1}$, the first line
is also equivalent to Stirling's formula.
However, the asymptotic form of $c_n$ 
already represents a non obvious asymptotic result.


\smallskip
We shall see in the next section that, once this basis has been
established, many asymptotic estimates follow very easily.
\section{Additive Parameters}

We now follow the approach of Section~2,
in order to derive expected values of several parameters of interest
in the study of random mappings: First, set up generating
function equations;
second, analyze locally the singularities of these
generating functions.
We consider here {\sl additive parameters\/}
whose values can be determined by simple (essentially additive) rules from
the structural decomposition of random mappings into
functional graphs.
It proves convenient to subdivide additive parameters
into two classes:
\begin{description}
\item {\sl direct parameters\/} (e.g., the number
of connected components) represent the number of
	certain distinguished configurations in mappings;
\item {\sl cumulative parameters\/} (e.g., expected distance to 
	cycle, $\lambda$) represent characteristics of mappings
	as seen from a random point.
\end{description}
{\sl Note.} Estimates given in this section are
essentially classical.
The first results on random mappings appear to
have been found in the 1950's by a variety of methods
including exact enumerations, discrete probability
or generating functions.
The paper by Harris \cite{Harris60}
provides a first extensive approach to problems
discussed in this section.
Further results are given by Stepanov \cite{Stepanov69}
or Arney and Bender
\cite{ArBe82}, and our presentation follows similar
lines. 
% We also refer to Kolchin's book \cite{Kolchin86}
% for a detailed study of random mappings via
% probabilistic methods.

\subsection{Direct Parameters}
Let $\xi[\varphi]$ be a parameter of functional graph
(or equivalently, mapping) $\varphi$, such as
the number of connected components. We introduce
the quantities
\begin{equation}
\xi_n=\sum_{\varphi\in\Fn} \xi[\varphi]
\qquad\hbox{and}\qquad
\Xi(z)=\sum_{n\ge0}\xi_n{z^n\over n!},
\end{equation}
called respectively the total value (over $\Fn$)
and the (exponential) generating function associated
to parameter $\xi$.
Observe that, with ${\cal F}=\cup_n\Fn$, the generating function
$\Xi(z)$ has the alternative form
\begin{equation}
\Xi(z)=\sum_{\varphi\in\cal F}\xi[\varphi]{z^{|\varphi|}\over|\varphi|\,!},
\end{equation}
and the expected value of $\xi$ taken over $\Fn$
is nothing but
\begin{equation}
{\bf E}\{\xi \bigm| \Fn\}={\xi_n\over n^n}=
{n!\over n^n}\,{[z^n]\,\Xi(z)}.
\end{equation}
Thus, once $\Xi(z)$ is known, the expectation analysis
of $\xi$ becomes similar to counting problems
encountered earlier.

\begin{theorem}[Direct Parameters]
The expectations of parameters number of components,
number of cyclic points, number of terminal points,
number of image points, and number of $k$-th iterate
image points\footnote{\Small In the sequel, we use
the term ``point'' as synonym for ``node''.
Parameter {\sl number of components\/} refers to
the number of connected components;
a point is {\sl cyclic\/} if it belongs to a cycle;
$x$ is {\sl terminal\/} if it has no preimage
($\varphi^{(-1)}(x)=\emptyset$),
and it is an {\sl image point\/} otherwise.
A $k$--th iterate image point of $\varphi$
is an image point of the $k$--th iterate
$\varphi^{(k)}$ of $\varphi$.
Clearly, $(iii)$ and $(iv)$ are 
equivalent results, and $(iv)$ is a particular case of $(v)$.}
 in a random mapping of size $n$
have the asymptotic forms, as $n\to\infty$,
\begin{displaymath}
\begin{array}{llc}
(i)&\hbox{\# Components}& {\scriptstyle 1\over2}\log n\\[2mm]
(ii)&\hbox{\# Cyclic nodes}& \sqrt{\pi n/ 2}\\[2mm]
(iii)&\hbox{\# Terminal nodes}& e^{-1}n\\[2mm]
(iv)&\hbox{\# Image points}& (1-e^{-1})\,n\\[2mm]
(v)&\hbox{\# $k$-th iterate image points}& (1-\tau_k)\,n,
\end{array}
\end{displaymath}
where the $\tau_k$ satisfy the recurrence $\tau_0=0$,
$\tau_{k+1}=e^{-1+\tau_k}$.
\end{theorem}

\noindent{\bf Proof.}
{\sl The algebra of generating functions.}
Introduce temporarily bivariate generating functions
which for a given parameter $\xi$ are defined as
\begin{equation}
\label{biv}
\xi(u,z)=
\sum_{\varphi\in\cal F}u^{\xi[\varphi]}\,{z^{|\varphi|}\over|\varphi|\,!}.
% \sum_{n\ge0}\left(\sum_{\varphi\in\Fn} u^{\xi[\varphi]}\right)
% {z^n\over n!}.
\end{equation}
We can view variable $u$ as ``{\sl marking}'' parameter $\xi$.
The generating function associated to (mean value of) $\xi$ is
nothing but 
\begin{equation}
\label{bivar}
\Xi(z)=\left.{\partial\over \partial u}\xi(u,z)\right|_{u=1}.
\end{equation}

We shall illustrate the method of proof
in cases $(i)$, $(ii)$ and $(iii)$.
%  the remaining two cases being simple variants.
For the
number of components and number of cyclic points, we find
respectively as values of $\xi(u,z)$:
\begin{equation}
\label{bcc}
\begin{array}{rcl}
\xi_1(u,z) & = & \exp\big(u \log{1\over 1-t(z)}\big)\\
\xi_2(u,z) & = & \exp\big( \log{1\over 1-u\,t(z)}\big).
\end{array}
\end{equation}
For the number of terminal nodes (points without preimages),
we have instead a two level scheme,
\begin{equation}
\label{bterm}
\left\{
\begin{array}{ccl}
\xi_3(u,z) & = & \exp\big( \log{1\over 1-t(u,z)}\big)\\
t(u,z) & = & ze^{t(u,z)}+(u-1)z,
\end{array}
\right.
\end{equation}
where $t(u,z)$ is the {\GF} for trees with $u$ marking leaves.

Eqs.~(\ref{bcc},\ref{bterm}) derive from a simple
extension of the translation schemes
of Section~2.1, introducing only
an auxiliary variable $u$ which
``marks'' configurations of interest.

Applying principle (\ref{bivar})
to bivariate {\GF}'s (\ref{bcc},\ref{bterm}), we find
for the corresponding {\GF}'s of total values the forms
\begin{equation}
\label{total}
\begin{array}{lll}
\Xi_1(z) & = & \ds{1\over 1-t(z)}\cdot\log\big({1\over 1-t(z)}\big)\\[3mm]
\Xi_2(z) & = & \ds{t(z)\over (1-t(z))^2}\\[3mm]
\Xi_3(z) & = & \ds{z\over (1-t(z))^3}.
\end{array}
\end{equation}

\smallskip
{\sl The Analysis of Generating Functions.}
All {\GF}'s above are expressible in terms of the tree function
$t(z)$. Singularity analysis as $z\to e^{-1}$ is
now immediate from the discussion of Section~2.2.
Consider for instance case~$(i)$ dealing
with the number of components.
>From Eq.~(\ref{singt}), we find {\sl directly\/}
for $\Xi_1(z)$ the singular expansion
\begin{equation}
\Xi_1(z)\sim{1\over2\sqrt{2}}\,{1\over\sqrt{1-ez}}\log{1\over 1-ez}.
\end{equation}
Analytic continuation beyond the circle
of convergence is guaranteed by continuation
properties of $t(z)$ (cf.~Section 2.2). Thus, we
are justified in applying the singularity analysis theorem, and we get
\begin{equation}
[z^n]\,\Xi_1[z]\sim{1\over2\sqrt{2}}{e^n\log n\over \sqrt{\pi n}},
\end{equation}
from which part~$(i)$ of the theorem follows
after normalization by $n!/n^n$.
% The other cases can be treated in exactly the same fashion.

Finally case $(iv)$ is a direct variant of case $(iii)$.
Case $(v)$ follows simply by adapting the argument
used for counting terminal nodes,
with the help of the {\GF}'s of trees of bounded height which
we discuss in Section~4.~~\eop

% \begin{small}
% \noindent
% {\bf Figure 3.} Expected values (in asymptotic form)
% of some of the main additive parameters of a random mapping
% of size $n$. Such a mapping has on the average ${1\over2}\log n$
% components, a total of $\approx\sqrt n$ cyclic nodes
% and $e^{-1}n$ terminal nodes. 
% 
% A random point is
% at an average distance of ${1\over2}\sqrt{\pi n\over2}$
% from its cycle and that cycle itself has an average of
% ${1\over2}\sqrt{\pi n\over2}$ elements.
% 
% On the average, the tree containing a random element contains
% $n\over3$ nodes, the corresponding component size is $2n\over3$.
% Thus, a random mapping has few cyclic elements
% but a fairly klarge component and one or several large trees.
% \end{small}
% \end{figure}


\subsection{Cumulative Parameters}

We now turn to the study of random mappings in $\Fn$ as seen from a
random point (any of the $n$ nodes
in the associated functional graph is taken equally likely).
Let now $\xi[\varphi,\nu]$ be a parameter
of point $\nu$ in mapping $\varphi\in\FF$.
An example of such a parameter
is the distance of point $\nu$ to its cycle in $\varphi$.
We introduce the quantities
\begin{equation}
\xi_n=\sum_{\scriptstyle\nu\in\varphi\atop \scriptstyle\varphi\in{\cal F}_n}
\xi[\varphi,\nu]
\qquad\hbox{and}\qquad
\Xi(z)=\sum_{n\ge0}\xi_n{z^n\over n!},
\end{equation}
called again total value of $\xi$
and generating function associated with $\xi$.
The expected value of $\xi$ is now to be taken
over the set $[1..n]\times\Fn$ (which has cardinality
$n^{n+1}$) and is
\begin{equation}
{\bf E}\{\xi\bigm|\Fn\}={\xi_n\over n^{n+1}}=
{n!\over n^{n+1}}\,{[z^n]\,\Xi(z)}.
\end{equation}

\begin{theorem}[Cumulative Parameter Estimates]
Seen from a random point in a random mapping of $\Fn$,
the expectations of parameters\footnote{\Small Tail length,
cycle length and rho--length are defined at the beginning
of Section~2. The {\sl tree size\/} parameter of node $\nu$ means
the size of the maximal tree (rooted on a cycle) containing $\nu$;
{\sl component size\/}  means the size of the
connected component that contains $\nu$.
The {\sl predecessors size\/} of $\nu$ is the size
of the tree rooted at $\nu$ or equivalently the
number of iterated preimages of $\nu$.}
 tail length, cycle length, rho--length,
tree size, component size, and predecessors size
have the following asymptotic forms:
\begin{displaymath}
\begin{array}{llc}
(i)&\hbox{Tail length}\ (\lambda)& \sqrt{\pi n/8}\\
(ii)&\hbox{Cycle length}\ (\mu)& \sqrt{\pi n/8}\\
(iii)&\hbox{Rho length}\ (\rho=\lambda+\mu)& \sqrt{\pi n/2}\\
(iv)&\hbox{Tree size}& {n/3}\\
(v)&\hbox{Component size}& {2n/3}.\\
(vi)&\hbox{Predecessors size}& {\sqrt{\pi n/8}}.
\end{array}
\end{displaymath}
\end{theorem}

\noindent
{\bf Proof.}
We shall just give the main steps in the proof
in the case of the cycle length parameter~$(ii)$.

% \noindent
{\sl The algebra of generating functions.}
The bivariate {\GF}
$$\log{1\over1-ut(z)}$$
is a {\GF} of connected components, where variable $u$
marks the number of cyclic elements.
If we consider
\begin{equation}
\label{ccyc}
z\left.{\partial^2\over\partial z\partial u}\log{1\over1-ut(z)}
\right|_{u=1},
\end{equation}
then we have a generating
function for
weighted single--component mappings
where a component of size $n$ with $k$ cyclic
points has weight $n\cdot k$.

The expression in (\ref{ccyc}) is equal to $zt^\prime/(1-t)^2$.
We then cumulate these weights over all components
of random mappings;
we can prove generally that this operation corresponds to
multiplication of the single--component
generating function by $1/(1-t)$. Thus, the {\GF} associated to cycle length
is
$$\xi(z)={zt^\prime(z)\over(1-t(z))^3}.$$

{\sl The analysis of generating functions.}
>From our basic expansion (Proposition~1 and (\ref{singt})) of
$t(z)$ around the singularity
$z=e^{-1}$, we find that $t^\prime(z)\sim2^{-1/2}e(1-ez)^{-1/2}$.
Thus, we have
$$\xi(z)\sim {1\over4}(1-ez)^{-2}
\qquad\hbox{as $z\to e^{-1}$},
$$
and the result for cycle length  follows from Theorem~1.

Analogous methods can be employed to cope with the other five cases.~~\eop

% Add Preimages of a point???

\subsection{Probability Distributions}
Though this is not our main
purpose here,
it is also of interest to consider various characteristics of
probability distributions of random mapping parameters.
Variance and higher moments can be determined by the same methods
as have been employed earlier in this section,
though often at a higher computational cost.

Exact probability distributions in random mappings usually have
(asymptotic) limit forms, a number of them,
like in the case of simpler parameters of Section~3.1
being either Gaussian
(with density $e^{-x^2/2}$) or Rayleigh (with density $xe^{-x^2/2}$)
in the limit.
% For instance, it is known that,
% after normalisation by mean and standard deviation, 
% all parameters of Theorem~1 have asymptotically
% normal distributions. 
Let us examine for instance
the parameter number
of components from Section~3.1;
asymptotic normality was first derived by
Stepanov \cite{Stepanov69}. First, the variance estimate
is easily derived by differentiation of the function $\xi_1(u,z)$
given in (\ref{bcc}) and we find that
the standard deviation is $\sim{1\over2}\log n$. In \cite{FlSo89a},
the authors derive Stepanov's result as
a particular case of a general law for
coefficients of bivariate generating
functions of the form $e^{uf(z)}$:
The idea, which is applicable to several other parameters,
is to extract the coefficient of $z^n$ in the bivariate
{\GF} using singularity analysis, and taking $u$ complex in
the vicinity of $1$, we estimate in this way
the characteristic function of the discrete
distribution of interest.

The methods we have already introduced can also
be used to derive refined counting results like
the number of cycles of size $r$ (for a fixed integer $r$)
in a random mapping.

\begin{theorem}[r--configurations]
For any fixed integer $r$, the parameters\footnote{\Small An
$r$--{\sl node\/} is a node of indegree $r$;
a {\sl cycle tree\/} is a tree rooted on a cycle;
a {\sl predecessor tree\/} is an arbitrary tree in the functional graph.}
number of $r$-nodes, 
number of predecessor trees of size $r$,
number of cycle trees of size $r$ and  number of components of size $r$,
have the following asymptotic
mean values:
\begin{displaymath}
\begin{array}{llc}
(i)&\hbox{$r$-nodes:} & n e^{-1}/ r!\\
(ii)&\hbox{$r$-predecessor trees:} &n t_r e^{-r}/r!\\
(iii)&\hbox{$r$-cycle trees:}& (\sqrt{\pi n/2})\cdot t_re^{-r}/r!\\
(iv)&\hbox{$r$-cycles:}& 1/r\\
(v)&\hbox{$r$-components:}& c_re^{-r}/r!,\\
\end{array}
\end{displaymath}
where $t_r$ is the number of trees having $r$ nodes, $t_r=r^{r-1}$,
and $c_r=r![z^r]c(z)$ is the number of connected mappings
of size $r$.
\end{theorem}

\noindent
{\bf Proof.}
Generating functions result from the marking techniques of
Section~3.1. For instance, the {\GF} of 
functional graphs with $u$ marking $r$--cycles (case~$(iv)$) is
$$f(u,z)=\exp\bigg(\log{1\over1-t(z)}+(u-1){t(z)^r\over r}\bigg).$$
Computation of the coefficients of
$$f_u(1,z)={1\over (1-t(z))^2}t_r{z^r\over r}
$$
by singularity analysis yields the result.~~\eop

\smallskip
We thus see that node degrees in a random mapping
are approximately Poisson distributed with parameter $1$,
a result consistent with our earlier estimate of the number
of terminal nodes. The expected number of $r$--cycles
decreases as $1/r$, a property similar to
that of random permutations:
For instance, a random mapping has on the average
1 fixed point. 
(Notice however that the implied error terms are
not uniform; a random permutation has an average of $\log n$ cycles,
while a random mapping has only ${1\over2}\log n$.)
Contour integration techniques will usually
provide useful estimates when one needs to let $r$ vary
as a function of $n$.


\section{Extremal Statistics}

The purpose of this section is to examine
extremal statistics on random mappings. We consider
questions which,
in the perspective of random number generators
are like: ``{\sl Are there good seed values that lead to long
periods?\/}''.
In particular for $\xi$ one of the parameters
discussed in Section~3.2 ---$\lambda$, $\mu$,
$\rho=\lambda+\mu$, tree size or component size---
we consider $\xi^{\max}$ defined by
\begin{equation}
\xi^{\max}[\varphi]=\max_{\nu\in\varphi} \xi[\varphi,\nu].
\end{equation}
The generating function approach works fairly well for these
parameters. 
As in Section~3.1,
we introduce the generating
function associated with an extremal parameter
$\xi^{\max}$,
\begin{equation}
\label{Ximax}
\Xi(z)=\sum_{n\ge0}\xi_n {z^n\over n!},
\qquad\hbox{where\ \ }
\xi_n=\sum_{\varphi\in\Fn}\xi^{\max}[\varphi].
\end{equation}
Thus ${n! \, n^{-n}}\,[z^n]\,\Xi(z)$
represents  the expectation ${\bf E}\{\xi^{\max}{\bigm|}\Fn\}$.

The approach to the determination
of $\Xi$ goes through a class of generating functions
$f^{[k]}(z)$
where $f^{[k]}(z)$ is a ``subseries'' of the generating function
of all functional graphs defined by
\begin{equation}
\label{fk}
f^{[k]}(z)=\sum_{\varphi\in{\cal F}_n^{[k]}}
{z^{|\varphi|}\over|\varphi|\,!},
\qquad\hbox{with\ \ }
{\cal F}_n^{[k]}=\{\varphi\in\Fn\ \big|\ \xi^{\max}[\varphi]\le k\}.
\end{equation}
By a classical formula\footnote{\Small The argument
is a generating function version
of the following well known formula for the mean value of a 
discrete random variable $X$:
$${\bf E}\{X\}=\sum_{k\ge1} k\,{\rm Pr}\{X=k\}
=\sum_{k\ge1} {\rm Pr}\{X\ge k\}=\sum_{k\ge0}[1-{\rm Pr}\{X\le k\}].$$},
$\Xi$ is expressed in terms of the $f^{[k]}$ by
\begin{equation}
\label{Xifk}
\Xi(z)=\sum_{k\ge0}
\big[f(z)-f^{[k]}(z)\big].
\end{equation}

However, the analytic treatment of the $f^{[k]}$ and of the associated
sum in (\ref{Xifk})
becomes appreciably more difficult than in our earlier examples.
Corresponding generating
functions lead to two sorts of analytic problems:
\begin{description}
\item {\sl Truncated series.}
We need to find uniform estimates for truncated Taylor series
near their dominant singularity [$\mu$, tree size,
component size].
\item {\sl Singular iteration.}
We need to estimate uniformly the convergence
of iteration schemes near a singularity of the fixed point
[$\lambda$ and $\rho$].
\end{description}
We distinguish two categories of parameters,
longest paths ($\lambda,\mu,\rho$)
and largest components (trees and connected components).

\subsection{Longest Paths}


The case of the longest cycle in a random functional 
graph will serve to introduce the subject. The expectation was
first determined by Purdom and Williams \cite{PuWi68}.
These authors use a result of Shepp and Lloyd
\cite{ShLl66} which is based on deep Tauberian
methods and which describes the distribution
of the longest cycle in a random permutation.
Our derivation proceeds instead directly
from generating functions using singularity analysis.

\begin{theorem}
The expectation of the maximum cycle length
in a random mapping of $\Fn$ satisfies
$${\bf E}\{\mu^{\max}{\bigm|}\Fn\}
\sim c_1 \sqrt{n},$$
where $c_1\approx 0.78248$ is given by
$$c_1=\sqrt{\pi\over 2}\int_0^\infty
\big[1-e^{-E_1(v)}\big]\,dv,
$$
and $E_1(v)$ denotes the exponential integral
$$E_1(v)=\int_v^\infty e^{-u}{du\over u}.$$
\end{theorem}

\noindent
{\bf Proof.} (Sketch)
Generating functions in this problem involve the
{\sl truncated logarithm},
\begin{equation}
\ell_k(u)=\sum_{j=1}^k {u^j\over j}.
\end{equation}
Let $f^{[k]}(z)$ denote the {\GF}
of functional graphs, all of whose cycles
have length at most $k$.
Then, we have
\begin{equation}
\label{muk}
f^{[k]}(z)=\exp\big(\ell_k( t(z)) \big),
\end{equation}
with $t(z)$ again the tree function.

Introduce the generating function $\Xi(z)$ associated to parameter
$\mu^{\max}$
in the sense of (\ref{Ximax}).
This {\GF} is readily
determined from
(\ref{muk}):
\begin{equation}
\label{muaverage}
\Xi(z)=\sum_{k\ge0}
\big[{1\over 1-t(z)}-f^{[k]}(z)\big]
={1\over 1-t(z)}
\sum_{k\ge1}
\big[1-e^{-r_k(t(z))}\big],
\end{equation}
where $r_k(u)$ is the complement of the truncated logarithm,
$$r_k(u)=\log{1\over1-u}-\ell_{k-1}(u)
=\sum_{j\ge k} {u^j\over j}.
$$

The problem rests now on the determination of
the asymptotic  behaviour of $\Xi(z)$ as
$z\to e^{-1}$.
Set $t(z)=e^{-x}$.
By conformal mapping properties of $t(z)$ related to its square--root
singularity,
when $z$ lies in a suitable indented domain
that includes the disk $|z|<e^{-1}$
(a $\cal D$ domain in the sense of Theorem~1),
we have $|t(z)|<1$ so that
$x$ lies in the half plane $\Re(x)>0$.

The main steps for the estimation of
$\Xi(z)$ are:
\begin{eqnarray}
\label{mua}
\Xi(z)&=&{1\over1-t(z)}\sum_{k\ge1}\big[1-\exp(-\sum_{j\ge k}{e^{-jx}\over j})\big]\\
\label{mub}
  &\sim&{1\over 1-t(z)}\sum_{k\ge1}\big[1-\exp(-\int_{kx}^\infty
e^{-v}\,{dv\over v})\big]\\
\label{muc}
  &\sim&{1\over(1-t(z))^2}
\int_0^\infty \big[1-\exp(-\int_u^\infty e^{-v}\,{dv\over v})\big]\,du.
\end{eqnarray}
Once Eq.~(\ref{muc}) is established,
the theorem follows immediately by singularity analysis.
Now the transition from (\ref{mua}) to (\ref{mub})
results from approximating a sum by an integral,
i.e.~by Euler--Maclaurin summation. (It is
important that we should have
convergence of the integral,
but this is granted since $\Re(x)>0$,
which also allows us to change the upper limit of
integration from $x\infty$ to $+\infty$
using Cauchy's theorem.)
The transition from (\ref{mub}) to (\ref{muc})
follows similarly by Euler summation,
noting that the step $x$ in the discrete sum
(\ref{mub}) is $\sim1-t(z)$ as $z\to e^{-1}$.
The only details that are omitted from this proof
are the derivation of uniform error bounds.~~\eop

\smallskip

In passing, observe that the same method permits one to
estimate the expected length of the longest
cycle in a random permutation,
thereby avoiding the delicate Tauberian arguments
of \cite{ShLl66}.
Related distribution results are discussed by Stepanov
in \cite{Stepanov69}.

\smallskip

The next theorem concerns the expected value of
$\lambda^{\max}$. 
Results concerning distribution estimates were first derived by
Sachkov \cite{Sachkov73}
and Proskurin \cite{Proskurin73}
using multivariate probabilistic methods.
The derivation that follows brings a ``singular iteration problem'',
and the corresponding methods are also useful for $\rho^{\max}$ estimates.



\begin{theorem}
The expectation of the maximum tail length ($\lambda^{\max}$)
in a random mapping of $\Fn$ satisfies
$${\bf E}\{\lambda^{\max}{\bigm|}\Fn\}
\sim c_2 \sqrt{n},$$
where $c_2\approx 1.73746$ is given by
$$c_2=\sqrt{2\pi}\log 2.$$
\end{theorem}

\noindent
{\bf Proof.} (Sketch)
Let $t^{[h]}(z)$ denote the {\GF}
of trees with height at most $h$.
(Height is measured by the number of edges along
a longest branch, so that a one node
tree has height $0$.)
These generating functions are given by the recurrence
\begin{equation}
\label{th}
t^{[0]}(z)=z,\qquad
t^{[h+1]}(z)=z\exp(t^{[h]}(z)).
\end{equation}
We note that, as $h\to\infty$,
we have $t^{[h]}(z)\to t(z)$,
at least in the sense of 
convergence in the ring of formal power series.
The {\GF} for mappings with $\lambda^{\max}\le h$
follows again from the techniques
of Section~2, and it is
\begin{equation}
f^{[h]}(z)=\exp(\log{1\over1-t^{[h]}(z)})=
{1\over 1-t^{[h]}(z)}.
\end{equation}
The {\GF} associated to $\xi^{\max}=\lambda^{\max}$
is then found by Eq.~(\ref{Xifk}) to be
\begin{equation}
\label{lambdaverage}
\Xi(z)=\sum_{h\ge0}
\big[{1\over1-t(z)}-{1\over1-t^{[h]}(z)}\big].
\end{equation}

The analytic problem now lies with determining
the nature of the approximation
of $t(z)$ by the $t^{[h]}(z)$ when
$z$ is in the vicinity of $e^{-1}$.
This is a {\sl singular iteration\/}
problem. For instance, for $z$ real, $0<z<e^{-1}$,
the convergence is geometric. On the
opposite, for $z>e^{-1}$,
we have a case of strong hyperexponential divergence.
At exactly $z=e^{-1}$,
convergence is extremely slow
being of order $1/h$.
In other terms, we approximate
a function, $t(z)$ with an algebraic singularity
(branch point), by a collection
of entire functions $t^{[h]}(z)$,
and we need to find uniform estimates in $z$ and $h$
in a neighbourhood of the singularity
of the limit\footnote{\Small It turns out that
the $t^{[h]}(z)$ converge to $t(z)$
for all $z$ in $\{z \bigm| z=\zeta e^{-\zeta},\, |\zeta|\le 1\}$.
This follows from recent results in iteration of entire
functions due to Devaney \cite{Devaney84,Devaney89};
however, these results do not seem to provide
the necessary quantitative information we need.}.

Approximations similar to those needed for the proof
of Theorem~6  are provided by us in
\cite{FlOd82}, where we analyze the
expected height of random trees of various sorts
in this manner
(see also \cite{ReSz67} for closely related
results).
Imitating the method
of proof of \cite{FlOd82},
we define
\begin{displaymath}
\epsilon=\epsilon(z)=2^{1/2}\sqrt{1-ez}
\qquad\hbox{and}\qquad
e_h(z)=t(z)-t^{[h]}(z).
\end{displaymath}
% we find that in a complex neighbourhood of $z=e^{-1}$,
% the differences $e_h$ are very well approximated by
% \begin{equation}
% \label{ehapp}
% e_h(z)\approx2\epsilon
% {(1-\epsilon)^h\over1-(1-\epsilon)^h}.
% \end{equation}
% Recall that we also have
% $$t(z)=1-\epsilon-{1\over6}\epsilon^2+O(|\epsilon|^3)
% \qquad\hbox{as $z\to e^{-1}$.}$$
We also introduce the ``indented'' domain
\begin{equation}
\label{O44}
D=\{z \bigm| \, |z|\le e^{-1},\  |\Arg(e^{-1}-z)|\le{\pi/2}+\delta\}
\end{equation}
for some $\delta>0$.
The first step, whose rather involved proof we omit,
is to show that in the region
\begin{displaymath}
\{z \bigm| \, |z|\le e^{-1}+\delta,\  z\not\in D\}
\end{displaymath}
we have $e_h(z)$ small and $t^{[h]}(z)$
bounded away from 1, so that $\Xi(z)$
is analytic there.
Therefore, in order to apply Theorem~1,
we only need to study $\Xi(z)$ for $z\in D$.

The main step in the proof of the theorem is to establish that for $z\in D$,
the $e_h(z)$ are approximated by an explicit function of $h$ and
$\epsilon$,
\begin{equation}
\label{O45}
e_h(z)\approx 2\epsilon 
{(1-\epsilon)^h\over 1-(1-\epsilon)^h}\,.
\end{equation}
This approximation shows both the slow convergence
of $t^{[h]}(e^{-1})$ to
$t(e^{-1})$
(in fact, it shows that $e_h(e^{-1})\sim 2/h$),
and the geometric convergence for $\epsilon\not=0$.
The proof of a precise form of
(\ref{O45}) proceeds along lines similar to those of \cite{FlOd82},
although there are some additional technical complications.

We define
\begin{equation}
\label{O46}
w(z)= %{1\over z}\bigg({z\over1-e^{-z}}-1-z/2 \bigg),
{1\over1-e^{-z}}-{1\over z}-{1\over 2},
\end{equation}
so that $w(z)$ is analytic in $|z|<2\pi$.
The basic recurrence for the $t^{[h]}(z)$
shows that
\begin{equation}
\label{O47}
e_{h+1}(z)=t(z)(1-e^{-e_h(z)}),
\end{equation}
and therefore, by normalizing and the trick of ``taking inverses''\footnote{\Small This technique amounts to comparing a non linear slowly converging
iteration to a homographic recurrence, $u_{n+1}=(au_n+b)/(cu_n+d)$.
A good illustration is de Bruijn's treatment of
the iterates of the function $\sin(x)$ in \cite[Ch.~8]{deBruijn81}.},
\begin{equation}
\label{O48}
{t(z)^j\over e_j(z)}
={t(z)^{j-1}\over e_{j-1}(z)}
+{1\over2}t(z)^{j-1}+
t(z)^{j-1}w(e_{j-1}(z)),
\end{equation}
from which it follows that
\begin{equation}
\label{O49}
{t(z)^h\over e_h(z)}=
{1\over 2}{1-t(z)^h\over 1-t(z)}
+{1\over t(z)-z}
+\sum_{j=0}^{h-1}t(z)^jw(e_j(z)).
\end{equation}

Equation~(\ref{O49}) is the basic tool used to estimate $e_h(z)$,
with the first term in (\ref{O49}) corresponding to
approximation (\ref{O45}).
Another argument shows that if the $\delta$ in the
definition (\ref{O44}) of $D$ is taken to be small enough,
then $|e_h(z)|<5$, say for all $h\ge0$ and
all $z\in D$.
This means that the expansion (\ref{O49}) holds for all
$z\in D$, without singularities arising from
the $w$ function.
Sharp bounds for the error in the approximation (\ref{O45})
for $e_h(z)$ are obtained by iterated  use of 
(\ref{O49}):
First the crude bound for $e_j(z)$, when inserted into (\ref{O49}),
gives a more refined estimate which is then used to obtain an improved
 estimate for the sum on the right hand side of  (\ref{O49}),
yielding the final approximation result.

As an illustration, we develop the case where $z=e^{-1}$. 
The reduced form of (\ref{O49}), with $t(e^{-1})=1$ and 
$e_h\equiv e_h(e^{-1})$ reads
\begin{equation}\label{O49bis}
{1\over e_h}={h\over2}+{1\over1-e^{-1}}+
\sum_{j=0}^{h-1}w(e_j).
\end{equation}
We start ``bootstrapping'' with the information that
$0< e_h <1$. Eq.~(\ref{O49bis}) provides
$$
{h\over2}+O(1) \le {1\over e_h} \le {h\over 2}+ {h\over 10} +O(1),
$$
which guarantees that $1/e_h$ is upper and lower bounded by terms that are 
of order $h$. Thus $e_h=\Theta({1\over h})$. Reinserting this information
inside (\ref{O49bis}), and using the fact that $w(x)=x/12+O(x^3)$
for small $x$, we get the improved estimate
$$
{h\over2}+O(1) \le {1\over e_h} \le {h\over 2}+ O(\log h),
$$
so that $e_h\sim 2/h$. Continuing in this fashion,
we obtain
$${1\over e_h}\equiv{1\over e_h(e^{-1})}=
{h\over 2}+{1\over12}\log h +O(1),$$
and an expansion to an arbitrary order can be generated
in this way.

Returning now to $\Xi(z)$, we have
\begin{equation}
\begin{array}{ccl}
\label{exactlmax}
\Xi(z)&=&\ds{1\over1-t(z)}\sum_{h\ge0}{e_h(z)\over1-t^{[h]} (z) }\\
  &=&\ds{1\over(1-t(z))^2}\sum_{h\ge0}
{e_h(z)\over1+{e_h(z)\over 1-t(z)}}.
\end{array}
\end{equation}
Setting, like in the preceding
theorem, $t(z)=e^{-x}\sim 1-\epsilon$,
the computation develops as follows:
\begin{eqnarray}
\label{app1}
\Xi(z)&\sim&\ds{2\over\epsilon}
	\sum_{h\ge0}{(1-\epsilon)^h\over1+(1-\epsilon)^h}\\
\label{app2}
  &\sim&\ds{2\over\epsilon}\sum_{h\ge0}{e^{-hx}\over1-e^{-hx}}\\
\label{app3}
  &\sim&\ds{2\over\epsilon^2}\int_0^\infty{e^{-y}\over1-e^{-y}}\,dy\\
\label{app4}
  &\sim&\ds{2\log2\over\epsilon^2}.
\end{eqnarray}
A crucial step there consists of justifying the use of
the approximation (\ref{O45})
inside the exact form (\ref{exactlmax})
resulting in
Eq.~({\ref{app1}) or
its equivalent form (\ref{app2}). % is the one that needs most work.
Once ({\ref{app1}) and (\ref{app2}) are established, (\ref{app3})
follows by Euler--Maclaurin summation.
The final result (\ref{app4}), when subjected to singularity analysis
yields the statement of the theorem.~~\eop

\smallskip

The last result in this subsection
concerns the parameter $\rho^{\max}$ also called sometimes,
in accordance with graph theoretic terminology, the
{\sl diameter\/}. It
provides an answer to an open problem of Knuth (\cite{Knuth81},
Ex.~3.1.14, p.~519).
As could be expected from the nature of the parameter $\rho^{\max}$,
the proof combines the tools developed
for Theorems~5 ($\mu^{\max}$) and 6 ($\lambda^{\max}$), and in particular
it strongly relies on the estimates of $t^{[h]}(z)$ and $e_h(z)$.

\begin{theorem}
The expectation of the maximum rho length ($\rho^{\max}$)
in a random mapping of $\Fn$ satisfies
$${\bf E}\{\rho^{\max}{\bigm|}\Fn\}
\sim c_3 \sqrt{n},$$
where $c_3\approx 2.4149$ is given by
$$c_3=\sqrt{\pi\over 2}\int_0^\infty
\big[1-e^{-E_1(v)-I(v)}\big]\,dv,
$$
with $E_1(v)$ denoting the exponential integral
and
$$I(v)=\int_0^v e^{-u}\big[1-\exp({-2u\over e^{v-u}-1})\big]
\,{du\over u}.$$
\end{theorem}
Results from the previous sections indicate that,
in a random mapping, most of the points tend
to be grouped together in a single giant component.
This component might therefore be expected to have very tall trees and 
a large cycle. Thus, the inequality
$$c_3=2.4149...<c_1+c_2=2.5199...$$
is rather interesting as it says that,
with non zero asymptotic probability,
the tallest tree in a functional graph is not
rooted on the longest cycle.

\noindent
{\bf Proof.} (Sketch)
Due to the intrinsically technical proof,
we shall content ourselves here with a brief
description of the major points of the analysis.

The generating function of functional graphs with rho--length
at most $k$ is, in accordance with (\ref{Ximax}),
\begin{equation}
\label{Xirhomax}
f^{[k]}(z)=e^{v_k(z)}
\qquad\hbox{where\ \ }
v_k(z)=t^{[k-1]}(z)+{1\over2}(t^{[k-2]}(z))^2+
\cdots+{1\over k}(t^{[0]}(z))^k,
\end{equation}
with $v_0(z)=0$.
This form is easily justified, since in order
to build a connected component
with rho--length $\le k$, we
either graft a tree of height $\le k-1$ on a 
1 node cycle, or two trees of height at most $k-2$ on
a 2 node cycle etc.
Thus the {\GF} of $\rho^{\max}$ is
$$\Xi(z)=\sum_{k\ge0}
\big[{1\over 1-t(z)}-e^{v_k(z)}\big].
$$
Let now $\Xi_0(z)$ be the {\GF} associated with the
longest cycle parameter defined in (\ref{muaverage}). 
Several routes are conceivable.
A convenient one starts by considering the difference
$$
\Delta(z)=\Xi(z)-\Xi_0(z)=
\sum_{k\ge0}\big[e^{\ell_k(t(z))}-e^{v_k(z)}\big]
$$
which is associated to $\rho^{\max}-\mu^{\max}$.
Factoring out the quantity $e^{\ell_k(t(z))}$ in the general term, we
find:
\begin{equation}
\label{F0}
\Delta(z)={1\over1-t(z)}
\sum_{k\ge0}e^{-\sum_{j>k}t(z)^j/j}\big[1-e^{-w_k(z)}\big],
\end{equation}
where the $w$'s are given by
\begin{eqnarray}
\label{F1}
w_{k}(z)&=&\ds \sum_{l=1}^{k}{1\over l}\big[t(z)^l-(t^{[k-l]}(z))^l\big]
\nonumber\\
	&=&\ds \sum_{l=1}^{k}{t(z)^l\over l}
		\bigg[1-\big({t^{[k-l]}(z)\over t(z)}\big)^l\bigg]
\nonumber\\
	&=&\ds \sum_{l=1}^{k}{t(z)^l\over l}
		\bigg[1-\exp\big(-l(t(z)-t^{[k-l-1]}(z))\big)\bigg]
\nonumber\\
	&=&\ds \sum_{l=1}^{k}{t(z)^l\over l}
		\bigg[1-\exp\big(-l e_{k-l-1}(z)\big)\bigg].
\end{eqnarray}
Taken together, the last form in (\ref{F1})  and
Eq.~(\ref{F0}) summarize the algebraic forms
of generating functions needed for asymptotic analysis.


>From this exact form, the analysis proceeds, setting again $t(z)=e^{-x}$,
so that $x\sim2^{1/2}\sqrt{1-ez}$.
We use the $\approx$ symbol to emphasize the fact that error terms
are not made explicit (and may be dominant in some 
eventually unessential regions).

First it can be proved that the dominant terms in the sum (\ref{F0})
of $\Delta(z)$ are for those values of $k$ such that $kx=\Theta(1)$.

A crucial step is to approximate $w_k(z)$.
We have from (\ref{F1})
\begin{displaymath}
\label{F2}
w_k(z)\approx
x \sum_{l=1}^k {e^{-lx}\over lx}
\bigg[1-\exp\big(-l e_{k-l-1}(z)\big)\big],
\end{displaymath}
where, by the general approximation of (\ref{O45}),
\begin{equation}
\label{F3}
l e_{k-l-1}(z)\approx
2lx {e^{-(k-l)x}\over1-e^{-(k-l)x}}.
\end{equation}

We now appeal to a continuous model for these sums based
on Euler--Maclaurin summation. Setting
$kx=v$, $lx=u$, we derive for
$w_k(z)$ the approximation
\begin{equation}
\label{F4}
\begin{array}{lll}
w_k(z)&\approx&\ds \int_0^v e^{-u}
\bigg[1-\exp\big(-2u {e^{-(v-u)}\over 1-e^{-(v-u)}}\big)\bigg]
\,{du\over u}\\
 & \approx & I(kx).
\end{array}
\end{equation}
Injecting this form inside the main formula (\ref{F0}) for $\Delta(z)$
leads us to
\begin{displaymath}
\Delta(z)\approx{1\over 1-t(z)}\sum_{k\ge0}e^{-E_1(kx)}
\big[1-e^{-I(kx)}\big],
\end{displaymath}
which yields to a final assault of Euler Maclaurin:
\begin{equation}
\label{F5}
\Delta(z)\sim {1\over x^2}
\int_0^\infty e^{-E_1(v)}\big[1-e^{-I(v)}\big]\,dv.
\end{equation}


There are of course considerable technical difficulties in
actually organizing the proper approximations with their error terms.
The form (\ref{F5}) combined with the information gathered in (\ref{muc})
% also \ref{mua} and \ref{mub}
regarding the {\GF} of $\mu^{\max}$ shows that
\begin{equation}
\label{F6}
\Xi(z)\sim
{1\over x^2}
\int_0^\infty \big[1-e^{-E_1(v)-I(v)}\big]\,dv.
\end{equation}
At this stage,
the result falls as a ripe fruit by singularity analysis.~~\eop



\subsection{Largest Configurations}

We consider here the analysis of the largest
tree and of the largest component in a random mapping.
The analysis given here will be only partial
since we shall appeal to 
a {\sl smoothness hypothesis\/}
(which is intuitively clear,
but harder to establish rigorously).

Generating function equations here involve series truncation
operators that we have already used implicitly
when dealing with longest cycle.
Let $a(z)=\sum_{n}a_n z^n$ be a power series.
We introduce
two operators called
{\sl truncation\/} ${\bf T}_m$ and {\sl remainder\/}
${\bf R}_m$ that are defined by
\begin{equation}
{\bf T}_m[a(z)]=\sum_{n\le m}a_n z^n,
\qquad
{\bf R}_m[a(z)]=\sum_{n> m}a_n z^n.
\end{equation}

\begin{figure}[thb]
\vspace*{10.3cm}
%%%\special{psfile=trunc32.ps hscale=0.6 vscale=0.6 hoffset=72}

\medskip
\noindent
\begin{smallit}
{\bf Figure 3.}
The star diagram of zeros of the polynomial $U_{32}(z)$, where
$$
U_m(z)=1-\sum_{n=1}^m n^{n-1} {z^n\over n\,!}.
$$
This polynomial is a ``truncation'' of $1-t(z)$,
with $t(z)$ being the tree function, and its
zeros appear in the analysis of largest tree size.
In accordance with Jentzsch's theorem,
the zeros tend to accumulate around the circle $|z|=e^{-1}$.
\end{smallit}

\smallskip
\noindent\hrule
\end{figure}


Let $\xi^{max}$ be one of the parameters of
random mappings,
largest tree size or largest component size.
We shall say that the parameter is {\sl smooth\/}
if the following condition is satisfied:
\begin{equation}
\label{smooth}
\hbox{\it There exists $\delta$ such that\ \ }
\delta=\lim_{n\to\infty}{1\over n}{\bf E}\{\xi^{\max}{\bigm|}\Fn\}.
\end{equation}
If $\delta$ exits, then by standard
Abelian theorems \cite[Chap.~7]{Titchmarsh39},
$\Xi(z)$ satisfies
$\Xi(z)\sim\delta_1(1-ez)^{-3/2}$
when $z$ tends to $e^{-1}$
{\sl along the real axis\/} $z<e^{-1}$,
for some $\delta_1$ directly related to $\delta$
(actually $\delta_1=2\sqrt{2}\delta$).
Thus if we find that, limited to the real line
inside its circle of convergence,
$\Xi(z)$ has the proper behaviour,
then  we are able to deduce the value of $\delta$:
$$\delta={1\over2\sqrt2}\lim_{z\to e^{-1}}
\Xi(z)(1-ez)^{3/2}.$$

The smoothness assumption thus
dispenses  with finding local expansions
in a {\sl complex\/} neighbourhood of $e^{-1}$.
The reason why we introduce it here
is to bypass some intrinsic difficulty in the singular behaviour
of truncated Taylor series. Indeed, Jentzsch's
theorem \cite[p.~238]{Titchmarsh39}
states that,
{\sl for every power series, every point of the circle of convergence
is a limit--point of zeros of partial sums}.
For largest components, the
generating functions $f^{[k]}$ of~(\ref{fk})
involve truncated Taylor series
and thus exhibit a very irregular 
behaviour on the circle $|z|=e^{-1}$.
The validity of our singular expansions
is then restricted to the interior of the disk
of convergence $|z|<e^{-1}$.
It is probable that a more refined analysis
(e.g.~using different integration contours for
different terms in the {\GF} $\Xi(z)$)
would enable us to dispense with the smoothness
condition, but this is presently not obvious.
 
\begin{theorem}
Assuming the smoothness condition,
the expected value of the size of the largest tree\footnote{\Small Interesting
distribution properties of the size of the largest tree are discussed in
\cite[p.~164]{Kolchin86} and \cite{Pavlov77}.}
and the
size of the largest connected component in a random mapping
of $\Fn$
are asymptotically
\begin{equation}
\begin{array}{llcc}
(i)&\hbox{Largest tree:}&&d_1n\\
(ii)&\hbox{Largest component:}&&d_2n,
\end{array}
\end{equation}
where $d_1\approx0.48$ and $d_2\approx0.75782$
are given by
\begin{eqnarray*}
d_1&=&\ds 2\int_0^\infty
\bigg[1-{1\over1+{1\over2\sqrt\pi}\int_x^\infty e^{-v}v^{-3/2}\,dv}\bigg]\,
dx\\
d_2&=&\ds 2\int_0^\infty\bigg[1-\exp\big({1\over2}
\int_x^\infty e^{-v}v^{-1}\,dv\big)\bigg]\,dx.
\end{eqnarray*}
\end{theorem}

\noindent
{\bf Proof.} (Sketch)
The generating functions associated to the two
cases under discussion are respectively
\begin{eqnarray*}
\Xi_1(z)&=&\ds
	\sum_{m\ge0}\bigg[{1\over1-t(z)}-{1\over1-\Tm[t(z)]}\bigg]\\
\Xi_2(z)&=&\ds
	\sum_{m\ge0}\bigg[{1\over1-t(z)}-e^{-\Tm[c(z)]}\bigg].
\end{eqnarray*}
To approximate them, we  set
$z=e^{-1-y}$.

Consider the case of largest tree ($\Xi_1$).
Then, the {\GF} can be rewritten as
\begin{equation}
\label{ltree}
\Xi_1(z)={1\over1-t(z)}
\sum_{m\ge0}\bigg[1-{1\over1+\Rm[t(z)]/(1-t(z))}\bigg].
\end{equation}
When $m$ is large enough, and $y$ small,
using $1-t(z)\sim 2^{1/2}y^{1/2}$,
we get by Stirling's approximation
and Euler Maclaurin summation:
\begin{equation}
\label{ltreeapp}
\begin{array}{ccc}
\ds {\Rm[t(z)]\over 1-t(z)}&\approx&\ds 2^{-1/2}y^{-1/2} \sum_{n>m}{e^{-ny}\over\sqrt{2\pi n^3}}\\
	&\approx& \ds {1\over2\sqrt{\pi}}
		\int_{my}^\infty e^{-v} v^{-3/2}\,dv.
\end{array}
\end{equation}
The final step consists in transporting approximation
(\ref{ltreeapp}) inside Eq.~(\ref{ltree}),
and using a further step of Euler--Maclaurin
summation. The derivation for maximum
component size is similar.~~\eop



\section{Extensions}

The methodology discussed here
is applicable to the analysis of a large class of combinatorial structures,
roughly speaking those that can be specified
using the combinatorial constructions of Section~2.
It is also systematic enough that some of these analyses
can be automated using computer algebra systems.



\subsection{Alternative Models}

Harris \cite{Harris60} already discusses mappings without fixed points.
In the context of Section~2.1,
this means that the specification
of functional graphs ({\tt FunGraph})
has to be altered by prohibiting
cycles of length equal to $1$ inside components:
\begin{verbatim}
  type    FunGraph   = set(Component);
          Component  = cycle(Tree,card>1);
          Tree       = Node*set(Tree);
          Node       = Latom(1);
\end{verbatim}
It is a simple exercise to derive the modified
form of Eqns.~(\ref{funz}) in this case:
\begin{eqnarray}
\hbox{\it FunGraph\/}(z)&=&\exp(\hbox{\it Component\/}(z));\nonumber\\
\hbox{\it Component\/}&=&\log(1-\hbox{\it Tree\/}(z))^{-1}-Tree(z);\nonumber\\
\hbox{\it Tree\/}(z)&=&\hbox{\it Node\/}(z)\cdot\exp(\hbox{\it Tree\/}(z));\nonumber\\
\label{ext:funz}
\hbox{\it Node\/}(z)&=&z,
\end{eqnarray}
and in the equation for ${\it Component\/}(z)$, we
have taken out the possibility of an isolated tree
on a (size 1) cycle.
In other words, the equation
for modified functional graphs is
\begin{equation}
f^*_1(z)={e^{-t(z)}\over 1-t(z)}.
\end{equation}

Following Meir and Moon \cite{MeMo78},
Arney and Bender \cite{ArBe82} discuss
random mappings with constraints on the degrees of nodes.
In fact, if we consider the functional graph attached to
a quadratic transformation $\phi(x)=x^2+c\bmod{n}$ for
$n$ prime, we see that, with a single exception $x=c$,
all nodes have degree $0$ or $2$.
This justifies interest in binary functional graphs,
where the only (in)degrees of nodes  allowed are $0$ or $2$.
In that case, the specification only needs editing:
\begin{verbatim}
  type    FunGraph   = set(Component);
          Component  = cycle(Node*BinTree);
          BinTree    = Node + Node * set(BinTree, card = 2);
          Node       = Latom(1),
\end{verbatim}
The equation determining the {\GF} $f^*_2(z)$  of these modified
mappings becomes thus
\begin{equation}
\label{fun2z}
f^*_2(z)={1\over 1-z b(z)},
\qquad\hbox{with\ \ }
b(z)=z+{{1\over2} z  b^2(z)}.
\end{equation}
Solving the quadratic equation for $b(z)$, we then find
that 
$$f^*_2(z)={1\over\sqrt{1-2z^2}},$$
and in particular, there are $2^{-n}(2n)!{2n\choose n}$
binary functional graphs of size $2n$.
Algebraically,
the case of general degree restrictions can be treated
with comparable ease, and the corresponding analytic 
treatment involves the general discussion
on singularity analysis of implicitly defined functions
given in Section~2.2.

It is then a simple task to adjust the approach taken in earlier
sections (especially Sect.~3) to such modified models.
Analysis reveals that, in this case, though multiplicative
constants are quite sensitive to such changes,
the basic orders of growth of parameters remain 
essentially unaffected. An example in sharp contrast with
this situation is treated in the next section as an illustration
of the capabilities of an automatic analysis system.

\subsection{Automatic Analysis}

The methodology that we have followed in order to analyze additive
parameters of random mappings is general enough, so as
to make it amenable to some form of automatization.
Together with B.~Salvy and P.~Zimmermann, the first author
has developed a system named {\LUO} (Lambda--Upsilon--Omega),
which takes as inputs specifications of combinatorial
structures and characteristic parameters, and produces
(in a number of cases) automatically the expected values
of the parameters. The system makes extensive use of resources 
of the computer algebra system {\sc Maple} \cite{Maple}.

Such an approach proves useful when analyzing complex models.
A description of the current state of the system is given in 
\cite{CookBook} and it will only be illustrated by
treating a {\sl ``sensitivity analysis''}
problem due to Mich\`ele Soria
who discusses systematically such phenomena in her thesis \cite{Soria89}.

The analysis below is produced automatically
by the {\LUO} system. % and we extract and comment its salient features.
The session  presents the analysis of a variant of the model
of random mappings:
We modify the classical definition of functional graphs by forcing 
all nodes on cycles to have indegree 2 exactly.
In other words, we consider special functional graphs
(the {\tt Sfungraph} type) made of sets of cycles of special {\sl planted\/}
trees ({\tt Stree}).
The problem consists in determining to what extent essential parameters
are sensitive to such a change in the model.
Standard functional graphs have on average
${1\over2}\log n+O(1)$ components (cycles)  and
$\sim\sqrt{\pi n}$ nodes on cycles.
The small change in the specifications
somewhat unexpectedly results in a
rather drastic change of stochastic properties
of these graphs.

\medskip

\begin{smallit}
The {\LUO} system accepts as inputs structural descriptions
of ``decomposable'' structures in the style of Section~2
and of our earlier formal specifications.
Thus, our class of special functional graphs will be 
specified quite naturally by:
\begin{verbatim}
    type    Sfungraph  = set(Scomponent);
            Scomponent = cycle(Stree);
            Stree      = product(Node,Tree);
            Tree       = product(Node,set(Tree));
            Node       = Latom(1);
\end{verbatim}

\noindent
The {\LUO} system is primarily designed to estimate the average case 
complexity of algorithms. In order to analyze parameters
like the number of components, we therefore write a procedure
whose {\sl complexity\/} is precisely equal to the parameter
to be analyzed. The second part of the input thus reads:
\begin{verbatim}
    procedure number_of_components(f : Sfungraph);
    begin
            forall c in f do
                    count;
    end;
    
    procedure number_of_cyclic_points(f : Sfungraph);
    begin
            forall c in f do
                    forall d in c do
                            count;
    end;
    
    measure count:1;
\end{verbatim}
where the last line specifies that {\tt count} is a counter with 
constant complexity equal to 1.

Systematic translation mechanisms allow us to compile such specifications
into equations over generating functions. This task is achieved by the
{\sc Algebraic Analyzer} of {\LUO} written in the Caml language
\cite{Zimmermann89}.
% >>> ALGEBRAIC ANALYZER ...
\begin{verbatim}
    Counting generating functions:
      Tree(z)=Node(z)*exp(Tree(z))
      Stree(z)=Node(z)*Tree(z)
      Scomponent(z)=L(Stree(z))
      Sfungraph(z)=exp(Scomponent(z))
      Node(z)=z
    
    Complexity descriptors:
      tau_number_of_components(z)=(exp(Scomponent(z))*1*Scomponent(z))+0
      tau_number_of_cyclic_points(z)=(exp(Scomponent(z))*1*Stree(z)/(1-Stree(z)))
\end{verbatim}
The second batch (labelled ``complexity descriptors'') represents
generating functions of procedures' costs.
These equations are then solved by a {\sc Solver} programme written in Maple.
The solution is here expressed in terms of
$L(y)\equiv\log(1-y)^{-1}$  and of Maple's $W$--function which is
defined (implicitly) by $W(z)e^{W(z)}=z$.
\begin{verbatim}
         tau_number_of_components(z) = exp(L(- z W(- z))) L(- z W(- z))

                                            exp(L(- z W(- z))) z W(- z)
        tau_number_of_cyclic_points(z) = - -----------------------------
                                                    1 + z W(- z)
\end{verbatim}

At this stage, an {\sc Analytic Analyzer}
with extensive asymptotic capabilities, takes control
of the asymptotic analysis \cite{Salvy89}.
It is built on a large library of Maple programmes (currently
about 7000 lines), and on this problem,
it selects a strategy based on
singularity analysis.
The number of special functional graphs ({\tt Sfungraph})
 of size $n$
then appears in its {\sl raw\/} form produced by the system as:
% Number of arguments of number_of_components of size n is n! times:
\begin{verbatim}
   ...  n! times:
                    3/2  1/2         2
             exp(-1)    2    exp(1/2)  exp(-1/2) exp(n)         exp(n)
       (1/2 --------------------------------------------) + (O(--------))
                                   2   1/2  3/2                    2
                      (1 - exp(-1))  Pi    n                      n

\end{verbatim}
a formula which, after going through Maple's simplifier and {\LaTeX}
interface yields {\sl verbatim}
$$
(n\,!)\times\bigg[
{ { ( { \frac{{ { \sqrt{2}} {e^{{ n -1}}}}}{{ 2 { {( { {e^{-1}} -1} )}
^{2}} { \sqrt{ \pi }} { n^{3/2}}}}})} +  { ( {O ( { \frac{{e^{n}}}{{ n
^{2}}}})})}}
\bigg].
$$
%
% \begin{verbatim}
% Total cost of number_of_components on all arguments of size n is n! times:
% \end{verbatim}
% $$\big((n\,!\exp({n\over2})\big)\cdot
% { -  \frac{{ { \sqrt{2}} {( { {\ln { 1 {- {e^{-1}}}}} -1} )} {e^{-1}}}
% }{{ 2 { n^{3/2}} { {( { {e^{-1}} -1} )}^{2}} { \sqrt{ \pi }}}}}
% $$

The system then computes total costs (i.e., total values of parameters
over all structures of size $n$) via their generating functions.
>From there, mean value estimates folllow. For instance,
in the case of the {\sl average\/}
number of components, we get the following message
% Average cost for number_of_components on random inputs of size n is:
\begin{verbatim}
    Floating point evaluation:
                                                    1
                              (1.458675144) + (O(------))
                                                   1/2
                                                  n
\end{verbatim}
where the symbolic form of the constant $1.4586$ was also determined in passing
by the system:
$$
% { 1 { -  {\ln { 1 {- {e^{-1}}}}}}}
1-\log(1-e^{-1}).
$$
Similarly, for the number of cyclic points, we obtain
% \begin{verbatim}
% Average cost for number_of_cyclic_points on random inputs of size n is:
% \end{verbatim}
% $$\big((n\,!\exp({n\over2})\big)\cdot
% { -  \frac{{ { \sqrt{2}} {( { {e^{-1}}+ 1} )} {e^{-1}}}}{{ 2 { {( { {
% e^{-1}} -1} )}^{3}} { \sqrt{ \pi }} { n^{3/2}}}}}
% $$
\begin{verbatim}
    Floating point evaluation:
                                                    1
                              (2.163953412) + (O(------))
                                                   1/2
                                                  n
\end{verbatim}
with the symbolic form of the constant being
$$
{ -  \frac{{ {e^{-1}}+ 1}}{{ {e^{-1}} -1}}}.
$$
\end{smallit}

\medskip

In total, within a few minutes of symbolic computations, the system,
starting from formal specifications, has determined 
first symbolically, then numerically, that:
$(i)$~the expected number of components is $\sim 1.45$;
$(ii)$~the expected number of points lying on cycles is $\sim~2.16$.
This example demonstrates an unusual case  %  a rather extreme case
of model sensitivity
(compare with the corresponding values
of $O(\log n)$ and $O(\sqrt{n})$ for unconstrained random mappings).
The precise capabilities of the system are described in
\cite{FlSaZi89,CookBook,Salvy89,Zimmermann89}.
\section{Conclusions}

\begin{figure}
\vspace*{9cm}
%%%\special{psfile=des.ps hoffset=-24 voffset=-30 hscale=0.9 vscale=0.9}
\noindent
\begin{smallit}
{\bf Figure 4.}
A rendering due to Quisquater and  Delescaille
of the ``giant component'' in a  functional graph
representing an iteration structure of the DES
cryptosystem. The DES is used here as an iterator on a set
of cardinality $2^{56}$ by letting its ``output'' loop
on its ``key'' entry (keeping the ``message''fixed).
The drawing represents a skeleton graph
where approximately 1 in every $10^6$ points is sampled.
Such graphs are discussed % by Quisquater and  Delescaille
in \cite{QuDe88,QuDe89b}.
\end{smallit}

\smallskip
\noindent\hrule
\end{figure}


We have seen a systematic approach to the analysis of
a large number of parameters of random mappings (or functional graphs)
using a coherent generating function framework.

In a  random mapping of size $n$, cycles presents themselves after about $\sqrt{n}$
iteration steps (Section~2), and this phenomenon is fairly
unavoidable since the expected diameter is also $O(\sqrt{n})$
(Section~3).
Also, random functional graphs tend to have one giant component
and a few large trees.

These facts are well illustrated by
extensive computations performed by J-J. Quisquater
with the DES cryptographic system (see Fig.~4 and \cite{QuDe88,QuDe89b}).
Simulations with shift register sequences \cite{ArBe82}
or with Pollard's algorithm \cite{Pollard75}
(i.e., quadratic functions),
as well as Bach's theoretical results \cite{Bach89}
also confirm the frequent validity of predictions
based on the heuristic random mapping model
for various applications in cryptography, random number generation,
computational number theory, or the analysis of algorithms.

\paragraph{Acknowledgements.}
This research was supported in part by the ESPRIT II Basic Research
Actions Program of the EC under contract No. 3075 (project ALCOM).

\frenchspacing
\renewcommand{\baselinestretch}{0.90}


%%% \bibliography{/home/yquem/algo/flajolet/lib/bib/algo}
\bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{ArBe82}
J.~Arney and E.~D. Bender.
\newblock Random mappings with constraints on coalescence and number of
  origins.
\newblock {\em Pacific J. Math.}, 103:269--294, 1982.

\bibitem{Bach89}
E.~Bach.
\newblock Toward a theory of {P}ollard's rho--method.
\newblock {\em Information and Computation\/}, to appear, 1989.

\bibitem{BrPo81}
R.~P. Brent and J.~M. Pollard.
\newblock Factorization of the eighth {F}ermat number.
\newblock {\em Mathematics of Computation}, 36:627--630, 1981.

\bibitem{Broder85}
A.~Z. Broder.
\newblock Weighted random mappings; properties and applications.
\newblock Technical Report STAN-CS-85-1054, Computer Science Dept., Stanford
  University, 1985.
\newblock (Author's PhD Thesis).

\bibitem{Maple}
B.W. Char, K.O. Geddes, G.H. Gonnet, M.B. Monagan, and S.M. Watt.
\newblock {\em {MAPLE:} {R}eference {M}anual}.
\newblock University of Waterloo, 1988.
\newblock 5th edition.

\bibitem{deBruijn81}
N.~G. de~Bruijn.
\newblock {\em Asymptotic Methods in Analysis}.
\newblock North Holland, third edition, 1958.
\newblock Reprinted by Dover, 1981.

\bibitem{Delaurentis88}
J.~M. Delaurentis.
\newblock Components and cycles of a random function.
\newblock In C.~Pomerance, editor, {\em Advances in Cryptology}, volume 293 of
  {\em Lecture Notes in Computer Science}, pages 231--242, 1988.
\newblock (Proceedings of CRYPTO'87, Santa--Barbara.).

\bibitem{Devaney89}
R.~L. Devaney.
\newblock Dynamics of entire maps.
\newblock in {\em Proc. International Conference on Dynamics}, Stefan Banach
  Center, Warsaw (to appear).

\bibitem{Devaney84}
R.~L. Devaney.
\newblock Julia sets and bifurcation diagrams for exponential maps.
\newblock {\em Bulletin of the American Mathematical Society}, 11:167--171,
  1984.

\bibitem{Evgrafov66}
M.~A. Evgrafov.
\newblock {\em Analytic Functions}.
\newblock Dover, New York, 1966.

\bibitem{FlKnPi89}
P.~Flajolet, D.~E. Knuth, and B.~Pittel.
\newblock The first cycles in an evolving graph.
\newblock {\em Discrete Mathematics}, 75:167--215, 1989.

\bibitem{FlOd82}
P.~Flajolet and A.~Odlyzko.
\newblock The average height of binary trees and other simple trees.
\newblock {\em Journal of Computer and System Sciences}, 25:171--213, 1982.

\bibitem{FlOd90}
P.~Flajolet and A.~M. Odlyzko.
\newblock Singularity analysis of generating functions.
\newblock {\em SIAM Journal on Discrete Mathematics}, 3(1), February 1990.
\newblock To appear. Also available as INRIA Research Report 826, 1987, 25p.

\bibitem{FlSaZi89}
P.~Flajolet, B.~Salvy, and P.~Zimmermann.
\newblock {L}ambda--{U}psilon--{O}mega: An assistant algorithms analyzer.
\newblock In T.~Mora, editor, {\em Applied Algebra, Algebraic Algorithms and
  Error--Correcting Codes}, volume 357 of {\em Lecture Notes in Computer
  Science}, pages 201--212, 1989.
\newblock (Proceedings AAECC'6, Rome, July 1988).

\bibitem{CookBook}
P.\ Flajolet, B.~Salvy, and P.~Zimmermann.
\newblock {L}ambda--{U}psilon--{O}mega: The 1989 {C}ookbook.
\newblock Research Report 1073, Institut National de Recherche en Informatique
  et en Automatique, August 1989.

\bibitem{FlSo89a}
P.~Flajolet and M.~Soria.
\newblock Gaussian limiting distributions for the number of components in
  combinatorial structures.
\newblock {\em J. Combinatorial Theory}, 1989.
\newblock To appear. Available as INRIA Research Report {\rm 809}, March 1988.

\bibitem{Foata74}
D.~Foata.
\newblock {\em La s\'{e}rie g\'{e}n\'{e}ratrice exponentielle dans les
  probl\`{e}mes d'\'{e}num\'{e}ration}.
\newblock S.M.S. Montreal University Press, 1974.

\bibitem{GoJa83}
I.~P. Goulden and D.~M. Jackson.
\newblock {\em Combinatorial Enumeration}.
\newblock John Wiley, New York, 1983.

\bibitem{Harris60}
B.~Harris.
\newblock Probability distributions related to random mappings.
\newblock {\em Annals of Mathematical Statistics}, 31(2):1045--1062, 1960.

\bibitem{Jaworski85}
J.~Jaworski.
\newblock {\em Random Mappings}.
\newblock PhD thesis, A. Mickiewicz University, 1985.
\newblock (In Polish).

\bibitem{Kalugin88}
I.~B. Kalugin.
\newblock A class of random mappings.
\newblock {\em Proceedings of the Steklov Institute of Mathematics},
  177(4):79--110, 1988.
\newblock (Issue on {\em Probabilistic Problems of Discrete Mathematics\/}).

\bibitem{Knuth73}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 3: Sorting and
  Searching.
\newblock Addison-Wesley, 1973.

\bibitem{Knuth81}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 2: Seminumerical
  Algorithms.
\newblock Addison-Wesley, 2nd edition, 1981.

\bibitem{Kolchin86}
V.~F. Kolchin.
\newblock {\em Random Mappings}.
\newblock Optimization Software Inc., New York, 1986.
\newblock Translated from {\it Slu\v cajnye Otobra\v zenija\/}, Nauka, Moscow,
  1984.

\bibitem{MeMo78}
A.~Meir and J.~W. Moon.
\newblock On the altitude of nodes in random trees.
\newblock {\em Canadian Journal of Mathematics}, 30:997--1015, 1978.

\bibitem{Mutafchiev84}
L.~R. Mutaf{\v c}iev.
\newblock On some stochastic problems of discrete mathematics.
\newblock In {\em Mathematics and Education in Mathematics {\rm (Sunny
  Beach)}}, pages 57--80, Bulgarian Academy of Sciences, Sophia, Bulgaria,
  1984.

\bibitem{Mutafchiev88}
L.~R. Mutaf{\v c}iev.
\newblock Limit theorems concerning random mapping patterns.
\newblock {\em Combinatorica}, 8:345--356, 1988.

\bibitem{Odlyzko82}
A.~M. Odlyzko.
\newblock Periodic oscillations of coefficients of power series that satisfy
  functional equations.
\newblock {\em Advances in Mathematics}, 44:180--205, 1982.

\bibitem{Olver74}
F.~W.~J. Olver.
\newblock {\em Asymptotics and Special Functions}.
\newblock Academic Press, 1974.

\bibitem{Pavlov88}
A.~I. Pavlov.
\newblock On an equation in a symmetric semigroup.
\newblock {\em Proceedings of the Steklov Institute of Mathematics},
  177(4):121--128, 1988.
\newblock (Issue on {\em Probabilistic Problems of Discrete Mathematics\/}).

\bibitem{Pavlov77}
Yu.~L. Pavlov.
\newblock The asymptotic distribution of maximum tree size in a random forest.
\newblock {\em Theory of Probability and Applications}, 22:509--520, 1977.

\bibitem{Pavlov88a}
Yu.~L. Pavlov.
\newblock On random mappings with constraints on the number of cycles.
\newblock {\em Proceedings of the Steklov Institute of Mathematics},
  177(4):131--143, 1988.
\newblock (Issue on {\em Probabilistic Problems of Discrete Mathematics\/}).

\bibitem{Pollard75}
J.~M. Pollard.
\newblock A {Monte Carlo} method for factorization.
\newblock {\em BIT}, 15(3):331--334, 1975.

\bibitem{Proskurin73}
G.~V. Proskurin.
\newblock On the distribution of the number of vertices in strata of a random
  mapping.
\newblock {\em Theory of Probability and Applications}, 18:803--808, 1973.

\bibitem{PuWi68}
P.~Purdom and J.~Williams.
\newblock Cycle length in a random function.
\newblock {\em Transactions of the American Mathematical Society},
  133:547--551, 1968.

\bibitem{QuDe88}
J.-J. Quisquater and J.-P. Delescaille.
\newblock Other cycling tests for {DES}.
\newblock In C.~Pomerance, editor, {\em Advances in Cryptology}, volume 293 of
  {\em Lecture Notes in Computer Science}, pages 255--256. Springer-Verlag,
  1988.
\newblock (Proceedings of CRYPTO'87, Santa--Barbara.).

\bibitem{QuDe89b}
J.-J. Quisquater and J.-P. Delescaille.
\newblock How easy is collision search? {N}ew results and applications to
  {DES}.
\newblock In {\em Proceedings of CRYPTO'89}, Lecture Notes in Computer Science.
  Springer-Verlag, 1989.
\newblock To appear.

\bibitem{ReSz67}
A.~R{\'e}nyi and G.~Szekeres.
\newblock On the height of trees.
\newblock {\em Australian Journal of Mathematics}, 7:497--507, 1967.

\bibitem{Sachkov73}
V.~N. Sachkov.
\newblock Random mappings with bounded height.
\newblock {\em Theory of Probability and Applications}, 18:120--130, 1973.

\bibitem{Salvy89}
B.~Salvy.
\newblock Fonctions g{\'e}n{\'e}ratrices et asymptotique automatique.
\newblock Research Report 967, Institut National de Recherche en Informatique
  et en Automatique, 1989.

\bibitem{ShLl66}
L.~A. Shepp and S.~P. Lloyd.
\newblock Ordered cycle lengths in a random permutation.
\newblock {\em Transactions of the American Mathematical Society},
  121:340--357, 1966.

\bibitem{Soria89}
M.~Soria.
\newblock {\em M{\'e}thodes d'analyse pour les constructions combinatoires et
  les algorithmes}.
\newblock Doctorat {\`e}s sciences, Universit\'e de Paris--Sud, Orsay, 1989.

\bibitem{Stanley86}
R.~P. Stanley.
\newblock {\em Enumerative Combinatorics}, volume~I.
\newblock Wadsworth \& Brooks/Cole, 1986.

\bibitem{Stepanov69}
V.~E. Stepanov.
\newblock Limit distributions of certain characteristics of random mappings.
\newblock {\em Theory of Probability and Applications}, 14:612--626, 1969.

\bibitem{Titchmarsh39}
E.~C. Titchmarsh.
\newblock {\em The Theory of Functions}.
\newblock Oxford University Press, 2nd edition, 1939.

\bibitem{Zimmermann89}
P.~Zimmermann.
\newblock Alas: un syst{\`e}me d'analyse alg{\'e}brique.
\newblock Research Report 968, Institut National de Recherche en Informatique
  et en Automatique, 1989.

\end{thebibliography}

% ======================================================================
\end{document}