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

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

Words 205

avoids τ(i +1,j + 1) at level m, we know that any word with landscape X



must avoid τ (i, j)atlevelm. Now deﬁne a word w



as follows:

1. The word w



has landscape X



2. For any p,thep-th low cluster of w



is identical to the p-th low cluster

of w.

3. For any q,theq-thhighclusterofw



is identical to the q-thhighcluster

of w.

Clearly there is a unique word w



satisfying these properties. For example,

for the word w = 534212 considered above, w



has landscape HLmH,andis

given by 521234. Note that the subsequence of all the low letters of w is the

same as the subsequence of all the low letters of w



, and these sequences are

partitioned into low clusters in the same way. An analogous property holds

for the high letters.

We claim that w



is an (m + 1)-hybrid. We have already pointed out that



avoids τ(i, j) at level m. Let us now argue that w



avoids τ(i, j) at level

m, for every m<m, using proof by contradiction. Assume that w



contains a

subsequence s =

i−1

 m

j−i−1

t−j

,forsome<m<h.Ifh<m,thenall

the letters of s are low, and since w has the same subsequence of low letters

as w



, we know that w also contains s as a subsequence, contradicting the

assumption that w is an m-hybrid.

Assume now that h ≥ m.Letx and y be the two letters adjacent to h in

the sequence s (note that h is not the last symbol of s,sox and y are well

deﬁned). Both x and y are low, and they belong to distinct low clusters of



, because the symbol h is not low. Since the low letters of w are the same

as the low letters of w



, and they are partitioned into clusters in the same

way, we know that w contains a subsequence

i−1

 m

j−i−1



t−j

,whereh



is not low. This shows that w contains τ(i, j)atlevelm, which is impossible,

because w is an m-hybrid.

By an analogous argument, we may show that w



avoids τ(i +1,j +1) at

any level 8m>m. We conclude that the mapping described above transforms

an m-hybrid w into an (m +1)-hybridw



. It is easy to see that the mapping

is reversible and therefore provides the required bijection between m-hybrids

and (m + 1)-hybrids for all m ≥ 1. Therefore, combining the bijections for

ﬁxed m, we have a bijection between τ(i, j)-avoiding and τ(i+1,j+1)-avoiding

words, and the claim follows by induction on i and j. 2

From Propositions 6.18 and 6.19 and Theorem 6.20 we can obtain clas-

siﬁcations for patterns of lengths four, ﬁve, and six. Tables 6.3-6.5 show

all the nontrivial Wilf-equivalence classes (those where the Wilf class is not

equal to the symmetry class). In Tables G.3 and G.4 we list all of the Wilf-

equivalence classes (including the trivial ones) together with a selection of

values of AW

[k]

(n) which show that these Wilf-classes are indeed the only

206 Combinatorics of Compositions and Words

TABLE 6.3: Wilf-equivalence classes for patterns of length 4

1223∼1232∼1322∼2132 1123∼1132

1234∼1243∼1432∼2143 1112∼1121

ones. Note that for patterns of lengths four and ﬁve, Propositions 6.18 and

6.19 and Theorem 6.20, together with the symmetry operations, suﬃce to give

a complete classiﬁcation.

TABLE 6.4: Wilf-equivalence classes for patterns of length 5

12223∼12232∼12322∼13222∼21232∼21322 12435∼13254

12345∼12354∼12543∼15432∼21354∼21543 12443∼21143

12234∼12243∼12343∼12433∼21243∼21433 12134∼12143

11234∼11243∼11432 11123∼11132

11223∼11232∼11322 12534∼21534

11112∼11121∼11211 12453∼21453

In addition, we can apply Propositions 6.18 and 6.19 and Theorem 6.20 to

compositions by deﬁning an analogous matrix representation of a composition

and creating bijections for compositions of n with a ﬁxed number of parts. In

the case of compositions the symmetry class consists only of τ and R(τ), so

more patterns have to be checked. Tables G.1 and G.2 give the complete Wilf-

classiﬁcation for subsequence patterns of length four and ﬁve for compositions

and list selected values of AC

to show that the listed Wilf-classes are indeed

diﬀerent.

Now that we have given the complete classiﬁcation according to Wilf-

equivalence, we will derive the generating functions AW

[k]

(x)andAW

(x, y)

for subsequence patterns of length three. Some of these results will be obtained

by specializing generating functions derived in Chapter 5, but sometimes this

will lead to complicated results. In those cases we will state the theorems that

were originally derived for words.

6.5 Subsequence patterns – Generating functions

We give results for subsequence patterns of length three. Table 6.2 indicates

that there are two Wilf-classes for patterns with repeated letters, namely 111

Words 207

TABLE 6.5: Wilf-equivalence classes for patterns of length 6

112223∼112232∼112322∼113222 124433∼214433

112345∼112354∼112543∼115432 124353∼214353

122334∼122343∼122433∼212343∼212433∼221433 124453∼214453

122234∼122243∼123343∼123433∼124333 126435∼216435

∼212243∼213433∼214333 125634∼215634

122223∼122232∼122322∼123222∼132222 126534∼216534

∼212232∼212322∼213222∼221322 123443∼211243

122345∼122354∼122543∼123454∼123544 125435∼132154

∼212354∼212543∼213544∼221543 125344∼215344

123456∼123465∼123654∼126543∼165432 123435∼132354

∼213465∼213654∼216543∼321654 124335∼133254

111223∼111232∼111322 123534∼213534

112334∼112343∼112433 125354∼213154

123554∼211354∼211543 125334∼215334

122435∼132454∼132544 113245∼113254

121345∼121354∼121543 125463∼215463

111112∼111121∼111211 122134∼122143

123645∼213645∼231654 126453∼216453

123564∼213564∼312654 124343∼212143

123546∼132465∼132654 121234∼121243

124356∼124365∼214365 123543∼213543

121334∼121343∼121433 123145∼123154

122534∼212534∼221534 124443∼211143

111234∼111243∼111432 124533∼214533

123345∼123354∼213354 125534∼215534

122453∼212453∼221453 124635∼214635

122443∼211343∼211433 111123∼111132

112234∼112243 125364∼215364

124535∼131254 124553∼214553

126354∼216354 125436∼143265

124563∼214563 126345∼216345

125346∼134265 125543∼215543

124354∼213254 124543∼214543

112134∼112143 123245∼123254

124435∼132254 125434∼215434

125433∼215433 125643∼215643

121134∼121143 125453∼215453

124653∼214653

208 Combinatorics of Compositions and Words

and 112, and just one class for permutation patterns. Since the results for

patterns with repeated letters are easier to derive, we present those results

ﬁrst, even though historically, permutation patterns were studied ﬁrst. In

addition, we give results for the generating functions for the number of words

that avoid a pair of patterns {132, 12 ···}, or contain 123 or 132 exactly once.

Theorem 6.21 The exponential generating function for the number of k-ary

words of length n that avoid the pattern 111 is given by



n≥0

111

[k]

(n)

=(1+x +

)

and therefore we obtain the number of k-ary words of length n that avoid 111

111

[k]

(n)=n!



j=0





n−j



n−j

Proof This follows from Theorem 5.11 with x =1,y = x,andA =[k],

followed by two applications of the binomial theorem. 2

Example 6.22 Since we have an explicit formula, we can easily compute the

sequence of values for AW

111

[k]

(n). The values for k =6and n =0, 1,...,12

are 1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400,

7484400,and7484400. Note that for n ≥ 13, a subsequence order-isomorphic

to 111 has to occur because we have only six letters in the alphabet.

For the pattern 112 we state the result and proof given in [33] which shows

an interesting connection to the (unsigned) Stirling numbers of the ﬁrst kind

which count the number of permutations of length n with k disjoint cycles

(see for example [72]).

Theorem 6.23 Let F

112

(x, y)=



k,n≥0

112

[k]

(n)

.Then

112

[k]

(n)=



j=0



n + k − j −1

"

n −j

and

112

(x, y)=

1 − y



1 − y

1 − y − xy



1/y

where

is the unsigned Stirling number of the ﬁrst kind (see Table A.1).

http://en.wikipedia.org/wiki/Stirling numbers of the ﬁrst kind

Words 209

Proof The recurrence for AW

112

[k]

(n) is the same as the one used in the proof

of Theorem 5.13 (except there the recurrence is in terms of the generating

functions). Consider all words w ∈AW

[k]

(112) which contain at least one 1.

Their number is

112

(n, k)=AW

112

[k]

(n) −|{w ∈AW

[k]

(112) : w has no 1s}|

= AW

112

[k]

(n) − AW

112

[k−1]

(n). (6.2)

On the other hand, each such w either ends in 1 or not. If w ends in 1 then

deletion of this 1 produces a word ¯w ∈AW

[k]

n−1

(112), because addition of

a 1 to the right end of any word ¯w ∈AW

[k]

n−1

(112) does not produce extra

occurrences of the pattern 112.

If w does not end in 1 then it can only contain a single 1 that does not

occur at end of w. Deletion of this 1 produces a word ¯w ∈AW

[2,k]

n−1

(112) and

the single 1 can occur in n −1 positions (all except the rightmost one). Thus

we have

112

(n, k)

= AW

112

[k]

(n − 1) + (n − 1)|{w ∈AW

[k]

n−1

(112) : w has no 1s}|

= AW

112

[k]

(n − 1) + (n − 1)AW

112

[k−1]

(n − 1). (6.3)

Combining (6.2) and (6.3), we get for n, k ≥ 1that

112

[k]

(n) − AW

112

[k−1]

(n)=AW

112

[k]

(n − 1) + (n − 1)AW

112

[k−1]

(n − 1), (6.4)

with initial conditions AW

112

[0]

(n)=δ

for all n ≥ 0, AW

112

[k]

(0) = 1, and

112

[k]

(1) = k for all k ≥ 0. Let F

112

(n; y)=



k≥0

112

[k]

(n)y

. Multiplying

(6.4) by y

and summing over k ≥ 0, we get for n ≥ 1that

112

(n; y) − δ

− yF

112

(n; y)

= F

112

(n − 1; y) − δ

n−1,0

+(n − 1)yF

112

(n − 1; y).

Solving for F

112

(n; y)resultsin

112

(n; y)=

1+(n − 1)y

1 − y

112

(n − 1; y)forn ≥ 2. (6.5)

Furthermore, F

112

(0; y)=

1 − y

and F

112

(1; y)=

(1 − y)

. Iterating (6.5)

yields

112

(n; y)=

y(1 + y)(1 + 2y) ···(1 + (n − 1)y)

(1 − y)

n+1

=(1+y)(1 + 2y) ···(1 + (n − 1)y)



(1 − y)

n+1



. (6.6)

210 Combinatorics of Compositions and Words

That is, F

112

(n; y) is a convolution of two functions. If we are able to deter-

mine the coeﬃcients of each of these two functions, then we can compute

112

[k]

(n) as the convolution of the respective coeﬃcients (see Deﬁnition

2.34). First,

(1 + y)(1 + 2y) ···(1 + (n − 1)y)=y

n−1



j=0



+ j



= y



k=0

#





k=0

n−k



k=0

n − k

Using (A.3) and reindexing, we obtain the series expansion of the second

function as

(1 − y)

n+1

∞



k=0



n + k − 1



Therefore, AW

112

[k]

(n) can be computed as the convolution

112

[k]

(n)=

n − k

∗



n + k − 1





j=0



n + k − j − 1

"

n − j

which proves the ﬁrst statement. The result for F

112

(x, y) can be obtained as

the exponential generating function of F

112

(n; y) from the recursive relation

(6.5). Alternatively, we can build the generating function F

112

(x, y)fromthe

recurrence relation (6.4). Multiplying by

n−1

(n−1)!

, summing over n ≥ 1, and

recognizing the resulting series as a derivative yields



n≥1

(AW

112

[k]

(n) − AW

112

[k−1]

(n))



n≥1

(AW

112

[k]

(n − 1) − AW

112

[k−1]

(n − 1))

n−1

(n − 1)!



n≥1

112

[k−1]

(n − 1)

(n − 1)!

Deﬁning F (x; k)=



n≥0

112

[k]

(n)

gives that

112

(x; k) −

112

(x; k − 1)

= F

112

(x; k) −F

112

(x; k − 1) +

(xF

112

(x; k − 1)),

or equivalently,

112

(x; k)=F

112

(x; k)+(1+x)

112

(x; k − 1).

Words 211

Multiplying this recurrence by y

and summing over k ≥ 1, we obtain

112

(x, y)=

1 − y −yx

112

(x, y).

Solving this equation and using the initial condition F

112

(0,y)=

1 − y

yields

the desired formula. 2

Example 6.24 Since we have an explicit formula, we can compute the se-

quence of values for AW

112

[3]

(n) by using that

=1,

n−1





,and

n−2

(3n − 1)





(see Table A.1),asfollows:



j=0



n +2− j

"

n − j



n +2

"



n +1

"

n −1



"

n − 2

(n +2)(n +1)

+(n +1)





(3n − 1)





(24 + 22n +21n

+2n

+3n

The values of AW

112

[3]

(n) for n =0, 1,...,20 are 1, 3, 9, 24, 56, 116, 218, 379,

619, 961, 1431, 2058, 2874, 3914, 5216, 6821, 8773, 11119, 13909, 17196,and

21036.

Now we turn our attention to the case of the permutation patterns, which

were historically the ﬁrst ones to be studied. Three diﬀerent methods, namely

the Noonan-Zeilberger algorithm, the block decomposition method, and the

scanning-element algorithm, have been used for deriving

123

(x, y)=AW

132

(x, y).

We will present three diﬀerent proofs to showcase the advantages and disad-

vantages of each of these approaches. Before doing so, we will state the result

on the generating function for the number of words avoiding a permutation

pattern.

Theorem 6.25 [31, Theorem 3.2] The generating function for the number of

k-ary words of length n that avoid 132 is given by

132

(x, y)=1+

2x(1 − x)



1 −

(1 − 2x)

− y

1 − y



Note that in [31, Theorem 3.2], an explicit formula for AW

132

[k]

(n)isalso

given. We start with the original proof.

212 Combinatorics of Compositions and Words

6.5.1 Noonan-Zeilb erger algorithm

We discuss the Noonan-Zeilberger algorithm primarily for its historical im-

portance, as its use in Burstein’s thesis [31] started the research area of pattern

avoidance in words. The Noonan-Zeilberger algorithm [163] was originally

designed for enumerating permutations containing and avoiding permutation

patterns. Burstein generalized this algorithm in two directions: by considering

a set of patterns rather than a single pattern, and by adding the corrections

needed to apply it to words instead of permutations. We will describe the

generalized algorithm and illustrate it by deriving the generating function for

the number of 123-avoiding words.

Noonan-Zeilberger algorithm for words

Let τ =(τ

(1)

,...,τ

()

) be a vector of subsequence patterns and let r =

,...,r



), where r

indicates the number of times the pattern τ

(j)

to occur. If avoidance of a pattern is the goal, then r

=0.

Then the Noonan-Zeilberger algorithm for words can be described as fol-

lows:

1. Deﬁne a recurrence for the k-ary words of length n avoiding the patterns

τ . This is a matter of art and may involve removing either the ﬁrst or

last letter of the word, removing speciﬁc smallest or largest letters of

the word, and so on. Repeat if necessary.

2. Identify the auxiliary parameters of the recurrence which are associated

with the auxiliary subpatterns that arise in Step 1.

3. Assign a main variable for each pattern τ

(i)

of τ , and an auxiliary vari-

able for each of the auxiliary parameters.

4. Let the weight of the word w be deﬁned as wt(w)=



occ

(w)

,where

occ

(w) is the number of occurrences of the j-th pattern in w and the

product is over all patterns (main and auxiliary) which need to be con-

sidered for the recurrence obtained after Step 1.

5. Let s(w)=(s

,...,s

) be the content vector of w,thatis,s

is the

number of occurrences of the letter i in w, and deﬁne

n,s



w∈[k]

,s(w)=s

wt(w)x

Determine a functional equation for F

n,s

by using the recurrence devel-

oped in Step 1.

6. Solve the equation obtained in Step 5. This usually involves taking r

partial derivatives with respect to q

for j =1, 2,...,,thatis,with

respect to the variables corresponding to the main patterns.

Words 213

7. Set q

=0forj =1, 2,..., (main patterns) and q

=1forj>

(auxiliary patterns). This ensures avoidance of the main patterns and

renders the auxiliary patterns irrelevant.

8. Sum the resulting equation over all content vectors s with

|s| = s

+ ···+ s

= n

to compute F



w∈[k]

wt(w).

We are now ready give the proof of Theorem 6.25 using the Noonan-

Zeilberger algorithm.

Proof Since there is only the single pattern 123 to be avoided, r =(0).

Creating a recurrence relation by removing the last letter, we have to check for

the occurrence of any pattern 12 which could have led to an occurrence of the

pattern 123 with the letter that has been removed. Thus, for j =2, 3,...,k,

let occ

(w) be the number of occurrences of w

≤ j such that i

Introducing auxiliary variables q

,...,q

to keep track of the 2-letter patterns

that end with j =2,...,k, we obtain the weight of w as

wt(w)=q

occ

123

(w)



j=2

occ

(w)

Deﬁne F

(q; q

,...,q



w∈[k]

wt(w)=



s

n,s

(q; q

,...,q

)where

n,s

(q; q

,...,q



w∈[k]

,s(w)=s

wt(w)

and s =(s

,...,s

) is the content vector of w. To create the recurrence, let

w be any word of length n, w



be the word obtained by deleting the last letter

from w, and assume that w

= i.Thenfori =1,wt(w)=wt(w



). If i>1

then the last letter i of w can form a pattern 12 with any letter j<i,which

occurs s

times in w. In addition, any occurrence of a 2-letter pattern 12

ending in j<ican create an occurrence of 123. Therefore

wt(w)=wt(w





i−1

j=1



i−1

j=2

occ



)

= q

occ

123



)



i−1

j=1

i−1



j=2

(qq

)

occ



)



j=i

occ



)

Summing over all w with a given content vector s, we obtain that

n,s

(q; q

,...,q

)=δ(s −e

≥



0)F

n−1,s−e

(q; q

,...,q

)



i=2



i−1

j=1

δ(s −e

≥



0)F

n−1,s−e

(q; qq

,...,qq

i−1

,...,q

), (6.7)

214 Combinatorics of Compositions and Words

where e

is the i-th unit content vector,



0=(0,...,0), δ denotes the truth

value of the corresponding proposition, and inequalities hold componentwise.

Note that the condition δ(s −e

≥



0) ensures that the last letter can be an i.

Let

n,s

(k, I)=F

n,s

(0; 0, 0,...,0

-. /

I−1

, 1, 1,...,1

-. /

k−I

)

be the number of words with given content vector s that contain no occur-

rences of the pattern 123 and no instances of w

<Iwith i

Then, substituting q = q

= ···= q

=0,q

I+1

= ···= q

=1forI ∈ [k]into

(6.7), we obtain that

n,s

(k, I)=



i=1

δ(s −e

≥



0)F

n−1,s−e

(k, I)δ(s

= ···= s

i−1

=0)



i=I+1

δ(s −e

≥



0)F

n−1,s−e

(k, i − 1). (6.8)

Note that we need the condition δ(s

= ··· = s

i−1

= 0) to ensure that we

do not get zero factors when setting q

,...,q

i−1

=0. NowletJ

be the

smallest letter that occurs in w.WeseethatifJ

>I then the ﬁrst sum on

the right-hand side of (6.8) is zero, because s

=0foralli =1, 2,...,I implies

that δ(s − e

≥



0) = 0 for all i ≤ I. What happens if J

≤ I?Ifi<J

then s

=0,soδ(s −e

≥



0) = 0. If i>J

then δ(s

= ··· = s

i−1

=0)=0,

because s

> 0. Thus the only possible nonzero summand occurs when

i = J

, so our recursive relation takes the form

n,s

(k, I)=δ(J

≤ I)F

n−1,s−e

(k, I)+



i=I+1

δ(s−e

≥



0)F

n−1,s−e

(k, i−1).

Summing over all s ∈ N

such that |s| = n, we obtain (after adjusting the

index of the second sum) that

(k, I)=



i=1



|s|=n,J

n−1,s−e

(k, I)+

k−1



i=I

n−1

(k, i). (6.9)

Note that in the ﬁrst sum we have a restriction on the values of s by the

deﬁnition of J

, and therefore we do not obtain F

n−1

(k, I). Furthermore,

since the smallest letter that occurs is i, the alphabet can be adjusted from

[k]to[k − i + 1], with the resulting adjustment in the variables that are set

to zero as well. With these modiﬁcations (6.9) becomes

(k, I)=



i=1

n−1

(k − i +1,I − i +1)+

k−1



i=I

n−1

(k, i).