LINEBURG

2 2

j=1 j=1

where = ±1 for each j. Then

j

2’z

CA (z) = + u(z) , (10.49)

2(1 ’ z)

where

|z|

|u(z)| ¤ .

2(1 ’ |z|)

For |z| = r < 1, we have |u(z)| ¤ r/(2(1 ’ r)). On the other hand, z ’ (2 ’ z)/(1 ’ z) maps

circles to circles, since it is a fractional linear transformation, so it takes the circle |z| = r to

100

the circle with center on the real axis that goes through the two points (2 ’ r)/(1 ’ r) and

(2 + r)/(1 + r). Therefore for |z| = r < 1,

1 ’ r ’ r2

2+r r

|CA (z)| ≥ ’ = , (10.50)

1 ’ r2

2(1 + r) 2(1 ’ r)

and so |CA (z)| ≥ 1/16 for |z| = r ¤ 0.6. Hence, if k ≥ 9, then on |z| = 0.6,

|(1 ’ 2z)CA (z)| ≥ 1/80 > (0.6)k , (10.51)

and thus (1 ’ 2z)CA (z) and h(z) have the same number of zeros in |z| ¤ 0.6. On the other

hand, CA (z) has no zeros in |z| ¤ 0.6 by (10.50), while 1 ’ 2z has one, so we obtain the desired

result, at least for k ≥ 9. (A more careful analysis shows that h(z) has only one root inside

|z| = 0.6 even for 4 ¤ k < 9. For 1 ¤ k ¤ 3, there are cases where there is no zero inside

|z| ¤ 0.6.) Example 6.7 shows how to obtain precise estimates of the single zero.

We note that (10.50) shows that for |z| = 0.55, k ≥ 9

|h(z)| ≥ |1 ’ 1.1|0.2 ’ (0.55)k ≥ 0.02 ’ 0.01 ≥ 1/100 , (10.52)

a result that was used in Example 9.2.

Example 10.7. Coins in a fountain. An (n, k) fountain is an arrangement of n coins in rows

such that there are k coins in the bottom row, and such that each coin in a higher row touches

exactly two coins in the next lower row. Let a n,k be the number of (n, k) fountains, and

an = an,k the total number of fountains of n coins. The values of a n for 1 ¤ n ¤ 6 are

k

1, 1, 2, 3, 5, 9. If we let a0 = 1 then it can be shown [313] that

∞

1

an z n =

f (z) = . (10.53)

z

1’ z2

n=0 1’

z3

1’ 1...

This is a famous continued fraction of Ramanujan. (Other combinatorial interpretations of

this continued fraction are also known, see the references in [313]. For related results, see

[326, 327].) Although one can derive the asymptotics of the a n from the expansion (10.53), it is

more convenient to work with another expansion, known from previous studies of Ramanujan™s

continued fraction:

p(z)

f (z) = , (10.54)

q(z)

101

where

z r(r+1)

r

p(z) = (’1) , (10.55)

(1 ’ z)(1 ’ z 2 ) . . . (1 ’ z r )

r≥0

2

zr

r

q(z) = (’1) . (10.56)

(1 ’ z)(1 ’ z 2 ) . . . (1 ’ z r )

r≥0

Clearly both p(z) and q(z) are analytic in |z| < 1, so f (z) is meromorphic there. We will show

that q(z) has a simple real zero x0 , 0.57 < x0 < 0.58, and no other zeros in |z| < 0.62, while

p(x0 ) > 0. It will then follow from Theorem 10.4 that

an = cx’n + O((5/3)n ) as n’∞, (10.57)

0

where c = ’p(x0 )/(x0 q (x0 )). Numerical computation shows that c = 0.31236 . . ., x 0 =

0.576148769 . . . .

To establish the claim about x0 , let pn (z) and qn (z) denote the n-th partial sums of the

series (10.55) and (10.56), respectively. Write a(z) = q 3 (z)(1 ’ z)(1 ’ z 2 )/(1 ’ z 3 ), so that

a(z) = 1 ’ 2z ’ z 2 + z 3 + 3z 4 + z 5 ’ 2z 6 ’ z 7 ’ z 9 , (10.58)

and consider

9

b(z) = (z ’ zj ) ,

j=1

where the zj are 0.57577, ’0.46997 ± i0.81792, 0.74833 ± i0.07523, ’1.05926 ± i0.36718,

0.49301 ± i1.58185, in that order. (The z j are approximations to the zeros of a(z), obtained

from numerical library subroutines. How they were derived is not important for the veri¬-

ak z k ,

cation of our proof.) An easy hand or machine computation shows that if a(z) = k

bk z k , then

b(z) =

9

|ak ’ bk | ¤ 1.7 — 10’4 ,

k=0

and so |a(z) ’ b(z)| ¤ 1.7 — 10’4 for all |z| ¤ 1. Another computation shows that |b(z)| ≥

8 — 10’4 for all |z| = 0.62.

On the other hand, for 0 ¤ u ¤ 0.62 and |z| = u, we have for k ≥ 5

2 2

z (k+1) ’k u2k+1 u9

¤ ¤ . (10.59)

1 ’ z k+1 1 ’ uk+1 1 ’ u5

Therefore

∞ m

2

zk u16 u9

k

¤ 6 — 10’4 ,

(’1) k ¤ (10.60)

1 ’ u4 1 ’ u5

Πj=4 (1 ’ z j ) m≥0

k=4

102

and so by Rouch´™s theorem, q(z) and b(z) have the same number of zeros in |z| ¤ 0.62, namely

e

1. Since q(z) has real coe¬cients, its zero is real. This establishes the existence of x 0 . An easy

computation shows that q(0.57) > 0, q(0.58) < 0, so 0.57 < x 0 < 0.58.

To show that p(x0 ) > 0, note that successive summands in (10.55) decrease in absolute

magnitude for each ¬xed real z > 0, and p(z) > 1 ’ z 2 /(1 ’ z) > 0 for 0 < z < 0.6.

The method used in the above example is widely applicable to generating functions given

by continued fractions. Typically they are meromorphic in a disk centered at the origin, with

a single dominant pole of order 1. Usually there is no convenient representation of the form

(10.54) with explicit p(z) and q(z), and one has to work harder to establish the necessary

properties about location of poles.

It was mentioned in Section 6.4 that unimodality of a sequence is often deduced from

information about the zeros of the associated polynomial. If the zeros of the polynomial

n

ak z k

A(z) =

k=0

n ’1

are real and ¤ 0, then the ak are unimodal, and even the ak are log-concave. However,

k

weaker properties follow from weaker assumptions on the zeros. If all the zeros of A(z) are in

the wedge-shaped region centered on the negative real axis |Arg(’z)| ¤ π/4, and the a k are

n ’1

real, then the ak are log-concave, but the ak are not necessarily log-concave. (This follows

k

by factoring A(z) into polynomials with real coe¬cients that are either linear or quadratic, and

noting that all have log-concave coe¬cients, so their product does too.) One can prove other

results that allow zeros to lie in larger regions, but then it is necessary to impose restrictions

on ratios of their distances from the origin.

10.5. Implicit functions

’1

Section 6.2 presented functions, such as f (z), that are de¬ned implicitly. In this section

we consider related problems that arise when a generating function f (z) satis¬es a functional

equation f (z) = G(z, f (z)). Such equations arise frequently in graphical enumeration, and

there is a standard procedure invented by P´lya and developed by Otter that is almost algo-

o

rithmic [188, 189] and routinely leads to them. Typically G(z, w) is analytic in z and w in a

small neighborhood of (0, 0). Zeros of analytic functions in more than one dimension are not

isolated, and by the implicit function theorem G(z, w) = w is solvable for w as a function of

103

z, except for those points where

‚

Gw (z, w) = G(z, w) = 1 . (10.61)

‚w

Usually for z in a small neighborhood of 0 the solution w of G(z, w) = w will not satisfy

(10.61), and so w will be analytic in that neighborhood. As we enlarge the neighborhood

under consideration, though, a simultaneous solution to G(z, w) = w and (10.61) will eventually

appear, and will usually be the dominant singularity of f (z) = w(z). The following theorem

covers many common enumeration problems.

Theorem 10.6. Suppose that

∞

fn z n

f (z) = (10.62)

n=1

is analytic at z = 0, that fn ≥ 0 for all n, and that f (z) = G(z, f (z)), where

gm,n z m wn .

G(z, w) = (10.63)

m,n≥0

Suppose that there exist real numbers δ, r, s > 0 such that

(i) G(z, w) is analytic in |z| < r + δ and |w| < s + δ,

(ii) G(r, s) = s, Gw (r, s) = 1,

(iii) Gz (r, s) = 0 and Gww (r, s) = 0.

+

Suppose that gm,n ∈ ∪ {0} for all m and n, g0,0 = 0, g0,1 = 1, and gm,n > 0 for some m

¡

and some n ≥ 2. Assume further that there exist h > j > i ≥ 1 such that f h fi fj = 0 while the

greatest common divisor of j ’ i and h ’ i is 1. Then f (z) converges at z = r, f (r) = s, and

fn = [z n ]f (z) ∼ (rGz (r, s)/(2πGww (r, s)))1/2 n’3/2 r ’n as n ’ ∞ . (10.64)

Example 10.8. Rooted labeled trees. As was shown in Example 6.1, the exponential generat-

ing function t(z) of rooted labeled trees satis¬es t(z) = z exp(t(z)). Thus we have G(z, w) =

z exp(w), and Theorem 10.6 is easily seen to apply with r = e ’1 , s = 1. Therefore we obtain

the asymptotic estimate

tn /n! = [z n ]t(z) ∼ (2π)’1/2 n’3/2 en as n’∞. (10.65)

On the other hand, from Example 6.6 we know that t n = nn’1 , a much more satisfactory

answer, so that the estimate (10.65) only provides us with another proof of Stirling™s formula.

104

The example above involves an extremely simple application of Theorem 10.6. More com-

plicated cases will be presented in Section 15.1.

The statement of Theorem 10.6 is long, and the hypotheses stringent. All that is really

needed for the asymptotic relation (10.64) to hold is that f (z) should be analytic on {z : |z| ¤

r, z = r} and that

f (z) = c(r ’ z)1/2 + o(|r ’ z|1/2 ) (10.66)

for |z ’ r| ¤ , |Arg(r ’ z)| ≥ π/2 ’ for some > 0. If these conditions are satis¬ed,

then (10.64) follows immediately from either the transfer theorems of Section 11.1 or (with

stronger hypotheses) from Darboux™s method of Section 11.2. The purpose of Theorem 10.6 is

to present a general theorem that guarantees (10.66) holds, is widely applicable, and is stated

to the maximum extent possible in terms of conditions on the coe¬cients of f (z) and G(z, w).

Theorem 10.6 is based on Theorem 5 of [33] and Theorem 1 of [284]. The hypotheses

of Theorem 5 of [33] are simpler than those of Theorem 10.6, but, as was pointed out by

Can¬eld [67], the proof is faulty and there are counterexamples to the claims of that theorem.

The di¬culty is that Theorem 5 of [33] does not distinguish adequately between the di¬erent

solutions w = w(z) of w = G(z, w), and the singularity of the combinatorially signi¬cant

solution may not be the smallest among all singularities of all solutions. The result of Meir

and Moon [284] provides conditions that assure such pathological behavior does not occur.

(The statement of Theorem 10.6 incorporates some corrections to Theorem 1 of [284] provided

by the authors of that paper.) It would be desirable to prove results like (10.64) under a

simpler set of conditions.

In many problems the function G(z, w) is of the form

G(z, w) = g(z)φ(w) + h(z) , (10.67)

where g(z), φ(w), and h(z) are analytic at 0. For this case Meir and Moon have proved a

useful result (Theorem 2 of [284]) that implies an asymptotic estimate of the type (10.64).

The hypotheses of that result are often easier to verify than those of Theorem 10.6 above.

(As was noted by Meir and Moon, the last part of the conditions (4.12a) of [284] has to be

replaced by the condition that yi > hi , yj > hj , and yk > hk for some k > j > i ≥ 1 with

gcd(j ’ i, k ’ i) = 1.)

Whenever Theorem 10.6 applies, fn = [z n ]f (z) equals the quantity on the right-hand side

of (10.64) to within a multiplicative factor of 1 + O(n ’1 ). One can derive fuller expansions for

105

the ratio when needed.

11. Small singularities of analytic functions

In most combinatorial enumeration applications, the generating function has a single

dominant singularity. The methods used to extract asymptotic information about coe¬cients

split naturally into two main classes, depending on whether this singularity is large or small.

In some situations the same generating function can be said to have either a large or a small

singularity, depending on the range of coe¬cients that we are interested in. This is illustrated

by the following example.

Example 11.1. Partitions with bounded part sizes. Let p(n, m) be the number of (unordered)

partitions of an integer n into integers ¤ m. It is easy to see that

∞ m

n

(1 ’ z k )’1 .

Pm (z) = p(n, m)z = (11.1)

n=0 k=1

The function Pm (z) is rational, but has to be treated in di¬erent ways depending on the

relationship of n and m. If n is large compared to m, it turns out to be appropriate to say that

Pm (z) has a small singularity, and use methods designed for this type of problems. However,

if n is not too large compared to m, then the singularity of P m (z) can be said to be large.

(Since the largest part in a partition of n is almost always O(n 1/2 log n) [105], p(n, m) ∼ p(n)

if m is much larger than n1/2 log n.)

Although Pm (z) has singularities at all the k-th roots of unity for all k ¤ m, z = 1 is clearly

the dominant singularity, as |Pm (r)| grows much faster as r ’ 1’ than |Pm (z)| for z = r exp(iθ)

for any θ ∈ (0, 2π). If m is ¬xed, then the partial function decomposition can be used to obtain

the asymptotics of p(n, m) as m ’ ∞. We cannot use Theorem 9.1 directly, since the pole of

Pm (z) at z = 1 has multiplicity 1. However, either by using the generalizations of Theorem 9.1

that are mentioned in Section 9.1, or by the subtraction of singularities principle, we can show

that for any ¬xed m,

’1 ’1

m m

p(n, m) ∼ [z n ] (1 ’ z)’m ∼ ((m ’ 1)!)’1

k! k! as n’∞. (11.2)

k=1 k=1

(See [23] for further details and estimates.) This approach can be extended for m growing slowly

with n, and it can be shown without much e¬ort that the estimate (11.2) holds for n ’ ∞,

m ¤ log log n, say. However, for larger values of m this approach becomes cumbersome, and

other methods, such as those of Section 12, are necessary.

106

11.1. Transfer theorems

This section presents some results, drawn from [135], that allow one to translate an asymp-

totic expansion of a generating function around its dominant singularity into an asymptotic

expansion for the coe¬cients in a direct way. These results are useful in combinatorial enu-

meration, since the conditions for validity are frequently satis¬ed. The proofs, which we do

not present here, are based on the subtraction of singularities principle, but are more involved

than in the cases treated in Section 10.2.

We start out with an application of the results to be presented later in this section.

Example 11.2. 2-regular graphs. The generating function for 2-regular graphs is known [81]

to be

1 1

f (z) = (1 ’ z)’1/2 exp ’ z ’ z 2 . (11.3)

2 4

(A simpler proof can be obtained from the exponential formula, cf. Eq. (3.9.1) of [377].) We

see that f (z) is analytic throughout the complex plane except for the slit along the real axis

from 1 to ∞, and that near z = 1 it has the asymptotic expansion

1

f (z) = e’3/4 (1 ’ z)’1/2 + (1 ’ z)1/2 + (1 ’ z)3/2 + · · · . (11.4)

4

Theorem 11.1 below then shows that as n ’ ∞,

n ’ 1/2 n ’ 3/2 1 n ’ 5/2

[z n ]f (z) ∼ e’3/4 + + + ···

n n 4 n

e’3/4 5 15

√

∼ 1’ ’ + ··· . (11.5)

8n 128n2

πn

The basic transfer results will be presented for generating functions that have a single

dominant singularity, but can be extended substantially beyond their circle of convergence.

For r, · > 0, and 0 < φ < π/2, we de¬ne the closed domain ∆ = ∆(r, φ, ·) by

∆(r, φ, ·) = {z : |z| ¤ r + ·, |Arg(z ’ r)| ≥ φ} . (11.6)

In the main result below we will assume that a generating function is analytic throughout

∆ \ {r}. Later in this section we will mention some results that dispense with this requirement.

We will also explain why analyticity throughout ∆ \ {r} is helpful in obtaining results such as

those of Theorem 11.1 below.

One advantage to using Cauchy™s theorem to recover information about coe¬cients of gen-

erating functions is that it allows one to prove the intuitively obvious result that small smooth

107

changes in the generating function correspond to small smooth changes in the coe¬cients. We

will use the quantitative notion of a function of slow variation at ∞ to describe those functions

for which this notion can be made precise. (With more e¬ort one can prove that the same

results hold with a less restrictive de¬nition than that below.)

De¬nition 11.1. A function L(u) is of slow variation at ∞ if

i) There exist real numbers u0 and φ0 with u0 > 0, 0 < φ0 < π/2, such that L(u) is analytic

and = 0 in the domain

{u : |Arg(u ’ u0 )| ¤ π ’ φ0 } . (11.7)

Copyright Design by: Sunlight webdesign