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 . 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 .

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  using Poisson approximations and Tauberian
theorems. The derivation sketched above follows [134, 135]. The paper  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 .
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  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 .

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  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 .

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  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 , 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

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 . 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)ОГЛАВЛЕНИЕ След. стр. >>