LINEBURG


<< . .

 14
( 24)



. . >>

CA (z) = 1 + z+ jz , (10.48)
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)

<< . .

 14
( 24)



. . >>

Copyright Design by: Sunlight webdesign