LINEBURG


<< . .

 15
( 24)



. . >>


ii) There exists a function (x), de¬ned for x ≥ 0 with lim x’∞ (x) = 0, such that for all
θ ∈ [’(π ’ φ0 ), π ’ φ0 ] and u ≥ u0 , we have


L(ueiθ )
’1 < (u) (11.8)
L(u)
and
L(u log 2 u)
’1 < (u) . (11.9)
L(u)


Theorem 11.1. Assume that f (z) is analytic throughout the domain ∆ \ {r}, where ∆ =
∆(r, φ, ·), r, · > 0, 0 < φ < π/2, and that L(u) is a function of slow variation at ∞. If ± is
any real number, then

A) If
1
f (z) = O (z ’ r)± L
r’z
uniformly for z ∈ ∆ \ {r}, then

[z n ]f (z) = O(r ’n n’±’1 L(n)) as n ’ ∞ .


B) If
1
f (z) = o (z ’ r)± L
r’z
uniformly as z ’ r for z ∈ ∆ \ {r}, then

[z n ]f (z) = o(r ’n n’±’1 L(n)) as n ’ ∞ .




108
C) If ± ∈ {0, 1, 2, . . .} and
1
f (z) ∼ (r ’ z)± L
r’z
uniformly as z ’ r for z ∈ ∆ \ {r}, then

r ’n n’±’1
n
[z ]f (z) ∼ L(n) .
“(’±)

The restriction that there be only one singularity on the circle of convergence is easy to
relax. If there are several (corresponding to oscillatory behavior of the coe¬cients), their
contributions to the coe¬cients add. The crucial fact is that at each singularity the function
f (z) should be continuous except for an angular region similar to that of ∆(r, φ, ·).
The requirement that the generating function f (z) be analytic in the interior of ∆(r, φ, ·) is
in general harder to dispense with, at least by the methods of [135]. However, if the singularity
at r is su¬ciently large, one can obtain the same results with weaker assumptions that only
require analyticity inside the disk |z| < r. The following result is implicit in [135].

Theorem 11.2. Assume that f (z) is analytic in the domain{z : |z| ¤ r, z = r} and that L(u)
is a function of slow variation at ∞. If ± is any ¬xed real number with ± < ’1, then the
implications A), B), and C) of Theorem 11.1 are valid.



Example 11.3. Longest cycle in a random permutation. The average length of the longest
cycle in a permutation on n letters is [z n ]f (z), where
® « 

f (z) = (1 ’ z)’1 j ’1 z j » .
°1 ’ exp ’
k≥0 j≥k

It is easy to see that f (z) is analytic in |z| < 1, and a double application of the Euler-Maclaurin
summation formula shows that f (z) ∼ G(1 ’ z) ’2 as z ’ 1, uniformly for |z| ¤ 1, z = 1,
where
∞ ∞
t’1 e’t dt
G= 1 ’ exp ’ dx = 0.624 . . . . (11.10)
0 x

Therefore, by Theorem 11.2 with L(u) = 1,

[z n ]f (z) ∼ Gn as n’∞, (11.11)

a result ¬rst proved by Shepp and Lloyd [342] using Poisson approximations and Tauberian
theorems. The derivation sketched above follows [134, 135]. The paper [134] contains many

109
other applications of transfer theorems to random mapping problems. Additional recent papers
on the cycle structure of random permutations are [19, 187]. They use probabilistic methods,
not transfer theorems, and contain extensive references to other recent works.
 




In applying transfer theorems, it is useful to have explicit expansions and estimates for the
coe¬cients of some frequently occurring functions. We state several asymptotic series:
« 
n’±’1  (±)
n ±
ek n’k  , ± = 0, 1, 2, . . . ,
[z ](1 ’ z) ≈ 1+ (11.12)
“(’±)
k≥1

where
2k
(±)
(’1)j »k,j (± + 1)(± + 2) · · · (± + j) ,
ek = (11.13)
j=k

and the »k,j are determined by

et (1 + vt)’1’1/v = »k,j v k tj . (11.14)
k,j≥0

In particular,

(±)
e1 = ±(± + 1)/2,
(±)
e2 = ±(± + 1)(± + 2)(3± + 1)/24 .

Also, for ±, β ∈ {0, 1, 2, . . .},
« 
n’±’1 (±,β)
n ± ’1 β
(log n)β 1 + (log n)’k  ,
[z ](1 ’ z) (’z log(1 ’ z)) ≈ ek (11.15)
“(’±)
k≥1

where
dk
β
(±,β) k
“(’s)’1
ek = (’1) “(’±) . (11.16)
k
k ds s=±

Further examples of asymptotic expansions are presented in [135].
Why is the analyticity of a function f (z) throughout ∆(r, φ, ·) \ {r} so important? We
explain this using as an example a function f (z) that satis¬es

f (z) = (1 + o(1))(1 ’ z)1/2 (11.17)

as z ’ 1 with z ∈ ∆ = ∆(1, π/8, 1). We write

f (z) = (1 ’ z)1/2 + g(z) , (11.18)


110
so that
|g(z)| = o(|1 ’ z|1/2 ) . (11.19)

Since [z n ](1 ’ z)1/2 grows like n’3/2 , we would like to show that

|[z n ]g(z)| = o(n’3/2 ) as n’∞. (11.20)

If g(z) were analytic in a disk of radius 1 + δ for some δ > 0, then we could conclude that
|[z n ]g(z)| < (1 + δ/2)’n for large n, a conclusion much stronger than (11.20). However, if all
we know is that g(z) satis¬es (11.19) in |z| ¤ 1, then we can only conclude from Cauchy™s
theorem that [z n ]g(z) = O(1), since (11.19) implies that |g(z)| ¤ C for all |z| < 1 and some
C > 0. Then Theorem 10.2 gives
|[z n ]g(z)| ¤ Cr ’n (11.21)

uniformly for all n ≥ 0 and all r < 1, and hence |[z n ]g(z)| ¤ C for all n, a result that is far
from what is required. If we know that g(z) can be continued to ∆ \ {r} and satis¬es (11.19)
there, we can do a lot better. We choose the contour “ = “ 1 ∪ “2 ∪ “3 ∪ “4 , pictured in Fig. 1,
with

“1 = {z : |z ’ 1| = 1/n, |Arg(z ’ 1)| ≥ π/4} , (11.22)

“2 = {z : z = 1 + r exp(πi/4), 1/n ¤ r ¤ δ} , (11.23)

“3 = {z : |z| = |1 + δ exp(πi/4)|, |Arg(z ’ 1)| ≥ π/4} , (11.24)

“4 = {z : z = 1 + r exp(’πi/4), 1/n ¤ r ¤ δ} , (11.25)

where 0 < δ < 1/2. We will show that the integrals
1
g(z)z ’n’1 dz
gj = (11.26)
2πi “j

on the “j are small. On “3 , g(z) is bounded, so we trivially obtain the exponential upper
bound
|g3 | = O((1 + δ/2)’n ) . (11.27)

On “1 , |g(z)| = o(n’1/2 ), |z ’n’1 | ¤ (1 ’ 1/n)’n’1 = O(1), and the length of “1 is ¤ 2π/n, so

|g1 | = o(n’3/2 ) as n’∞. (11.28)

Next, on “2 , for z = 1 + r exp(πi/4),

|z|’n = |1 + r2’1/2 + ir2’1/2 |’n = (1 + r21/2 + r 2 )’n/2

¤ (1 + r)’n/2 ¤ exp(’nr/10) (11.29)

111
for 0 ¤ r < 1. Since g(z) satis¬es (11.19), for any > 0 we have

|g(1 + r exp(πi/4))| ¤ r 1/2 (11.30)

if 0 < r ¤ · for some · = ·( ) ¤ δ. Therefore
· ∞
1/2
|g2 | ¤ r exp(’nr/10)dr + O exp(’nr/10)dr
0 ·

n’3/2 r 1/2 exp(’r/10)dr + O(exp(’n·/10)) ,
¤ (11.31)
0

and so
|g2 | = o(n’3/2 ) . (11.32)

Since |g4 | = |g2 |, inequalities (11.27), (11.28), and (11.32) show that (11.20) holds.
The critical factor in the derivation of (11.20) was the bound for (11.29) for |z| ’n on the
segment z = 1 + r exp(πi/4). Integrating on the circle |z| = 1 or even on the line Re (z) = 1
does not give a bound for |z|’n that is anywhere as small, and the resulting bounds do not
approach (11.20) in strength. The use of the circular arc “ 1 in the integral is only a minor
technical device used to avoid the singularity at z = 1.
When one cannot continue a function to a region like ∆ \ {1}, it is sometimes possible
to obtain good estimates for coe¬cients by working with the generating function exclusively
in |z| ¤ 1, provided some smoothness properties apply. This method is outlined in the next
section.

11.2. Darboux™s theorem and other methods

A singularity of f (z) at z = w is called algebraic if f (z) can be written as the sum of a
function analytic in a neighborhood of w and a ¬nite number of terms of the form

(1 ’ z/w)± g(z) , (11.33)

where g(z) is analytic near w, g(w) = 0, and ± ∈ {0, 1, 2, . . .}. Darboux™s theorem [87] gives
asymptotic expansions for functions with algebraic singularities on the circle of convergence.
We state one form of Darboux™s result, derived from Theorem 8.4 of [354].

Theorem 11.3. Suppose that f (z) is analytic for |z| < r, r > 0, and has only algebraic
singularities on |z| = r. Let a be the minimum of Re (±) for the terms of the form (11.33) at



112
the singularities of f (z) on |z| = r, and let w j , ±j , and gj (z) be the w, ±, and g(z) for those
terms of the form (11.33) for which Re (±) = a. Then, as n ’ ∞,

gj (wj )n’±j ’1
n ’n ’a’1
[z ]f (z) ’ n + o(r n ). (11.34)
“(’±j )wj
j

Jungen [219] has extended Darboux™s theorem to functions that have a single dominant
singularity which is of a mixed algebraic and logarithmic form. His method can be applied
also to functions that have several such singularities on their circle of convergence.
We do not devote much attention to Darboux™s and Jungen™s theorems because they can be
obtained from the transfer theorems of Section 11.1. The only reason for stating Theorem 11.3
is that it occurs frequently in the literature.
Some functions, such as

(1 + z k /k 2 ) ,
f (z) = (11.35)
k=1

are analytic in |z| ¤ 1, cannot be continued outside the unit circle, yet are nicely behaved
on |z| = 1. Therefore there is no dominant singularity that can be studied to determine the
asymptotics of [z n ]f (z). To minimize the size of the integrand, it is natural to move the
contour of integration in Cauchy™s formula to the unit circle. Once that is done, it is possible
to exploit smoothness properties of f (z) to bound the coe¬cients. The Riemann-Lebesgue
lemma implies that if f (z) is integrable on the unit circle, then as n ’ ∞,
π
n ’1
f (eiθ ) exp(’niθ)dθ = o(1) .
[z ]f (z) = (2π) (11.36)
’π

More can be said if the derivative of f (z) exists on the unit circle. When we apply integration
by parts to the integral in (11.36), we ¬nd
π
n ’1
f (eiθ ) exp(’(n ’ 1)iθ)dθ ,
[z ]f (z) = (2πn) (11.37)
’π

and so |[z n ]f (z)| = o(n’1 ) if f (z) exists and is integrable on the unit circle. Existence of higher
derivatives leads to even better estimates. We do not attempt to state a general theorem, but
illustrate an application of this method with an example. The same technique can be used in
other situations, for example in obtaining better error terms in Darboux™s theorem [87].

Example 11.4. Permutations with distinct cycle lengths. Example 8.5 showed that for the
function f (z) de¬ned by Eq. (8.58), [z n ]f (z) ∼ exp(’γ) as n ’ ∞. This coe¬cient is the
probability that a random permutation on n letters has distinct cycle lengths. The more precise

113
estimate (8.59) was derived by Greene and Knuth [177] by working with recurrences for the
coe¬cients of f (z) and auxiliary functions. Another approach to deriving fuller asymptotic
expansions for [z n ]f (z) is to use the method outlined above. It su¬ces to show that the
function g(z) de¬ned by Eq. (8.62) has a nice expansion in the closed disk |z| ¤ 1. Since

(’1)m’1
{Lim (z m ) ’ z m } ,
g(z) = ’z + (11.38)
m
m=2

where the Lim (w) are the polylogarithm functions [251], one can use the theory of the Li m (w).
A simpler way to proceed is to note, for example, that
∞ ∞
z 2k z 2k
= + r(z) , (11.39)
k2 k(k ’ 1)
k=2 k=2

where

z 2k
r(z) = ’ , (11.40)
k 2 (k ’ 1)
k=2

and so r (z) is bounded and continuous for |z| ¤ 1, as are the terms in (8.62) with m ≥ 3. On
the other hand,

z 2k
= z 2 + (1 ’ z 2 ) log(1 ’ z 2 ) , (11.41)
k(k ’ 1)
k=2

so we can write g(z) = g1 (z) + g2 (z), where g1 (z) is an explicit function (given by Eq. (11.41))
such that the coe¬cients of exp(g1 (z)) can be estimated asymptotically using transfer methods
or other techniques, and g2 (z) has the property that g2 (z) is bounded and continuous in |z| ¤ 1.
Continuing this process, we can ¬nd, for every K, an expansion for the coe¬cients of f (z) that
has error term O(n’K ). To do this, we write g(z) = G1 (z) + G2 (z). In this expansion G1 (z)
will be explicitly given and analytic inside |z| < 1 and analytically continuable to some region
that extends beyond the unit disk with the exception of cuts from a ¬nite number of points on
(K)
the unit circle out to in¬nity. Further, G 2 (z) will have the property that G2 (z) is bounded
and continuous in |z| ¤ 1. This will then give the desired expansion for the coe¬cients of
f (z).
 




12. Large singularities of analytic functions

This section presents methods for asymptotic estimation of coe¬cients of generating func-
tions whose dominant singularities are large.




114
12.1. The saddle point method

The saddle point method, also referred to as the method of steepest descent, is by far
the most useful method for obtaining asymptotic information about rapidly growing functions.
It is extremely ¬‚exible and has been applied to a tremendous variety of problems. It is also
complicated, and there is no simple categorization of situations where it can be applied, much
less of the results it produces. Given the purpose and limitations on the length of this chapter,
we do not present a full discussion of it. For a complete and insightful introduction to this
technique, the reader is referred to [63]. Many other books, such as [110, 115, 315, 385] also
have extensive presentations. What this section does is to outline the method, show when
and how it can be applied and what kinds of estimates it produces. Examples of proper and
improper applications of the method are presented. Later subsections are then devoted to
general results obtained through applications of the saddle point method. These results give
asymptotic expansions for wide classes of functions without forcing the reader to go through
the details of the saddle point method.
The saddle point method is based on the freedom to shift contours of integration when
estimating integrals of analytic functions. The same principle underlies other techniques, such
as the transfer method of Section 11.1, but the way it is applied here is di¬erent. When dealing
with functions of slow growth near their principal singularity, as happens for transfer methods,
one attempts to push the contour of integration up to and in some ways even beyond the
singularity. The saddle point method is usually applied when the singularity is large, and it
keeps the path of integration close to the singularity.
In the remainder of this section we will assume that f (z) is analytic in |z| < R ¤ ∞. We
will also make the assumption that for some R 0 , if R0 < r < R, then

max |f (z)| = f (r) . (12.1)
|z|=r

This assumption is clearly satis¬ed by all functions with real nonnegative coe¬cients, which
are the most common ones in combinatorial enumeration. Further, we will suppose that z = r
is the unique point with |z| = r where the maximum value in (12.1) is assumed. When
this assumption is not satis¬ed, we are almost always dealing with some periodicity in the
asymptotics of the coe¬cients, and we can then usually reduce to the standard case by either
changing variables or rewriting the generating function as a sum of several others, as was
discussed in Section 10. (Such a reduction cannot be applied to the function of Eq. (9.39),

115
though.)
The ¬rst step in estimating [z n ]f (z) by the saddle point method is to ¬nd the saddle point.
Under our assumptions, that will be a point r ∈ (R 0 , R) which minimizes r ’n f (r). We have
encountered this condition before, in Section 8.1. The minimizing r = r 0 will usually be

<< . .

 15
( 24)



. . >>

Copyright Design by: Sunlight webdesign