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

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

Probability Theory 377

If X is a Bernoulli random variable with parameter p then we obtain from

Deﬁnition 8.6 that

E(X)=p, Var(X)=p(1 − p), and σ =

p(1 − p).

Example D.10 The indicator function of a set A, denoted by I

,isaBern-

oulli random variable with p = P(success)=P(A). Therefore, E(I

P(A).

Deﬁnition D.11 Let X be a random variable which counts the number of

successes in n independent Bernoulli trials, each having success probability p.

Then X is called a Binomial random variable with parameters n and p and

we write X ∼B(n, p). Its probability function is given by

P(X = k)=





(1 − p)

n−k

for k =0, 1,...,n.

If X is a Binomial random variable with parameters n and p then

E(X)=np, Var(X)=np(1 − p), and σ =

np(1 − p).

Deﬁnition D.12 Let X be a random variable which counts the number of tri-

als needed until the ﬁrst success occurs in a sequence of independent Bernoulli

trials each having success probability p.ThenX is called a geometric random

variable with parameter p. Its probability function is given by

P(X = k)=(1− p)

k−1

p for k =1, 2,....

If X is a geometric random variable with parameter p then

E(X)=

, Var(X)=

1 − p

, and σ =

√

1 − p

Theorem D.13 (Markov and Chebyshev inequalities) Let X be a nonnegative

random variable and let Y be an arbitrary random variable. Then for any

t>0,

P(X ≥ t) ≤

E(X)

(Markov inequality)(D.2)

P(|Y −E(Y )|≥t) ≤

Var(Y )

(Chebyshev inequality)(D.3)

Proof We prove the theorem for discrete random variables. Let A be the

set of values of X,andletB = {x ∈ A | x ≥ t}.Thenfort>0

E(X)=



x∈A

xP(X = x) ≥



x∈B

xP(X = x)

≥ t



x∈B

P(X = x)=tP(X ≥ t),

378 Combinatorics of Compositions and Words

from which the Markov inequality follows. The proof of the Chebychev in-

equality follows directly from the Markov inequality, since

P(|Y − E(Y )|≥t)=P((Y − E(Y ))

≥ t

) ≤

Var(Y )

as claimed. For (absolutely) continuous random variables the proof follows

with sums replaced by integrals. 2

Note that these two inequalities tell us that the probability of being much

larger than the mean must decay. Speciﬁcally, an upper bound on the decay

is given in terms of the standard deviation of the random variable. These

two inequalities are examples of moment inequalities which are discussed for

example in Billingsley [24]. In the area of discrete mathematics, these types

of inequalities have been used to show the existence of certain combinatorial

objects in an approach introduced by Erd˝os and referred to as the probabilistic

method (in combinatorics). More details on the probabilistic method can be

found in Alon and Spencer [8].

Besides showing existence of combinatorial objects, so-called large deviation

estimates can be used to derive asymptotic behavior by showing that the

probability for large deviations of the random variable from its mean decays

exponentially.

Theorem D.14 (Large Deviation estimate) Let X ∼B(n, 1/2),then

P(|X −E(X)| >a) ≤ 2exp(−2a

/n).

Proof Let X

be a Bernoulli random variable with success probability 1/2

for i =1,...,n.Then

X − E(X)=



i=1



−





i=1

= Y,

where the Y

are independent symmetric random variables taking values 1/2

and −1/2 with equal probability. For any t>0, using the Markov inequality

and Theorem D.7, we have that

P(Y>a)=P(e

) ≤

E(e

)



i=1

E(e

)

Using Deﬁnition 8.6 we compute

E(e



exp





+exp



−



=cosh





We can show that cosh(x) ≤ exp(x

/2) for x>0 by comparing their respective

Taylor expansions. Thus,

P(Y>a) ≤ exp



n −at



for t>0.

Probability Theory 379

Minimizing the right-hand side over all t>0 yields t =4a/n.Usingthis

valueandthesymmetryofY completes the proof. 2

Alon and Spencer showed a more general result which we state without

proof.

Theorem D.15 [8, Theorem A.1.4] Let X

be mutually independent random

variables with

P(X

=1− p

)=p

and P(X

= −p

)=1− p

for p

∈ [0, 1].

Then for X =



i=1

and a>0,

P(X>a) < exp(−2a

/n).

Appendix E

Complex Analysis Review

This section provides the basic deﬁnitions and theorems that are used in the

asymptotic analysis. They can be found in any reference text (see for example

[5, 150]).

Deﬁnition E.1 Afunctionf(z) deﬁnedoveraregion is analytic at a point

∈if, for some open disc centered at z

and contained in , f (z) can be

represented by a convergent power series expansion

f(z)=



n≥0

(z −z

)

Afunctionisanalytic in a region  if and only if it is analytic at every point

of .Iff is analytic at z

, then there is a disc (of possibly inﬁnite radius)

such that f (z) converges for z inside the disc and is divergent for z outside

the disc. This disc is called the disc of convergence and its radius is the radius

of convergence, denoted by R(f; z

Example E.2 Consider the function f (z)=1/(1 − z) which is deﬁned in

C\{1}.Itisanalyticatz =0since it represents the geometric series which

converges for |z| < 1.Forz

=1, we can obtain the radius of convergence by

rewriting f(z) as follows:

1 − z

− (z − z

)

1 − z

1 −

z−z

1−z



n≥0



1 − z



n+1

(z −z

)

From the last equation we can read oﬀ that f(z) is analytic in the disc centered

at z

with radius of convergence |1 − z

|, and therefore R(f; z

)=|1 − z

Deﬁnition E.3 Afunctionf(z) deﬁnedoveraregion is called complex-

diﬀerentiable or holomorphic at z

lim

δ→0

f(z

+ δ) − f(z

)

381

382 Combinatorics of Compositions and Words

exists for δ ∈ C. In particular, the limit is independent of the way in which δ

tends to 0 in C. A function is holomorphic in the region  if and only if it is

holomorphic for every z

∈.

Theorem E.4 (Basic Equivalence Theorem) [68, Theorem IV.1] A function

is analytic in a region  if and only if it is holomorphic on .

Theorem E.5 Let f(z) be an analytic function in .Thenf(z) has deriva-

tives of all orders and the derivatives can be obtained through term-by-term

diﬀerentiation of the series expansion of the function.

Deﬁnition E.6 A curve γ in a region  is a continuous function which maps

[0, 1] into .Acurveiscalledsimple if the mapping γ is one-to-one, and

closed if γ(0) = γ(1).Aclosed curve is a loop if γ can be continuously

deformed to a single point within .

Theorem E.7 (Cauchy’s Coeﬃcient Formula) [68, Theorem IV.4] Let f(z)

be analytic in a region  containing 0 and let γ be a simple loop around 0 in

 that is positively oriented. Then

=[z

]f(z)=

2π



f(z)

n+1

Deﬁnition E.8 Afunctionh(z) is meromorphic at z

if and only if it can be

represented as f(z)/g(z) for z in a neighborhood of z

with z = z

,wheref(z)

and g(z) areanalyticatz

.Ifh(z) is meromorphic, then it has an expansion

of the form

h(z)=



n≥−M

(z −z

)

(E.1)

near z

.Ifh

−M

=0and M ≥ 1, then we say that h(z) has a pole of order

M at z = z

. A pole of order one is called a simple pole. The coeﬃcient

−1

is called the residue of h(z) at z = z

and is written as Res[h(z); z = z

Afunctionismeromorphic in a region  if and only if it is meromorphic at

every point of the region.

One of the most important theorems in complex analysis is Cauchy’s Resi-

due Theorem. It relates global properties of a function (the integral along

closed curves) to local properties (residues at poles).

Theorem E.9 (Cauchy’s Residue Theorem) [68, Theorem IV.3] Let h(z) be

meromorphic in the region  and let γ be a simple loop in  along which the

function h(z) is analytic. Then

2π



h(z)dz =



Res[h(z); z = s],

where the sum is over all poles s of h(z) enclosed by γ.

Complex Analysis Review 383

Deﬁnition E.10 Let f(z) be an analytic function deﬁned over the interior

region determined by a simple closed curve γ,andletz

be a point of the

bounding curve γ. If there exists an analytic function f

∗

(z) deﬁned over

some open set 

∗

containing z

such that f

∗

(z)=f(z) in ∩

∗

then f

is analytically continuable at z

.Iff is not analytically continuable at z

then z

is called a singularity or singular point.Iff(z) is analytic at 0,then

a singularity that lies on the boundary of the disc of convergence is called a

dominant singularity.

Theorem E.11 (Rouch´e’s theorem) Let the functions f(z) and g(z) be ana-

lytic in a region containing the interior of the simple closed curve γ.Assume

that |g(z)| < |f(z)| on γ.Thenf (z) and f(z)+g(z) have the same num-

ber of zeros inside the interior domain bounded by γ. Equivalently, f (γ) and

(f + g)(γ) have the same winding number.

Deﬁnition E.12 Let f(x) be a function deﬁned over the positive real num-

bers. Then the Mellin transform of f is deﬁned as the complex function f

∗

(s)

where

∗

(s)=



∞

f(x)x

s−1

dx.

The Mellin transform is used in many areas. We will use it for the asymp-

totic analysis of sums of the form

G(x)=



g(μ

x).

These types of sums are often called harmonic sums. In this context, the λ

are the amplitudes,theμ

are the frequencies,andg(x)isthebase function.

Example E.13 [67, page 4] The expected height of a Catalan tree involves

the quantity



k=0

d(k)



n−k







where d(k) denotes the number of divisors of k. The continuous analog to T

is given by

H(x)=

∞



k=0

d(k)e

−k

which is a harmonic sum with μ

= k, λ

= d(k) and g(x)=e

−x

.With

elementary analysis it can be established that T

≈ H(n). In this case, the

asymptotic analysis is made diﬃcult by the divisor function which ﬂuctuates

heavily and in an irregular manner.

Appendix F

Using Mathematica



and Maple

Throughout this book we have encountered several problems that are time

consuming at best and impossible to solve by hand at worst. Solving sys-

tems of equations or ﬁnding partial derivatives of complicated expressions are

best done with the assistance of computer algebra systems such as Maple

and Mathematica. The advantage of a computer algebra system is that it

can do symbolic algebra and has many specialized functions already built-in

or available as packages. Mathematica and Maple can be used for diﬀerent

aspects of research: to do the drudge work that is tedious by hand, to check

theoretically derived results quickly for algebraic mistakes, to simplify com-

plicated expressions, to ﬁnd patterns, and to guess generating functions. For

example, we can use Mathematica or Maple to compute a few derivatives or a

few iterations of a recurrence relation to detect a pattern in the results. Such

a pattern might then be proved by induction.

F.1 Mathematica



functions

In this section we focus on Mathematica functions that are useful for or

speciﬁc to combinatorial enumeration and provide a compact overview of these

functions and how they are applied. Note that all Mathematica functions start

with capital letters and use square brackets, and that code followed by ; does

not return any output.

F.1.1 General functions

Here we list a number of general functions that are not speciﬁc to combina-

torics but play an important supportive role. The functions Sum[f,{i,n,m}]

and Product[f,{i,n,m}] compute the sum f (n)+···+f(m) and the product

f(n) ···f(m), respectively. To compute the sum and the product of the ﬁrst

ﬁve square numbers we use

Sum[x^2,{x,1,5}]

Product[x^2,{x,1,5}]

which returns 55 for the sum and 14400 for the product.

385

386 Combinatorics of Compositions and Words

Two very useful functions are Simplify[expr] and FullSimplify[expr]

which apply various simpliﬁcation rules to expr,withFullSimplify trying a

wider range of transformations. For example,

Simplify[1/(1-x)/(1-2*x)+x/(1-2*x)]

returns

(1+x-x^2)/(1-3x+2x^2)

Solving systems of equations is usually tedious by hand and prone to algebraic

error. We can use Solve[eqns, vars] to solve the system eqns in the vari-

ables vars. To solve the system of three equations u + v + w =1,3u + v =3,

and u − 2v − w =0intermsofu, v,andw,weuse

Solve[{u+v+w==1,3u+v==3,u-2v-w==0},{u,v,w}]

which results in

Note that in Mathematica, equality in an equation (as opposed to an assign-

ment) is expressed using double equal signs.

Finally, there are functions to create sequences of values, usually the values

of a sequence whose coeﬃcients are given by an explicit formula. The function

Table[expr, {i,n,m}] generates the sequence created by evaluating expr at

the values of i from n to m. For example, the sequence of the third to tenth

powers of two is computed as

Table[2^i,{i,3,10}]

with output

{8,16,32,64,128,256,512,1024}

To create sequences of consecutive integers we use the function Range[n,m]

which creates the list {n,...,m}.

Range[3,12]

produces the output

{3,4,5,6,7,8,9,10,11,12}

F.1.2 Special sequences and combinatorial formulas

We will frequently encounter the binomial coeﬃcients





.Therelevant

function is Binomial[n,m]. For example

Binomial [10,5]

returns 252. There is also a function that computes the list of all possible

permutations of the elements in a list, Permutations[list]. For example,

to create the permutations of [3], we use

Using Mathematica



and Maple

387

Permutations[Range[1,3]]

which results in

{{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}

Mathematica also has functions for the Fibonacci and Lucas sequences.

Fibonacci[n] and LucasL[n] compute the n-th Fibonacci and Lucas number,

respectively. Combined with Table we can create the sequences of the ﬁrst

ten Fibonacci and Lucas numbers:

Table[Fibonacci[n],{n,1,10}]

Table[LucasL[n],{n,1,10}]

which returns

{1,1,2,3,5,8,13,21,34,55}

{1,3,4,7,11,18,29,47,76,123}

The partitions of n are computed by the function IntegerPartitions.For

example, the partitions of 4 are computed as

IntegerPartitions[4]

which gives

{{4},{3,1},{2,2},{2,1,1},{1,1,1,1}}

So how can we compute the compositions of n? There is no built-in function,

so we apply the function Permutations to each of the partitions of n.For

example, the compositions of 3 are created by

Flatten[Map[Permutations, IntegerPartitions[3]], 1]

which produces the output

{{3},{2,1},{1,2},{1,1,1}}

Note that Map applies the function Permutations to each of the partitions

of [3]. Flatten is used to get the appropriate list structure, so that each

composition is in its own list.

F.1.3 Series manipulation

The function Series computes power series expansions in one or more

variables. Series[f, {x,x0,n}] generates the power series expansion of f

about the point x = x0toorder(x −x0)

. For functions of several variables,

Series[f, {x,x0,nx},{y,y0,ny},...] successively ﬁnds series expansions

with respect to x,theny, and so on. To see the ﬁrst six terms of the power

series of the shifted Fibonacci sequence f(x)=

1−x−x

(see Table A.1) about

x =0weuse

Series[1/(1-x-x^2),{x,0,5}]

388 Combinatorics of Compositions and Words

with output

1+x+2x^2+3x^3+5x^4+8x^5+O[x]^6

The multivariate series expansion of f(x)=1/(1−x −y)about(x, y)=(0, 0)

to order 3 for x and order 2 for y is computed as

Series[1/(1 - x - y), {x, 0, 3}, {y, 0, 2}]

and returns

(1+y+y^2+O[y]^3)+(1+2y+3y^2+O[y]^3)x+(1+3y+6y^2+O[y]^3)x^2

+(1+4y+10y^2+O[y]^3)x^3+O[x]^4

Usually we are interested in the coeﬃcients of the generating functions. We

can obtain these by using the function Coefficient[expr, form, n] which

gives the coeﬃcient of form^n in expr. For example, if we are interested in

ﬁnding

]



1 − x −

√

1 − 2x − 3x



then we use

Series[(1-x-Sqrt[1-2x-3x^2])/(2x^2),{x,0,7}]

Coefficient[%,x,5]

which gives

1+x+2x^2+4x^3+9x^4+21x^5+51x^6+127x^7+O[x]^8

Note that % refers to the immediate last output (which may be nonsense

if there was a syntax error in the code, so beware). The two commands may

be combined as

Coefficient[Series[(1-x-Sqrt[1-2x-3x^2])/(2x^2),{x,0,7}],x,5]

and now the output consists of only the value 21. If we want coeﬃcients

of an exponential generating function then we need to take into account the

factorial factor. Say the function to be considered is f (x)=e

−1

and we

would like to ﬁnd [x

]f(x). Then we enter

5! Coefficient[Series[Exp[Exp[x]-1],{x,0,6}],x,5]

to obtain the answer 52. If instead of a single coeﬃcient value we want the

sequence of coeﬃcients (like those we have presented in many of the exam-

ples) then the function CoefficientList[poly,var] gives the coeﬃcients of

powers of var, starting with power 0. For example,

CoefficientList[Series[(1-x-Sqrt[1-2x-3x^2])/(2x^2),{x,0,7}],x]

returns

{1,1,2,4,9,21,51,127}