Heubach S., Mansour T. Combinatorics of Compositions and Words
Подождите немного. Документ загружается.
24 Combinatorics of Compositions and Words
Example 2.3 The sequence {2n}
n∈N
of even natural numbers is a subse-
quence of the sequence {n}
n∈N
of natural numbers.
In combinatorics, the notion of a one-to-one correspondence is especially
important, as it allows us to establish that two sets have the same cardinality,
that is, the same number of elements. This idea will be used repeatedly when
we discuss Wilf-equivalence in Chapters 4 and 5.
Definition 2.4 Afunctionf : A → B is injective or one-to-one if for all
x, y ∈ A, x = y implies that f (x) = f(y), that is, every element of the
codomain B is mapped to by at most one element of the domain A.Afunction
f : A → B is surjective or onto if for all y ∈ B there is an element x ∈ A
such that f(x)=y, that is, the range is equal to the codomain. A function is
bijective or one-to-one and onto if and only if it is both injective and surjective,
that is, every element of the codomain is mapped to exactly one element of the
domain. A bijective function is a bijection or a one-to-one correspondence.
Example 2.5 We will use a bijection to establish that the number of words
on the alphabet [3] that avoid the pattern 12–3 equals the number of words
on [3] that avoid the pattern 21–3. Avoiding the pattern 12–3 means that
there is no subsequence of the form w
i
w
i+1
w
j
such that w
i
<w
i+1
<w
j
with j>i+1. These two patterns are examples of generalized patterns,
which we will discuss in Chapter 5. Since the alphabet is [3], we have two
cases: If w does not contain the letter 3, then it automatically avoids both
12–3 and 21–3.Ifw contains at least one letter 3, the pattern 12–3 is avoided
if w = w
(1)
3w
(2)
3 ···3w
(s)
,wheres ≥ 2 and each of the w
(i)
for i<sis
a word on the alphabet [2] that avoids the pattern 12,andw
(s)
is any word
on [2].Thus,eachw
(i)
for i<sis of the form 2
j
1
,withj, ≥ 0.On
the other hand, a word w avoids 21–3 if either the word w does not contain
the letter 3,orw = w
(1)
3w
(2)
3 ···3w
(s)
,wheres ≥ 2 and each of the w
(i)
is a word on the alphabet [2] that avoids the pattern 21, and therefore is of
the form 1
j
2
,withj, ≥ 0. So what is the bijection? Here it is: For a
word w = w
(1)
3w
(2)
3 ···w
(s−1)
3w
(s)
that avoids 12–3, there is exactly one
corresponding word w
= f(w) that avoids 21–3 where
f(w)=R(w
(1)
)3R(w
(2)
)3 ···R(w
(s−1)
)3w
(s)
and R denotes the reversal map (see Definition 1.5). Likewise, starting with
aword
¯w =¯w
(1)
3¯w
(2)
3 ···¯w
(s−1)
3¯w
(s)
that avoids 21–3, we can map it to exactly one word w that avoids 12–3 using
the function f
−1
defined by
f
−1
(¯w)=R(¯w
(1)
)3R(¯w
(2)
)3 ···R(¯w
(s−1)
)3w
(s)
.
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 25
Clearly, f (f
−1
¯w)= ¯w and f
−1
f(w)=w, so we have established a bijection
or one-to-one correspondence between the set of words on [3] that avoid 12–3
and those that avoid 21–3.
Now we return to sequences. They can be defined either by an explicit
formula or via a recurrence relation. An explicit formula for a sequence allows
for direct computation of any term of the sequence by knowing just the value
of n, without the need to compute any other term(s) of the sequence.
Example 2.6 (Permutations) Given a set of n symbols, we want to count the
number of ways these n symbols can be arranged, which equals the number of
bijections from [n] to [n] or the number of permutations of [n](see Definition
1.10). There are n choices for the first element in the arrangement, n − 1
choices for the next element, n − 2 choices for the third element, ... ,one
choice for the last element. Therefore,
S
n
= |S
n
| = n · (n − 1) · (n − 2) ···2 · 1=n!.
Note that n!reads“n factorial”, and 0! = 1 by definition. With this
explicit formula it is easy to compute the number of permutations of [10] as
10! = 3, 628, 800.
A recurrence relation, on the other hand, defines the value of a
n
in terms
of the preceding value(s) of the sequence, together with an initial condition
or a set of initial conditions. The initial conditions are necessary to ensure a
uniquely defined sequence, and consist of the first k values of the sequence,
where k equals the difference between the highest and the lowest indices that
occur in the recurrence relation.
Example 2.7 (Recursion for the Fibonacci sequence) The Fibonacci sequence
is defined by
F
n
= F
n−1
+ F
n−2
,F
0
=0,F
1
=1,
that is, each term is the sum of the two preceding terms, except for the first two
values, which are needed to get the recursion started. Hence, the recurrence
relation only applies for n ≥ 2. From the initial conditions we can easily
compute F
2
= F
1
+ F
0
=1, F
3
=2, ... The first sixteen terms of the sequence
are given by 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 and 610
(see A000045 in [180]). To obtain these (and, with appropriate modification,
more) values we can use the following Maple code:
aseq:=proc(n)
if n<0 then return "seq not defined for negative indices";
elif n=0 then return 1;
elif n=1 then return 1;
else aseq(n-1)+aseq(n-2);
end if;
end proc:
seq(aseq(n),n=0..15);
© 2010 by Taylor and Francis Group, LLC
26 Combinatorics of Compositions and Words
The corresponding Mathematica code is
F[0] = 0; F[1] = 1;
F[n_] := F[n] = F[n - 1] + F[n - 2];
Table[F[n], {n, 0, 15}]
Note that the delayed assignment F[n_]:= F[n] = is a way to prompt Math-
ematica to retain already computed values, which is crucial in recursive com-
putations.
If we change the initial conditions for the Fibonacci recurrence we obtain
another famous sequence.
Example 2.8 (Recursion for the Lucas sequence) The Lucas sequence is de-
fined by
L
n
= L
n−1
+ L
n−2
,L
0
=2,L
1
=1,
which leads to the sequence whose terms for n =0,...,15 are given by 2, 1, 3,
4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843 and 1364 (see [180], A000032
and A000204). Modifying the code from Example 2.7, we can compute the
sequence of values as
aseq:=proc(n)
if n<0 then return "seq not defined for negative indices";
elif n=0 then return 2;
elif n=1 then return 1;
else aseq(n-1)+aseq(n-2);
end if;
end proc:
seq(aseq(n),n=0..15);
in Maple; in Mathematica,wecanuse
L[0] = 2; L[1] = 1;
L[n_] := L[n] = L[n - 1] + L[n - 2];
Table[L[n], {n, 0, 15}]
For a history of these two sequences, as well as applications where these
sequences occur, see [125]. It is customary to use the letters F and L for
these two sequences. A third sequence that is closely related to these two
is the shifted Fibonacci sequence, defined as f
n
= F
n+1
for n ≥ 0, which
occurs naturally in many different contexts. We will now look at additional
examples, namely compositions in {1, 2} and words on [3]; the first of these
will give rise to the shifted Fibonacci sequence.
Example 2.9 (Compositions in {1, 2} ) We want to count the number of com-
positions of n that contain only 1sand2s. For the first few values of n,we
can easily make a list of such compositions, as shown in Table 2.1, and count
their number directly.
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 27
TABLE 2.1: Compositions of n with 1s and 2s
n # of compositions compositions
1 1 1
2
2 11, 2
3
3 111, 12, 21
4
5 1111, 112, 121, 211, 22
5
8 11111, 1112, 1121, 1211, 122, 2111, 212, 221
The resulting sequence for the number of compositions looks very much like
the Fibonacci sequence, except it does not start correctly. We also have to
check whether this Fibonacci pattern continues beyond the first few values.
Let’s think about a systematic way to create the compositions of n in {1, 2}
recursively. Each such composition of n (for n ≥ 2) either starts with a 1
or a 2. We can create those starting with a 1 by appending a composition of
n −1,andthosestartingwitha2 by appending a composition of n − 2.Itis
customary to define the number of compositions of 0 to be 1(for the empty
composition). If we denote the number of compositions of n in {1, 2} by C
n
,
then we obtain the following recursion:
C
n
= C
n−1
+ C
n−2
,C
0
= C
1
=1,
which results in the shifted Fibonacci sequence.
Example 2.10 (Words avoiding given substrings) Let’s determine a
n
,the
number of words of length n on the alphabet {1, 2, 3} which do not start with
3 and do not contain the substrings 13, 22, 31,and32. If the word starts with
a 1, we can append any of the a
n−1
such words of length n − 1.Iftheword
starts with a 2, then the second letter has to be a 1 or a 3, that is, the word
starts with 21 or with 23. In the first case, there are no restrictions on how
the word can continue, so we can append any word of length n −2 without the
forbidden substrings, for a total of a
n−2
such words. If the word starts with
23, then the only possible words are of the form 233 ···3, and there is exactly
one. The initial conditions are a
0
=1and a
1
=2. Overall,
a
n
= a
n−1
+ a
n−2
+1,a
0
=1,a
1
=2.
In these two examples, the recurrence relation was very easy to derive,
whereas an explicit formula is hard to obtain directly. Very often, a recursive
relation can be obtained naturally, as it expresses how a sequence evolves
from one step to the next. Notice how we divided the objects to be counted
into classes or categories, each of which is counted separately. In the example
above, we focused on the first part of the composition or word. In the case
of the compositions, we could have just as easily focused on the last part, as
each composition either ends in a 1 or a 2. Focusing on the first and last
© 2010 by Taylor and Francis Group, LLC
28 Combinatorics of Compositions and Words
parts are common ways to categorize, but we will see other possibilities in the
examples throughout the book.
The drawback of a recurrence relation is that in order to obtain a specific
term of the sequence, say C
100
, all preceding values C
1
,C
2
,...,C
99
have to
be computed, unless an explicit formula can be derived. We will discuss ways
of deriving an explicit formula from a recurrence relation in Section 2.2.
Sometimes we are interested in more than one parameter, for example, in
addition to the number of compositions we may want to keep track of the
number of parts in the compositions of n, or the number of times the part 1
occurs in all compositions of n. In this case, we obtain a sequence with two
indices.
Definition 2.11 A sequence with k indices is a function a:I
k
→ B,denoted
by {a
n
1
,...,n
k
}
n
1
,...,n
k
∈I
or {a
→
n
}
→
n ∈I
k
,whereI ⊆ Z. The element a
→
n
of a
sequence {a
→
n
}
→
n ∈I
is called the
→
n -th term, and the vector
→
n of integers is
the sequence vector of indices.
If a sequence has only two indices, it is easy to list the sequence values in
a two-dimensional table.
Example 2.12 (Continuation of Example 2.9) Let a
n,m
denote the number
of compositions of n in {1, 2} with exactly m parts. FromTable2.1,wecan
read off that a
4,1
=0, a
4,2
=1, a
4,3
=3,anda
4,4
=1. To obtain the
recurrence relation for this sequence, we now also keep track of what happens
to the number of parts when we create the compositions recursively. Whenever
we either prepend a 1 or a 2 to a composition of n − 1 or n − 2, respectively,
the number of parts increases by one. Thus,
a
n,m
= a
n−1,m−1
+ a
n−2,m−1
,a
0,0
=1,a
1,1
=1,a
n,0
=0if n =0.
From the definition, a
n,m
=0if m>n, and we therefore present the values as
a triangular array in Table 2.2, where only the values corresponding to m ≤ n
are listed. Note that summing the elements across a row gives the number of
compositions of the respective n.
TABLE 2.2: Compositions of n in {1, 2} with m parts
n
\
m
0123...
0 a
0,0
=1
1
a
1,0
=0 a
1,1
=1
2
a
2,0
=0 a
2,1
=1 a
2,2
=1
3
a
3,0
=0 a
3,1
=0 a
3,2
=2 a
3,3
=1 ...
4
a
4,0
=0 a
4,1
=0 a
4,2
=1 a
4,3
=3 ...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 29
To compute the values for a
i,j
given in Table 2.2, we can use the following
Mathematica code:
a[n_, 0] := Piecewise[{{1, n == 0}, {0, n != 0}}];
a[n_, m_] := a[n, m] = a[n - 1, m - 1] + a[n - 2, m - 1];
Table[a[n, m], {n, 0, 4}, {m, 0, 3}]
TheMaplecodeisgivenby
a:=Matrix(5,5):
a[1,1]:=1:
for m from 2 to 5 do
a[1,m]:=0:
od:
for n from 2 to 5 do
a[n,1]:=0;
for m from 2 to 5 do
if n=m then a[n,m]:=1;
elif n<m then a[n,m]:=0;
else a[n,m]:=a[n-1,m-1]+a[n-2,m-1];
end if;
od:
od:
"print/rtable"(a);
Other examples of sequences with two indices are k-element permutations
and k-element combinations of n objects.
Example 2.13 (Permutations revisited ) In Example 2.6 we looked at all pos-
sible arrangements of a set of n objects. What if we only want to arrange
k ≤ n of the objects? In how many ways can this be accomplished? Arguing
as before, there are n choices for the first element in the arrangement, n − 1
choices for the second element, ..., n − k +1 choices for the k-th element.
Overall, if S
n,k
denotes the number of k-element permutations of n objects,
then
S
n,k
= n · (n − 1) ···(n − k +1)=
n!
(n − k)!
.
Note that S
n
in Example 2.6 is given by S
n,n
= n!/0! = n!.
For permutations, order matters. However, if we look at all possible k-
element subsets of a set with n elements, then order does not matter. What
matters is only whether a particular element is contained in the subset or not.
Selections without order are called combinations.
Example 2.14 (Combinations) How can we count the number of k-element
combinations of n objects? Rather than counting the k-combinations directly,
we make a connection with k-element permutations of n objects by creating
the k-element permutations in two steps. First we select the k elements, and
© 2010 by Taylor and Francis Group, LLC
30 Combinatorics of Compositions and Words
then we arrange them in all possible orders. If we let C
n,k
denote the number
of k-element combinations of n objects, then the first task can be done in C
n,k
ways, and each such selection can be arranged in S
k,k
= k! ways. Therefore,
S
n,k
= C
n,k
·k!, which implies that
C
n,k
=
S
n,k
k!
=
n!
(n − k)!k!
=
n
k
.
The values C
n,k
occur in the Binomial theorem, and
n
k
reads “n choose
k”. These values also occur in the famous Pascal’s Triangle,whichshowsyet
another way to display a sequence with two indices in tabular form.
Example 2.15 (Pascal’s Triangle) Pascal’s Triangle is named after Blaise
Pascal
1
, but was known about 500 years earlier both in the Middle East by
Al-Karaji
2
and in China by Jia Xian
3
.
It was named after Pascal (at least in Europe) due to Pascal’s important
Treatise on the Arithmetical Triangle, in which the binomial coefficients of
the form
n
k
for 0 ≤ k ≤ n are given in a triangular array.
TABLE 2.3: Pascal’s triangle.
0
0
1
0
1
1
2
0
2
1
2
2
3
0
3
1
3
2
3
3
.
.
.
1
11
121
1331
.
.
.
When displayed in the form of Table 2.3, where rows correspond to the values
of n, and the diagonals from lower left to upper right correspond to the values
1
http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Pascal.html
2
http://turnbull.mcs.st-and.ac.uk/∼history/Mathematicians/Al-Karaji.html
3
http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Jia Xian.html
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 31
of k, many interesting properties can be derived. One very useful property is
the fact that the two diagonals that “enclose” the triangle on the sides consist
of all 1s, and all other entries can be computed by adding the two values
directly above to the left and right of the entry. This property can be verified
by showing that
n
k
=
n − 1
k − 1
+
n − 1
k
, (2.1)
either by using the formula for
n
k
, or by giving a combinatorial argument.
Recall that
n
k
counts the number of ways to select a subset of k elements
from a set of n elements, say the set [n]. Now any subset either does or does
not contain the element n. If the subset contains the element n, then the
remaining k −1 elements are chosen from the set [n−1] in
n−1
k−1
ways. If the
subset does not contain the element n,thenallk elements are chosen from the
set [n −1], which can be done in
n−1
k
ways. Since these are the only possible
cases, and the two cases are disjoint, we can add the two counts to obtain the
result of (2.1). The entries of the enclosing diagonals are of the form
n
0
or
n
n
, and there is exactly one way to either select no or all elements from a
set of n objects.
2.2 Solving recurrence relations
We will now discuss methods to obtain explicit formulas from recurrence
relations. Different approaches can be used, some of which apply only to cer-
tain types of recurrence relations. Therefore, we start by classifying recurrence
relations.
Definition 2.16 A linear (in the a
i
) recurrence relation of order r is of the
form
P
0
(n)a
n
+ P
1
(n)a
n−1
+ ···+ P
r
(n)a
n−r
= q(n)
for all n ≥ r,whereP
r
is nonzero. The recurrence relation is called P-
recursive if P
0
,P
1
,...,P
r
and q are polynomials in n. In the special case
whereallthepolynomialsP
i
are constant, the recurrence relation reduces to
a linear recurrence relation of order r with constant coefficients.Ifq(n)=
0, then the recurrence relation is called homogeneous, otherwise it is called
nonhomogeneous.
The order of the recurrence relation is the number of prior terms needed
to compute the next one, and also equals the number of initial values a
n
0
,
a
n
0
+1
,...,a
n
0
+r−1
needed to obtain a unique sequence. The order can be
computed as the difference between the highest and lowest indices in the
© 2010 by Taylor and Francis Group, LLC
32 Combinatorics of Compositions and Words
recurrence relation. Note that the order may differ from the number of terms
in the recurrence relation.
Example 2.17 (Compositions in {1, 2} avoiding the substring 11) Let a
n
be
the number of compositions of n in {1, 2} that avoid the substring 11.Then
a
0
=1(the empty composition), a
1
=1(the composition 1),anda
2
=1(the
composition 2). In general, any such composition either starts with a 1 or
with a 2. A composition of n that starts with a 2 can be created by combining
a 2 with a composition of n−2 that avoids the substring 11. If the composition
starts with a 1, then it has to start with 12 (to avoid the substring 11),sowe
can combine a composition of n − 3 with 12 to obtain those compositions of
n. All together,
a
n
= a
n−2
+ a
n−3
,a
0
= a
1
= a
2
=1.
In this case, the order of the recurrence is n − (n −3) = 3.
We are now ready to discuss several methods of solving recurrence relations:
• Guess and check.
• Iteration (repeated substitution).
• Characteristic polynomial.
• Generating functions.
Note that with the exception of linear recurrence relations with constant
coefficients, there are no general methods for obtaining explicit formulas from
recurrences relations.
2.2.1 Guess and check
As the name indicates, the first method consists of guessing a solution and
then proving by induction that the guess is correct. Obtaining the right guess
is a matter of either smart observation or just plain luck.
Example 2.18 Consider the recurrence relation
a
n
= n · a
n−1
,n≥ 1,a
0
=1.
Computing the first few values gives a
0
=1, a
1
=1, a
2
=2, a
3
=6, a
4
=24,
and a
5
= 120. A reasonable guess (both from the values and the recurrence
relation) is that a
n
= n! for all n ≥ 0, which is easy to prove by induction:
a
n+1
=(n +1)· a
n
=(n +1)· n!=(n +1)!.
Note that this recurrence relation is P-recursive. We can also find the ex-
plicit formula for a
n
by using the Maple function rsolve or the Mathematica
function RSolve:
© 2010 by Taylor and Francis Group, LLC
Basic Tools of the Trade 33
rsolve({a(n)=n*a(n-1),a(0)=1},a(n));
and
RSolve[{a[n]==n*a[n - 1], a[0]==1}, a[n], n]
2.2.2 Iteration
The second method, iteration or repeated substitution, is most useful when
the recurrence relation is of order one. The method consists of applying the
recurrence relation repeatedly, simplifying the result and then recognizing a
pattern.
Example 2.19 Consider the recurrence relation
a
n
=
2n +1
n +1
· a
n−1
,n≥ 1,a
0
=1.
Repeated substitution gives
a
n
=
2n +1
n +1
· a
n−1
=
(2n + 1)(2n −1)
(n +1)n
·a
n−2
=
(2n + 1)(2n − 1)(2n −3)
(n +1)n(n −1)
·a
n−3
= ···
=
(2n + 1)(2n − 1) ···5 · 3
(n +1)n ···2
· a
0
=
(2n +1)!
(n +1)!· 2n(2n − 2) ···2
=
(2n +1)!
2
n
n!(n +1)!
=
1
2
n
2n +1
n
.
The explicit formula for a
n
can be obtained by modifying the Maple and Math-
ematica codes of Example 2.18:
rsolve({a(n)=(2*n+1)/(n+1)*a(n-1),a(0)=1},a(n));
and
RSolve[{a[n]==(2n+1)/(n+1)a[n - 1], a[0]==1}, a[n], n]
Note that the answer given by Mathematica is in terms of Gamma functions,
which is no surprise, as the Gamma functions are a generalization of the
binomial coefficients for noninteger values.
More generally, the explicit formula for the recurrence relation
a
n
= q(n) · a
n−1
,n≥ 1
© 2010 by Taylor and Francis Group, LLC