Images and Preimages in Random Mappings.
We present a general theorem that can be used to identify the limiting distribution for a class of combinatorial schemata. For example, many parameters in random mappings can be covered in this way. In particular, we can derive the limiting distribution of those points with a given number of total predecessors.
Introduction
By a random mapping ' 2 Fn
Fn we mean an arbitrary mapping
ng ng such that every mapping has equal probability n n .
The main purpose of this paper is to obtain limit theorems, when n tends to
innity, for special parameters in random mappings, e.g. for the number of image
points. Since every random mapping ' 2 Fn has equal probability it suces to
count the number of radom mappings ' 2 Fn satisfying a special property, e.g.
that the number of image points equals k. By dividing this number by n n we
get the probability of interest. In order to get the limit distribution for n !1
it is not necessary to know the exact value. We just have to evaluate these
numbers asymptotically. We shalll show that this can be done by a singularity
analysis of a proper bivariate generating function.
It should be noted that some of our limit distributions on random mappings
are well known (compare with [4, 16]). But our main goal is to provide a general
method to derive such limit theorems. In particular, we use bivariate generating
functions and singuarity analysis. Especially we are able to characterize the (up
to now unknown) limit distribution of the number of those points with a xed
number of total predecessors. It is a Gaussian distribution.
Our basic combinatorial concept is that of labelled combinatorial constructions
and the relation to exponential generating functions. A big advantage in
such combinatorial constructions is that we can mark a parameter in the constructions
which directly leads to bivariate generating function for the number
of objects according to their size, and the value of the parameter of interest.
Marking in Random Mappings
Every mapping ' 2 Fn can be identied with its functional graph G' where
ng and E(G' ng. It is obvious that each
component of G' consists of a cycle (at least of a loop) and every cyclic point
is the root of (labelled) tree. (see Figure 1)
Hence we can interprete a mapping ' 2 F as a set of cycles of trees. Further-
more, since there is no restriction on their structure, the trees (usually known
as Cayley trees) can be recursively described as a root followed by a set of trees:
Both structures, F and T , t into the concept of (labelled) combinatorial structures
synthetized by Ph. Flajolet [11] (see also [17]). Let us give a short description
of such structures.
Let C be a combinatorial stucture of (labelled) elements, let jcj denote the
size of c 2 C and c the number of elements of size n.
(Labelled means that there are always n! \isomorphic" elements
which dier by their labels Furthermore we associate to a (labelled)
combinatorial structure C the (exponential) generating function
x jcj
(jcj)!
The advantage of these generating functions is that there is a correspondence
between special combinatorial constructions and special operations with the
corresponding generating functions. For example, if the (labelled) combinatorial
structure C is the product C 1  C 2 then
Note that C 1  C 2 is not the set theoretic cartesian product because you have to
transform the labelling and the labelling
to a labelling ng of c 2 C 1  C 2 . Since there are k! \isomorphic"
element in C 1 and (n k)! \isomorphic" elements in C 2 we have
c 1;k
(n k)!
according to (4). Hence, if
and if
m1m
Applying this concept to random mappings, the (exponential) generating
function
the generating function for Cayley trees, is given by
A big advantage of such combinatorial constructions is that we can formally
mark a parameter in the constructions by a symbol like [u]. And this marking
directly leads to bivariate generating function for the number of objects
according to their size, and the value of the parameter of interest.
For example, if we are interested in the number of trees in graphs of random
mappings we have to mark the trees in the combinatorial construction
Formally this leads to
log1
which is exactly the generating function ^
n! u k of the numbers
f nk of random mappings with k trees in the graph representation. (Note that
the number of trees is exactly the number of cyclic points.)
Or if we are interested in the number of components, we have to mark
and get
Next we will use this marking method to describe special parameters related
to image and preimage points.
Points at distance d to a cycle. First we will discuss preimages of cyclic
points. For this purpose let Y' denote the cyclic points of a random mapping
Precisely, we are interested in ' d (Y '
non-cyclic points at distance d to the cyclic points.
and
A d+1 (x;
for d  1. Then
is the (exponential) generating function of random mappings where points contained
in ' d (Y' are marked.
Proof. Let
t d (x; u) denote the (exponential) generating function of labelled
rooted trees where nodes of distance d  0 from the root are marked. Obviously
we have
t(x) and
which directly leads to
t(x)):Points with in-degree r. Another interesting parameter is the number of
points  with j' 1 is a xed integer.
denote the solution of
Then
pr
pr (x;u) r 1
(r 1)!
is the (exponential) generating function of random mappings where points  with
are marked.
Proof. According to the recusive structure of Cayley trees
the nodes with in-degree r are those followed by r subtrees. Hence the bivariate
generating function for trees, with variable u marking nodes with in-degree r
m6=r
Now a cyclic point in the functional graph of a random mapping has in-degree
r if and only if it has in-degree r 1 in the corresponding trees. This proves
Notice that the expression of the bivariate generating function is simpler if
we neglect the edges between cyclic points (i.e. cyclic points are marked if they
have in-degree r + 1, and non cyclic points are marked if they have in-degree
r). Actually we then consider sequences of Cayley trees instead of random
mappings.
Lemma 2bis The (exponential) generating function of sequences of Cayley
trees where marked nodes are those with in-degree r is
u) is the same as in Lemma 2.
Points with r-antecedents. Finally we want to count those points where
the total number of preimages equals r  0.
denote the solution of
r! . Then

x r
r
r
(r m)!
is the (exponential) generating function of random mappings where points  with
Proof. As in the proof of Lemma 2 we rst mark the nodes with total number
of preimages r in Cayley trees : a node is marked if and only if it is the root of
a tree of total size r (the root is considered to be its own preimage). Hence we
get (14), where t r is the coecient of x r in the series expansion
the functional equation (9) we get by Lagrange's inversion
theorem
For cyclic points in a random mapping all points in the corresponding component
(of the functional graph) are preimages. Hence for a component with m cyclic
points, the bivariate generating function, with u marking the number of points
having r preimages, is
where
r
r(r m)!
is the number of forests composed with m components, and of total size r. This
directly gives (15). 2
d-th iterate points. It is also interesting to consider ' the
d-th iterate image points.
Lemma 4 Set
u) be the solution of
Then
is the (exponential) generating function of random mappings where points  2
are marked.
Proof. Clearly, h d (x) is the (exponential) generating function of Cayley
trees with height < d. In Cayley trees, d-th iterate image points are points at
distance  d from a leaf. Hence u), the bivariate generating function of
trees where nodes having a leaf at distance  d are marked satises (16). For
random mappings, since all cyclic points are d-th iterate image points we get
which leads to (17). 2
Here again, as in the case of points with in-degree r, the expression of the
bivariate generating function is simpler if we neglect the edges between cyclic
Lemma 4bis The (exponential) generating function of random mappings where
the marked points are those at distance  d from a leaf of their own subtree is
is the same as in Lemma 4.
Direct d-th iterate points. The most dicult example (from the combinatorial
point of view) is the case of d-th iterate image points of non-image
points ' d ng In other words we will count those nodes
which are connected by a (directed) path of length d to a non-image point.
Nevertheless there is a rather easy subcase where edges between cyclic points
are neglected, i.e. the problem can be reduced to a problem inside trees. Although
this is only a very small change it will turn out that the corresponding
limiting distibutions dier. (And it will also be the case for Lemmas 2 and 4
vs. Lemmas 2bis and 4bis.)
Lemma 5 Set
e y e y c i (x;y)
for i  0:
u) be the solution of
Then
~

log 1
is the (exponential) generating function of random mappings where marked
points are those connected to a leaf by a path of length d which does not contain
cyclic edges. (Note that the root of a tree of size 1 is also a leaf.)
Proof. Let denote the generating function of Cayley trees where
nodes having a leaf at distance d are marked. The generating function where
leaves are marked is
is the generating function for trees
with a leaf at distance d to the root : y d (x;
represents the trees such that the root is not at distance d to a
Lemma 5bis Let c i (x; y) and ^ l d (x; u) be dened as in Lemma 5 and let ^
f d (x; u)
be the (exponential) generating function of random mappings where points  2
ng are marked.
For
For
Then
Proof. The results for ^
points are not leaves of random mappings, and for cycles are
of no importance. For 2, the situation gets more delicate : in addition to
the interpretations of y 1 (x; u) and y 2 (x; u) observe that y 12 (x; u) corresponds to
those trees having both a leaf at distance 1 to the root and a leaf at distance
2 to the root. (For the sake of shortness we will use the terms y 1 -tree (resp.
for a tree with a leaf at distance 1 (resp. 2) to the root.) Set
Then w corresponds to additionally marking y 1 -trees which are not y 2 -trees. In
the same way s corresponds to marking twice y 2 -trees which are y 1 -trees too.
We will show (at the end of the proof) that the generating function
corresponds to a cycle of m trees where all nodes having a leaf at distance 2 are
marked (Amkl , see below, counts the number of cycles of length m containing k
l) of which are followed by an y 2 -tree). Since
m1m
log 1
we immediately get (22).
Therefore it remains to interprete (23). The problem on a cycle is that a
forces an additional mark at the next root on the cycle if and only if
this next root is not marked, i.e. the corresponding tree is not an y 2 -tree. For
example, if a cycle of length m contains no y 2 -tree then it is immediately clear
that 1
is the correct corresponding function, whereas the case of a cycle
containing only y 2 -trees the generating function of interest is 1
2 . For the
remaining cases consider a cycle containing exactly k (0 < k < m) y 2 -trees such
that l (0 < l  of these trees are followed by a tree which is not a y 2 -tree.
Note that
l
l 1
l 1
is the number of such arrangements on a (labelled) cycle of length m. In any of
these cases the corresponding generating function is 1
This proves (23). 2
3 General Theorems
be the generating function of a combinatorial structure and
the bivariate generating function where a parameter of
interest has been marked, i.e. c(x; c(x). We will now be interested in the
asymptotic distribution of this parameter in the system of combinatorial objects
of size n, when n tends to innity. For this purpose we introduce a sequence of
random variables dened by
where Pr denotes probability. Now the above problem reduces to nding the
limiting distribution of Xn .
An important analytic schema, related to combinatorial constructions \se-
quence" or \set of cycles", is
c(x; u) =1 a(x; u)
The next three theorems study this schema when a(x; u) has an algebraic singularity
(u) of squareroot type, such that a((1); 1. According to further
analytic properties of a(x; u), the limiting distribution of Xn is shown to be
either Gaussian, or Rayleigh, or the convolution of Gaussian and Rayleigh ; and
in each case the global limit result (convergence of distribution functions) is
accompanied by a local limit result (convergence of densities).
Let us rst state precisely the general form of the analytic schemas under
consideration.
Hypothesis [H]. Let c(x;
n;k c nk x n u k be a power series in two variables
with non-negative coecients c nk  0, such that c(x; 1) has radius of
convergence  > 0.
We suppose that c(x; u) expresses as c(x;
the local representation
r
for ju 1j < " and jx (u)j < ", arg(x (u)) 6= 0, where " > 0 is some xed
real number and g(x; u), h(x; u), and (u) are analytic functions.
Furthermore these functions satisfy
In addition x = (u) is the only singularity on the circle of convergence
can be analytically continued
to a region jxj <
Under this hypothesis, the limiting distribution of Xn in c(x; u) depends on
0 (1) and g u ((1); 1), as stated in the following three theorems.
Theorem 1 Let c(x; u) be a bivariate generating function satisfying [H]. If
const. for ju 1j < " and g u (; 1) < 0 then the sequence of random
variables dened by
has a Rayleigh limiting distribution, i.e.
d
and R() has density x exp
for x  0. Expected
value and variance are given by
r
Moreover we have the following local law
exp
uniformly for all k  0.
Theorem 2 Let c(x; u) be a bivariate generating function satisfying [H]. If
then Xn has a Gaussian limiting
distribution, i.e.
d
Expected value and variance
are given by
Furthermore there is local law of the form
exp
uniformly for all k  0.
Theorem 3 Let c(x; u) be a bivariate generating function satisfying [H]. If
then the limiting distribution of Xn is
the convolution of a Gaussian and a Rayleigh distribution, i.e.
d
are dened as in Theorem 2. Expected value
and variance are given by
(4
n)
and there is local law of the form
exp
exp

uniformly for all k  0, where
Z xexp
dt: (36)
then the corresponding Rayleigh distribution is supported on the negative
real axis and a similar local law holds.)
Remark. It should be noticed, that condition g(; in the theorems is
not a real restriction. In fact, it turns out that the case g(; is the most
dicult one, and the limiting distribution for other cases can also be found.
If g(; 1) > 0 then c(x; u) has a local representation of the form
r
On the other hand, if g(; 1) < 0, the algebraic singularity is not the dominating
one. Here d(; Hence by the
Weierstrass preparation theorem d(x; u) has a local representation of the form
and (u) are analytic functions
satisfying D(; 1) 6= 0,
In both cases, (37) and (38), we can apply Bender's theorem [5] (compare also
with [6] and [7]) to get asymptotic normality if  0 (1) < 0 (Evaluating the expected
value shows that  0 (1) cannot be positive).
When const. (see also [14] for this case), the limiting distribution
is Gaussian for g(; 1) > 0, and discrete for g(; 1) < 0 (for example there is a
derivated geometric law for the schema c(x;
Finally we want to remark that the assumption const in Theorem 1
can be weakened to  0 However, the proof would be a little bit more
complicated. Furthermore no example is known, where  0
const.
Before proving Theorems 1,2,3 (see section 5) we want to motivate why such
theorems have some importance in relation to random mappings.
4 Applications to Random Mappings
In this section we apply our theorems to obtain the limiting distributions for
various parameters of random mappings. It should be noted that some of the
obtained results are known but our intention is to provide all the results by
applying only one general principle. The underlying point is that the combinatorial
specication of random mappings out of Cayley trees, together with
the analytic form of the Cayley trees series, imply that all bivariate generating
functions
constructed in section 2 satisfy hypothesis [H].
4.1 Analytic frame
The basic property is that solutions of functional equations usually have algebraic
singularities of squareroot type.
Proposition 1 Let F (a; x; u) be a power series on three variables with non-negative
coecients and F (0; 0; Suppose that the system of equations
a
has positive solutions a 0 > 0, x 0 > 0 (which are supposed to be minimal) such
that (a contained in the region of convergence of F (a; x; u) and that
0: (41)
Then there exists a unique analytic solution a
nk a nk x n u k of
with non-negative coecients a nk  0 and a such that a(x; u) has the
local representation
r
for ju 1j < " and jx (u)j < ", arg(x (u)) 6= 0, where g(x; u), h(x; u), and
are analytic functions which satisfy
s
xed real number. Furthermore, if there are
gcd
a nk > 0
where
then is the only singularity on the circle of convergence
for ju 1j < " and there exists some  > 0 such that a(x; u) can be analytically
continued to the region jxj < x "The Proof of Proposition 1 is a combination of the implicit function theorem
and the Weierstrass preparation theorem (cf. [7, 8]).
Now it is easy to see the connection to random mappings. In any of the
above combinatorial constructions the solution a(x; u) (satisfying a( 1
of a functional equation of the type (42) is used to construct a nal generating
function which is more or less of the form
c(x; u) =1 a(x; u)
Hence we can directly apply our theorems to obtain the kind of asymptotic
distribution.
4.2 Distribution of parameters
The examples mentioned in section 2 cover the three types of limiting distribu-
tions, Gaussian, Rayleigh, or a convolution of both. It should be noted that in
applications 2,4 and 5, small structural modications (neglecting cyclic edges)
lead to dierent limit laws.
For the sake of shortness we will only mention the weak convergence law.
However, in all the cases the local law and the asymptotic expansions for mean
and variance hold, too.
Application 1 ([16]) Let Xn denote the number of non cyclic points at a xed
distance d > 0 to a cycle, in random mappings of size n. Then
d
Proof. From Proposition 1 it follows that ^ t(x) has a local representation of
the kind
where a(x) and b(x) are analytic functions around x
e with a( 1
2. Furthermore we can use the Taylor series expansion of
A d (x; u)
c lk (u 1) l (xe
to see that A d (x; has a representation of
the kind
A d (x;
2. Hence we can apply
Theorem 1. 2
Application 2 ([4]) Let r  0 be a xed integer and let Xn denote the number
of points  with j' 1
d
er! and
Proof. Let
Then another application of Proposition 1 provides a local representation of
r
consequently
2.
Hence we obain
pr (x;u) r
pr (x;u) r 1
(r 1)!
in which g( 1
2, and
the system of equations
implicit dierentiation gives
F
00 (1) =F pp F 3
x
F pp F x
Thus we can apply Theorem 2. 2
Application 2bis Let r  0 be a xed integer and let Xn denote the number
of nodes with in-degree r in a sequence of Cayley trees of total size n. Then
d
where  and  2 are the same as in Application 2, and
. In the
special case r = 1, the limiting distribution is only Gaussian since
Proof. In this case (1) is not equal to 0, except for 1. Hence the
convolution results by Theorem 3. 2
Application 3 Let r  0 be a xed integer and let Xn denote the number of
points  with
in mappings ' 2 Fn . Then
d
Proof. First notice that the analytic factor exp(  ) in (15) has no in
uence
on the parameters of interest ,  0 (1), and  00 (1). Therefore we can neglect it.
Hence we can proceed as in the proof on Application 2. Here we have
a
Consequently and we obtain a Gaussian limiting distribution. 2
Application 4 Let d  0 be a xed integer and let Xn denote the number of
points  2 ' d
d
e ) and
Proof. The proof is almost the same as the proof of Application 2. 2
We want to mention that the mean value was already determined in [13].
Application 4bis Let d  0 be a xed integer and let Xn denote the number
of points at distance  d from a leaf of their own subtree, in random mappings
of size n. Then
d
where  and  2 are the same as in Application 4, and
d
e
Proof. In this case
Hence the convolution result. 2
Application 5 Let d  0 be xed and Xn denote the number of nodes which
are connected to a leaf by a path of length d containing no cyclic edge, in random
mappings of size n. Then
d
d;y , and
@y c d ( 1
the limiting distribution is only Gaussian in this special case.
Proof. The proof runs along the same lines as the preceding ones. You only
have to apply Theorem 3 since
Application 5bis Let d 2 f0; 1; 2g be xed and let Xn be the number of points
ng
d
where  and  2 are as in Application 5, i.e.
for
and
for
2e 1+e 1=e e 1
e 1+e 1=e
for 2.
2e 2+e 1=e e 1
e 2+2e 1=e 2e 1
Proof. Especially in the case have to calculate  very carefully
but in all the cases
in the case d > 2, the combinatorial description is much more in-
volved. Nevertheless it may be conjectured that the limiting distribution is still
Gaussian.
5 Proof of the Theorems
The proofs of Theorems 1,2,3 proceed in the following way. First we derive
asymptotic expansions for mean value and variance, then we prove a weak limit
theorem using characteristic functions and nally we establish the corresponding
local limit theorem. This procedure seems to be redundant, and in fact it is.
But our aim is not only to prove special theorems, but to provide an example
for a general method to analyze the asymptotic distribution of a parameter in
combinatorial constructions.
5.1 Preliminaries
We rst list some useful formulae related to Gaussian and Rayleigh distributions.
Lemma 6 Let
be a Hankel contour starting from +e 2i 1, passing around 0
and tending to +1. Then2i
Z
e z
z is
where
Z 1e itx xe x 2 =2 dx
r
Z te u 2 =2 du
denotes the characteristic function of the Rayleigh distribution.
Proof. It suces to compare the Taylor expansion around By the
Hankel intregral representation of
Z
e z
z is
Z
On the other hand we have
Z 1X
it
where we have used the duplication formula for the -function. 2
Lemma 7 Let
be as in Lemma 6. Then2i
Z
e s
Z
e z
z
Proof. (53) and (54) follow immediately from the substitution
Lemma 8 Let
be as in Lemma 6 and ;  real constants. Then2iZZ
z iw
dz dw (55)
@
Proof. Since both sides of (56) can be interpreted as analytic functions in
around the real axis it suces to prove (56) for the case  > 0. In this
case we can use the substitutions
Then we can apply the polar substitution sin ' to getZ1
r
d' dr
Z
r
dz
iz
dr
A dr
22
3exp

@
where the integral
solved by using the substitution z = e i' and the
residue theorem:
Z
dz
z
The residues have to be calculated for
This completes the proof of Lemma 8.2
5.2 Proof of Theorem 1
We rst derive asymptotic expansions for mean value and variance. Since
we get
and

1!
Hence
Similarly we get
and
Next we will determine the characteristic function of Xn=
n. Since
Ee itXn=
we have to expand [x n ]c(x; u) for
purpose we will use Cauchy's formula
Z
c(z; u)
dz
z n+1
for the following path of integration
j#j
where
is the major
part of a Hankel contour
First let us concentrate on the path 1 . By using the substitution
we get2i
dz
z n+1
s
ds
Ze s
ds
ne s
ds
e log 2 n
we immediately get by (60) and Lemma 62i
dz
z n+1
2g
Now we make use of the fact that there are " 1 > 0,  1 > 0 such that
only have to observe that c nk  0,
that is the only singularity on the circle of convergence, and that c(x; u)
has the local representation (56). Hence it follows from
c
log n
that Zc(z; u)
dz
z n+1
O
Consequently, by (57), (58), (61), and (62)
Ee itXn=
2g
Thus we have proved a weak limit theorem.
In order to prove the local limit theorem we again use Cauchy's formula
Z Z
c(z; u)
du
dz
z
is as above (see 59) and  will be properly chosen.
then the mapping u 7! c(z; u) has a polar singularity
at
, where
s +O
with residue 1
Hence we can transform  in a way that2i
Z
c(z; u)
du
Z
c(z; u)
du
=g
exp
s
ZZ
c(z; u)
du
dz
z n+1
Zexp
s
ds
np
exp
4n
By elementary considerations we obtain
log n
Hence, by choosing we can estimate the remaining
integral
ZZ
c(z; u)
du
dz
z
and nally have proved the the local limit theorem.
5.3 Proof of Theorem 2
As above we have
and from
c u
1+ O
we immediately get
and from a little bit more rened analysis
Since
we have to determine
Z
c(z; u)
dz
z n+1
for
which we use the following
path of integration
log
arg
log
j#j
From
and from
r s
for directly get by applying Lemma 72i
dz
z n+1
Ze s
s
s
ds
It remains to estimate the integral on 2 . But this can be done as in the proof
of Theorem 1 since
log n):
In order to prove the local law we again use Cauchy's formula
Z
Z
c(z; u)
dz
z n+1
du
1g. For
as in the proof of the weak limit theorem, for
jtj < "g (for some suciently small " >
and for u 2
suciently small  > 0.
First, let By direct approximation
we have
(Note that and that jsj  1.) and
z n u
Hence we obtain by using the methods of [12] and a saddle point like integration
(compare with [9])(2i) 2
Z
dz
z n+1
du
Z
Ze it(k n) 1
s
ds dt
exp
Therefore the proof is nished if the remaining integrals are suciently small.
As above we
Z
dz
z n+1
du
O
Next we get(2i) 2
Z
Z
c(z; u)
dz
z n+1
du
O
since j(u)j  (1 suciently small constants
Finally, since c(z; u) is bounded for u 2  3 and z 2 we
Z
Z
c(z; u)
dz
z n+1
du
which completes the proof of the local theorem.
5.4 Proof of Theorem 3
As in the proof of Theorem 2 we get
and
Now, if we use the same normalization and the same path of integration (63) as
in Theorem 2, we obtain for
applying Lemma 62i
dz
z n+1
Ze s
s
ds
exp
'R
The remaining integral on 2 can be estimated as above. Hence we have proved
the weak convergence property.
In order to prove the local law we will proceed as in the proof of Theorem 2.
As above we can concentrate on the path of integration  1  1 . The remaining
integrals are negligible. Direct approximation yields(2i) 2
Z
dz
z n+1
du
Z
Ze it(k n) 1
nt
ds dt:
Hence an application of Lemma 8 and easy tail estimates complete the proof of
Theorem 3.
6 Conclusions
The main purpose of this paper is to provide general techniques to obtain the
limiting distribution of parameters in combinatorial constructions. It is the
second paper of a (planed) series of papers ([10]) devoted to this topic. Theorems
1{3 should be considered as examples of analytic theorems providing an
link between combinatorial constructions and its asymtotic distributions. (They
seem to be proper theorems to discuss random mappings.) The authors are convinced
that the methods presented in the preceding proofs can be used in many
other (dierent) problems. The basic ideas are singularity analysis (introduced
by Flajolet and Odlyzko [12]) and saddle point approximation.
Random mappings are widely and intensively discussed in literature, e.g. in
Kolchin's book [15] a probabilistic approach via branchning processes is presented
whereas Aldous and Pitman [3] use a completely dierent probabilistic
concept related to Aldous' continuum random trees [1, 2]. Our concept of generating
functions goes back to Arney and Bender [4] and to Flajolet and Odlyzko
[13]. They could identify many limiting distribution and provided asymptotic
expansions for mean and variance. (One gap could be lled by Application 3.)
It should be mentioned, too, that Arney and Bender [4] discussed a little bit
more general case, namely that the number of immediate predecessors of a point
(fg)j is not arbitrary but must be contained in a subset D of non-negative
integers, i.e. the corresponding tree function ^
t D (x) satises the functional equa-
tion
and the corresponding generating function for those mappings
From Proposition 1 it follows that if D contains a number  2 then it has a
squareroot singularity
around
and we are in a similar situation as in the classical case. Especially
we can adapt all the combinatorial constructions to this more general case and
obtain analog results by applying our theorems.



--R

The continuum random tree I
The continuum random tree III
Brwonian bridge asymptotics for random map- pings

Central and local limit theorems applied to asymptotic enu- meration
Central and local limit theorems applied to asymptotic enumeration.
Asymptotic distributions and a multivariate Darboux method in enumeration problems
The height distribution of leaves in rooted trees
A bivariate asymptotic expansion of coe
Marking in combinatorial constructions: Generating functions and limiting distriubutions
Elements of a general theory of combinatorial structures
Singularity analysis of generating func- tions
Random mapping statistics
Special limit distributions
New York
The limit distribution of the number of nodes in low strata of a random mapping

--TR

--CTR
Bernhard Gittenberger, Nodes of large degree in random trees and forests, Random Structures & Algorithms, v.28 n.3, p.374-385, May 2006
Cyril Banderier , Philippe Flajolet, Basic analytic combinatorics of directed lattice paths, Theoretical Computer Science, v.281 n.1-2, p.37-80, June 3 2002
combinatorial constructions;random mappings;limiting distributions