Heubach S., Mansour T. Combinatorics of Compositions and Words
Подождите немного. Документ загружается.
44 Combinatorics of Compositions and Words
Definition 2.34 The ordinary generating function and the exponential gen-
erating function for the sequence {a
→
n
}
→
n ∈N
k
are given by
A(
→
x )=
→
n ∈N
k
a
→
n
→
x
→
n
and E(
→
x )=
→
n ∈N
k
a
→
n
→
x
→
n
→
n !
,
respectively, where
→
x
→
n
=
k
j=1
x
n
j
j
and
→
n !=
k
j=1
n
j
!. Two formal power
series A(
→
x ) and B(
→
x ) are equal if a
→
n
= b
→
n
for all
→
n ∈ N
k
and we write
A(
→
x )=B(
→
x ).Thesetofformal power series or generating functions in
→
x =(x
1
,...,x
k
) is denoted by L[[
→
x ]].OnthesetL[[
→
x ]] we define addition
and subtraction of two power series by
A(
→
x ) ± B(
→
x )=
→
n ∈N
k
(a
→
n
± b
→
n
)
→
x
→
n
.
Multiplication of two power series is defined using the Cauchy product rule
C(
→
x )=A(
→
x ) · B(
→
x )=
→
n ∈N
k
→
m
+
→
m
=
→
n
a
→
m
b
→
m
→
x
→
n
,
where
→
m
,
→
m
∈ N
k
and
→
m
+
→
m
=(m
1
+m
1
,...,m
k
+m
k
). The function C
is called the convolution of A and B. For generating functions in one variable
this reduces to
n≥0
a
n
x
n
n≥0
b
n
x
n
=
n≥0
n
j=0
a
j
b
n−j
x
n
.
It can be shown that the set L[[
→
x ]] of all formal power series in
→
x over L is a
ring with the addition and multiplication as defined above. The multiplicative
operation might seem complicated at first, but it turns out to be exactly what
we need. Often, when counting combinatorial objects, we will break those of
size n into two parts of size k and n − k, where the two parts may have
different characteristics or types, and then sum over all possible values of k.
The resulting sum has the form of the Cauchy product, and the generating
function for the sequence in question can be obtained by multiplying the
generating functions for the individual sequences that count the objects of
the two different types. Here is an example of this approach.
Example 2.35 To obtain the generating function for the number of compo-
sitions of n with parts in N, we can count the compositions according to the
value with which they start, as in Example 2.9. If the composition starts with
k, k =1, 2,...,n, then it is followed by any composition of n − k.LetC
n
denote the number of compositions of n with parts in N. Then we get that
C
n
=
n
k=1
C
n−k
=
n
k=1
1 · C
n−k
for n ≥ 1,
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 45
that is, we obtain the number of compositions as a convolution of the sequence
{b
n
}
n≥1
with b
n
=1, and the sequence {C
n
}
n≥0
. The sequence {b
n
}
n≥1
has
generating function B(x)=
x
1−x
(why?), and therefore,
C(x) − 1=
x
1 − x
C(x) ⇒ C(x)=
1 − x
1 − 2x
.
(It is important not to forget to adjust for the term C
0
on the left-hand side
since the recurrence only holds for n ≥ 1.)
We now provide an alternative definition of the generating function which
is useful for certain questions.
Definition 2.36 Let A
→
n
= A
n
1
,n
2
,...,n
k
be a finite set parameterized by n
1
,
n
2
, ..., n
k
and let A denote the disjoint union of the A
→
n
. We say that
σ ∈A
→
n
has order
→
n and write ord(σ)=
→
n .Forσ ∈A, we define a statistic
→
s
σ
: A→(N
0
)
k
. Then the ordinary and exponential generating function for
the number of elements of A according to the order of σ and the statistic
→
s
σ
are given by
A(
→
x,
→
y )=
σ∈A
→
x
ord(σ)
→
y
→
s
σ
and E(
→
x,
→
y )=
σ∈A
→
x
ord(σ)
ord(σ)!
→
y
→
s
σ
,
respectively.
Example 2.37 Say we want to find an explicit formula for the number of
compositions in {1, 2} of order n with m
1
ones and m
2
parts. Then, the
statistic of interest is
→
s
σ
=(ones(σ), par(σ)),whereones(σ) is the number
of 1sinσ.WeletA denote the set of all compositions with parts in {1, 2}.
Then the generating function is given by
A(x, y)=
σ∈A
x
ord(σ)
→
y
→
s
σ
=
n≥0
x
n
m
1
,m
2
≥0
y
m
1
1
y
m
2
2
|{σ ∈A|ord(σ)=n,
→
s
σ
=(m
1
,m
2
)}|.
We now need to derive an expression for the generating function. Since any
composition σ ∈Ais either empty or starts with a 1 or a 2, it is not too hard
to see that A(x, y)=1+(xy
1
y
2
+ x
2
y
2
)A(x, y), which is equivalent to
A(x, y)=
1
1 − xy
2
(y
1
+ x)
=
m
2
≥0
y
m
2
2
x
m
2
(y
1
+ x)
m
2
=
m
2
≥0
m
2
m
1
=0
m
2
m
1
y
m
1
1
y
m
2
2
x
2m
2
−m
1
.
© 2010 by Taylor and Francis Group, LLC
46 Combinatorics of Compositions and Words
This implies that the number of compositions in {1, 2} of order n with m
1
ones and m
2
=(n + m
1
)/2 parts is given by
m
2
m
1
, which can be explained
combinatorially by choosing m
1
parts to be the ones among the m
2
parts in
the composition.
Since we often want to refer to the coefficient of x
n
, or more generally, of
→
x
→
n
, we define this useful notation.
Definition 2.38 Let A(x) be a generating function. Then [x
n
]A(x) denotes
the coefficient of x
n
in A(x), and more generally, [
→
x
→
n
] denotes the coefficient
of
→
x
→
n
in A(
→
x ).
Example 2.39 Using this notation for the generating function of Example
2.37, we obtain
[x
n
y
m
1
1
y
m
2
2
]A(x, y)=
m
2
m
1
if n =2m
2
− m
1
0 if n =2m
2
− m
1
.
Definition 2.40 A generating function A(
→
x ) ∈ L[[x]] is called rational if
there exist two polynomials p(
→
x ),q(
→
x ) ∈ L[
→
x ] such that A(
→
x )=
p(
→
x )
q(
→
x )
.It
is algebraic if there exists a nontrivial polynomial R ∈ L[
→
x ] such that A(
→
x )
satisfies a polynomial equation R(A; x
1
,...,x
k
)=0.
Note that every rational generating function is algebraic.
Example 2.41 The generating function F (x)=
x
1−x−x
2
for the Fibonacci
sequence is rational, whereas the generating function f(x) satisfying the poly-
nomial equation f(x)=1+xf(x)
3
is algebraic, but not rational.
We can also define two other operations on the ring L[[
→
x ]] which will assist
us greatly in manipulating generating functions.
Definition 2.42 The derivative and the integral of A(
→
x ) with respect to x
i
are defined by
∂
∂x
i
A(
→
x )=
→
n ∈N
k
a
→
n
n
i
x
n
i
−1
i
j=i
x
n
j
j
and
A(
→
x )dx
i
=
→
n ∈N
k
a
→
n
1
n
i
+1
x
n
i
+1
i
j=i
x
n
j
j
,
respectively.
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 47
Example 2.43 The generating function for the sequence {n·m}
n,m≥0
is given
by
n,m≥0
nmx
n
y
m
= xy
n,m≥0
nmx
n−1
y
m−1
= xy
∂
2
∂x∂y
n,m≥0
x
n
y
m
= xy
∂
2
∂x∂y
1
(1 − x)(1 −y)
=
xy
(1 − x)
2
(1 − y)
2
.
Now that we are on solid ground with regard to the allowed operations on
formal power series, we will look at rules that let us easily compute the gen-
erating functions for new sequences from known generating functions. These
rules will allow us to go directly from the recurrence relation to a functional
equation for the generating function without having to apply the definition of
the generating function. In addition, those rules will make it easy (with some
practice) to do the opposite, namely read off the coefficients of the sequence
from the generating function by expressing it in terms of known generating
functions (see Example 2.46).
Definition 2.44 We use A
ops
↔{a
n
}
n≥0
to indicate that A(x)=
n≥0
a
n
x
n
is the ordinary power series (ops) generating function of the sequence
{a
n
}
n≥0
.
Let us see how we can get the generating function of a new sequence from the
generating function of a related series. For example, if A
ops
↔{a
n
}
n≥0
,what
is the generating function of the sequence {a
n+1
}
n≥0
, that is, the sequence
that is shifted over by one? We use the definition of the generating function
to obtain
n≥0
a
n+1
x
n
=
1
x
n≥0
a
n+1
x
n+1
=
A(x) − a
0
x
.
This tells us that
A
ops
↔{a
n
}
n≥0
⇒
A − a
0
x
ops
↔{a
n+1
}
n≥0
.
Applying this rule repeatedly or using the definition of the generating function,
we obtain a general rule for computing the generating function of a shifted
sequence from the generating function of the original sequence.
Rule 2.45 [193, Rule 1, Chapter 2] If A
ops
↔{a
n
}
n≥0
, then for any integer
k>0,
A − a
0
− a
1
x − ...− a
k−1
x
k−1
x
k
ops
↔{a
n+k
}
n≥0
.
© 2010 by Taylor and Francis Group, LLC
48 Combinatorics of Compositions and Words
Proof See Exercise 2.11. 2
Example 2.46 (Continuation of Example 2.33) We have derived the gener-
ating function for the sequence {a
n
}
n≥0
given by
a
n
= a
n−1
+ a
n−2
+1,a
0
=1,a
1
=2
and obtained
A(x)=
1
(1 − x)(1 −x −x
2
)
.
We will now use knowledge of generating functions and their properties to
easily read off [x
n
]A(x). First we notice that the generating function is a
product of the geometric series with a function that is almost the generating
function of the Fibonacci sequence. Seeing a product should put us on the
alert for a convolution. Next we bring the second function to a convenient
form by multiplying with x/x. The resulting factor of
1
x
should be translated
into: “Aha! A shifted sequence,” due to Rule 2.45. We need now only check
whether the zero-th term of the sequence is equal to zero which is true for the
Fibonacci sequence. All together we have that
A(x)=
1
(1 − x)(1 −x −x
2
)
=
1
(1 − x)
1
x
x
(1 − x − x
2
)
=
1
1 − x
F (x) − F
0
x
.
Therefore, the sequence {a
n
}
n≥0
is a convolution of the sequence {1}
n≥0
and
the shifted Fibonacci sequence {F
n+1
}
n≥0
, that is
a
n
=
n
i=0
1 · F
n+1−i
=
n+1
i=1
F
i
= F
n+3
− 1,
where the last equality follows from a well-known identity (seeExercise2.7).
Thus, we have derived once more the result of Example 2.27.
Another very common modification of a sequence is multiplication by n,or
in general, by a polynomial in n. Let’s start again with the simplest case and
determine the generating function of {na
n
}
n≥0
from the generating function
A of {a
n
}
n≥0
. Again, we use the definition of the generating function and use
algebraic transformations to express it in terms of A(x):
n≥0
na
n
x
n
= x
n≥0
na
n
x
n−1
= xA
(x).
Thus, multiplying a sequence by n results in differentiating the generating
function and then multiplying by x.
Definition 2.47 We denote the differential operator by D,andwriteDf to
indicate f
for any function f. The second derivative of f will be denoted by
D
2
f, and in general, D
k
f denotes the k-th derivative of f.
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 49
Therefore, xDA
ops
↔{na
n
}
n≥0
. Repeatedly applying this fact gives that if
A
ops
↔{a
n
}
n≥0
,then(xD)
k
A
ops
↔
n
k
a
n
n≥0
. Together with the linearity of
the generating function we obtain this general rule.
Rule 2.48 [193, Rule 2, Chapter 2] Let P(n) be a polynomial in n.Then
A
ops
↔{a
n
}
n≥0
⇒ P (xD)A
ops
↔{P (n) · a
n
}
n≥0
.
We illustrate this rule with an example.
Example 2.49 What is the generating function of {3n + n
2
}
n≥0
?Looking
at this sequence through the generating function lens, we identify this as the
sequence {1}, multiplied by the polynomial P (n)=3n + n
2
.Thus,
3(xD)
1
1 − x
+(xD)
2
1
1 − x
ops
↔
3n + n
2
n≥0
,
and we compute the generating function A of the sequence 3n + n
2
as follows:
A(x)=3(xD)
1
1 − x
+(xD)
2
1
1 − x
=3x
1
1 − x
+(xD)
x
1
1 − x
=
3x
(1 − x)
2
+ x
x
(1 − x)
2
=
3x
(1 − x)
2
+
x(1 + x)
(1 − x)
3
=
2x(2 − x)
(1 − x)
3
.
Example 2.50 (Dyck words and Catalan numbers) A Dyck word of length
2n is a word on the alphabet {1, 2} consisting of n 1sandn 2s such that no
initial segment of the word has more 2s than 1s. For example, the Dyck words
of length six are
111222, 112122, 112212, 121122, and 121212.
Dyck words of length 2n can be used to encode valid arrangements of paren-
theses in a mathematical expression, with a 1 representing a left parenthesis
and a 2 representing a right parenthesis. The above Dyck words correspond to
the following parentheses arrangements:
((())), (()()), (())(), ()(()), and ()()().
We now want to count the number of Dyck words using generating functions.
To do so, we need to set up a recurrence relation of some form. Similar to
how we proceeded in Example 2.35, we split up the Dyck word into smaller
Dyck words as follows: For each position j, compute the difference between
the number of 1sandthenumberof2sinthefirstj positions. Since the word
is a Dyck word, j ≥ 0. We condition on the first position j where there is an
equal number of 1sand2s. Then we can write the Dyck word w of length 2n
as w =1w
2 w
,wherethe2 is at position j =2k +2. (Note that w
and w
© 2010 by Taylor and Francis Group, LLC
50 Combinatorics of Compositions and Words
may be empty words.) By construction, w
isaDyckwordoflength2k,and
since the number of 1sand2s balance at position 2k +2,thewordw
is also a
Dyck word, and it has length 2(n −k −1). This representation is unique, and
we can therefore count the Dyck words according to this decomposition to get
the following recurrence relation, where d
n
counts the Dyck words of length
2n:
d
n
=
n−1
k=0
d
k
d
n−k−1
for n ≥ 1.
Adjusting for the fact that the convolution sum has upper index n −1 instead
of n we get
D(x) − 1=xD(x)
2
⇒ D(x)=
1 −
√
1 − 4x
2x
.
To extract the coefficients [x
n
]D(x), we make use of the following well-known
identity (see Equation (A.2))
√
1+t =
m≥0
1/2
m
t
m
=1+
m≥1
(−1)
m−1
(2m − 2)!
2
2m−1
m!(m − 1)!
t
m
.
Thus,
D(x)=−
1
2x
m≥1
(−1)
m−1
(2m − 2)!
2
2m−1
m!(m − 1)!
(−4x)
m
=
m≥1
1
m
2m − 2
m − 1
x
m−1
=
m≥0
1
m +1
2m
m
x
m
. (2.10)
This implies that d
m
is given by the m-th Catalan number
1
m+1
2m
m
.The
Catalan sequence
7
1, 1, 2, 5, 14, 132, 429, 1430, 4862, 16796,... which occurs as
sequence A000108 in [180] counts an enormous number of different combina-
torial structures (see Stanley [182, Page 219 and Exercise 6.19] ).Itwasfirst
described in the 18th century by Leonard Euler
8
, who was interested in the
number of different ways of dividing a polygon into triangles. The sequence is
named after Eug`ene Charles Catalan
9
, who also worked on the problem and
discovered the connection to parenthesized expressions.
Any Dyck word can be visualized by a Dyck path, a lattice path in the plane
integer lattice Z×Z consisting of up-steps (1, 1) and down-steps (1, −1) which
never passes below the x-axis. From the definition of Dyck words it is obvious
that a Dyck word on {1, 2} of length 2n can be represented as a Dyck path
where a 1 represents an up-step and a 2 represents a down-step. For example,
the Dyck path for the Dyck word 112122 is given in Figure 2.1.
7
http://mathworld.wolfram.com/CatalanNumber.html
8
http://turnbull.mcs.st-and.ac.uk/ history/Mathematicians/Euler.html
9
http://turnbull.mcs.st-and.ac.uk/ history/Mathematicians/Catalan.html
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 51
0 1 2 3 4 5 6
0
1
2
FIGURE 2.1: Dyck path for the Dyck word 112122.
We next state two rules that are an immediate result of the way power
series are multiplied.
Rule 2.51 If A
i
ops
↔
a
(i)
n
n≥0
for i =1,...,m and A
ops
↔{a
n
}
n≥0
,then
A
1
A
2
···A
m
ops
↔
i
1
+i
2
+···+i
m
=n
a
(1)
i
1
a
(2)
i
2
···a
(m)
i
m
n≥0
,
and
A
m
ops
↔
i
1
+i
2
+···+i
m
=n
a
i
1
a
i
2
···a
i
m
n≥0
.
Finally, we look at the generating function of the partial sum of a sequence.
Rule 2.52 [193, Rule 5, Chapter 2] If A
ops
↔{a
n
}
n≥0
,then
A
1 − x
ops
↔
n
i=0
a
i
n≥0
.
We illustrate this rule by deriving the generating function for the sequence
of harmonic numbers.
Definition 2.53 The n-th harmonic number is defined by
H
n
=1+
1
2
+
1
3
+ ···+
1
n
for n ≥ 1.
Example 2.54 Let H
ops
↔{H
n
}
n≥1
. Then by Rule 2.52, H =
A
1−x
,where
A
ops
↔
1
n
n≥1
which means that we have to find A(x)=
n≥1
x
n
n
.Since
(DA )(x)=
n≥1
x
n−1
=
1
1 − x
,
© 2010 by Taylor and Francis Group, LLC
52 Combinatorics of Compositions and Words
we have that A(x)=
1
1−x
dx = −log(1 − x), and therefore,
1
1 − x
log
1
1 − x
ops
↔{H
n
}
n≥1
.
Similar rules can be derived for exponential generating functions.
Definition 2.55 We use E
egf
↔{a
n
}
n≥0
to indicate that E(x)=
n≥0
a
n
x
n
n!
is the exponential generating function (egf) of the sequence {a
n
}
n≥0
.
We start by determining the exponential generating function for a shifted
sequence.
Rule 2.56 [193, Rule 1’, Chapter 2] If A
egf
↔{a
n
}
n≥0
, then for any integer
k>0,
D
k
A
egf
↔{a
n+k
}
n≥0
.
Proof See Exercise 2.11. 2
So in this instance, the rule for the exponential generating function of a
shifted sequence is simpler than the corresponding one for the ordinary gen-
erating function. If we look at the impact of multiplying a sequence with
a polynomial, we obtain exactly the same result as in the case of ordinary
generating functions.
Rule 2.57 [193, Rule 2’, Chapter 2] Let P (n) be a polynomial in n and
E
egf
↔{a
n
}
n≥0
.Then
P (xD)E
ops
↔{P (n) · a
n
}
n≥0
.
When multiplying exponential generating functions, the answer is still a
convolution, but with a nice twist that results in a very useful formula.
Rule 2.58 [193, Rule3’, Chapter 2] If E
ops
↔{a
n
}
n≥0
and
˜
E
ops
↔{b
n
}
n≥0
,
then
E ·
˜
E
egf
↔
n
r=0
n
r
a
r
b
n−r
n≥0
,
and more generally,
E
k
egf
↔
r
1
+···+r
k
=n
n!
r
1
!r
2
! ···r
k
!
a
r−1
a
r−2
···a
r−k
n≥0
.
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 53
Proof We have
E(x) ·
˜
E(x)=
∞
i=0
a
i
x
i
i!
⎧
⎨
⎩
∞
j=0
b
j
x
j
j!
⎫
⎬
⎭
=
∞
i,j=0
a
i
b
j
x
i+j
i!j!
=
n≥0
x
n
⎧
⎨
⎩
∞
i+j=n
a
i
b
j
i!j!
⎫
⎬
⎭
.
Thus, the coefficient of x
n
/n!isgivenby
"
x
n
n!
#
E ·
˜
E =
∞
i+j=n
n!a
i
b
j
i!j!
=
n
r=0
n
r
a
r
b
n−r
.
2
We illustrate this rule with an example involving set partitions.
Definition 2.59 A partition {S
1
,S
2
,...,S
k
} of a set S is a collection of non-
empty sets such that S
i
∩ S
j
= ∅ for i = j and
$
k
i=1
S
i
= S.Thenumber
of partitions of a set S with n elements is enumerated by the Bell numbers
10
(named in honor of Eric Temple Bell
11
).Forn =0,...,10, the values of
B
n
,then-th Bell number, are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147,and
115975 (sequence A000110 in [180] ).
Example 2.60 We compute the exponential generating function for the Bell
numbers. It can be shown (see Exercise 2.16) that the Bell numbers satisfy the
recurrence B
n+1
=
n
k=0
n
k
B
k
for n ≥ 0,withB
0
=1. Looking at the right-
hand side of the equation, we see that this represents the series obtained by
multiplying the exponential generating functions of the Bell numbers and the
sequence of all 1s. If we denote the generating function for the Bell numbers
by B(x), then the exponential generating function of the left-hand side is given
by (DB )(x). All together,
B
= e
x
B,
which implies that B(x)=C exp(e
x
) for some constant C.SinceB
0
= B(0) =
1, we have that C = e
−1
, and therefore,
B(x)=exp(e
x
− 1).
We now return to the generating function for the Catalan sequence derived
in Example 2.50. It has a special property, namely that it can expressed as a
continued fraction. As the name suggests, continued fractions are expressions
10
http://mathworld.wolfram.com/BellNumber.html
11
http://www-groups.dcs.st-and.ac.uk/ history/Mathematicians/Bell.html
© 2010 by Taylor and Francis Group, LLC