LINEBURG

can be derived from Theorem 8.1. (For other results and references for partition asymptotics,

see [13, 23, 150].)

Theorem 8.2. Suppose that

∞ ∞

(1 ’ z k )’b(k) = a(n)z n ,

f (z) = (8.38)

n=0

k=1

where the b(k) ∈ Z, b(k) ≥ 0 for all k, and that for some C > 0, u > 0, we have

b(k) ∼ Cxu (log x)v as x’∞ . (8.39)

k¤x

Then

∼ u’1 {Cu“(u + 2)ζ(u + 1)}1/(u+1)

log n¤m a(n)

(8.40)

· (u + 1)(u’v)/(u+1) mu/(u+1) (log m)v/(u+1)

as m ’ ∞.

If b(k) = 1 for all k, a(n) is pn , the ordinary partition function. If b(k) = k for all k, a(n) is

the number of plane partitions of n. Thus Brigham™s theorem covers a wide class of interesting

partition functions. The cost of this generality is that we obtain only the asymptotics of the

logarithm of the summatory function of the partitions being enumerated. (For better estimates

of the number of plane partitions, for example, see [9, 170, 387]. For ordinary partitions, we

have the expansion (1.3).)

Brigham™s proof of Theorem 8.2 ¬rst shows that

f (e’w ) ∼ Cw’u (’ log w)v “(u + 1)ζ(u + 1) w ’ 0+

as (8.41)

and then invokes the Hardy-Ramanujan Tauberian theorem [328]. Instead, one can obtain a

proof from Theorem 8.1. The advantage of using Theorem 8.1 is that it is much easier to

generalize. Hardy and Ramanujan proved their Tauberian theorem only for functions whose

62

growth rates are of the form given by (8.41). Their approach can be extended to other functions,

but this is complicated to do. In contrast, Theorem 8.1 is easy to apply. The conditions of

Theorem 8.1 on the derivatives are not restrictive. For a function f (z) de¬ned by (8.38) we

have B ’ ∞ if b(k) = ∞, and the condition (8.33) can be shown to hold whenever there

are constants c1 and c2 such that for all w > 1, and all su¬ciently large m,

b(k) ¤ c1 wc2 b(k) , (8.42)

k¤mw k¤m

say. The main di¬culty in applying Theorem 8.1 to generalizations of Brigham™s theorem is

in accurately estimating the minimal value in Lemma 8.1.

There are many other applications of Lemma 8.1 and Theorem 8.1. For example, they can

be used to prove the results of [158] on volumes of spheres in the Lee metric.

Lemma 8.1 can be generalized in a straightforward way to multivariate generating functions.

If

am,n xm y n

f (x, y) = (8.43)

m,n≥0

and am,n ≥ 0 for all m and n, then for any x, y > 0 for which the sum in (8.43) converges we

have

am,n ¤ x’m y ’n f (x, y) . (8.44)

Generalizations of the lower bound of Theorem 8.1 to multivariate functions can also be derived,

but are again harder than the upper bound [289].

8.2. Tauberian theorems

The Brigham Tauberian theorem for partitions [58], based on the Hardy-Ramanujan

Tauberian theorem [328], was quoted already in Section 8.1. It applies to certain generat-

ing functions that have (in notation to be introduced in Section 10) a large singularity and

gives estimates only for the logarithm of the summatory function of the coe¬cients. Another

theorem that is often more precise, but is again designed to deal with rapidly growing par-

tition functions, is that of Ingham [212], and will be discussed at the end of this section.

Most of the Tauberian theorems in the literature apply to functions with small singularities

(i.e., ones that do not grow rapidly as the argument approaches the circle of convergence) and

give asymptotic relations for the sum of coe¬cients. References for Tauberian theorems are

[117, 154, 190, 212, 325]. Their main advantage is generality and ease of use, as is shown

63

by the applications made to 0-1 laws in [77, 78, 79]. They can often be applied when the

information about generating functions is insu¬cient to use the methods of Sections 11 and

12. This is especially true when the circle inside which the generating function converges is a

natural boundary beyond which the function cannot be continued.

One Tauberian theorem that is often used in combinatorial enumeration is that of Hardy,

Littlewood, and Karamata. We say a function L(t) varies slowly at in¬nity if, for every u > 0,

L(ut) ∼ L(t) as t ’ ∞.

Theorem 8.3. Suppose that ak ≥ 0 for all k, and that

∞

ak xk

f (x) =

k=0

converges for 0 ¤ x < r. If there is a ρ ≥ 0 and a function L(t) that varies slowly at in¬nity

such that

1

f (x) ∼ (r ’ x)’ρ L as x ’ r ’ , (8.45)

r’x

then

n

ak r k ∼ (n/r)ρ L(n)/“(ρ + 1) as n ’ ∞ . (8.46)

k=0

Example 8.4. Cycles of permutations ([33]). If S is a set of positive integers, and f n the

probability that a random permutation on n letters will have all cycle lengths in S (i.e.,

fn = an /n!, where an is the number of permutations with cycle length in S), then

∞

fn z n = exp(z k /k) = (1 ’ z)’1 exp(’z k /k) .

f (z) = (8.47)

n=0 k∈S k∈S

+

If |¢ \ S| < ∞, then the methods of Sections 10.2 and 11 apply easily, and one ¬nds that

«

fn ∼ exp ’ 1/k as n’∞. (8.48)

k∈S

+ \ S|

This estimate can also be proved to apply for |¢ = ∞, provided |{1, . . . , m} \ S| does not

grow too rapidly when m ’ ∞. If |S| < ∞ (or when |{1, . . . , m} © S| does not grow rapidly),

the methods of Section 12 apply. When S = {1, 2}, one obtains, for example, the result of

Moser and Wyman [292] that the number of permutations of order 2 is

∼ (n/e)n/2 2’1/2 exp(n1/2 ’ 1/4) as n’∞. (8.49)

64

(For sharper and more general results, see [292, 376].) The methods used in these cases are

di¬erent from the ones we are considering in this section.

We now consider an intermediate case, with

|{1, . . . , m} © S| ∼ ρm as m’∞. (8.50)

for some ¬xed ρ, 0 ¤ ρ ¤ 1. This case can be handled by Tauberian techniques. To apply

Theorem 8.3, we need to show that L(t) = f (1 ’ t ’1 )t’ρ varies slowly at in¬nity. This is

equivalent to showing that for any u ∈ (0, 1),

f (1 ’ t’1 ) ∼ f (1 ’ t’1 u)uρ as t’∞. (8.51)

Because of (8.47), it su¬ces to prove that

k ’1 {(1 ’ t’1 )k ’ (1 ’ t’1 u)k } = ρ log u + o(1) as t’∞, (8.52)

k∈S

but this is easy to deduce from (8.50) using summation by parts (Section 5). Therefore we

¬nd from Theorem 8.3 that

m

fn ∼ f (1 ’ 1/n)“(ρ + 1)’1 as n’∞. (8.53)

n=0

(For additional results and references on this problem see [317].)

As the above example shows, Tauberian theorems yield estimates under weak assumptions.

These theorems do have some disadvantages. Not only do they usually estimate only the

summatory function of the coe¬cients, but they normally give no bounds for the error term.

(See [154] for some Tauberian theorems with remainder terms.) Furthermore, they usually

apply only to functions with nonnegative coe¬cients. Sometimes, as in the following theorem

of Hardy and Littlewood, one can relax the nonnegativity condition slightly.

Theorem 8.4. Suppose that ak ≥ ’c/k for some c > 0,

∞

ak xk ,

f (z) = (8.54)

k=1

and that f (x) converges for 0 < x < 1, and that

lim f (x) = A . (8.55)

x’1’

Then

n

lim ak = A . (8.56)

n’∞

k=1

65

Some condition such as ak ≥ ’c/k on the ak is necessary, or otherwise the theorem would

not hold. For example, the function

1’x

= 1 ’ 2x + 2x2 · · ·

f (x) = (8.57)

1+x

satis¬es (8.55) with A = 0, but (8.56) fails.

We next present an example that shows an application of the above results in combination

with other asymptotic methods that were presented before.

Example 8.5. Permutations with distinct cycle lengths. The probability that a random per-

mutation on n letters will have cycles of distinct lengths is [z n ]f (z), where

∞

zk

f (z) = 1+ . (8.58)

k

k=1

Greene and Knuth [177] note that this is also the limit as p ’ ∞ of the probability that a

polynomial of degree n factors into irreducible polynomials of distinct degrees modulo a prime

p. It is shown in [177] that

[z n ]f (z) = e’γ (1 + n’1 ) + O(n’2 log n) as n’∞, (8.59)

where γ = 0.577 . . . is Euler™s constant. A simpli¬ed version of the argument of [177] will be

presented that shows that

[z n ]f (z) ∼ e’γ as n’∞. (8.60)

Methods for obtaining better expansions, even more precise than that of (8.59), are discussed

in Section 11.2. For related results obtained by probabilistic methods, see [20].

We have, for |z| < 1,

∞

log(1 + z k /k)

f (z) = (1 + z) exp

k=2

∞

(8.61)

k

= (1 + z) exp z /k + g(z)

k=2

= (1 + z)(1 ’ z)’1 exp(g(z)) ,

where

∞ ∞

(’1)m’1 z mk

g(z) = ’z + . (8.62)

km

m

m=2 k=2

66

Since the coe¬cients of g(z) are small, the double sum in (8.62) converges for z = 1, and we

have

∞ ∞

(’1)m’1 ’m

g(1) = lim g(z) = ’1 + k

m

z’1’

k=2 m=2

∞

(8.63)

{log(1 + k ’1 ) ’ k ’1 }

= ’1 +

k=2

= ’ log 2 + lim (log(n + 1) ’ Hn ) = ’ log 2 ’ γ ,

n’∞

where Hn = 1 + 1/2 + 1/3 + · · · + 1/n is the n-th harmonic number. Therefore, by (8.61), we

¬nd from Theorem 8.4 that if fn = [z n ]f (z), then

f0 + f1 + · · · + fn ∼ ne’γ as n’∞. (8.64)

To obtain asymptotics of fn , we note that if hn = [z n ] exp(g(z)), then by (8.61),

fn = 2h0 + 2h1 + · · · + 2hn’1 + hn . (8.65)

We next obtain an upper bound for |hn |. There are several ways to proceed. The method used

below gives the best possible result |h n | = O(n’2 ).

Since g(z) has the power series expansion (8.62), and h n = [z n ] exp(g(z)), comparison of

terms in the full expansion of exp(g(z)) and exp(v(z)) shows that |h n | ¤ [z n ] exp(v(z)), where

v(z) is any power series such that |[z n ]g(z)| ¤ [z n ]v(z). For n ≥ 2,

(’1)m’1 m m

n

[z ]g(z) = . (8.66)

m n

m|n

m≥2

m<n

The term (m/n)m is monotone decreasing for 1 ¤ m ¤ n/e, since its derivative with respect

to m is ¤ 0 in that range. Therefore

2 3

1 2 1 3 2 ’n/2

n

¤ 10n’2 ,

|[z ]g(z)| ¤ + + 2 (8.67)

2 n m n n

3¤m¤n/3

say. Hence we can take

∞

n’2 z n ,

v(z) = 10 (8.68)

n=1

and then we need to estimate

wn = [z n ] exp(v(z)) . (8.69)

67

We let w(z) = exp(v(z)), and note that

w (z) = v (z)w(z) , (8.70)

so for n ≥ 1,

n’1

wk (n ’ k)’1 .

nwn = 10 (8.71)

k=0

Further, since v(1) < ∞, and wn ≥ 0 for all n, we have wn ¤ A = w(1) = exp(v(1)) for all

n. Let B = 106 A and note that wn ¤ Bn’2 for 1 ¤ n ¤ 103 . Suppose now that wm ¤ Bm’2

for 1 ¤ m < n for some n ≥ 103 . We will prove that wn ¤ Bn’2 , and then by induction this

inequality will hold for all n ≥ 1. We apply Eq. (8.70). For 0 ¤ k ¤ 100, we use w k ¤ A,

(n ’ k)’1 ¤ 2n’1 . For 100 < k ¤ n/2,

wk (n ’ k)’1 ¤ Bk ’2 (n ’ k)’1 ¤ 2Bk ’2 n’1 , (8.72)

and so

wk (n ’ k)’1 ¤ B(40n)’1 . (8.73)

100¤k¤n/2

Finally,

wk (n ’ k)’1 ¤ 4Bn’2 (n ’ k)’1 ¤ 4Bn’2 Hn . (8.74)

n/2<k¤n’1 n/2<k¤n’1

Therefore, by (8.71),

nwn ¤ 2000An’1 + B(4n)’1 + 4BHn n’2 ¤ Bn’1 , (8.75)

which completes the induction step and proves that w n ¤ Bn’2 for all n ≥ 1.

There are Tauberian theorems that apply to generating functions with rapidly growing

coe¬cients but are more precise than Brigham™s theorem or the estimates obtainable with the

methods of Section 8.1. One of the most useful is Ingham™s Tauberian theorem for partitions

[212]. The following result is a corollary of the more general Theorem 2 of [212].

Theorem 8.5. Let 1 ¤ u1 < u2 < . . . be positive integers such that

|{uj : uj ¤ x}| = Bxβ + R(x) , (8.76)

where B > 0, β > 0, and

y

x’1 R(x)dx = b log y + c + o(1) as y’∞. (8.77)

1

68

Let

∞ ∞

n

(1 ’ z uj )’1 ,

a(z) = an z = (8.78)

n=1 j=1

∞ ∞

a— (z) = a— z n = (1 + z uj ) . (8.79)

n

n=1 j=1

Then, as m ’ ∞,

m

an ∼ (2π)’1/2 (1 ’ ±)1/2 ec V ’±(b+1/2) m(b+1/2)(1’±)’1/2 exp(±’1 (V m)± ) , (8.80)

n=1

m

a— ∼ (2π)’1/2 (1 ’ ±)1/2 2b (V — m)’±/2 exp(±’1 (V — m)± ) , (8.81)

n

n=1

where

± = β(β + 1)’1 , V = {Bβ“(β + 1)ζ(β + 1)}1/β , V — = (1 ’ 2’β )1/β V . (8.82)

If u1 = 1, then as n ’ ∞

an ∼ (2π)’1/2 (1 ’ ±)1/2 ec V ’±(b’1/2) n(b’1/2)(1’±)’1/2 exp(±’1 (V n)± ) , (8.83)

and if 1, 2, 4, 8, . . . all belong to {uj }, then

a— ∼ (2π)’1/2 (1 ’ ±)1/2 2b (V — )±/2 n±/2’1 exp(±’1 (V — n)± ) . (8.84)

n

Theorem 8.5 provides more precise information than Brigham™s Theorem 8.2, but under

more restrictive conditions. It is derived from Ingham™s main result, Theorem 1 of [212],

which can be applied to wider classes of functions. However, that theorem cannot be used to

derive Theorem 8.2. The disadvantage of Ingham™s main theorem is that it requires knowledge

of the behavior of the generating function in the complex plane, not just on the real axis.

On the other hand, the region where this behavior has to be known is much smaller than

it is for the analytic methods that give more accurate answers, and which are presented in

Copyright Design by: Sunlight webdesign