LINEBURG

 << Пред. стр. страница 7(всего 24)ОГЛАВЛЕНИЕ След. стр. >>

for example. The same estimate can be obtained by the bootstrapping technique.
В

6.3. Diп¬Ђerentiably п¬Ѓnite power series

Homogeneous recurrences with constant coeп¬ѓcients are the nicest large set of sequences
one can imagine, with rational generating functions, and well-understood asymptotic behavior.
The next class in complexity consists of the polynomially-recursive or, P -recursive sequences,
a0 , a1 , . . ., which satisfy recurrences of the form

pd (n)an+d + pdв€’1 (n)an+dв€’1 + В· В· В· + p0 (n)an = 0, nв‰Ґ0, (6.80)

46
where d is п¬Ѓxed and p0 (n), . . . , pd (n) are polynomials in n. Such sequences are common in
combinatorics, with an = n! a simple example. Normally P -recursive sequences do not have
explicit forms for their generating functions. In this section we brieп¬‚y summarize some of
their main properties. Asymptotic properties of P -recursive sequences will be discussed in
Section 9.2. The main references for the results quoted here are [254, 350].
A formal power series
в€ћ
ak z k
f (z) = (6.81)
k=0
dn f (z)
is called diп¬Ђerentiably п¬Ѓnite, or D-п¬Ѓnite, if the derivatives f (n) (z) = dz n , n в‰Ґ 0, span a
п¬Ѓnite-dimensional vector space over the п¬Ѓeld of rational functions with complex coeп¬ѓcients.
The following three conditions are equivalent for a formal power series f (z):

i) f (z) is D-п¬Ѓnite.

ii) There exist п¬Ѓnitely many polynomials q 0 (z), . . . , qk (z) and a polynomial q(z), not all 0,
such that
qk (z)f (k) (z) + В· В· В· + q0 (z)f (z) = q(z) . (6.82)

iii) There exist п¬Ѓnitely many polynomials p 0 (z), . . . , pm (z), not all 0, such that

pm (z)f (m) (z) + В· В· В· + p0 (z)f (z) = 0 . (6.83)

The most important result for combinatorial enumeration is that a sequence a 0 , a1 , . . ., is
P -recursive if and only if its ordinary generating function f (z), deп¬Ѓned by (6.81), is D-п¬Ѓnite.
This makes it possible to apply results that are more easily proved for D-п¬Ѓnite power series.
If f (z) is D-п¬Ѓnite, then so is the power series obtained by changing a п¬Ѓnite number of the
coeп¬ѓcients of f (z). If f (z) is algebraic (i.e., there exist polynomials q 0 (z), . . . , qd (z), not all
0, such that qd (z)f (z)d + В· В· В· + q0 (z)f (z) + q0 (z) = 0), then f (z) is D-п¬Ѓnite. The product
of two D-п¬Ѓnite power series is also D-п¬Ѓnite, as is any linear combination with polynomial
coeп¬ѓcients. Finally, the Hadamard product of two D-п¬Ѓnite series is D-п¬Ѓnite. The proofs rely
on elementary linear algebra constructions. An important feature of the theory is that identity
between D-п¬Ѓnite series is decidable.
The concept of a D-п¬Ѓnite power series can be extended to several variables [254, 405], and
there are generalizations of P -recursiveness [254, 405]. (See also .) Zeilberger  has
used the word holonomic to describe corresponding sequences and generating functions.

47
When we investigate a sequence {an }, sometimes the combinatorial context yields only
relations for more complicated object with several indices. While we might like to obtain the
an z n , we might instead п¬Ѓnd a formula for a generating function
generating function f (z) =

n
n
b n1 , . . . , n k z 1 1 , . . . , z k k ,
F (z1 , z2 , . . . , zk ) = (6.84)
n1 ,...,nk

where an = bn,n,...,n , say. When this happens, we say that f (z) is a diagonal of F (z 1 , . . . , zk ).
(There are more general deп¬Ѓnitions of diagonals in [90, 253, 254, 255], which are recent refer-
ences for this topic.) Diagonals of D-п¬Ѓnite power series in any number of variables are D-п¬Ѓnite.
Diagonals of two-variable rational functions are algebraic, but there are three-variable rational
functions whose diagonals are not algebraic .

6.4. Unimodality and log-concavity

A п¬Ѓnite sequence a0 , a1 , . . . , an of real numbers is called unimodal if for some index k,
a0 в‰¤ a1 в‰¤ В· В· В· в‰¤ ak and ak в‰Ґ ak+1 в‰Ґ В· В· В· в‰Ґ an . A sequence a0 , . . . , an of nonnegative
elements is called log-concave (short for logarithmically concave) if a 2 в‰Ґ ajв€’1 aj+1 holds for
j

1 в‰¤ j в‰¤ n в€’ 1. Unimodal and log-concave sequences occur frequently in combinatorics and
are objects of intensive study. We present a brief review of some of their properties because
asymptotic methods are often used to prove unimodality and log-concavity. Furthermore,
knowledge that a sequence is log-concave or unimodal is often helpful in obtaining asymptotic
information. For example, some methods provide only asymptotic estimates for summatory
functions of sequences, and unimodality helps in obtaining from those estimates bounds on
individual coeп¬ѓcients. This approach will be presented in Section 13, in the discussion of
central and local limit theorems.
The basic references for unimodality and log-concavity are [222, 352]. For recent results,
see also  and the references given there. All the results listed below can be found in those
sources and the references they list.
In the rest of this subsection we will consider only sequences of nonnegative elements.
A sequence a0 , . . . , an will be said to have no internal zeros if there is no triple of integers
0 в‰¤ i < j < k в‰¤ n such that aj = 0, ai ak = 0. It is easy to see that a log-concave
sequence with no internal zeros is unimodal, but there are sequences of positive elements that
are unimodal but not concave. The convolution of two unimodal sequences does not have to
be unimodal. However, it is unimodal if each of the two unimodal sequences is also symmetric.

48
Convolution of two log-concave sequences is log-concave. The convolution of a log-concave and
a unimodal sequence is unimodal. A log-concave sequence is even characterized by the property
that its convolution with any unimodal sequence is unimodal. This last property is related
to the variation-diminishing character of log-concave sequences (see ), which we will not
discuss at greater length here except to note that there are more restrictive sets of sequences
(the PВґlya frequency classes, see [56, 222]) which have stronger convolution properties.
o
n
The binomial coeп¬ѓcients , 0 в‰¤ k в‰¤ n, are log-concave, and therefore unimodal. The
k
n
q-binomial coeп¬ѓcients are log-concave for any q в‰Ґ 1. On the other hand, if we write a
kq
n
single coeп¬ѓcient for п¬Ѓxed n and k as a polynomial in q, the sequence of coeп¬ѓcients is
kq

unimodal, but does not have to be log-concave.
The most frequently used method for showing that a sequence a 0 , . . . , an is log-concave is
to show that all the zeros of the polynomial
n
ak z k
A(z) = (6.85)
k=0

n в€’1
are real and в‰¤ 0. In that case not only are the a k log-concave, but so are ak . Absolute
k

values of the Stirling numbers of both kinds were п¬Ѓrst shown to be log-concave by this method
. There are many unsolved conjectures about log-concavity of combinatorial sequences,
such as the Read-Hoggar conjecture that coeп¬ѓcients of chromatic polynomials are log-concave
(cf. ).
A variety of combinatorial, algebraic, and geometric methods have been used to prove
unimodality of sequences, and we refer the reader to  for a comprehensive and insightful
survey. In Section 12.3 we will discuss brieп¬‚y some proofs of unimodality and log-concavity
that use asymptotic methods. The basic philosophy is that since the Gaussian distribution is
log-concave and unimodal (when we extend the deп¬Ѓnition of these concepts to continuous dis-
tributions), these properties should also hold for sequences that by the central limit theorem or
its variants are asymptotic to the Gaussian. Therefore one can expect high-order convolutions
of sequences to be log-concave at least in their central region, and there are theorems that
prove this under certain conditions.

6.5. Moments and distributions

The second moment method is a frequently used technique in probabilistic arguments, as
is shown in Chapter ? and [55, 108, 348]. It is based on ChebyshevвЂ™s inequality, which says

49
that if X is a real-valued random variable with п¬Ѓnite second moment E(X 2 ), then

E(X 2 ) в€’ E(X)2
Prob (|X в€’ E(X)| в‰Ґ О±|E(X)|) в‰¤ . (6.86)
О±2 E(X)2

An easy corollary of inequality (6.86) that is often used is

E(X 2 ) в€’ E(X)2
Prob (X = 0) в‰¤ . (6.87)
E(X)2

(There is a slightly stronger version of the inequality (6.87), in which E(X) 2 in the denominator
is replaced by E(X 2 ).) The inequalities (6.86) and (6.87) are usually applied for X = Y 1 +
В· В· В· + Yn , where the Yj are other random variables. The helpful feature of the inequalities is
that they require only knowledge of the pairwise dependencies among the Y j , which is easier
to study than the full joint distribution of the Y j . For other bounds on distributions that can
be obtained from partial information about moments, see .
The reason moment bounds are mentioned at all in this chapter is that asymptotic methods
are often used to derive them. Generating functions are a common and convenient method for
doing this.

Example 6.8. Waiting times for subwords. In a continuation and application of Example 6.4,
let A be a binary string of length k. How many tosses of a fair coin (with sides labeled 0 and
1) are needed on average before A appears as a block of k consecutive outcomes? By a general
observation of probability theory, this is just the sum over n в‰Ґ 0 of the probability that A does
not appear in the п¬Ѓrst n coin tosses, and thus equals
в€ћ
fA (n)2в€’n = FA (1/2) = 2k CA (1/2) , (6.88)
n=0

where the last equality follows from Eq. (6.38). Another, more general, way to derive this is
to use GA (z). Note that gA (n)2в€’n is the probability that A appears in the п¬Ѓrst n coin tosses,
but not in the п¬Ѓrst n в€’ 1. Hence the r-th moment of the time until A appears is
в€ћ r
d
r в€’n
n gA (n)2 = z GA (z) . (6.89)
dz z=1/2
n=0

If we take r = 1, we again obtain the expected waiting time given by (6.88). When we take
r = 2, we п¬Ѓnd that the second moment of the time until the appearance of A is
в€ћ
n2 gA (n)2в€’n = 22k+1 CA (1/2)2 в€’ (2k в€’ 1)2k CA (1/2) + 2k CA (1/2) , (6.90)
n=0

50
and therefore the variance is
22k CA (1/2)2 в€’ (2k в€’ 1)2k CA (1/2) + 2k CA (1/2)
(6.91)
= 22k CA (1/2)2 + O(k2k ) ,

since 1 в‰¤ CA (1/2) в‰¤ 2. Higher moments can be used to obtain more detailed information.
A better approach is to use the method of Example 9.2, which gives precise estimates for the
tails as well as the mean of the distribution.
В

Information about moments of distribution functions can often be used to obtain the lim-
iting distribution. If Fn (x) is a sequence of distribution functions such that for every integer
k в‰Ґ 0, the k-th moment
xk dFn (x)
Вµn (k) = (6.92)

converges to Вµ(k) as n в†’ в€ћ, then there is a limiting measure with distribution function F (x)
whose k-th moment is Вµ(k). If the moments Вµ(k) do not grow too rapidly, then they determine
the distribution function F (x) uniquely, and the F n (x) converge to F (x) (in the weak star sense
). A suп¬ѓcient condition for the Вµ(k) to determine F (x) uniquely is that the generating
function
в€ћ
Вµ(2k)xk
U (x) = (6.93)
(2k)!
k=0
should converge for some x > 0. In particular, the standard normal distribution with
x
в€’1/2
exp(в€’u2 /2)du
F (x) = (2ПЂ) (6.94)
в€’в€ћ

has Вµ(2k) = 1 В· 3 В· 5 В· 7 В· . . . В· (2k в€’ 1) (and Вµ(2k + 1) = 0), so it is determined uniquely by its
moments. On the other hand, there are some frequently encountered distributions, such as the
log-normal one, which do not have this property.

7. Formal power series

This section discusses generating functions f (z) that might not converge in any interval
around the origin. Sequences that grow rapidly are common in combinatorics, with a n = n!
the most obvious example for which
в€ћ
an z n
f (z) = (7.1)
n=0

does not converge for any z = 0. The usual way to deal with the problem of a rapidly growing
sequence an is to study the generating function of a n /bn , where bn is some sequence with

51
known asymptotic behavior. When bn = n!, the ordinary generating function of a n /bn is then
the exponential generating function of a n . For derangements (Eqs. (1.1) and (6.7)) this works
well, as the exponential generating function of d n converges in |z| < 1 and has a nice form.
Unfortunately, while we can always п¬Ѓnd a sequence b n that will make the ordinary generating
function f (z) of an /bn converge (even for all z), usually we cannot do it in a way that will
yield any useful information about f (z). The combinatorial structure of a problem almost
always severely restricts what forms of generating function can be used to take advantage of
the special properties of the problem. This diп¬ѓculty is common, for example, in enumeration
of labeled graphs. In such cases one often resorts to formal power series that do not converge
in any neighborhood of the origin. For example, if c(n, k) is the number of connected labeled
graphs on n vertices with k edges, then it is well known (cf. ) that
m
в€ћ в€ћ в€ћ
(1 + x)( 2 ) y m
xk y n
c(n, k) = log . (7.2)
n! m!
n=0 k=0 m=0

While the series inside the log in (7.2) does converge for в€’2 в‰¤ x в‰¤ 0, and any y, it diverges
for any x > 0 as long as y = 0, and so this is a relation of formal power series.
There are few methods for dealing with asymptotics of formal power series, at least when
compared to the wealth of techniques available for studying analytic generating functions.
Fortunately, combinatorial enumeration problems that do require the use of formal power series
often involve rapidly growing sequences of positive terms, for which some simple techniques
apply. We start with an easy general result that is applicable both to convergent and purely
formal power series.

an z n and b(z) = bn z n are power series with
Theorem 7.1. () Suppose that a(z) =
radii of convergence О± > ОІ в‰Ґ 0, respectively. Suppose that b nв€’1 /bn в†’ ОІ as n в†’ в€ћ. If
cn z n = a(z)b(z), then
a(ОІ) = 0, and

cn в€ј a(ОІ)bn as nв†’в€ћ . (7.3)

The proof of Theorem 7.1, which can be found in , is simple. The condition О± > ОІ is
important, and cannot be replaced by О± = ОІ. We can have ОІ = 0, and that is indeed the only
possibility if the series for b(z) does not converge in a neighborhood of z = 0.

Example 7.1. Double set coverings [33, 80]. Let v n be the number of choices of subsets
S1 , . . . , Sr of an n-element set T such that each t в€€ T is in exactly two of the S i . There is

52
no restriction on r, the number of subsets, and some of the S i can be repeated. Let cn be
cn z n /n!,
the corresponding number when the S i are required to be distinct. We let C(z) =
vn z n /n! be the exponential generating functions. Then it can be shown that
V (z) =

C(z) = exp(в€’1 в€’ (ez в€’ 1)/2)A(z) , (7.4)

V (z) = exp(в€’1 + (ez в€’ 1)/2)A(z) , (7.5)

where
в€ћ
A(z) = exp(k(k в€’ 1)z/2)/k! . (7.6)
k=0
We see immediately that A(z) does not converge in any neighborhood of the origin. We have
в€ћ
k n (k в€’ 1)n
n в€’n
an = [z ]A(z) = 2 . (7.7)
k!
k=2

By considering the ratio of consecutive terms in the sum in (7.7), we п¬Ѓnd that the largest term
occurs for k = k0 with k0 log k0 в€ј 2n, and by the methods of Section 5.1 we п¬Ѓnd that
ПЂ 1/2 k0 (k0 в€’ 1)n
n
an в€ј 1/2 n as nв†’в€ћ. (7.8)
n 2 (k0 в€’ 1)!
Therefore anв€’1 /an в†’ 0 as n в†’ в€ћ, and Theorem 7.1 tells us that

cn в€ј vn в€ј eв€’1 n!an as nв†’в€ћ. (7.9)
В

Usually formal power series occur in more complicated relations than those covered by
Theorem 7.1. For example, if fn is the number of connected graphs on n labeled vertices
which have some property, and Fn is the number of graphs on n labeled vertices each of whose
connected components has that property, then (cf. )
в€ћ в€ћ
xn xn
1+ Fn = exp fn . (7.10)
n! n!
n=1 n=1

Theorem 7.2. () Suppose that
в€ћ
an xn , fhk xh y k ,
a(x) = F (x, y) =
n=1 h,kв‰Ґ0
(7.11)
в€ћ
bn xn = F (x, a(x)) ,
b(x) = D(x) = Fy (x, a(x)) ,
n=0

where Fy (x, y) is the partial derivative of F (x, y) with respect to y. Assume that a n = 0 and

53
(i)
anв€’1 = o(an ) as nв†’в€ћ, (7.12)

(ii)
nв€’r
|ak anв€’k | = O(anв€’r ) for some r>0 , (7.13)
k=r

(iii) for every Оґ > 0 there are M (Оґ) and K(Оґ) such that for n в‰Ґ M (Оґ) and h + k > r + 1,

|fhk anв€’hв€’k+1 | в‰¤ K(Оґ)Оґ h+k |anв€’r | . (7.14)

Then
rв€’1
bn = dk anв€’k + O(anв€’r ) . (7.15)
k=0

Condition (iii) of Theorem 7.2 is often hard to verify. Theorem 2 of  shows that this
condition holds under certain simpler hypotheses. It follows from that result that (iii) is
valid if F (x, y) is analytic in x and y in a neighborhood of (0, 0). Hence, if F (x, y) = exp(y) or
F (x, y) = 1+y, then Theorem 7.2 becomes easy to apply. One can also deduce from Theorem 2
of  that Theorem 7.2 applies when (i) and (ii) hold, b 0 = 0, bn в‰Ґ 0, and
в€ћ
b(z k )/k
1 + a(z) = exp , (7.16)
k=1

another relation that is common in graph enumeration (cf. Example 15.1). There are also
some results weaker than Theorem 7.2 that are easier to apply .

Example 7.2. Indecomposable permutations . For every permutation Пѓ of {1, . . . , n), let
{1, . . . , n} = в€ЄIh , where the Ih are the smallest intervals such that Пѓ(I h ) = Ih for all h.
For example, Пѓ = (134)(2)(56) corresponds to I 1 = {1, 2, 3, 4}, I2 = {5, 6}, and the identity
permutation has n components. A permutation is said to be indecomposable if it has one
component. For example, if Пѓ has the 2-cycle (1n), it is indecomposable. Let c n be the number
of indecomposable permutations of {1, . . . , n}. Then 
в€ћ
 << Пред. стр. страница 7(всего 24)ОГЛАВЛЕНИЕ След. стр. >>