LINEBURG

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

where cA (0) = 1 and for 1 в‰¤ j в‰¤ k в€’ 1,
1 if a1 a2 В· В· В· akв€’j = aj+1 aj+2 В· В· В· ak ,
cA (j) = (6.36)
0 otherwise .
As examples, we note that if A = 1000, then C A (z) = 1, whereas CA (z) = 1 + z + z 2 + z 3 if
A = 1111. The generating function
в€ћ
fA (n)z n
FA (z) = (6.37)
n=0

then satisп¬Ѓes
CA (z)
FA (z) = . (6.38)
z k + (1 в€’ 2z)CA (z)
To prove this, deп¬Ѓne gA (n) to be the number of binary sequences b 1 b2 В· В· В· bn of length n such
that b1 b2 В· В· В· bk = A, but such that bj bj+1 В· В· В· bj+kв€’1 = A for any j with 2 в‰¤ j в‰¤ n в€’ k + 1; i.e.,
sequences that start with A but do not contain it any place else. We then have g A (n) = 0 for
n < k, and gA (k) = 1. We also deп¬Ѓne
в€ћ
gA (n)z n .
GA (z) = (6.39)
n=0

We next obtain a relation between GA (z) and FA (z) that will enable us to determine both.
If b1 b2 В· В· В· bn is counted by fA (n), then for x either 0 or 1, the string xb 1 b2 В· В· В· bn either does
not contain A at all, or if it does contain it, then A = xb 1 b2 В· В· В· bkв€’1 . Therefore for n в‰Ґ 0,

2fA (n) = fA (n + 1) + gA (n + 1) (6.40)

39
and multiplying both sides of Eq. (6.40) by z n and summing on n в‰Ґ 0 yields

2FA (z) = z в€’1 (FA (z) в€’ 1) + z в€’1 GA (z) . (6.41)

We need one more relation, and to obtain it we consider any string B = b 1 b2 В· В· В· bn that
does not contain A any place inside. If we let C be the concatenation of A and B, so that
C = a1 a2 В· В· В· ak b1 b2 В· В· В· bn , then C starts with A, and may contain other occurrences of A, but
only at positions that overlap with the initial A. Therefore we obtain,
k
fA (n) = gA (n + j) for n в‰Ґ 0 , (6.42)
j=1
cA (kв€’j)=1

and this gives the relation
FA (z) = z в€’k CA (z)GA (z) . (6.43)

Solving the two equations (6.41) and (6.43), we п¬Ѓnd that F A (z) satisп¬Ѓes (6.38), while

zk
GA (z) = k . (6.44)
z + (1 в€’ 2z)CA (z)

The proof above follows that in , except that  uses generating functions in z в€’1 , so
the formulas look diп¬Ђerent. Applications of the formulas (6.38) and (6.44) will be found later
in this chapter, as well as in [182, 130]. Other approaches to string enumeration problems are
referenced there as well. Other approaches and applications of string enumerations are given
in the references to  and in papers such as .
В

The above example can be generalized to provide generating functions that enumerate
sequences in which any of a given set of patterns are forbidden .
Whenever one has a п¬Ѓnite system of linear recurrences with constant coeп¬ѓcients that in-
(i)
volve several sequences, say an , 1 в‰¤ i в‰¤ k, n в‰Ґ 0, one can translate these recurrences into
(i)
linear equations with polynomial coeп¬ѓcients in the generating functions A (i) (z) = an z n for
these sequences. To obtain the A(i) (z), one then needs to solve the resulting system. Such so-
lutions will exist if the matrix of polynomial coeп¬ѓcients is nonsingular over the п¬Ѓeld of rational
functions in z. In particular, one needs at least as many equations (i.e., recurrence relations)
as k, the number of sequences, and if there are exactly as many equations as sequences, then
the determinant of the matrix of the coeп¬ѓcients has to be a nonzero polynomial.
One interesting observation is that when a system of recurrences involving several sequences
is solved by the above method, each of the generating functions A (i) (z) is a rational function

40
(i)
in z. What this means is that each of the sequences a n , 1 в‰¤ i в‰¤ k, satisп¬Ѓes a linear recurrence
(j)
with constant coeп¬ѓcients that does not involve any of the other a n sequences! In principle,
therefore, that recurrence could have been found right at the beginning by combinatorial
(j)
methods. However, usually the degree of the recurrence for an isolated a n sequence is high,
typically about k times as large as the average degree of the k recurrences involving all the
(j) (j)
an . Thus the use of several sequences a n leads to much simpler and combinatorially more
appealing relations.
That generating functions can signiп¬Ѓcantly simplify combinatorial problems is shown by
the following example. It is taken from , and is a modiп¬Ѓcation of a result of Klarner 
and PВґlya . This example also shows a more complicated derivation of explicit generating
o
functions than the simple ones presented so far.

Example 6.5. Polyomino enumeration . Let a n be the number of n-square polyominoes
P that are inequivalent under translation, but not necessarily under rotation or reп¬‚ection, and
such that each row of P is an unbroken line of squares. Then a 1 = 1, a2 = 2, a3 = 6. We
deп¬Ѓne a0 = 0. It is easily seen that

an = (m1 + m2 в€’ 1)(m2 + m3 в€’ 1) В· В· В· (msв€’1 + ms в€’ 1) , (6.45)

where the sum is over all ordered partitions m 1 + В· В· В· + ms = n of n into positive integers mi .
Let ar,n be the sum of terms in (6.45) with m1 = r, where we set an,n = 1, and ar,n = 0 if
r > n or n < 0. Then
в€ћ
an = ar,n , (6.46)
r=1
в€ћ
ar,n = (r + i в€’ 1)ai,nв€’r , r<n. (6.47)
i=1

Deп¬Ѓne
в€ћ в€ћ
ar,n xr y n ,
A(x, y) = (6.48)
n=1 r=1
so that
в€ћ
an y n
A(1, y) = (6.49)
n=1
is the generating function of the an , which are what we need to estimate.
By (6.47), we п¬Ѓnd that
в€ћ в€ћ в€ћ в€ћ
nn
(r + i в€’ 1)ai (n в€’ r)xr y n
A(x, y) = xy +
n=1 n=1 r=1 i=1

41
(6.50)
x2 y 2
xy xy
= + A(1, y) + G(x, y) , (6.51)
1 в€’ xy (1 в€’ xy)2 1 в€’ xy

where
в€ћ в€ћ
в€‚
iai,n y n =
G(y) = A(x.y) , (6.52)
в€‚x x=1
n=1 i=1

We now set x = 1 in (6.50) and obtain an equation involving A(1, y) and G(y), namely

y2
y y
A(1, y) = + A(1, y) + G(y) . (6.53)
1 в€’ y (1 в€’ y)2 1в€’y

We next diп¬Ђerentiate (6.50) with respect to x, and set x = 1. This gives us a second equation,

2y 2
y y
G(y) = + A(1, y) + G(y) . (6.54)
(1 в€’ y)2 (1 в€’ y)3 (1 в€’ y)2

We now eliminate G(y) from (6.53) and (6.54) to obtain

y(1 в€’ y)3
A(1, y) = . (6.55)
1 в€’ 5y + 7y 2 в€’ 4y 3

This formula shows that

an+3 = an+2 в€’ 7an+1 + 4an for n в‰Ґ 2 . (6.56)

Using the results of Section 10 we can easily obtain from (6.55) an asymptotic estimate

an в€ј cО±n as nв†’в€ћ, (6.57)

where c is a certain constant and О± = 3.205569 . . . is the inverse of the smallest zero of
1 в€’ 5y + 7y 2 в€’ 4y 3 .
В

For other methods and results related to polyomino enumeration, see [326, 327].

6.2. Composition and inversion of power series

So far we have only discussed simple operations on generating functions, such as multipli-
cation. What happens when we do something more complicated? There are several frequently
occurring operations on generating functions whose results can be described explicitly.
Fa` di BrunoвЂ™s formula . Suppose that
a
в€ћ в€ћ
zm zn
A(z) = am , B(z) = bn , (6.58)
m! n!
m=0 n=0

42
are two exponential generating functions with b 0 = 0. Then the formal composition C(z) =
A(B(z)) is well-deп¬Ѓned, and
в€ћ
zn
C(z) = cn (6.59)
n!
n=0
with
n
c0 = 0, cn = ak Bn,k (b1 , b2 , . . . , bnв€’k+1 ) , (6.60)
k=1
where the Bn,k are the exponential Bell polynomials deп¬Ѓned by
в€ћ в€ћ
tn uk tm
Bn,k (x1 , . . . , xnв€’k+1 ) = exp u xm , (6.61)
n! m!
m=1
n,k=0

with the xj independent variables.
Fa` di BrunoвЂ™s formula makes it possible to compute successive derivatives of functions
a
such as log A(z) in terms of the derivatives of A(z). For further examples, see [81, 335, 336].
Fa` di BrunoвЂ™s formula is derivable in a straightforward way from the multinomial theorem.
a
Composition of generating functions occurs frequently in combinatorics and analysis of
algorithms. When it yields the desired generating function as a composition of several known
generating functions, the basic problem is solved, and one can work on the asymptotics of the
coeп¬ѓcients using Fa` di BrunoвЂ™s formula or other methods. A more frequent event is that
a
the composition yields a functional equation for the generating function, as in Example 6.1,
where the exponential generating function t(z) for labeled rooted trees was shown to satisfy
t(z) = z exp(t(z)). General functional equations are hard to deal with. (Many examples
will be presented later.) However, there is a class of them for which an old technique, the
Lagrange-BВЁ rmann inversion formula, works well. We start by noting that if
u
в€ћ
fn z n
f (z) = (6.62)
n=0

is a formal power series with f0 = 0, f1 = 0, then there is an inverse formal power series
в€’1
f (z) such that
в€’1 в€’1
f (f (z)) = f (f (z)) = z . (6.63)
в€’1
The coeп¬ѓcients of f (z) can be expressed explicitly in terms of the coeп¬ѓcients of f (z). More
generally, we have the following result.
Lagrange-BВЁ rmann inversion formula. Suppose that f (z) is a formal power series
u
with [z 0 ]f (z) = 0, [z 1 ]f (z) = 0, and that g(z) is any formal power series. Then for n в‰Ґ 1,

[z n ]{g(f в€’1
)(z)} = nв€’1 [z nв€’1 ]{g (z)(f (z)/z)в€’n } . (6.64)

43
In particular, for g(z) = z, we have

[z n ]f в€’1
(z) = nв€’1 [z nв€’1 ](f (z)/z)в€’n . (6.65)

Example 6.6. Rooted labeled trees. As was shown in Example 6.1, the exponential gener-
ating function of rooted labeled trees satisп¬Ѓes t(z) = z exp(t(z)). If we rewrite it as z =
в€’1
t(z) exp(в€’t(z)), we see that t(z) = f (z), where f (z) = z exp(в€’z). Therefore Eq. (6.65)
yields

[z n ]t(z) = nв€’1 [z nв€’1 ] exp(в€’nz)

(6.66)

= nв€’1 nnв€’1 /(n в€’ 1)! = nnв€’1 /n! ,

which shows that tn , the number of rooted labeled trees on n nodes, is n nв€’1 .
В

Proof of a form of the Lagrange-BВЁ rmann theorem is given in Chapter ?. Extensive dis-
u
cussion, proofs, and references are contained in [81, 173, 205, 375]. Some additional recent
references are [159, 208]. There exist generalizations of the Lagrange-BВЁ rmann formula to
u
several variables [173, 169, 208].
The Lagrange-BВЁ rmann formula, as stated above, is valid for general formal power series. If
u
в€’1 в€’1
f (z) is analytic in a neighborhood of the origin, then so are f (z) and g(f )(z), provided
g(z) is also analytic near 0 and f (0) = 0, f (0) = 0. Most of the presentations of this inversion
formula in the literature assume analyticity. However, that is not a real restriction. To prove
(6.65), say, in full generality, it suп¬ѓces to prove it for any n. Given n, if we let
n n
k
gk z k ,
F (z) = fk z , G(z) =
k=0 k=0

then we see that
[z n ]{g(f в€’1
)(z)} = [z n ]G(F в€’1
)(z) , (6.67)

and F (z) and G(z) are analytic, so the formula (6.65) can be applied. Thus combinatorial
proofs of the Lagrange-BВЁ rmann formula do not oп¬Ђer greater generality than analytic ones.
u
While the analytic vs. combinatorial distinction in the proofs of the Lagrange-BВЁ rmann
u
formula does not matter, it is possible to use analyticity of the functions f (z) and g(z) to
obtain useful information. Example 6.6 above was atypical in that a simple explicit formula

44
was derived. Often the quantity on the right-hand side of (6.64) is not explicit enough to make
clear its asymptotic behavior. When that happens, and g(z) and f (z) are analytic, one can
use the contour integral representation
1
[z nв€’1 ]{g (z)(f (z)/z)в€’n } = g (z)f (z)в€’n dz , (6.68)
2ПЂi О“

where О“ is a positively oriented simple closed contour enclosing the origin that lies inside the
region of analyticity of both g(z) and f (z). This representation, which is discussed in Sec-
tion 10, can often be used to obtain asymptotic information about coeп¬ѓcients [z n ]g(f в€’1 )(z)
(cf. ).
The Lagrange-BВЁ rmann formula can provide numerical approximations to roots of equa-
u
tions and even convergent inп¬Ѓnite series representations for such roots. An important case is
the trinomial equation y = z(1 + y r ), and there are many others.

Example 6.7. Dominant zero for forbidden subword generating functions. The generating
functions FA (z) and GA (z) of Example 6.4 both have denominators

h(z) = z k + (1 в€’ 2z)C(z) , (6.69)

where C(z) is a polynomial of degree в‰¤ k, with coeп¬ѓcients 0 and 1, and with C(0) = 1. It will
be shown later that h(z) has only one zero ПЃ of small absolute value, and that this zero is the
dominant inп¬‚uence on the asymptotic behavior of the coeп¬ѓcients of F A (z) and GA (z). Right
now we obtain accurate estimates for ПЃ.

For simplicity, we will consider only large k. Since C(z) has nonnegative coeп¬ѓcients and
C(0) = 1, h(3/4) в‰¤ (3/4)k в€’ 1/2 < 0 for k в‰Ґ 3. On the other hand, h(1/2) = 2 в€’k . Therefore
h(z) has a real zero ПЃ with 1/2 < ПЃ < 3/4. As k в†’ в€ћ, ПЃ в†’ 1/2, since

ПЃk = (2ПЃ в€’ 1)C(ПЃ) , (6.70)

and ПЃk в†’ 0 as k в†’ в€ћ for 1/2 < ПЃ < 3/4, while 2ПЃ в€’ 1 and C(ПЃ) are bounded. We can deduce
from (6.69) that
2ПЃ в€’ 1 в€ј 2в€’k C(1/2)в€’1 as kв†’в€ћ, (6.71)

uniformly for all polynomials C(z) of the prescribed type. By applying the bootstrapping
technique (see Section 5.4) we can п¬Ѓnd even better approximations. By (6.71),

C(ПЃ) = C(1/2) + O(|ПЃ в€’ 1/2|) = C(1/2) + O(2 в€’k ) , (6.72)

ПЃk = 2в€’k (1 + O(2в€’k ))k = 2в€’k (1 + O(k2в€’k )) , (6.73)

45
so (6.70) now yields
ПЃ = 1/2 + 2в€’kв€’1 C(1/2)в€’1 + O(k2в€’2k ) . (6.74)

Even better approximations can be obtained by repeating the process using (6.74). At the
next stage we would apply the expansion

C(ПЃ) = C(1/2) + (ПЃ в€’ 1/2)C (1/2) + O((ПЃ в€’ 1/2)2 )

(6.75)
= C(1/2) + 2в€’kв€’1 C (1/2) + O(k2в€’2k )

and a similar one for ПЃk .
A more systematic way to obtain a rapidly convergent series for ПЃ is to use the inversion
formula. If we set u = ПЃ в€’ 1/2, then (6.70) can be rewritten as w(u) = 1, where
в€ћ
в€’k
aj uj ,
w(u) = 2uC(1/2 + u)(1/2 + u) = (6.76)
j=1

with
a1 = 2k+1 C(1/2) = 0 . (6.77)

в€’1
Hence u = w (1), and the Lagrange-BВЁ rmann inversion formula (6.65) yields the coeп¬ѓcients
u
в€’1
of w (z). In particular, we п¬Ѓnd that

ПЃ = 1/2+u в‰€ 1/2+2в€’kв€’1 C(1/2)в€’1 +k2в€’2kв€’1 C(1/2)в€’2 в€’2в€’2kв€’2 C (1/2)C(1/2)в€’3 +В· В· В· (6.78)

as a PoincarВґ asymptotic series. With additional work one can show that the series (6.78)
e
converges, and that

ПЃ = 1/2 + 2в€’kв€’1 C(1/2)в€’1 + k2в€’2kв€’1 C(1/2)в€’2
(6.79)
2в€’2kв€’2 C (1/2)C(1/2)в€’3 O(k 2 2в€’3k )
в€’ + ,
 << Пред. стр. страница 6(всего 24)ОГЛАВЛЕНИЕ След. стр. >>