Heubach S., Mansour T. Combinatorics of Compositions and Words

Подождите немного. Документ загружается.

316 Combinatorics of Compositions and Words

Example 8.9 We start by computing the average number of parts in a ran-

dom composition of n. From Theorem 3.3, we have that the number of com-

positions of n is given by C(n)=2

n−1

and the number of compositions of n

with m parts is given by C(m; n)=



n−1

m−1



.LetX

par

(n) denote the number

of parts in a random composition of n. Then the average number of parts is

given by

E(X

par

(n)) =

n−1



m=1



n − 1

m − 1



n−1





m=1

(m − 1)(n − 1)!

(n − m)!(m − 1)!



m=1



n − 1

m − 1





n−1



(n − 1)



m=2



n − 2

m − 2



n−1



n−1

(n − 1)2

n−2

n−1

n − 1

+1=

n +1

This was not too hard! With a little bit more eﬀort we can establish the

corresponding result for palindromic compositions.

Example 8.10 We now compute the average number of parts in a random

palindromic composition of n where we have to distinguish between odd and

even n. From Theorems 3.4 and 3.5 we have that P (n)=2

n/2

and that

P (2k;2n







− 1

k − 1



and P (2k +1;2n



− 1) = P (2k +1;2n







− 1



Let X

par

(n) denote the number of parts in a random palindromic composition

of n.Then

E(X

par

(2n



)) =



⎡

⎣





k=1





− 1

k − 1





−1



k=0

(2k +1)





− 1



⎤

⎦



⎡

⎣





k=1

2(k − 1)





− 1

k − 1







− 1

k − 1





−1



k=0





− 1







− 1



⎤

⎦



2(n



− 1)2



−2

+2·2



−1

+2(n



− 1)2



−2



−1



n +1

Asymptotics for Compositions 317

Similarly, for odd n =2n



− 1,weobtain

E(X

par

(2n



− 1)) =



−1



−1



k=0

(2k +1)





− 1





−1

2(n



− 1)2



−2



−1

= n



− 1+1=

n +1

How do we proceed if we do not have an explicit formula for the statistic

of interest, but we do have the generating function? In this case, we can

compute the mean and the variance of the statistic from a diﬀerent but related

generating function, namely the probability generating function.

Deﬁnition 8.11 The probability generating function of a discrete random

variable X is deﬁned as pg

(u)=



P(X = m)u

= E(u

).Themoment

generating function of a random variable X is deﬁned as M

(t)=E(e

Example 8.12 Let Ω=C

with n ≥ 1 be the set of compositions of n where

we assume that all compositions occur equally likely. Then X

par

(n)=par(σ)

for σ ∈C

is a discrete random variable that takes values m =1, 2,...,n.

The respective (nonzero) probabilities are computed via the compositions that

have m parts:

P(X

par

(n)=m)=

n−1



n − 1

m − 1



Thus, the probability generating function of X

par

is given by

(u)=



m=1

P(X

par

(n)=m)u

n−1



m=0



n − 1



= u



1+u



n−1

Lemma 8.13 We can obtain the k-th moment and the k-th factorial mo-

ment of a discrete random variable X from the probability generating function

(u) as follows:

1. E(X

∂

∂t

(t)

(

t=0

∂

∂t

)

(

t=0

2. E(X(X −1)(X − 2) ···(X − k +1))=

∂

∂u

(u)

(

u=1

318 Combinatorics of Compositions and Words

How is the generating function for a

n,m

related to the probability gener-

ating function from which we can obtain the moments via diﬀerentiation?

Lemma 8.14 provides the answer.

Lemma 8.14 For ﬁxed n,letX be a statistic on the compositions of n,

A(x, q)=



n,m≥0

n,m

,andN =[x

]A(x, 1). Then the mean μ and

the variance σ

of X are given by

μ = E(X)=

]

∂

∂q

A(x, q)

(

q=1

(8.2)

and

=Var(X)=

]



∂

∂q

A(x, q)+

∂

∂q

A(x, q) −



∂

∂q

A(x, q)





(

q=1

]

∂

∂q

A(x, q)

(

q=1

+ μ −μ

. (8.3)

Proof Follows immediately from Lemma 8.13 as we have that pg

(q)=

]A(x, q). 2

We illustrate the use of this lemma by revisiting Example 8.9 and recom-

puting the average number of parts in a random composition from C

.In

addition, we derive the variance of the number of parts.

Example 8.15 (Example 8.9 revisited) From (4.4) we have that the generat-

ing function for the number of compositions of n with m parts is given by

C(x, y)=

1 − y

1−x

1 − x

1 − x − xy

It can be shown (see Exercise 8.3) that

]

∂

∂y

C(x, y)

(

y=1

= k! · 2

n−1−k





−



n − 1



. (8.4)

Using this expression, we can now compute the mean and the variance. For

k =1, we obtain that

E(X

par

(n)) =

n−1

n−2

(2n − (n −1)) =

n +1

as before. For the variance we use k =2to compute

E(X

par

(n)

n−1

]



∂

∂y

C(x, y)

(

y=1



+ n − 2

Asymptotics for Compositions 319

Therefore, the variance for the number of parts is given by

+ n − 2

n +1

−

(n +1)

n −1

As another example, we compute the average number of rises in composi-

tions.

Example 8.16 Using (4.8) in the proof of Corollary 4.5, we obtain that for

(x, y)=



n≥0



σ∈C

ris(σ)x

par( σ)

(x, y)=



i≥1



j≥i+1

i+j



1 − y

1 − x





i≥1

i+1

1 − x



1 − y

1 − x



1 − x



1 − y

1 − x



(1 − x − yx)(1 + x)

Sinceweareinterestedinthenumberofrises,wesety =1. This leads to

(x, 1) =

(1 + x)(1 − 2x)



n≥1

3n · 2

n−2

− 5 · 2

n−2

− (−1)

Dividing by the total number of compositions and extracting the coeﬃcient of

we obtain that the average number of rises in a random composition of n

is given by

E(X

ris

(n)) =

3n − 5

−

(−1)

9 · 2

n−1

for n ≥ 1.

Similarly, for l

(x, y)=



n≥0



σ∈C

lev(σ)x

par( σ)

,weobtain(by comparing the

expressions given in Theorem 4.5 and the above derivation) that

(x, y)=



j≥1



1 − y

1 − x



(1 − x)

(1 + x)(1 − x − xy)

This implies that

(x, 1) =

(1 − x)

(1 + x)(1 − 2x)



n≥2

3n · 2

+8(−1)

so that the average number of levels in a random composition of n is given by

E(X

lev

(n)) =

3n +1

(−1)

9 · 2

n−2

320 Combinatorics of Compositions and Words

Note that we have obtained the series expansions for r

(x, y) and l

(x, y) with

thecoeﬃcientsexpressedasfunctionsofn (as opposed to numerical values)

by using the following Maple command. The function rgf_expand takes as

its input a rational function f(x) and returns [x

]f(x) in terms of n.

with(genfunc);

rgf_expand(f(x),x;n);

In Mathematica we use the function SeriesCoefficient to compute

(x, 1)

as a function of n:

SeriesCoefficient[x^3/((1 + x) (1 - 2 x)^2), {x, 0, n}]

However, knowing the generating function for the statistic of interest does

not always guarantee success in computing the expected value. For example, if

we want to compute the same averages for Carlitz compositions (see Deﬁnition

1.18), trouble arises when we try to extract the coeﬃcient of x

of the function

∂

∂y

(x, y, 1, 0, 1)

(

y=1



i≥1

(1 + x

)



1 −



i≥1

1+x



In this case, even though we have an explicit formula for the number of Carlitz

compositions with respect to the statistic of interest, the expression is too

complicated to compute an explicit result for the average. In such cases, we

can obtain only asymptotic results (see Exercise 8.4) using tools from complex

analysis that we will introduce and will discuss in the next section.

We conclude this section by giving some deﬁnitions that will play an im-

portant role for asymptotic results in terms of distributions.

Deﬁnition 8.17 Let X be a random variable. If there exists a nonnegative,

real-valued function f : R → [0, ∞) such that

P(X ∈ A)=



f(x)dx

for any measurable set A ⊂ R (a set that can be constructed from intervals by

a countable number of unions and intersections),thenX is called (absolutely)

continuous and f is called its density function.

Deﬁnition 8.18 A continuous random variable X is called a normal random

variable with mean μ and variance σ

if its density function is of the form

f(x)=

√

2π

exp

−(x − μ)

2σ

Asymptotics for Compositions 321

and we will write X ∼N(μ, σ

).Theparametersμ and σ that appear in the

density are the mean and the standard deviation of X.Ifμ =0and σ =1,

then X is called a standard normal random variable.

It can be shown that if X ∼N(μ, σ

), then the standardized random

variable

X−μ

is a standard normal random variable, that is,

X−μ

∼N(0, 1).

Following Bender [18], we deﬁne asymptotic normality for a sequence of two

indices.

Deﬁnition 8.19 To a given a sequence {a

(k)}

n,k≥0

with a

(k) ≥ 0 for all

k, we associate a normalized sequence

(k)=

(k)



j≥0

(j)

We say that {a

(k)}

n,k≥0

is asymptotically normal with mean μ

and vari-

ance σ

or satisﬁes a central limit theorem if

lim

n→∞

sup

(



k≤σ

x+μ

(k) −

√

2π



−∞

−t

(

=0,

and write a

(k)

≈N(μ

,σ

8.3 Tools from complex analysis

For the moment, we leave randomness and probabilities behind and focus

on complex analysis instead, even though we will eventually combine the two

areas in the quest for determining asymptotic behavior. The main result that

we draw on is that for a complex function, the location of the singularities de-

termines the growth behavior of the coeﬃcients of the power series expansion

of the function when n becomes large. Therefore, we will regard the gener-

ating function as a complex function instead of as a formal expression, and

use variables z and w instead of variables x and y to remind ourselves of that

viewpoint. We provide the necessary deﬁnitions for basic terminology and

related results in Appendix E and start by giving the speciﬁc results (drawn

primarily from Flajolet and Sedwick [68]) that will be used in the subsequent

analysis of restricted compositions.

The typical generating function that we will consider satisﬁes the following

theorem.

Theorem 8.20 [68, Theorems IV.5 and IV.6] A function f (z) that is ana-

lytic at the origin and whose expansion at the origin has a ﬁnite radius of

322 Combinatorics of Compositions and Words

convergence R necessarily has a singularity on the boundary of its disc of con-

vergence, |z| = R. Furthermore,iftheexpansionoff(z) at the origin has

nonnegative coeﬃcients, then the point z = R is a singularity of f (z), that

is, there is at least one singularity of smallest modulus that is real-valued and

positive.

Note that the second part of Theorem 8.20 indicates that we can very eas-

ily ﬁnd the dominant singularity for our generating functions – we just need

to check the analyticity of the function along the positive real line and ﬁnd

the smallest value where the function ceases to be analytic. This singular-

ity will determine the rate of growth, expressed using the notation ≈ (see

Deﬁnition 7.36).

Theorem 8.21 (Exponential Growth Formula) [68, Theorem IV.7] If f(z)

is analytic at the origin and R is the modulus of a singularity nearest to the

origin in the sense that

R =sup{r ≥ 0 | f is analytic in |z| <r},

then the coeﬃcient f

=[z

]f(z) satisﬁes

≈





In the case of functions with nonnegative coeﬃcients, speciﬁcally combinato-

rial generating functions, one can also deﬁne

R =sup{r ≥ 0 | f is analytic for all 0 ≤ z<r}.

Theorem 8.21 directly links the exponential growth of the coeﬃcients to

the location of the singularities nearest to the origin (called “First Principle of

Coeﬃcient Analysis” by Flajolet and Sedwick [68]). If the generating function

is not only analytic, but also rational, then we can give a more detailed answer

for the asymptotic behavior, which includes slower growth factors.

Theorem 8.22 (Expansion of rational functions) [68, Theorem IV.9] If f(z)

is a rational function that is analytic at the origin with poles at ρ

,ρ

,...,ρ

of orders r

,...,r

, respectively, then there exist polynomials {P

(z)}

j=1

such that for n>n

=[z

]f(z)=



j=1

(n)ρ

−n

. (8.5)

Furthermore, the degree of P

is one less than the multiplicity of ρ

Asymptotics for Compositions 323

Proof Let f(z)=N(z)/D(z)andletn

=deg(N) −deg(D). Using partial

fraction expansion, we can write

f(z)=Q(z)+



ρ,r

(z −ρ)

where Q(z) is a polynomial of degree n

, ρ ranges over the poles of f(z)and

r is bounded from above by the multiplicity of ρ as a pole of f .Thus,for

n>n

, only the terms in the sum contribute to the coeﬃcient of z

,and

using (A.3) we obtain that

]

(z −ρ)

(−1)

]

1 −

(−1)



n + r − 1



−n

. (8.6)

Since the binomial coeﬃcient is a polynomial of degree r − 1inn,the

statement follows by collecting the terms associated with a given ρ

. 2

Theorem 8.22 gives a very precise representation of the coeﬃcients. Some-

times all we care about is the asymptotic behavior, that is, we are only inter-

ested in the factor that dominates the growth. In such a case, we do not need

to perform the partial fraction decomposition and explicit determination of

the polynomials P

Example 8.23 Let

f(z)=

(1 − z

)

(1 − z)

(1 − z

/4)

Then f can be rewritten as

f(z)=

(1 − z)

(1 + z)

(2 − z)

(2 + z)

(1 + z

)

to reveal that f has a pole of order four at z =1and poles of order two at

z = −1, 2, −2, i, −i. Therefore

= P

(n)+P

(n)2

−n

+ P

(n)(−2)

−n

+ P

(n)i

−n

+ P

(n)(−i)

−n

+ P

(n)(−1)

−n

where the degree of P

is three and all other polynomials have degree one. To

derive how f

behaves asymptotically, only the poles at roots of unity (those

closest to the origin) need to be considered, as they correspond to the fastest

exponential growth. Among those, it suﬃces to consider the root ρ =1because

its order is bigger than the order of the other roots of unity. Substituting z =1

everywhere except at the singularity gives that

f(z) ≈

· 1

·3

·2

(1 − z)

324 Combinatorics of Compositions and Words

Now we can use (A.3) to derive that

≈



n +3



≈

If the generating function is not rational but only meromorphic, then we

obtain an asymptotic result that resembles the structure of the exact result

for rational functions.

Theorem 8.24 (Expansion of meromorphic functions) [68, Theorem IV.10]

Let f(z) be a meromorphic function in the closed disk {z ||z|≤R} with poles

at ρ

,ρ

,...,ρ

of orders r

,...,r

, respectively. If f(z) is analytic on

|z| = R and at z =0, then there exist m polynomials {P

(z)}

j=1

such that

=[z

]f(z) ≈



j=1

(n)ρ

−n

. (8.7)

Furthermore, the degree of P

is one less than the multiplicity of ρ

Proof We provide a proof based on subtracting singularities. (A second,

alternative proof based on contour integration can be found in [68].) If ρ is a

pole, we can expand f (z) locally as

f(z)=



k≥−M

ρ,k

(z −ρ)

= S

(z)+H

(z), (8.8)

where S

(z) consists of the “singular part,” that is, the terms with nega-

tive indices, and H

(z)isanalyticatρ. Therefore we can express S

(z)as

(z)/(z − ρ)

,whereN

(z) is a polynomial of degree less than M .Ifwe

let S(z)=



(z), then it is easy to see that f(z) − S(z)isanalyticfor

|z|≤R, because we have removed the singularities of f(z) by subtracting

them. We determine the asymptotic behavior of

]f(z)=[z

]S(z)+[z

](f(z) − S(z))

by analyzing the singular and the analytic part separately. The coeﬃcient

]S(z) is obtained by applying Theorem 8.22. Using Cauchy’s coeﬃcient

formula (E.7) with the contour γ = { z ||z| = R} and bounding the integral

leads to

(

](f(z) − S(z))

(

2π

(



|z|=R

(f(z) − S(z))

n+1

(

≤

2π

n+1

2πR,

where C =sup{|f(z) − S(z)|||z| = R}. Thus, the contribution of the

analytic part has a slower growth rate and can be neglected, which proves the

statement. 2

Asymptotics for Compositions 325

A special case that we will encounter in many applications is that of a

meromorphic function with a single dominant pole. In this case, we can

explicitly state the exponential growth rate.

Theorem 8.25 Let f (z)=1/h(z) and let ρ

∗

be the positive zero with smallest

modulus and multiplicity one. Then, in a neighborhood of ρ

∗

f(z) ≈

1 − z/ρ

∗

and

]f(z) ≈ A(ρ

∗

)

−n

with A =

−1

∗

h(z)|

z=ρ

∗

Proof From the proof of Theorem 8.24 we have that S

∗

(z)=

z−ρ

∗

,where

c = lim

z→ρ

∗

(z −ρ

∗

)f(z). Furthermore, using (8.6), we have that

∗

(z)=

−c

∗

(ρ

∗

)

−n

We can determine c by using l’Hˆopital’s Rule to obtain that

c = lim

z→ρ

∗

z − ρ

∗

h(z)

= lim

z→ρ

∗



(z)



(z)|

z=ρ

∗

which proves the statement. 2

Example 8.26 We illustrate the use of Theorem 8.25 by applying it to the

generating function for the number of compositions with parts in A = {1, 2}

(see Example 3.14). In this case we actually know an explicit formula for the

coeﬃcients, so we can see how the asymptotic result compares to the explicit

one. From Theorem 3.10, we know that

(n)=F

n+1

√

(α

n+1

− β

n+1

)

where α =(1+

√

5)/2 and β =(1−

√

5)/2.Since|α| > 1 and |β| < 1,the

dominant term is the α term and we obtain that

(n) ≈

√

=0.723607(1.61803)

Now we derive the asymptotics by applying Theorem 8.25. From Example 3.14

we know that the generating function for these compositions is given by

(z)=

1 − z −z

−1

(z −(1 −

√

5)/2)(z − (1 +

√

5)/2)