Enumerative Combinatorics: Combinatorial Decompositions
and Functional Equations^{*}
Mireille BousquetMélou
Labri, Université Bordeaux 1 (France)
Algorithms Seminar
March 26 and 27, 2001
[summary by Mathias Vandenbogaert]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
The primary purpose of this course is the elaboration of methods for
providing answers to problems that arise in enumerative
combinatorics. The main tool to be used in this respect are (ordinary)
generating functions. The objects that will be dealt with are
2dimensional walks (for which several convexity
constraints will be taken into account) and trees. These objects are
more generally described as ``decomposable'' objects. A description of
the principal combinatorial decompositions by means of functional
equations of generating functions will be presented as an equivalent
but more synthetic approach to the use of recurrences. The modelling
by generating functions of combinatorial structures like trees and
walks will be discussed. The same principles hold for maps, animals,
and polyominoes. The ``kernel method'' and ``quadratic method''
techniques will be presented. The course will be illustrated by
numerous examples.
1 Enumeration Problems and the Way of Solving Them
The approach in solving an enumerative problem consists in a
combinatorial step that examines the structure of the objects under
consideration, and a step that resolves the recurrence relations or
functional equations. By observing the structure of the objects, some
(recursively definable) property can be translated into a
mathematical, nontautological information on a_{n}, the number of
objects of size n. Instead of manipulating recurrence relations,
generating functions describing the corresponding functional equations
are used:
A(t) = 

a_{n} t^{n} = 

t^{A} 
is called the ordinary generating function of the combinatorial class
A endowed with the size function ., where the number of
objects a_{n} are to be finite. A power series with coefficients
in A can be written å_{n ³ 0} a_{n} t^{n} with a_{n} Î N.
Using counting generating functions it can be noticed that paths of
various sorts are invariably algebraic functions, which are
defined as solutions of a polynomial equation
[11].
There is a simple correspondence between operations on combinatorial
classes of objects and combinations of the associated generating
functions. This allows us to derive directly functional relations
between generating functions starting from definitions of
combinatorial objects.
 Union:
A(z) + B(z) is the enumerative ordinary generating function of A
È B. If a_{n} and b_{n} are the numbers of objects
of size n in A and B respectively, then a_{n}+b_{n} is the
number of objects of size n in A È B.
 Cartesian Product:
A(z) B(z) is the enumerative ordinary generating function of A ×
B. The number of objects of size n in
A × B equals the simple convolution å_{0 £ k £ n}
a_{k}b_{nk}. Alternatively:

z^{g} = 



z^{a+b} = A(z)B(z). 
 Sequences:
(1A(z))^{1} is the enumerative ordinary generating
function of sets of objects of
A = 
{ 
(B_{1}, B_{2},...,B_{k})  B Î B, k ³ 0 
} 
.

The cardinality of A is A = å_{i=1}^{k} B_{i}, and the
generating function of A(z) is
A(t) = 

B(t)^{k}= 
( 
1B(t) 
) 
^{1} 
according to the statements of union and cartesian product.
It can be proven that a strong algebraic decomposability
prevails for directed lattice paths, which is obtained
by a specific technique, the``kernel method'' [2, 6].
The decomposability enables us to determine the location and nature
of dominant singularities.
2 Enumeration Example
Fix a finite set of vectors of Z × Z,
S = {(a_{1},b_{1}),...,(a_{m},b_{m})}.
A lattice path or walk relative to S is a
sequence v = (v_{1},...,v_{n}) such that each v_{j} is in S.
The geometric realization of a lattice path v = (v_{1},...,v_{n})
is the sequence of points (P_{0}, P_{1},...,P_{n}) such that P_{0} = (0,0) and
P_{j1}P_{j} = v_{j}. The quantity n is referred to as the size of the path.
The elements of S are called steps or jumps.
For these paths, the solution F(t,u) (which is always an algebraic
function of t and u),
and combinatorial explanations for the simple formulae obtained from the recurrence relations
can be found in [9].
2.1 Dyck paths
A classical example can be given with Dyck paths.
A Dyck path of length 2n is a path in
the plane from (0,0) to (2n,0) which uses only steps (1,1) (NorthEast),
called rises, and (1,1) (SouthEast), called falls.
A Dyck path ends on the xaxis and does not go below the xaxis.
A Dyck path therefore has
even length, with the number of NorthEast steps equal to the number of SouthEast
steps. A lattice point on the path is called a peak if it is immediately preceded
by a NorthEast step and immediately followed by a SouthEast step [10].
A peak is at height k if its ycoordinate is k.
By D_{n} we denote the set of all Dyck paths of halflength n.
Obviously, D_{0} = {e}.
Every nonempty Dyck path a can be decomposed uniquely in the
following manner [7]:
a = ub_{1} dg_{1},
when writing
u for a NorthEast step, and d for a SouthEast step, and where
b_{1} and g_{1} are possibly empty Dyck paths.
This relation implies that
D_{n} = u D_{0} d D_{n1} È u D_{1} d D_{n2} È ... È
u D_{n2} d D_{1} È u D_{n1} d D_{0}, n ³ 1.
Alternatively, we can write a = b_{2} ug_{2} d in a unique
manner, where b_{2} and g_{2} are possibly empty Dyck paths.
This relation implies that
D_{n} = D_{0} u D_{n1} d È D_{1} u D_{n2} d È ... È
D_{n2} u D_{1} d È D_{n1} u D_{0} d, n ³ 1.
Both equations have disjoint unions. Thus we obtain
D_{n} = D_{0} D_{n1} + D_{1}
D_{n2} + ... +
D_{n2} D_{1} + D_{n1} D_{0},
n ³ 1.
As D_{0} = 1, this sequence with n ³ 0 satisfies the same recurrence
relation as the sequence (c_{n})_{n ³ 0} of Catalan numbers.
2.2 Enumeration of Dyck paths
Let p be a fixed nonnegative integervalued parameter of a Dyck
path, i.e., a mapping from È_{n ³ A} D_{n} into {0, 1, 2,
...}. If D is a finite set of Dyck paths, then by D(t) we
denote the enumerating polynomial of D relative to the
parameter p given by
D(t) = 

d_{n} t^{n}
with 
d_{n} = 

t^{p(d)}. 
D(t) is the generating function for the enumeration of Dyck paths
according to semilength (coded by t). Thus, d_{n} is the
enumerating polynomial of the set of all Dyck paths of length n.
The recurrence relation for Dyck paths satisfies

ì
ï
í
ï
î 
d_{2n} = 

d_{2k} d_{2n2k2}, n ³ 1, 

d_{0} = 1. 


This gives on summation:
D(t) = 

d_{2n} t^{2n}
= 1 + 
æ
ç
ç
è 

t^{2n} 
ö
÷
÷
ø 

æ
ç
ç
è 

d_{2k} d_{2n2k2} 
ö
÷
÷
ø 
= 1 + t^{2} D(t)^{2}.

This quadratic equation is easily solved for D(t):
D(t) = 
1 ± (14t^{2})^{1/2} 

2t^{2} 

. 
The solution 1  (14t^{2})^{1/2}/2t^{2} is chosen
in order to ascertain the existence of a Taylor series
expansion at t=0.
It is known [2, 7, 8, 10, 11]
that the number of Dyck paths of length 2n is c_{n},
the nth Catalan number, given by c_{n} = 1/n+1().
2.3 Enumeration of Dyck prefixes
Let b_{n,k} be the number of prefixes of length n, with final
height k. Then

b_{n,0} 
= d_{n} (Dyck paths) 









F(t,u) 
= 

b_{n,k} t^{n} u^{k} Î Q [[t,u]]
= 
æ
ç
ç
è 

t^{n} 
ö
÷
÷
ø 

æ
ç
ç
è 

b_{n,k} u^{k} 
ö
÷
÷
ø 
Î Q [u][[t]]












which is a series in t whose coefficients are polynomials in u.
The last equation is equivalent to:
F(t,u) = 1 + t(u + u^{1}) F(t,u)  tu^{1} F(t,0),
which defines the generating function F(t,u) for these paths, counted
by their length (variable t) and their height (variable u).
This equation uniquely defines F(t,u) as a power series in t with
polynomial coefficients in u.
More constraints can be imposed on such Dyck prefixes.
2.3.1 Dyck Paths with no peaks at height m
Let G_{m}(x) = å_{n ³ 0} g(m,n)x^{n} be the generating function
for Dyck paths of length 2n with no peaks at height m for some fixed m ³ 1.
We proceed to show that
This can be illustrated by a path starting with a NorthEast step
followed by a segment which represents any Dyck path of length
2k, 0 £ k £ n1, with no peaks at height m1.
This segment is followed, after a SouthEast step,
by a second segment which represents
any Dyck path of length 2n22k with no peaks at height m.
Therefore
g(m,0) = 1
and
g(m,n) = 

g(m1,k)g(m,n1k) = [x^{n1}] 
( 
G_{m1}(x)G_{m}(x) 
) 
.

Thus,
G_{m}(x) = 1+xG_{m1}(x)G_{m}(x),
or equivalently,
This way, the number of Dyck paths of length 2n with no peaks at height
1 is the Fine number f_{n} for n ³ 0.
Obviously, g(1,0) = 1 and g(1,1) = 0. For n ³ 2,
a Dyck path of length 2n with no peaks at height 1 has a
segment representing any Dyck path of length 2k, 1 £ k £ n1,
and a second segment representing a Dyck path of length 2n2k2
with no peaks at height 1.
Therefore, for n ³ 2, we have

g(w,n) 











= [x^{n1}] 
( 
C(x)G_{1}(x) 
) 
 g(1,n1) 











= [x^{n}] 
( 
xC(x)G_{1}(x) 
) 
 g(1,n1).












Therefore,

G_{1}(x) 
= 1 + 

g(1,n)x^{n} = 1+xC(x)G_{1}(x) xxG_{1}(x) +x 











= 1 + xG_{1}(x) 
( 
C(x)  1 
) 
= 1 + xG_{1}(x)xC^{2}(x).












That is,
2.3.2 No peaks at height 2
Another extension establishes that the number of Dyck paths
of length 2n with no peaks at height 2 is the
Catalan number c_{n1}, for n ³ 1.
This can be shown [10] using the first extension, so that
2.4 Bilateral paths or bridges
A bridge is a path whose end point P_{n} lies on the xaxis.
Given a class C of paths, we let C_{n}
denote the subclass of paths that have size n,
and C_{n,k} Ì C those that have
final altitude equal to k.
We introduce the corresponding ordinary generating functions:
C(z) = 

C_{n} z^{n}, uC(z,u) = 

C_{n,k}
u^{k} z^{n}. 
By characterising these generating functions, that are algebraic in
the case of bridges, a strong algebraic
decomposition prevails, which renders the calculation of the generating function's effective.
The decomposability of generating function's makes it possible to extract their singular structure,
and to solve the corresponding asymptotic enumeration problems.
The equation corresponding to such a lattice path is:
B(t) = 1 + t^{2}D(t)B(t)+t^{2}B(t)D(t) = 

. 
For D(t) = 1 ± (14t^{2})^{1/2}/2t^{2},
B(t) = 
1 

1  1 ± (1  4t^{2})^{1/2} 

=


= 

t^{2n} 

. 
Alternatively, since (14t^{2})^{1/2} = 1  2t^{2}  2t^{4} + O(t^{6}),
we can find for Dyck paths:
D(t) = 
1 +12t^{2} 2t^{4} + O(t^{6}) 

2t^{2} 

= 

+ 1  t^{2} + O(t^{4}) 
or
D(t) = 
1  (14t^{2})^{1/2} 

2t^{2} 

, 
which
is the result we found before.
3 Lagrange Inversion Formula
Inherently to the symbolic method, the extraction of coefficients
of generating functions defined by functional equations is a frequently occurring problem.
For this purpose, the Lagrange Inversion Theorem provides a tool that is commonly used
and especially dedicated to the enumeration of trees.
This theorem states that given the generating function A(z) = å_{n ³ 0} a_{n} z^{n}
for which z = f(A(z)), if f(z) verifies the condition f(0) = 0
and f'(0) ¹ 0, then
a_{n} º [z^{n}] A(z) =


[u^{n1}] 
æ
ç
ç
è 

ö
÷
÷
ø 
^{n}. 
Additionally,
[z^{n}] 
( 
A(z) 
) 
^{m} = 

[u^{nm}] 
æ
ç
ç
è 

ö
÷
÷
ø 
^{n}

and
[z^{n}] g 
( 
A(z) 
) 
= 

[u^{n1}]g'(u) 
æ
ç
ç
è 

ö
÷
÷
ø 
^{n}.

By application of the reciprocal function to both sides of the
equation z = f(A(z)), it can be noticed that the function
A(z) is the reciprocal of f(z). The surprising effect of the
inversion theorem resides in the relation it establishes between the
powers of a function and the coefficients of the reciprocal function.
3.1 Example: Catalan numbers
The language of Dyck words,
satisfies the defining recurrence D = e+xDx^{_}D.
This translates to the algebraic (noncommutative) equation
D(x, 

) = 1 + x D(x, 

) 

D(x, 

).

Since we have an algebraic and nonambiguous grammar, we can rewrite the system
with commutative variables:
D(x, 

) = 1 + x 

D(x, 

)^{2}.

As we know that the length of the words is always even, we will have n for
a total length of 2n, when we only count x (or x^{_}). Thus, we can
substitute x^{_} for e, and x for t.
D(t) = 1 + t 
( 
D(t) 
) 
^{2} ÜÞ tD(t)^{2}D(t)+1=0

By simply solving this secondorder equation, we get D(t) = 1
 (14t)^{1/2}/2t (the other root is negative, hence not
applicable). This solution is to converted into the form D(t) =
å_{n ³ 0} a_{n} t^{n}, for which a_{n} gives us the number of Dyck
words having n letters t (x), hence the number of Dyck words of
length 2n. Using Taylor series expansion and applying the Lagrange
Inversion Formula, we get C_{n}
[z^{n}]C(t)=[z^{n}] 

z^{n1} (1+z)^{2n}= 



. 
4 Algebraic Structures and the Kernel Method
4.1 Algebraic equations
The equation describing subdiagonal NorthEast paths,
F(t,u) = 1 + t(u + 1/u) F(t,u)  t/u F(t,0),
belongs to a class of equations that share two properties [3]:

The equation uniquely defines F(t,u) as a power series in t with
polynomial coefficients in u. There exist other, nonpowerseries solutions, for instance
the rational function
Hence, any method for solving the recurrence relation above must use the fact that
F(t,u) is a power series.
 When trying to derive an equation in F(t,0) only from the recurrence relation,
we end up with a tautologic expression. In other words, if we first multiply
F(t,u) by u and directly set u = 0, this would give us 0 = tF(t,0)  tF(t,0).
It can be noticed that the recurrence relation is linear in F(t,u) and F(t,0), and
we can strongly expect its solution to be algebraic and to satisfy
F(t,0) = 
1  (14t^{2})^{1/2} 

2t^{2} 

= 




,

since subdiagonal walks ending on the main diagonal are wellknown to be counted
by Catalan numbers.
The generic form of equations that share the above properties, is
P 
( 
F(t,u),F_{1}(t),F_{2}(t),...,F_{k}(t),t,u 
) 
= 0, 
where P is a polynomial in k + 3 variables with real coefficients.
We assume that this equation defines uniquely all its unknowns as power series in t:
the series F_{i}(t) have real coefficients, while F(t,u) has its coefficients
in R [u].
Rewriting our equation according to this generic form of equations yields:
F(t,u) 
( 
u  t(u^{2} + 1) 
) 
 u + tF_{1}(t) = 0, 
with F_{1}(t) = F(t,0), by setting u = 0.
In solving this instance, we propose to determine f_{n},
the number of excursions of length n and type W,
the set of jumps which is a finite subset of Z, via the corresponding
bivariate generating function
F(z,u) = 

f_{n,k} u^{k} z^{n}, 
where f_{n,k} is the number of walks of length n and final altitude k.
In particular, F(z) = F(z,0). Let c denote the smallest (negative) value
of a jump, and d denote the largest (positive) jump. A functional role is played
by the ``characteristic polynomial'' of the walk
[1, 2, 11],
S(y) = 

y^{w}
= 

S_{j} y^{j}, 
which is a Laurent polynomial. The bivariate generating function of generalised walks where intermediate
values are allowed to be negative is rational:
The main result to be proven is the following: for each finite set W Ì Z,
the generating function of excursions is an algebraic function that is explicitly
computable from W. This problem is solved by an application
of the kernel method [2].
4.2 Kernel method
[2].
Let f_{n}(u) = [z^{n}]F(z,u) be the generating function of walks of length n with
u recording the final altitude.
There is a simple recurrence relating f_{n+1}(u) to f_{n}(u),
namely,
f_{n+1}(u) = S(u) f_{n}(u)  r_{n}(u)
where r_{n}(u) is a Laurent polynomial consisting of the sum of all the monomials of
S(u)f_{n}(u) that involve negative powers of u:
r_{n}(u) = 


( 
[u^{j}] S(u)f_{n}(u) 
) 
u^{j} =
{u^{<0}}S(u)f_{n}(u),

where {u^{<0}} denotes the singular part of a Laurent expansion:
{u^{<0}}f(z) := 

( 
[u^{j}]f(u) 
) 
u^{j}. 
The idea behind the formula is to subtract the effect of those steps that would
take the walk below the horizontal axis. Thus the generating function F(z,u) satisfies the fundamental
functional equation
F(z,u) = 1 + zS(u)F(z,u)  z{u^{<0}} 
( 
S(u)F(z,u) 
) 
. 
Explicitly, we have
F(z,u) = 1 + zS(u)F(z,u) 
z 

l_{j} (u) 
æ
ç
ç
è 


F(z,u) 
ö
÷
÷
ø 
_{u=0}, 
for Laurent polynomials l_{j}(u) that depend on S(u) in an
effective way by l_{j}(u) = 1/j!{u^{<0}}u^{j}S(u) [2].
Both equations involve an unknown bivariate generating
function F(z,u) and c univariate generating functions, the partial
derivatives of F specialized at u=0. In particular, the latter
functional equation determines fully the c+1 unknowns. The basic
technique is known as ``cancelling the kernel'' and relies on strong
analyticity properties.
The equation to be used by the basic kernel technique starts by
grouping on one side the terms involving F(z,u). The main principle
of the kernel method consists in coupling the values of z and u in
such a way that 1zS(u)=0, so that F(z,u)
disappears. Consequently, the ``kernel equation'' 1zS(u)=0, is
rewritten as u^{c} = z(u^{c}S(u)). This kernel equation
defines c+d branches of an algebraic function. Coupling z and u
by u = u_{l}(z) gives that (z,u) is close to (0,0) where F is
bivariate analytic, so that substitution gives
1z 

l_{j} 
( 
u_{l}(z) 
) 
æ
ç
ç
è 

F(z,u) 
ö
÷
÷
ø 
_{u=0}, l=0,...,c1, 
which is a linear system of c equations in c unknowns with algebraic coefficients
that determines F(z,0).
Therefore, the generating function of excursions is expressible as
F(z) = 



u_{l}(z),
where S_{c} = [u^{c}]S(u) 
is the multiplicity of the smallest
element c Î W.
More generally the bivariate generating function of nonnegative walks is bivariate algebraic and given by
F(z,u) = 



( 
u  u_{l}(z) 
) 
. 
In other words, to make explicit the solution F_{s} of the recurrence
of the subdiagonal NorthEast paths, written as F(t,u) (u  t(u^{2} + 1))  u + tF_{1}(t) = 0,
we rewrite it as Q(x)F(x) = K(x)U(x) [4],
where K stands for the unknown initial conditions, and Q is the kernel:
F(t,u) 
( 
u  t(u^{2} + 1) 
) 
= u  U(t), 
F_{s}(t) Q(t) = K(t)  U(t).
Again, the kernel method consists in cancelling the kernel Q(x),
by handling a choice of algebraic values a of t,
which yields a system of equations K(a)  U(a) = 0.
Solving this system generally allows to make U explicit.
This provides F_{s} for generic t:
The function U(t) is a sum of m unknown multivariate
functions F_{i}(t_{1},...,t_{d1}). Cancelling the kernel with m
different values for t_{d} (which then become functions of (t_{1},...,t_{d1}))
yields a system which allows to make explicit the F_{i}'s.
Regrouping the terms in F(t,u) by the kernel method yields:
4.3 The Quadratic Method
An analogous approach is referred to as the ``quadratic method,'' used
to solve equations of the form
z(x,y)^{2} + P_{1} 
( 
x,y,z(x,0) 
) 
z(x,y) + P_{2} 
( 
x,y,z(x,0) 
) 
= 0 
with P_{i} Î F[[x]][y,u], where F is an algebraically closed
field of characteristic zero.
Rewrite the equation as
æ
ç
ç
è 
z+ 

P_{1} 
ö
÷
÷
ø 
^{2}= 

P_{1}^{2}P_{2}=:DÎF[[x]][y,u]. 
If some y=y_{0}ÎF[[x]] is known to kill z+1/2P_{1}, then
this y_{0} is a double root of D(x,y,u), viewed as a polynomial
in (F[[x]][u])[y]. The resultant R(x,u) of D
and ¶D/¶ y with respect to y has to be
zero. When we know by an external argument that the quadratic
equation admits a series solutions z(x,y)ÎF[[x,y]], for example
when it has a combinatorial interpretation, and therefore that
z(x,0) is a series in F[[x]], the polynomial equation
R(x,z(x,0))=0 delivers this value in F[[x]]
for z(x,0).
After substitution, there only remains to solve an equation of the
form z^{2} + P_{1}z + P_{2} = 0 with P_{i} Î F[[x]][y].
In [5], necessary and sufficient conditions are derived in
order that such an equation has a solution z in either of the rings
F[[x]][y] or F[[x,y]]. In view of obtaining them, resume from
the relation (z+1/2P_{1})^{2}=D. Since
P_{1}ÎF[[x]][y]ÌF[[x,y]], we get that there is a solution
in F[[x]][y] or F[[x,y]], respectively, if and only if
D has a square root in the same ring. Again in [5],
it is proved that UÎF[[x]][y] has a square root if and only if
it factors under the form U=P^{2}R for a polynomial PÎF[x,y] and
a series RÎ1+yF[[x]][y]. Therefore, the equation has a solution
in F[[x]][y] or F[[x,y]], respectively, if and only if
D rewrites under the form P^{2}R for some polynomial P and
some series R of the form
R=1+yF[[x]][y] or R=1+xyF[[x]][y],
respectively.
References
 [1]

Banderier (C.), BousquetMélou (M.), Denise (A.), Flajolet (P.), Gardy
(D.), and GouyouBeauchamps (D.). 
Generating functions for generating trees. Discrete
Mathematics. 
25 pages. To appear.
 [2]

Banderier (Cyril) and Flajolet (Philippe). 
Basic analytic combinatorics of directed lattice paths. 
Available from
http://algo.inria.fr/flajolet/Publications/BaFl01.ps.gz
, August
2001. 39 pages. Accepted for publication in Theoretical
Computer Science.
 [3]

BousquetMélou (Mireille). 
On (some) functional equations arising in enumerative
combinatorics. 
In preparation. Extended abstract for FPSAC'2001 available from
http://deptinfo.labri.ubordeaux.fr/~bousquet/
.
 [4]

BousquetMélou (Mireille) and Petkovsek (Marko). 
Linear recurrences with constant coefficients: the multivariate case.
Discrete Mathematics, vol. 225, n°13, 2000,
pp. 5175. 
Formal power series and algebraic combinatorics (Toronto, ON, 1998).
 [5]

Brown (William G.). 
On the existence of square roots in certain rings of power series.
Mathematische Annalen, vol. 158, 1965, pp. 8289.
 [6]

Cori (Robert) and Richard (Jean). 
Énumération des graphes planaires à l'aide des séries
formelles en variables non commutatives. Discrete Mathematics, vol. 2,
1972, pp. 115162.
 [7]

Deutsch (Emeric). 
Dyck path enumeration. Discrete Mathematics, vol. 204,
n°13, 1999, pp. 167202.
 [8]

Duchon (Philippe). 
On the enumeration and generation of generalized Dyck words. Discrete Mathematics, vol. 225, n°13, 2000,
pp. 121135. 
Formal power series and algebraic combinatorics (Toronto, ON, 1998).
 [9]

Dvoretzky (A.) and Motzkin (Th.). 
A problem of arrangements. Duke Mathematical Journal, vol. 14,
1947, pp. 305313.
 [10]

Peart (Paul) and Woan (WenJin). 
Dyck paths with no peaks at height k. Journal of Integer
Sequences, vol. 4, n°1, 2001. 
Article 01.1.3. 6 pages.
 [11]

Sedgewick (Robert) and Flajolet (Philippe). 
An introduction to the analysis of algorithms. 
AddisonWesley Publishing Co., Reading, MA, 1996.
 *
 Lecture notes for a course given during the workshop
ALÉA'01 in Luminy (France).
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.