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 An be the set of elements in A that have size n and use the same group of letters for the counts An = CardAn. We further assume that the An are all finite. The counting sequence of A is the sequence of integers {An}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 Sn=2n.

Average-case 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 W-trees.

1  A Symbolic Method for Enumerative Combinatorics

A counting sequence {An}n³ 0 can be encoded by different types of formal power series: an ordinary generating function ån ³ 0 Anzn, an exponential generating function ån ³ 0 An/n!zn, a Dirichlet series ån³ 0An/nz, ... 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 Nn = 1. Its ordinary generating function is ån³ 0zn =1/1-z, its exponential generating function is ån³ 01/n!zn = ez, its Dirichlet series ån³ 01/nz=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 An depends on finitely many of the Bn and Cn). Then F is an admissible construction if and only if the counting sequence {An} of A is a function of the counting sequences {Bn} and {Cn} of B and C only. In that case, this function may be translated into a simple operator relating formal power series representing {An}n³ 0, {Bn}n³ 0, and {Cn}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 zn. Thus the class A is mapped to the ordinary generating function
A(z)=ogf(A )(z)=
 
å
aÎA
z|a|=
 
å
n³ 0
Anzn.
An additional assumption on the sizes is made: if an element a can be decomposed into a combination of elements b1, b2, ..., bk, then the size of a is the sum of the sizes of the bi. Its translation as regards monomials is the usual product law:
z|a|A = z|b1|B1 z|b2|B2... z|bk|Bk.

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) =
 
å
(b,g) Î B×C
z|(b,g)|A =
 
å
b Î B, g Î C
z|b|B+|g|C =
 
å
b Î B
z|b|B·
 
å
g Î C
z|g|C = 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)=
 
å
a Î BÈC
z|a|A =
 
å
b Î B
z|b|B +
 
å
g Î C
z|g|C -
 
å
a Î BÇC
z|a|BÈ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 + ... =
 
å
k³ 0
ogf(B)k =
1
1-ogf(B)
.

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 (a1,...,ak) and (b1,...,bk) represent the same directed cycle if and only if there exists an integer l such that for all i, ai =bi+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
An =
 
å
k+l=n
n!
k! l!
BkCl.
This equation can be rewritten as
An
n!
=
 
å
k+l=n
Bk
k!
Cl
l!
.
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 {An}n³ 0 is represented by A(z) = egf(A)(z) = ån³ 0An/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/1-ogf(B)(z) 1/1-egf(B)(z)
Set exp(åk=1¥(-1)k+1/kogf(B)(zk)) exp(egf(B)(z))
Cycle åk=1¥f(k)/klog(1/1-ogf(B)(zk)) log1/1-egf(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
f(z) =
 
å
n³ 0
fn(z-a)n.

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) =
 
å
n ³ -M
hn(z-a)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
Res [ h(z);z=a ] .

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
1
2ip
ó
õ
 


G
g(z) dz =
 
å
s
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 [zn] f(z) admits the integral representation
fnº[zn] f(z) =
1
2ip
ó
õ
 


G
f(z)
dz
zn+1
.

2.2  Singularities and exponential rate

Most of the counting sequences encoded by functions have an asymptotic behavior that can be described by An ~ Gnq(n) where q(n) is a subexponential function: the real number G=limsupn®+¥|fn|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 [zn] f(z) is 1/R.

Proof. Cauchy's formula applied to a circle G of center 0 and radius R'<R gives
|fn|= ½
½
½
½
½
½
1
2ip
ó
õ
 


G
f(z)
dz
zn+1
½
½
½
½
½
½		 £
|2p R'|
|2ip|
sup  {  f(z) | |z|=R'  }  R'-(n+1) =O ( R'-n ) ,
so that G=limsupn|fn|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 |fn|£K/R'n. The series ån³0fnzn 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 non-negative. This situation allows to locate one dominant singularity more precisely.
Theorem 4  [Pringsheim's theorem]   If a function has Taylor coefficients that are real non-negative, 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 D-analytic 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(z-1) | >f  } .
A domain is a D-domain if it is a D(f,R) for some R and some f. A function is D-analytic if it is analytic in some D-domain.
Theorem 5  [Big-oh transfer [1]]   Let a be a number not in {0,-1,-2,...}. Assume that f(z) is D-analytic and that it satisfies in the intersection of a neighbourhood of 1 and of its D-domain the condition
f(z) = O æ
ç
ç
è		 (1-z)-a æ
ç
ç
è		 log
1
1-z
ö
÷
÷
ø		 b ö
÷
÷
ø		 .
Then
[zn] f(z) = O ( na-1(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 D-domain of f: we choose the positively oriented contour gn º g = g1 + g2 + g3 + g4, with
ì
ï
ï
ï
ï
ï
í
ï
ï
ï
ï
ï
î
g1= ì
í
î		  z | |z-1|=
1
n
| Arg(z-1) | ³q  ü
ý
þ
g2= ì
í
î		  z | 
1
n
£ |z-1|, |z|£ r, Arg(z-1) = q  ü
ý
þ
g3= {  z | |z-1|=r, | Arg(z-1) | ³q  }
g4= ì
í
î		  z | 
1
n
£ |z-1|, |z|£ r, Arg(z-1)=-q  ü
ý
þ

If the D-domain 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
fn(j) =
1
2ip
ó
õ
 


gj
f(z)
dz
zn+1
.

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
| fn(1) | = O æ
ç
ç
è		 æ
ç
ç
è
1
n
ö
÷
÷
ø		 1-a ö
÷
÷
ø		 ,
as the function f is O((1/n)-a), the contour has length O(1/n), and z-n-1 is O(1) there.
Function f(z) Asymptotic expansion of the coefficients fn
1 0
(1-z)-1 1
(1-z)-2 n+1
(1-z)-3 1/2n2+3/2n+1
(1-z)1/2 -1/(p n3)1/2(1/2+3/16n+25/256n2+O(1/n3))
(1-z)-1/2 1/(p n)1/2(1-1/8n+1/128n2+5/1024n3+O(1/n4))
log(1-z)-1 1/n
(1-z)-3/2log(1-z)-1 (n/p)1/2(2logn+2g+4log2-2+3logn/4n+ O(1/n))



Table 2: Examples of applications of the transfer theorem.

Rectilinear parts.
Setting w = eiq and performing the change of variable z = 1+w t/n, we find
| fn(2) | <
1
2p
ó
õ
¥


1
K  æ
ç
ç
è
t
n
ö
÷
÷
ø		 -a ½
½
½
½		 1+
w t
n
½
½
½
½		 -n-1 dt,
for some constant K > 0 such that |f(z)| < K(1-z)-a ``over the D-domain.'' 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+
w t
n
½
½
½
½		 ³ 1+
t
n
cosq,
there results
| fn(2) | <
K
2p
Jnna-1
where
Jn= ó
õ
¥


1
t-a æ
ç
ç
è		 1+
tcosq
n
ö
÷
÷
ø		 -n dt.

For a given a, the integrals Jn are all bounded above by some constant since they admit a limit as n tends to infinity:
Jn ® ó
õ
¥


1
t-ae-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
| fn(2) | = O ( na-1 ) ,
and the same bound holds for fn(4) by symmetry.

Outer circle.
There, f(z) is bounded while z-n is of the order r-n. Thus, fn(3) is exponentially small.



In summary, each of the four integrals of the split contour contributes O(na-1). 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:
  1. any three points of the cloud are not aligned;
  2. any line has at least one of its points in the cloud;
  3. 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 2-regular 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 2-regular graphs where the size of an element is its number of vertices.

A labeled 2-regular graph is a set of non-oriented 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
1
1-z
- æ
ç
ç
è
1
1!
z+
1
2!
z2 ö
÷
÷
ø		 .
A non-oriented cycle of at least 3 vertices admits exactly 2 distinct orientations, so that the generating function of non-oriented cycle of at least 3 vertices is
C>2(z) =
1
2
C+>2(z).
Then the series of the sets of non-oriented cycles on at least 3 vertices and equivalently of the clouds is
Clouds(z) = expC>2(z) =
exp æ
ç
ç
è		 -
1
2
z-
1
4
z2 ö
÷
÷
ø
(1-z)1/2
.

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

This expansion is valid in a D-domain so that by the principle of singularity analysis, the asymptotic determination of the coefficients cn = [zn] Clouds(z) results from a direct translation of the expansion
Clouds(z)=e-3/4
1
(1-z)1/2
+e3/4(1-z)1/2+O ( (1-z)3/2 )
into
cn =      
e-3/4
æ
è
n-1/2
-1/2
ö
ø
    
 
+e-3/4
æ
è
n-3/2
-3/2
ö
ø
    
 
+O æ
ç
ç
è
1
n5/2
ö
÷
÷
ø
     
  =      
e-3/4
(p n)1/2
æ
ç
ç
è		 1-
1
8n
+
1
128n2
+··· ö
÷
÷
ø		     
 
-
e-3/4
2(p n3)1/2
æ
ç
ç
è		 1+
3
8n
+··· ö
÷
÷
ø		     
 
+O æ
ç
ç
è
1
n5/2
ö
÷
÷
ø		 .
     
We finally have the asymptotic behavior of the counting sequence {Cn}n³ 0 of clouds,
Cn
n!
= cn =
e-3/4
(p n)1/2
+
3e-3/4
8(p n3)1/2
+ O æ
ç
ç
è
1
n5/2
ö
÷
÷
ø		     as n®+¥.

3.2  W-trees

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 TW of W-trees 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 W-tree is its number of nodes. This class is well defined if 0 Î W otherwise there are no finite W-trees.

Since a W-tree is made of a root and a sequence of length i Î W of W-trees, its ordinary generating function T satisfies
T(z) = z·
 
å
w Î W
( T(z) ) w.
Let P(X) be the polynomial åw Î WXw. 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 = t0, then T(z) is analytic at z = y(t0) if and only if y'(t0) ¹ 0. To have an intuition of this result, consider the analytic expansion of y near t0:
y(t) = y(t0) + (t-t0)y'(t0) +
1
2
(t-t0)2y''(t0) + ···.
If y'(t0)¹ 0, solving formally for t suggests that t-t0 ~ 1/y'(t0)(z-y(t0)) and a full expansion is obtained by repeated substitutions. If on the contrary y'(t0) = 0 and y''(t0) ¹ 0, solving formally now suggest that (t-t0)2 ~ 2/y''(t0)(z-y(t0)) so that the inversion problem should admit two solutions satisfying
t-t0 ~ ±(
2
-y''(t0)
)1/2 ( y(t0)-z ) 1/2.
In this case the point y(t0) is a branch point, so that T(z) cannot be analytic at this point. If the first nonzero derivative of y at t0 is of order r³ 2, the same remark holds with a local behavior for t then of the form (y(t0)-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 eiq 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 (1-w)xw can be rewritten in åw Î W (1-w)(xk)w/k. Thus if lk = rk then l is an other dominant singularity so all complexes (r e2ip l/k)0 £ l £ k-1 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) =-r2P''(r)/P(r)3. Thus if W contains an element greater than 1, Y''(r) > 0 and
T(z) = T(r) ± (
2P(r)3
r2P''(r)
)1/2(r)1/2(1-
z
r
)1/2 + O æ
ç
ç
è		 (1-
z
r
)3/2 ö
÷
÷
ø		 .
This expansion is valid on a D-domain; thus using a transfer theorem, we obtain the asymptotic equivalent
[zn] T(z) ~ (
2
r2Y''(r)
)1/2(r)1/2
1
2(p n3)1/2
r-n = Crr-nn-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. 216--240.

[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 LATEX by HEVEA.