<< . .

( 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)

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)
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 [161].) Zeilberger [405] has
used the word holonomic to describe corresponding sequences and generating functions.

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) =

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 [151].

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

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 [56] 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.

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 [222]), 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.
The binomial coe¬cients , 0 ¤ k ¤ n, are log-concave, and therefore unimodal. The
q-binomial coe¬cients are log-concave for any q ≥ 1. On the other hand, if we write a
single coe¬cient for ¬xed n and k as a polynomial in q, the sequence of coe¬cients is

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
ak z k
A(z) = (6.85)

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

values of the Stirling numbers of both kinds were ¬rst shown to be log-concave by this method
[195]. 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. [57]).
A variety of combinatorial, algebraic, and geometric methods have been used to prove
unimodality of sequences, and we refer the reader to [352] 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

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)

(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 [343].
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)

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
r ’n
n gA (n)2 = z GA (z) . (6.89)
dz z=1/2

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)

and therefore the variance is
22k CA (1/2)2 ’ (2k ’ 1)2k CA (1/2) + 2k CA (1/2)
= 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
[50]). A su¬cient condition for the µ(k) to determine F (x) uniquely is that the generating

U (x) = (6.93)
should converge for some x > 0. In particular, the standard normal distribution with
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)

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

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. [349]) that
∞ ∞ ∞
(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. ([33]) 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 [33], 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

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)


A(z) = exp(k(k ’ 1)z/2)/k! . (7.6)
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)

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
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. [394])
∞ ∞
xn xn
1+ Fn = exp fn . (7.10)
n! n!
n=1 n=1

Theorem 7.2. ([34]) Suppose that

an xn , fhk xh y k ,
a(x) = F (x, y) =
n=1 h,k≥0

bn xn = F (x, a(x)) ,
b(x) = D(x) = Fy (x, a(x)) ,

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

an’1 = o(an ) as n’∞, (7.12)

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

(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)

bn = dk an’k + O(an’r ) . (7.15)

Condition (iii) of Theorem 7.2 is often hard to verify. Theorem 2 of [34] 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 [34] 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)

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 [393].

Example 7.2. Indecomposable permutations [81]. 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 [81]

<< . .

( 24)

. . >>

Copyright Design by: Sunlight webdesign