LINEBURG

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

Doubly-indexed arrays, for example a n,k , 0 в‰¤ n < в€ћ, 0 в‰¤ k в‰¤ n, are encoded as two-variable
generating functions. Depending on the array, sometimes one uses
в€ћ n
an,k xk y n ,
f (x, y) = (6.3)
n=0 k=0

and sometimes other forms that might even mix ordinary and exponential types, as in
в€ћ n
yn
an,k xk .
f (x, y) = (6.4)
n!
n=0 k=0

For example, the Stirling numbers of the п¬Ѓrst kind, s(n, k) ((в€’1) n+k s(n, k) is the number of
permutations on n letters with k cycles) have the generating function (see pp. 50, 212вЂ“213,
and 234вЂ“235 in )
в€ћ n
yn
s(n, k)xk = (1 + y)x .
1+ (6.5)
n!
n=1 k=1

In general, a generating function is just a formal power series, and questions of convergence
do not arise in the deп¬Ѓnition. However, some of the main applications of generating functions
in asymptotic enumeration do rely on analyticity or other convergence properties of those
functions, and there the domain of convergence is important.
A generating function is just another form for the sequence that deп¬Ѓnes it. There are many
reasons for using it. One is that even for complicated sequences, generating functions are

32
frequently simple. This might not be obvious for the partition function p(n), which has the
ordinary generating function
в€ћ в€ћ
n
(1 в€’ z k )в€’1 .
f (z) = p(n)z = (6.6)
n=0 k=1

The sequence p(n), which is complicated, is encoded here as an inп¬Ѓnite product. The terms in
the product are simple and vary in a regular way with the index, but it is not clear at п¬Ѓrst what
is gained by this representation. In other cases, though, the advantages of generating functions
are clearer. For example, the exponential generating function for derangements (Eq. (1.1) and
Example 5.6) is
в€ћ в€ћ n
zn
dn n n!
(в€’1)k
f (z) = z=
n! n! k!
n=0 n=0 n=0
в€ћ в€ћ
(в€’1)k eв€’z
zn =
= , (6.7)
k! 1в€’z
k=0 n=k

which is extremely compact.
Reasons for using generating functions go far beyond simplicity. The one that matters
most for this chapter in that generating functions can be used to obtain information about the
asymptotic behavior of sequences they encode, information that often cannot be obtained in
any other way, or not as easily. Methods such as those of Section 10.2 can be used to obtain
immediately from Eq. (6.7) the asymptotic estimate d n в€ј eв€’1 n! as n в†’ в€ћ. This estimate can
also be derived easily by elementary methods from Eq. (1.1), so here the generating function is
not essential. In other cases, though, such as that of the partition function p(n), all the sharp
estimates, such as that of Hardy and Ramanujan given in (1.5), are derived by exploiting the
properties of the generating function. If there is any main theme to this chapter, it is that
generating functions are usually the easiest, most versatile, and most powerful way to study
asymptotic behavior of sequences. Especially when the generating function is analytic, its
behavior at the dominant singularities (a term that will be deп¬Ѓned in Section 10) determines
the asymptotics of the sequence. When the generating function is simple, and often even when
it is not simple, the contribution of the dominant singularity can often be determined easily,
although the sequence itself is complicated.
There are many applications of generating functions, some related to asymptotic questions.
Averages can often be studied using generating functions. Suppose, for example, that a n,k ,
0 в‰¤ k в‰¤ n, 0 в‰¤ n < в€ћ, is the number of objects in some class of size n, which have weight k

33
(for some deп¬Ѓnition of size and weight), and that we know, either explicitly or implicitly, the
generating function f (x, y) of an,k given by (6.4). Then
в€ћ n
yn
g(y) = f (1, y) = an,k (6.8)
n!
n=0 k=0

is the exponential generating function of the number of objects of size n, while
в€ћ n
yn
в€‚
h(y) = f (x, y) = kan.k (6.9)
в€‚x n!
x=1
n=0 k=0

is the exponential generating function of the sum of the weights of objects of size n. Therefore
the average weight of an object of size n is

[y n ]h(y)
. (6.10)
[y n ]g(y)

The wide applicability and power of generating functions come primarily from the struc-
tured way in which most enumeration problems arise. Usually the class of objects to be counted
is derived from simpler objects through basic composition rules. When the generating func-
tions are chosen to reп¬‚ect appropriately the classes of objects and composition rules, the п¬Ѓnal
generating function is derivable in a simple way from those of the basic objects. Suppose,
for example, that each object of size n in class C can be decomposed uniquely into a pair of
objects of sizes k and n в€’ k (for some k) from classes A and B, and each pair corresponds to
an object in C. Then cn , the number of objects of size n in C, is given by the convolution
n
cn = ak bnв€’k , (6.11)
k=0

an z n , B(z) =
(where ak is the number of objects of size k in A, etc.). Hence if A(z) =
bn z n , C(z) = cn z n are the ordinary generating functions, then

C(z) = A(z)B(z) . (6.12)

Thus ordered pairing of objects corresponds to multiplication of ordinary generating functions.
an z n and
If A(z) =
n
bn = ak ,
k=0

bn z n is given by
then B(z) =
A(z)
B(z) = , (6.13)
1в€’z

34
so that the ordinary generating function of cumulative sums of coeп¬ѓcients is obtained by
dividing by 1 в€’ z. There are many more such general correspondences between operations
on combinatorial objects and on the corresponding generating functions. They are present,
implicitly or explicitly, in most books that cover combinatorial enumeration, such as [81, 173,
351, 377]. The most systematic approach to developing and using general rules of this type has
been carried out by Flajolet and his collaborators . They develop ways to see immediately
(cf. ) that if we consider mappings of a set of n labeled elements to itself, so that all n n
distinct mappings are considered equally likely, then the generating function for the longest
path length is given by
в€ћ
1
в€’ evk (z)
f (z) = , (6.14)
1 в€’ t(z)
k=0

where
1 1
vk (z) = tkв€’1 (z) + tkв€’2 (z)2 + В· В· В· + t0 (k)k , (6.15)
2 k
with
t0 (z) = z , th+1 (z) = z exp(th (z)) , (6.16)

and t(z) = lim th (z) (in the sense of formal power series, so convergence is that of coeп¬ѓcients).
hв†’в€ћ
Furthermore, as is mentioned in Section 17, many of these rules for composition of objects and
generating functions can be implemented algorithmically, automating some of the chores of
applying them.
We illustrate some of the basic generating function techniques by deriving the generating
function for rooted labeled trees, which will occur later in Examples 6.6 and 10.8. (The rooted
unlabeled trees, with generating function given by (1.8), are harder.)

Example 6.1. Rooted labeled trees. Let t n be the number of rooted labeled trees on n vertices,
so that t1 = 1, t2 = 2, t3 = 9. (It will be shown in Example 6.6 that t n = nnв€’1 .) Let
в€ћ
zn
t(z) = tn (6.17)
n!
n=1

be the exponential generating function. If we remove the root of a rooted labeled tree with n
vertices, we are left with k в‰Ґ 0 rooted labeled trees that contain a total of n в€’ 1 vertices. The
total number of ways of arranging an ordered selection of k rooted trees with a total of n в€’ 1
vertices is
[z nв€’1 ]t(z)k .

35
Since the order of the trees does not matter, we have

1 nв€’1
]t(z)k
[z
k!

diп¬Ђerent trees of size n that have exactly k subtrees, and so
в€ћ
1 nв€’1
]t(z)k
tn = [z
k!
k=0
в€ћ
nв€’1
t(z)k /k! = [z n ]z exp(t(z)) ,
= [z ] (6.18)
k=0

which gives
t(z) = z exp(t(z)) . (6.19)

As an aside, the function th (z) of Eq (6.16) is the exponential generating function of rooted
labeled trees of height в‰¤ h.
В

The key to the successful use of generating functions is to use a generating function that is
of the appropriate form for the problem at hand. There is no simple rule that describes what
generating function to use, and sometimes two are used simultaneously. In combinatorics
and analysis of algorithms, the most useful forms are the ordinary and exponential generating
functions, which reп¬‚ects how the classes of objects that are studied are constructed. Sometimes
other forms are used, such as the double exponential form
в€ћ
an z n
f (z) = (6.20)
(n!)2
n=0

that occurs in Section 7, or the Newton series
в€ћ
f (z) = an z(z в€’ 1) В· В· В· (z в€’ n + 1) . (6.21)
n=0

Also frequently encountered are various q-analog generating functions, such as the Eulerian
в€ћ
an z n
f (z) = . (6.22)
(1 в€’ q)(1 в€’ q 2 ) В· В· В· (1 в€’ q n )
n=1

In multiplicative number theory, the most common are Dirichlet series
в€ћ
an nв€’z ,
f (z) = (6.23)
n=1

which reп¬‚ect the multiplicative structure of the integers. If a n is a multiplicative function (so
that amn = am an for all relatively prime positive integers m and n) then the function (6.23)

36
has an Euler product representation

(1 + ap pв€’z + ap2 pв€’2z + В· В· В·) ,
f (z) = (6.24)
p

where p runs over the primes. This allows new tools to be used to study f (z) and through it
an . Additive problems in combinatories and number theory often are handled using functions
such as functions such as
в€ћ
z ak ,
f (z) = (6.25)
n=1

where 0 в‰¤ a1 < a2 < В· В· В· is a sequence of integers. Addition of two such sequences then
corresponds to a multiplication of the generating functions of the form (6.25).
We next mention the вЂњsnake oil method.вЂќ This is the name given by Wilf  to the
use of generating functions for proving identities, and comes from the surprising power of this
technique. The typical application is to evaluation of sequences given by sums of the type

an = bn,k . (6.26)
k

The standard procedure is to form a generating function of the a n and manipulate it through
interchanges of summation and other tricks to obtain the п¬Ѓnal answer. The generating function
can be ordinary, exponential, or (less commonly) of another type, depending on what gives the
best results. We show a simple application of this principle that exhibits the main features of
the method.

Example 6.2. A binomial coeп¬ѓcient sum . Let
n
n + k nв€’k
an = 2 , nв‰Ґ0. (6.27)
2k
k=0

We deп¬Ѓne A(z) to be the ordinary generating function of a n . We п¬Ѓnd that
в€ћ в€ћ n
n + k nв€’k
an z n = zn
A(z) = 2
2k
n=0 n=0 k=0
в€ћ в€ћ в€ћ в€ћ
n+k n+k
в€’k nn в€’k в€’k
(2z)n+k
= 2 2z = 2 (2z)
2k 2k
n=0
k=0 n=k k=0
в€ћ в€ћ k
(2z)2k 1 z
в€’k в€’k
= 2 (2z) =
(1 в€’ 2z)2k+1 1 в€’ 2z 1 в€’ 2z
k=0 k=0
1 в€’ 2z 2 1
= = + . (6.28)
(1 в€’ 4z)(1 в€’ z) 3(1 в€’ 4z) 3(1 в€’ z)

37
Therefore we immediately п¬Ѓnd the explicit form

an = (22n+1 + 1)/3 for nв‰Ґ0. (6.29)

В

We next present some additional examples of how generating functions are derived. We
start by considering linear recurrences with constant coeп¬ѓcients.
The п¬Ѓrst step in solving a linear recurrence is to obtain its generating function. Suppose
that a sequence a0 , a1 , a2 , . . . satisп¬Ѓes the recurrence
d
an = ci anв€’i , nв‰Ґd. (6.30)
i=1

Then
в€ћ dв€’1 в€ћ d
n n n
f (z) = an z = an z + z ci anв€’i (6.31)
n=0 n=0 i=1
n=d
dв€’1 d в€ћ
n i
anв€’i z nв€’i
= an z + ci z
n=0 i=1 n=d
dв€’1 d dв€’iв€’1
an z n + ci z i an z n
= f (z) в€’ ,
n=0 n=0
i=1

and so
g(z)
f (z) = , (6.32)
d i
1в€’ i=1 ci z
where
dв€’1 d dв€’iв€’1
n i
an z n
g(z) = an z в€’ ci z (6.33)
n=0 n=0
i=1

is a polynomial of degree в‰¤ d в€’ 1. Eq. (6.32) is the fundamental relation in the study of linear
ci z i is called the characteristic polynomial of the recursion.
recurrences, and 1 в€’

Example 6.3. Fibonacci numbers. We let F 0 = 0, F1 = 1, Fn = Fnв€’1 + Fnв€’2 for n в‰Ґ 2, and
в€ћ
Fn z n .
F (z) =
n=0

Then by (6.32) and (6.33),
z
F (z) = . (6.34)
В

1 в€’ z в€’ z2

38
Often there is no obvious recurrence for the sequence a n being studied, but there is one
involving some other auxiliary function. Usually if one can obtain at least as many recurrences
as there are sequences, one can obtain their generating functions by methods similar to those
used for a single sequence. The main additional complexity comes from the need to solve a
system of linear equations with polynomial coeп¬ѓcients. We illustrate this with the following
example.

Example 6.4. Sequences with forbidden subwords. Let A = a 1 a2 В· В· В· ak be a binary string of
length k. Deп¬Ѓne fA (n) to be the number of binary strings of length n that do not contain A
as a subword of k adjacent characters. (Subsequences do not count, so that if A = 1110, then
A is contained in 1101110010, but not in 101101.) We introduce the correlation polynomial
CA (z) of A:
kв€’1
cA (j)z j ,
CA (z) = (6.35)
 << Пред. стр. страница 5(всего 24)ОГЛАВЛЕНИЕ След. стр. >>