LINEBURG

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 [182], except that [182] 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 [182] and in papers such as [18].

The above example can be generalized to provide generating functions that enumerate

sequences in which any of a given set of patterns are forbidden [182].

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 [349], and is a modi¬cation of a result of Klarner [229]

and P´lya [321]. 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 [349]. 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 [81]. 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. [273]).

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 )

’ + ,

Copyright Design by: Sunlight webdesign