Symbolic Enumerative Combinatorics and Complex Asymptotic Analysis^{*}
Philippe Flajolet
Projet
Algo,
Inria Rocquencourt (France)
Algorithms Seminar
March 26 and 27, 2001
[summary by Yvan Le Borgne]
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
Complex analysis is a fruitful source of asymptotic estimates in
enumerative combinatorics. This lecture starts with a symbolic method
to encode counting sequences of combinatorial structures by complex
functions. The residue theorem is then applied to extract from these
functions the asymptotic behavior of the corresponding
sequences.^{1}
A class of combinatorial structures (often simply called a
class) is a finite or countable set on which a size
function is defined, the size of an element being a nonnegative
integer. If A is a class, the size of an element a Î A
is denoted by a, or a_{A} in the few cases where
the underlying class needs to be made explicit. Given a class A we
consistently let A_{n} be the set of elements in A that have
size n and use the same group of letters for the counts A_{n} =
CardA_{n}. We further assume that the A_{n} are all finite. The
counting sequence of A is the sequence of integers
{A_{n}}_{n ³ 0}. For instance, binary sequences are
combinatorial structures that form a class S when the size of a
word is defined to be its length. The corresponding counting sequence
is then given by S_{n}=2^{n}.
Averagecase analysis of algorithms typically reduces to counting
problems for combinatorial structures. Statistical physics is another
field of application of counting sequences where the free energy of a
system may be expressed as the logarithm of the number of accessible
states which can be described by a combinatorial structure.
There are two main approaches to estimate the asymptotic behavior of
the counting sequence of a class. The first one is to embed the
combinatorial structure in a stochastic model where the randomly
chosen element is representative of the elements of the class. This
allows to eliminate rare pathological elements. Then the asymptotic
behavior of the counting sequence is deduced from the behavior of the
stochastic model. The second approach, which will be described here,
is based on the decomposition of elements of the class into
combination of elements of simpler classes and lower size. Counting
sequences are encoded by formal generating functions that can have
tractable compact representations as complex functions. A restriction
to certain combinations, called admissible constructions, preserves
these tractable representations since they directly translate into
simple operators on the complex functions of the subclasses. The
extraction of the counting sequence encoded by a complex function is
sometimes difficult, but complex analysis can often be used to obtain
the asymptotic behavior.
This summary presents in the first section a symbolic method to
compute a function encoding the counting sequence of a class. The
second section is dedicated to complex analysis. The aim is to give a
method to extract the asymptotic behavior of a counting sequence
encoded by a complex function. The final section illustrates these
methods throughout two examples: clouds and Wtrees.
1 A Symbolic Method for Enumerative Combinatorics
A counting sequence {A_{n}}_{n³ 0} can be encoded by different
types of formal power series: an ordinary generating function å_{n
³ 0} A_{n}z^{n}, an exponential generating function å_{n ³ 0}
A_{n}/n!z^{n}, a Dirichlet series å_{n³
0}A_{n}/n^{z}, ... The aim of these representations is to
lead in some cases to a description of a counting sequence shorter
than the sequence itself. For instance the class N of natural
integers, where the size of n is n, is such that N_{n} = 1. Its
ordinary generating function is å_{n³ 0}z^{n} =1/1z, its
exponential generating function is å_{n³ 0}1/n!z^{n} =
e^{z}, its Dirichlet series å_{n³ 0}1/n^{z}=z(z).
Assume that F is a binary construction that associates to two
classes B and C a new class
A =F{B,C},
in a finite way (each A_{n} depends on finitely many of the B_{n}
and C_{n}). Then F is an admissible construction if
and only if the counting sequence {A_{n}} of A is a function of
the counting sequences {B_{n}} and {C_{n}} of B and C
only. In that case, this function may be translated into a simple
operator relating formal power series representing {A_{n}}_{n³
0}, {B_{n}}_{n³ 0}, and {C_{n}}_{n³ 0}. This section is
devoted to some particular admissible constructions in the case of
unlabeled and labeled combinatorial structures. The goal is to define
a language of elementary combinatorial constructions such that any
expression of a class in this language can be translated
straightforwardly into a function encoding the counting sequence of
the class.
1.1 Unlabeled structures
The principle of this representation is that an element of size n is
encoded by the monomial z^{n}. Thus the class A is mapped
to the ordinary generating function
A(z)=ogf(A 
)(z)= 

z^{a}= 

A_{n}z^{n}. 
An additional assumption on the sizes is made: if an element a
can be decomposed into a combination of elements b_{1},
b_{2}, ..., b_{k}, then the size of a is the sum of
the sizes of the b_{i}. Its translation as regards monomials is
the usual product law:
z^{aA} = z^{b1B1}
z^{b2B2}... z^{bkBk}.
Let us consider the class A defined as the Cartesian
product of two given classes B and C. Following the
additional assumption, the size of the element a =
(b,g) is b_{B}+g_{C}. Thus we have
A(z) =


z^{(b,g)A}
= 

z^{bB+gC}
= 

z^{bB}· 

z^{gC}
= B(z)C(z).

Here is the first example of an admissible construction which has a
simple translation in terms of ordinary generating functions:
ogf(B×C)(z) = ogf(B)(z)·ogf(C)(z).
The union of two classes B and C is translated into
the sum of the two ordinary generating functions in the case of a
disjoint union. More generally,
ogf(BÈC 
)(z)= 

z^{aA}
= 

z^{bB}
+ 

z^{gC}
 

z^{aBÈC}
= ogf(B) + ogf(C)  ogf(BÇC).

The additional assumption on the sizes implies that the size of an
element a of BÇC is well defined since a_{B}=
a_{BÈC} = a_{C}.
The class A of finite sequences of elements of the class
B is denoted Seq(B). It is well defined if and only if the
class B has no element of size zero, a restriction which prevents
from getting an infinite number of sequences of size zero. Grouping
sequences of the same length yields the relation
Seq(B) = {e} È B È (B×B) È
(B×B×B)È···,
where e is an element of size zero which has essentially the
same meaning as the empty word in the context of languages. Thus,
using both previous constructions,
ogf 
( 
Seq(B) 
) 
= 1 + ogf(B) + ogf(B)^{2} + ogf(B 
)^{3}
+ ... = 

ogf(B)^{k} = 

.

The class A of subsets of the class B is denoted
Set(B). The class of directed cycles of the class B
is denoted Cycle(B). Directed cycles are sequences defined up to
cyclic permutations: two sequences (a_{1},...,a_{k}) and
(b_{1},...,b_{k}) represent the same directed cycle if and
only if there exists an integer l such that for all i, a_{i}
=b_{i+lmodk}. These two constructions admit almost reasonable
translations mentioned at the end of this section.
1.2 Labeled structures
Many objects of classical combinatorics present themselves naturally
as labeled structures whose ``atom'' (typically nodes in a graph or a
tree) bear distinctive integer labels. For instance the cycle
decomposition of a permutation represents the permutation as an
unordered collection of cyclic graphs whose nodes are labeled by
integers. More precisely, an element of size n of a labeled
structure can be decomposed in n ``atomic'' elements of size 1 and
these atoms are labeled by distinct elements of {1,...,n}.
Operation on labeled structures are based on a special product, the
labeled (or partionnal) product that distributes
labels between components. This operation is a natural analogue of the
Cartesian product for plain unlabeled structures. The labeled product
in turn leads to labeled analogues of the sequence, set, and cycle
constructions.
Let us define the labeled product A = BÄC of two classes
B and C. The ordered pair (b,g), for bÎB
and gÎC, is not a labeled structure since atoms of b,
respectively g, have labels in {1,...,b},
respectively {1,...,g}, leading to atoms with
common labels. A natural lift of these two labelings, is a labeling
with labels in {1,...,b+g} such that the
order relation between labels of b, respectively g, are
preserved. These labeled structures are the elements of the labeled
product. For instance, consider the class of chains which are total
orderings of the elements of {1,...,k} for all integers k. The
pair consisting of the two chains (2,1) and (1) is not a labeled
structure: ((2,1),(1)) has two atoms labeled 1. On the
other hand, three natural expansions lead to labeled structures:
((2,1),(3)), ((3,1),(2)), and
((3,2),(1)).
Any element of A has a unique decomposition into elements of
B×C. But conversely, the pair of an element of B of
size k and an element of C of size l, is the decomposition of
as many elements as there are possibilities to label (b,g)
by {1,...,l+k} in a way that preserves the labeling induced on
b and g. So there are (k+l)!/k! l! such
decompositions. As regards the counting sequence, an element of
size n of A decomposes into a pair of elements of size k
and l such that k+l=n, so that
This equation can be rewritten as
The use of exponential generating functions to encode the counting
sequences is then natural because the previous equation characterizes
the product of two such functions. So the counting sequence
{A_{n}}_{n³ 0} is represented by A(z) = egf(A)(z) =
å_{n³ 0}A_{n}/n!, which was chosen such that
egf(BÄC) = egf(B)· egf(C).
The same work as for unlabeled structures leads to the results
summarized in Table 1.
Construction 
Unlabeled structures 
Labeled structures 
Product 
ogf(B)·ogf(C) 
egf(B)·egf(C) 
Union 
ogf(B)+ogf(C) 
egf(B)+egf(C) 
Sequence 
1/1ogf(B)(z) 
1/1egf(B)(z) 
Set 
exp(å_{k=1}^{¥}(1)^{k+1}/kogf(B)(z^{k})) 
exp(egf(B)(z)) 
Cycle 
å_{k=1}^{¥}f(k)/klog(1/1ogf(B)(z^{k})) 
log1/1egf(B)(z) 
Table 1: Admissible constructions and generating functions interpretations.
2 Complex Asymptotic Analysis
Once a function encoding the counting sequence has been determined, it
remains to extract the sequence from the function. The explicit
expansion of the function is often too difficult. To avoid it, the
crucial observation is that most of the generating functions that
occur in combinatorial enumerations are also analytic
functions: their expansions converge in a neighborhood of the
origin and Cauchy's integral formula expresses Taylor coefficients of
such analytic functions as contour integrals.
This section is dedicated to a short presentation of analytic
functions, then to the determination of the exponential growth of the
counting sequence, and finally to the subexponential factors.
2.1 Residue theorem
A function f(z) of the complex variable z is analytic at
a point z=a if it is defined in a neighborhood of z=a and is given
there by a convergent power series expansion
The quotient of two analytic functions f(z)/g(z) gives the intuition
of what is a meromorphic function. More precisely, h(z) is
meromorphic at z=a if and only if in a neighborhood of
z=a it is given by an expansion of the form
h(z) = 

h_{n}(za)^{n} for z¹ a. 
If M ³ 1 and h_{M}¹ 0 then h(z) is said to have a
pole of order M at z = a. When h(z) has a pole of
order M ³ 1 at z = a, then the coefficient h_{1} is called
the residue of h(z) at z=a and it is designated by
The important residue theorem relates global properties of a meromorphic function (its integral along curves) to its local properties at designated points, the poles.
Theorem 1 [Cauchy's residue theorem]
Let G be a simple closed curve oriented positively and
situated inside a simply connected region D (like a disk), and
assume g(z) to be meromorphic in D and analytic on
G. Then

ó
õ 

g(z) dz = 

Res 
[ 
g(z); z = s 
] 
, 
where the sum is extended to all poles of g(z) enclosed in G.
A direct application of the residue theorem concerns coefficients of analytic functions.
Theorem 2 [Cauchy's coefficient formula]
Let f(z) be analytic in a simply connected region D and let
G be a closed curve oriented positively and located inside D
that simply encircles the origin. Then the coefficient [z^{n}] f(z)
admits the integral representation
f_{n}º[z^{n}] f(z) = 

ó
õ 

f(z) 

. 
2.2 Singularities and exponential rate
Most of the counting sequences encoded by functions have an asymptotic
behavior that can be described by A_{n} ~ G^{n}q(n) where
q(n) is a subexponential function: the real number
G=limsup_{n®+¥}f_{n}^{1/n} is called the
exponential rate of growth of the counting sequence.
This parameter has a straightforward interpretation as regards the
function which encodes the counting sequence. A singularity
of such a function can be informally defined as a point where the
function ceases to be analytic. Singularities of smallest modulus of a
function analytic at 0 are called dominant singularities.
The exponential rate of growth is linked to the modulus of dominant
singularities by the following theorem.
Theorem 3 [Exponential growth formula] If f(z) is analytic
at 0 and R is the modulus of a singularity of f(z) nearest to
the origin, then the exponential rate of growth of the coefficients
[z^{n}] f(z) is 1/R.
Proof.
Cauchy's formula applied
to a circle G of center 0 and radius R'<R gives
f_{n}= 
½
½
½
½
½
½ 

ó
õ 

f(z) 

½
½
½
½
½
½ 
£ 

sup 
{ 
f(z)  z=R' 
} 
R'^{(n+1)}
=O 
( 
R'^{n} 
) 
,

so that G=limsup_{n}f_{n}^{1/n}£1/R', and G£1/R by
letting R' approach R.
We now assume G<1/R and proceed to get a contraction,
proving G=1/R in this way. Fix R' such that
G<1/R'<1/R. For some constant K and all sufficiently
large n, we have f_{n}£K/R'^{n}. The series
å_{n³0}f_{n}z^{n} therefore converges normally on the set of
all z of modulus R, since 0<R/R'<1. This contradicts the
existence of a singularity of modulus R.
An additional property of functions defined by counting sequences is
that their coefficients are nonnegative. This situation allows to
locate one dominant singularity more precisely.
Theorem 4 [Pringsheim's theorem]
If a function has Taylor
coefficients that are real nonnegative, then one of its dominant
singularities, if there is a singularity, is real positive.
2.3 Subexponential approximation
If the location of the singularities of a function determines the
exponential rate of growth of its coefficients, the nature of the
singularities determines the way the dominant exponential term in
coefficients is modulated by a subexponential factor.
For sake of simplicity, we assume that the singularities are
isolated. By change of the variable, we can assume that all the
dominant singularities are of modulus 1. Moreover we assume that
there is a unique dominant singularity which is 1.
The notion of Danalytic function is defined to describe the
scope of the following transfer theorem which maps the local behavior
of the function around its dominant singularity to the asymptotic form
of its coefficients. Given two numbers f, R, with R>1
and 0<f<p/2, the open domain D(f,R) is defined as
D(f,R) = 
{ 
z  z<R, z¹ 1,

 
Arg(z1) 
 
>f 
} 
.

A domain is a Ddomain if it is a D(f,R) for
some R and some f. A function is Danalytic if
it is analytic in some Ddomain.
Theorem 5 [Bigoh transfer [1]]
Let a be a number not in {0,1,2,...}. Assume that
f(z) is Danalytic and that it satisfies in the intersection
of a neighbourhood of 1 and of its Ddomain the condition
f(z) = O 
æ
ç
ç
è 
(1z)^{a} 
æ
ç
ç
è 
log 

ö
÷
÷
ø 
^{b} 
ö
÷
÷
ø 
. 
Then
[z^{n}] f(z) = O 
( 
n^{a1}(logn)^{b} 
) 
. 
Proof.
The starting point is Cauchy's coefficient formula. We apply it to a
particular loop around the origin which is internal to the
Ddomain of f: we choose the positively oriented contour
g_{n} º g =
g_{1} + g_{2} + g_{3} + g_{4}, with

ì
ï
ï
ï
ï
ï
í
ï
ï
ï
ï
ï
î 
g_{1}= 
ì
í
î 
z  z1= 


 
Arg(z1) 
 
³q 
ü
ý
þ 

g_{2}= 
ì
í
î 
z  

£ z1, z£ r, Arg(z1) = q 
ü
ý
þ 

g_{3}= 
{ 
z  z1=r, 
 
Arg(z1) 
 
³q 
} 

g_{4}= 
ì
í
î 
z  

£ z1, z£ r, Arg(z1)=q 
ü
ý
þ 



If the Ddomain of f is D(f,R), we assume that
1<r<R, and f<q<p/2, so that the contour g
lies entirely inside the domain of analycity of f.
For j = 1, 2, 3, 4, let
The analysis proceeds by bounding the absolute value of the integral along each of the four parts. In order to keep notations simple, we detail the proof in the case where b = 0.
Inner circle.
From trivial bounds, the contribution there is
 
f_{n}^{(1)} 
 
= O 
æ
ç
ç
è 
æ
ç
ç
è 

ö
÷
÷
ø 
^{1a} 
ö
÷
÷
ø 
, 
as the function f is
O((1/n)^{a}), the contour has
length O(1/n), and z^{n1} is O(1) there.
Function f(z) 
Asymptotic expansion of the coefficients f_{n} 
1 
0 
(1z)^{1} 
1 
(1z)^{2} 
n+1 
(1z)^{3} 
1/2n^{2}+3/2n+1 
(1z)^{1/2} 
1/(p n^{3})^{1/2}(1/2+3/16n+25/256n^{2}+O(1/n^{3})) 
(1z)^{1/2} 
1/(p n)^{1/2}(11/8n+1/128n^{2}+5/1024n^{3}+O(1/n^{4})) 
log(1z)^{1} 
1/n 
(1z)^{3/2}log(1z)^{1} 
(n/p)^{1/2}(2logn+2g+4log22+3logn/4n+ O(1/n)) 
Table 2: Examples of applications of the transfer theorem.
Rectilinear parts.
Setting w = e^{iq} and
performing the change of variable z = 1+w t/n, we find

 
f_{n}^{(2)} 
 
<


ó
õ 

K 
æ
ç
ç
è 

ö
÷
÷
ø 
^{a} 
½
½
½
½ 
1+ 

½
½
½
½ 
^{n1} dt,

for some constant K > 0 such that f(z) <
K(1z)^{a} ``over the Ddomain.'' In fact we have a
constant for a small neighborhood V of 1 due to the asymptotic
assumption and an other constant that comes from the compacity of a
closed set C included in D such that all the used loops are
in CÈ V. From the relation
½
½
½
½ 
1+ 

½
½
½
½ 
³ 1+ 

cosq, 
there results
 
f_{n}^{(2)} 
 
< 

J_{n}n^{a1} 
where
J_{n}= 
ó
õ 

t^{a} 
æ
ç
ç
è 
1+ 

ö
÷
÷
ø 
^{n} dt. 
For a given a, the integrals J_{n} are all bounded above by some constant since they admit a limit as n tends to infinity:
J_{n} ® 
ó
õ 

t^{a}e^{tcosq} dt. 
(The condition on q that 0<q<p/2 precisely
ensures convergence of the integral.) Thus, globally, on this part of
the contour, we have
 
f_{n}^{(2)} 
 
= O 
( 
n^{a1} 
) 
, 
and the same bound holds for f_{n}^{(4)} by symmetry.
Outer circle.
There, f(z) is bounded while z^{n} is
of the order r^{n}. Thus, f_{n}^{(3)} is exponentially small.
In summary, each of the four integrals of the split contour
contributes O(n^{a1}). The statement of the theorem thus
follows.
This theorem can be extended to equivalents giving a fairly mechanical
process to translate aymptotic information on a function into
information on its coefficients. These are simple functions that are
used as a scale since any function equivalent to it around its
dominant singularity as the same asymptotic expansion. See
Table 2.
3 Examples
3.1 Clouds
Let us consider n lines in general position in the plane. A
cloud is a subset of the set of the intersection points of
the lines such that:

any three points of the cloud are not aligned;
 any line has at least one of its points in the cloud;
 the set is maximal for inclusion among the sets that
satisfies points 1 and 2.
The size of a cloud is the number of points it contains.
There is a more combinatorial description of a cloud since they are in
bijection with labeled 2regular graphs (any vertex has degree 2, no
loops, no multiple edges). In the bijection, the line labeled i is
the vertex labeled i of the graph and the intersection between the
line i and j is mapped to an edge between i and j. Indeed,
point 1 in the definition exactly means that any vertex of the graph
has degree at most 2 because three aligned intersections are
necessarily on a common line since the picture is as general as
possible. Point 2 translates the fact that any vertex has degree at
least 1. Assume there are at least two vertices i, j of degree 1
in the cloud S. Then SÈ{(ij)} is a cloud and that is in
contradiction with point 3. Finally, there cannot be only one vertex
of degree 1 since the sum of the degree of vertices of a graph is
even (each edge appears twice). As regards the size, since there are
two intersections per line in a cloud and that an intersection is
shared by two lines, the size of the cloud is the number of
vertices. Thus instead of clouds we could equivalently consider the
class of labeled 2regular graphs where the size of an element is its
number of vertices.
A labeled 2regular graph is a set of nonoriented cycles of size at
least 3 and we are interested in the exponential generating function
of this structure. Oriented cycles of size at least 3 are the oriented
cycles that do not contain 1 or 2 elements only so their generating
function is
C_{+}^{>2}(z) = log 

 
æ
ç
ç
è 

z+ 

z^{2} 
ö
÷
÷
ø 
. 
A nonoriented cycle of at least 3 vertices admits exactly 2 distinct
orientations, so that the generating function of nonoriented cycle of at
least 3 vertices is
C^{>2}(z) = 

C_{+}^{>2}(z). 
Then the series of the sets of nonoriented cycles on at least
3 vertices and equivalently of the clouds is
Clouds(z) = expC^{>2}(z) =

exp 
æ
ç
ç
è 
 

z 

z^{2} 
ö
÷
÷
ø 


(1z)^{1/2} 

.

Thus, Clouds(z) is the product of 1/(1z)^{1/2} which
admits 1 as singularity of minimal modulus and is analytic in C
\ [ 1,+¥), and exp(1/2z1/4z^{2})
that is entire. The behavior of Clouds(z) around 1 is the product
of 1/(1z)^{1/2} and
exp(3/4)(1+(1z)+1/4(1z)^{2}1/12(1z)^{3}+O((1z)^{4}))),
the standard Taylor expansion at 1 of exp(1/2z1/4z^{2}).
Clouds(z) =


+e^{3/4}(1z)^{1/2}+ 

 

+ ···

This expansion is valid in a Ddomain so that by the principle
of singularity analysis, the asymptotic determination of the
coefficients c_{n} = [z^{n}] Clouds(z) results from a direct
translation of the expansion
Clouds(z)=e^{3/4} 

+e^{3/4}(1z)^{1/2}+O 
( 
(1z)^{3/2} 
) 
into

c_{n} 
= 










= 


æ
ç
ç
è 
1 

+ 

+··· 
ö
÷
÷
ø 



 
e^{3/4} 

2(p
n^{3})^{1/2} 

æ
ç
ç
è 
1+ 

+··· 
ö
÷
÷
ø 








We finally have the asymptotic behavior of the counting sequence
{C_{n}}_{n³ 0} of clouds,


= c_{n} = 

+

3e^{3/4} 

8(p
n^{3})^{1/2} 

+ O 
æ
ç
ç
è 

ö
÷
÷
ø 
as n®+¥.

3.2 Wtrees
A subset W of N is aperiodic if the greatest common divisor
of its elements is 1. Given an aperiodic finite set W, the
class T_{W} of Wtrees is the set of rooted trees with a
total order on the children of each node such that the degree of each
node is in W. For instance binary trees are
{0,1,2}trees. The size of an Wtree is its number of
nodes. This class is well defined if 0 Î W otherwise there
are no finite Wtrees.
Since a Wtree is made of a root and a sequence of length i
Î W of Wtrees, its ordinary generating function T
satisfies
Let P(X) be the polynomial å_{w Î W}X^{w}. The
equation becomes T(z) = z P(T(z)). To check if the
function T is analytic at z we rephrase the above equation as
z = T(z)/P 
( 
T(z) 
) 
= y 
( 
T(z) 
) 
so that it is a generic instance of the inversion problem for analytic
functions (y(u) = u/P(u)).
An important statement of the inversion theorem is that if y is
analytic at t = t_{0}, then T(z) is analytic at z = y(t_{0}) if
and only if y'(t_{0}) ¹ 0. To have an intuition of this result,
consider the analytic expansion of y near t_{0}:
y(t) = y(t_{0}) + (tt_{0})y'(t_{0}) +


(tt_{0})^{2}y''(t_{0}) + ···.

If y'(t_{0})¹ 0, solving formally for t suggests that tt_{0}
~ 1/y'(t_{0})(zy(t_{0})) and a full expansion
is obtained by repeated substitutions. If on the contrary y'(t_{0})
= 0 and y''(t_{0}) ¹ 0, solving formally now suggest that
(tt_{0})^{2} ~ 2/y''(t_{0})(zy(t_{0})) so that
the inversion problem should admit two solutions satisfying
tt_{0} ~ ±( 

)^{1/2} 
( 
y(t_{0})z 
) 
^{1/2}. 
In this case the point y(t_{0}) is a branch point, so that
T(z) cannot be analytic at this point. If the first nonzero
derivative of y at t_{0} is of order r³ 2, the same remark
holds with a local behavior for t then of the form
(y(t_{0})z)^{1/r}.
Because of Pringsheim's theorem, if T has a finite radius, then
there is a dominant singularity in [ 0,+¥). Thus finding a
dominant singularity of T results in searching the smallest positive
zero of y'. Let r be this minimal zero of y'(x) =
P(x)xP'(x)/P(x)^{2}. This number satisfies
P(r)  r P'(r) = 0.
Now we have to check the number of distinct dominant singularities. By
definition a dominant singularity can be written as l = r
e^{iq} and satisfies y'(l) = 0. Assume there is an
integer k³ 2 such that all w Î W is divided by
k. In this case P(x)xP'(x) = å_{w Î W}
(1w)x^{w} can be rewritten in å_{w Î W}
(1w)(x^{k})^{w/k}. Thus if l^{k} = r^{k} then
l is an other dominant singularity so all complexes (r
e^{2ip l/k})_{0 £ l £ k1} are distincts dominant
singularities. To apply the tranfert theorems presented in the
previous section safely we have to ensure that there is a unique
dominant singularity,^{2} therefore we made the assumption that the set
W is aperiodic. We admit that this condition is sufficient to
have a unique dominant singularity r (there is a proof using the
case of equality in the triangular inequality).
Since r satisfies P(r)  r P'(r) = 0, we have
y''(r) =r^{2}P''(r)/P(r)^{3}. Thus if W
contains an element greater than 1, Y''(r) > 0 and
T(z) = T(r) ± ( 

)^{1/2}(r)^{1/2}(1 

)^{1/2} + O 
æ
ç
ç
è 
(1 

)^{3/2} 
ö
÷
÷
ø 
.

This expansion is valid on a Ddomain; thus using a transfer
theorem, we obtain the asymptotic equivalent
[z^{n}] T(z) ~ ( 

)^{1/2}(r)^{1/2} 

r^{n} = C_{r}r^{n}n^{3/2}.

References
 [1]

Flajolet (Philippe) and Odlyzko (Andrew). 
Singularity analysis of generating functions. SIAM Journal on
Discrete Mathematics, vol. 3, n°2, 1990, pp. 216240.
 [2]

Flajolet (Philippe) and Sedgewick (Robert). 
The Average Case Analysis of Algorithms: Complex Asymptotics and
Generating Functions. 
Research Report n°2026, Institut National de Recherche en
Informatique et en Automatique, 1993. 100 pages.
 [3]

Flajolet (Philippe) and Sedgewick (Robert). 
The Average Case Analysis of Algorithms: Counting and Generating
Functions. 
Research Report n°1888, Institut National de Recherche en
Informatique et en Automatique, 1993. 116 pages.
 *
 Lecture notes for a course given during the workshop
ALÉA'01 in Luminy (France).
 1
 This summary is inspired by the book in
preparation of Flajolet and Sedgewick [2, 3].
 2
 A generalisation of transfer theorems
exists for the case of multiple of singularities; see
[2, p. 85].
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.