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

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

Words 225

Let us call the i-th row of (6.22) the i-th level of p(n, k). If I(n, k;



)=∅

then there are no (m + 1)-active elements of the set P (n, k;



). Thus if

∪



I(n, k;



)=∅ then (6.22) contains only m + 1 levels and we can ask

if there is an exact formula for the sequence {p(n, k)}

n≥0

. To answer this

question, we deﬁne for any sequence {p(n, k)}

n,k≥0

the generating functions

(x;v



n≥0

p(n, k;v

)



n≥0





1≤j

,...,j

≤k

p(n, k;



)



i=1

−1



(6.23)

and

P (x, y; v



k≥0

(x;v

Now we can describe the scanning-element algorithm whose input is a family

of sets {P(n, k)}

n,k≥0

and whose output is an exact formula for the sequence

{p(n, k)}

n,k≥0

Scanning-element algorithm on words

1. Find a recurrence relation for the sequence {p(n, k)}

n,k≥0

as described

in (6.22).

2. Decide whether the sequence {p(n, k)}

n,k≥0

results in a ﬁnite system

of recurrence relations with t + 1 equations. If yes, continue; otherwise

stop.

3. Rewrite the system of recurrence relations in the statement of (6.22) in

terms of generating functions with t indeterminates v

,...,v

.Thisis

done by multiplying the recurrence relations by



i=1

−1

and summing

over

∈ I(n, k),j

∈ I(n, k; j

),...,j

∈ I(n, k; j

,...,j

t−1

4. Extract from Step 3 a system of functional equations in t +2 variables

x, y, v

,...,v

5. Solve this system to get an expression for P (x, y;1, 1,...,1), which is

a formula for the ordinary generating function



n,k≥0

p(n, k)x

,as

desired.

The above algorithm suggests to reﬁne the k-ary words according to the

value(s) of the leftmost element(s), and then to apply algebraic techniques.

Step 2 is the crucial one (as in the case of permutations, see [64]) because the

system of equations often is not ﬁnite or has coeﬃcients that do depend on n



226 Combinatorics of Compositions and Words

We now give the third proof for Theorem 6.25, actually using τ = 123

instead of τ = 132. For the scanning-element algorithm, either pattern is

equally easy. Note that we derive the generating function of the 123-avoiding

words according to their ﬁrst letter, that is, we are obtaining a reﬁned result

as a by-product of the proof.

Proof (of Theorem 6.25 using scanning-element algorithm) Deﬁne

P (n, k)=AW

[k]

(123)

and let w = w

···w

∈AW

[k]

(123). If w starts with k or k − 1, then w

cannot be part of any pattern 123, so the set P (n −1,k) is a reduction of the

sets P (n, k; k)andP (n, k; k −1). If w

= j ≤ k −2thenj ∈ I(n, k). Now we

look at the ﬁrst two letters of w.Ifw

= ij with i ≥ j then w avoids 123 if

and only if jw

···w

∈AW

[k]

n−1

(123), so the set P(n − 1,k; j) is a reduction

of the set P (n, k; i, j) for all i ≥ j.Ifi<jthen the only letters that can

follow are from the alphabet [j], so we can map ijw

···w

∈AW

[k]

(123) to

···w

∈AW

[j]

n−1

(123). Thus the set P (n − 1,j; i) is a reduction of the

set P (n, k; i, j) for all i<j. Putting these all together, (6.19) leads to the

following equations:

p(n, k; k)=p(n, k; k −1) = p(n − 1,k) (6.24)

p(n, k; i)=



j=1

p(n, k; i, j)+



j=i+1

p(n, k; i, j)



j=1

p(n − 1,k; j)+



j=i+1

p(n − 1,j; i), (6.25)

for all 1 ≤ i ≤ k − 2. Multiplying (6.25) by v

i−1

and summing over all

1 ≤ i ≤ k −1, we obtain a recurrence in terms of p(n, k; v):

p(n, k; v) − p(n, k; k)v

k−1



j=1

j−1

− v

k−1

1 − v

p(n − 1,k; j)+



j=2

(p(n − 1,j; v) −p(n − 1,j; j)v

j−1

Therefore

p(n, k; v) − p(n − 1,k;1)v

k−1



j=1

j−1

− v

k−1

1 − v

p(n − 1,k; j)+



j=2

(p(n − 1,j; v) −p(n − 1,j;1)v

j−1

)

1 − v



p(n − 1,k; v) − v

k−1

p(n − 1,k;1)





j=2



p(n − 1,j; v) −p(n − 2,j;1)v

j−1



Words 227

which implies that

p(n, k; v)=

1 − v



p(n − 1,k; v) − v

p(n − 1,k;1)





j=2



p(n − 1,j; v) −p(n − 2,j;1)v

j−1



(6.26)

for all n ≥ 2. This leaves the cases n =0andn =1. Forn =0,weobtain

the generating function P(0,k; v) = 1 directly from the deﬁnition. For n =1,

we use that p(1,k; j) = 1 by deﬁnition and thus

p(1,k; v)=1+v + ···+ v

k−1

1 − v

Multiplying (6.26) by x

and summing over n ≥ 2, we arrive at

(x; v) −

1 − v

x − 1=

1 − v



(x; v) −1) − v

(x;1)− 1)



+ x



j=2

(x; v) − 1) − x



j=2

j−1

(x;1),

which is equivalent to

(x; v)=1− (k −1)x +

1 − v



(x; v) − v

(x;1)



+ x



j=2

(x; v) −x



j=2

j−1

(x; 1) (6.27)

for all k ≥ 2. From the deﬁnitions we have that

(x; v)=1andP

(x; v)=

1 − x

Multiplying (6.27) by

(to get rid of the factor v

of P

(x; 1), the function

we want), summing over k ≥ 2 and simplifying, we obtain that

P (x,

; v)=

(v + x

)(v − y) − v

(v − y)

1 − v

P (x,

; v) − P (x, y;1)

v − y

vP(x,

; v) − xP (x, y;1)

or equivalently



1 −

1 − v

−

v − y



P (x,

; v)=

(v + x

)(v − y) − v

(v − y)

(6.28)

−



1 − v

v − y



P (x, y;1).

228 Combinatorics of Compositions and Words

Equation (6.28) can be solved using the kernel method as described in [13].

This method consists of setting the coeﬃcient of the function that we would

like to “get rid of” to zero, so that the remainder of the equation can be solved

for the function of interest. If substituting the solution so obtained into the

remainder of the equation results in a solution that can be expanded into a

Taylor series (as opposed to a Laurent series), then this is indeed a solution

and it is unique. So let’s get started. We want to eliminate P (x, y/v; v)and

then solve for P (x, y;1)=AW

123

(x, y). Setting 1 −

1−v

−

v−y

=0resultsin

+,−

1+y − 2x ±

(1 − y)((1 − 2x)

− y)

2(1 − x)

Now we substitute both solutions into the equation for P (x, y; 1) and compute

lim

x→0

P (x, y;1) for v = v

and v = v

−

, respectively. The solution for which

the limit equals 1 is the correct one. In our case this happens for v = v

Thus

123

(x, y)=P (x, y;1)=

+ x

)(v

− y) − v

x(v

− y)



1 − v

− y



Simplifying the resulting expression by rationalizing the denominator we ob-

tain that

123

(x, y)=1+

1 − x

y +

2x(1 − x)



1 − 2x −

(1 − 2x)

− y

1 − y



the result of Theorem 6.25. 2

Having computed an explicit expression for P (x, y;1), we can obtain an

explicit expression for P (x, y; v) from (6.28) by keeping v as a parameter

instead of substituting the computed solution v

. This result allows us to

enumerate the words that avoid 123 according to the ﬁrst letter, a result that

is a by-product of the scanning-element algorithm and that is much harder to

obtain from the other two methods, if at all.

6.5.4 Containing 123 or 132 exactly once

We conclude the discussion of permutation patterns of length three with

results on the number of k-ary words of length n that contain the patterns

123 and 132, respectively, exactly once. Keep in mind that Wilf-equivalence

applies to the avoidance of patterns. When counting according to the occur-

rence of patterns, the story is quite diﬀerent. Not only are the generating

functions diﬀerent, but also the methods used in their derivation diﬀer. Both

results were proved by Firro and Mansour in [65]. They derived the result for

the pattern 123 using the scanning-element algorithm and the result for the

Words 229

pattern 132 using the block decomposition approach. In each case, the other

method is either diﬃcult to use or cannot be applied. This once more illus-

trates the necessity of having several methods available in one’s “toolbox.”

We will state the two results without proof.

Theorem 6.37 The generating function for the number of k-ary words of

length n that contain the pattern 123 exactly once is given by

(x − 1) + x

(9 − 10x +2x

)(1 − y) − x(3 − 2x)(1 − y)

+(1− y)

(1 − x)

(1 − y)

−

y(1 − x − y)((1 − x)(1 − 2x) − y)

(1 − x)

(1 − 2x)

− y

1 − y

Moreover, for k ≥ 3 and n ≥ 0, the number of k-ary words of length n that

contain the pattern 123 exactly once is given by

n+2,k

− 3h

n+1,k

+2h

n,k

− 2(h

n+2,k−1

− h

n+1,k−1

) − 1+

n+2



j=0

n+2−j,k−2

where

n,k



j=0

(−1)

n−j

1+j



n −j



k − 1+j





Theorem 6.38 The generating function for the number of k-ary words of

length n that contain the pattern 132 exactly once is given by

x + y − 1 − ((1 − 2x)(1 − x) − y)

(1−2x)

−y

1−y

−

2(1 − x)

(1 − y)

6.6 Generalized patterns of type (2,1)

We start once more by classifying the patterns according to Wilf-equiva-

lence. When considering avoidance of permutation patterns of type (2, 1)

in compositions, there were three equivalence classes, namely 12–3 ∼ 21–3,

23–1 ∼ 32–1, and 13–2 ∼ 31–2 (see Theorems 5.18 and 5.19). Using the

complement map, the three classes reduce to two classes and we obtain the

following results as a special case of compositions (see Theorem 5.21). For

the pattern 13–2 we only obtain a recursion from Lemma 5.25 and there is no

explicit formula known for this generating function.

230 Combinatorics of Compositions and Words

Proposition 6.39 The generating functions for the number of words avoid-

ing the patterns 12–3 and 13–2, respectively, are given by

12–3

[k]

(x)=



i=1

1 −

(1−x)

i−1

and

13–2

[k]

(x)=1+



i=1

13–2

[k]

(i|x),

where

13–2

[k]

(i|x)=x

⎛

⎝

i+1



j=1

13–2

[k]

(j|x)+



j=i+2

13–2

[i+k−j+1]

(j|x)

⎞

⎠

with AW

13–2

[k]

(k|x)=AW

13–2

[k]

(k − 1|x)=xAW

13–2

[k]

(x).

Note that AW

12–3

[1]

(x)=AW

13–2

[1]

(x)=

1−x

and AW

12–3

[2]

(x)=AW

13–2

[2]

(x)=

1−2x

. Burstein and Mansour [33] derived the generating functions AW

13–2

[k]

(i|x),

i =1, 2, 3, 4, using the recursion given in Proposition 6.39.

Theorem 6.40 The generating functions for the number of words that start

with i =1, 2, 3, 4 and avoid τ =13–2 are given by

13–2

[k]

(1|x)=

1 − x

13–2

[k]

(2|x)=

1 − 2x

13–2

[k]

(3|x)=

(1 − x)

(1 − 2x)(1 − 3x + x

)

13–2

[k]

(4|x)=

1 − 4x +6x

− 3x

(1 − 2x)(1 − 3x)(1 − 3x + x

)

We now consider patterns of type (2, 1) with repeated letters. In the case

of compositions we had a total of ﬁve equivalence classes, namely 11–1, 11–2,

22–1, 12–2 ∼ 21–2 and 21–1 ∼ 12–1. In Theorem 5.38 we gave a combinatorial

argument for the equivalence of the patterns 12–2 and 21–2. Burstein and

Mansour [34] showed the same equivalence in the case of words using an

analytical proof.

The complement map reduces the ﬁve equivalence classes to just three in

the case of words, namely 11–1, 11–2 ∼ 22–1, and the class consisting of the

remaining patterns. We start by giving the generating function for 11–1, a

result given originally by Burstein and Mansour in [34].

Words 231

Theorem 6.41 For al l k ≥ 1,

11–1

[k]

(x)=det

(

(x) −A

(x)0... 0

k−1

(x)1−A

k−1

(x) ... 0

k−2

(x)0 1... 0

(x)00

−A

(x)

(x)+A

(x)0 0 ... 1

(



i=1

(x)+



j=1

⎛

⎝

(x)



i=j+1

(x)

⎞

⎠

where A

(x)=

1−(j−1)x

and B

(x)=

1+x

1−(j−1)x

Note that the proof given in [34] proceeds from the recurrence relation that

is obtained after appropriate simpliﬁcation when setting x =1andy = x in

(5.6) of Theorem 5.39. The result follows by induction.

For the pattern 11–2, we obtain a nice explicit result from Theorem 5.41.

This theorem is also an example of the phenomenon that complementary pat-

terns have structurally similar generating functions for compositions, which

coincide when specialized to the case of words.

Proposition 6.42 The generating function for k-ary words of length n that

avoid 11–2 is given by

11–2

[k]

(x)=

k−1



j=0

1 − (j − 1)x

1 − (j + x)x

Finally, we present the result given in [33] for the pattern 21–1.

Theorem 6.43 For k ≥ 0,

21–1

[k]

(x)=1+

k−1



d=0



d+1

21–1

[k−d]

(x)

k−1



i=d

(1 − x)

i−d







Proof Let AW

21–1

[k]

,...,i

|n)bethenumberofwordsw in AW

[k]

(21-1)

that start with i

···i

. Now consider AW

21–1

[k]

(i, j|n). If j ≥ i then the letter

i cannot be part of any 21-1 in a word w beginning with ij and therefore

places no further restrictions on the rest of w,so

21–1

[k]

(i, j|n)=AW

21–1

[k]

(j|n − 1).

If j<ithen deleting the ﬁrst i from a word w starting with ij results in a

word w



∈AW

[k]

n−1

(21-1) which contains exactly one j,andj is the ﬁrst letter.

232 Combinatorics of Compositions and Words

Now let w



∈AW

[k−1]

n−1

(21-1) be the word obtained from w



by subtracting one

from each letter that is bigger than j. Obviously, this mapping is a bijection

onto the set of words in AW

[k−1]

n−1

(21-1) starting with j (since neither it, nor

the inverse mapping, which consists of adding one to each letter that is at

least j and it is not the ﬁrst letter j creates any new occurrences of 21-1).

Thus

21–1

[k]

(i, j|n)=AW

21–1

[k−1]

(j|n − 1).

Using that

21–1

[k]

(i|n)=



j=1

21–1

[k]

(i, j|n)

we obtain that

21–1

[k]

(i|n)

i−1



j=1

21–1

[k−1]

(j|n − 1) +



j=i

21–1

[k]

(j|n − 1)

= AW

21–1

[k]

(n − 1) +

i−1



j=1

(AW

21–1

[k−1]

(j|n − 1) − AW

21–1

[k]

(j|n − 1)).

(6.29)

Using (6.29) we can prove by induction on d that

21–1

[k]

(d|n)

d−1



j=0



d − 1



d−1−j



i=0



d − 1 − j



(−1)

21–1

[k−j]

(n − 1 − i − j).

Hence for all n ≥ 1,

21–1

[k]

(n)



d=1

d−1



j=0



d − 1



d−1−j



i=0



d − 1 − j



(−1)

21–1

[k−j]

(n − 1 − i − j)

with AW

21–1

[k]

(0) = 1. Multiplying by x

and summing over n ≥ 1, yields

21–1

[k]

(x) − 1=



d=1

d−1



j=0



d − 1



j+1

(1 − x)

d−1−j

21–1

[k−j]

(x),

and therefore

21–1

[k]

(x) − 1=

k−1



d=0



d+1

21–1

[k−d]

(x)

k−1



i=d

(1 − x)

i−d







as claimed. 2

We conclude the chapter on pattern avoidance in words with the most

general type of pattern, namely partially ordered patterns.

Words 233

6.7 Avoidance of partially ordered patterns

Like the other patterns, POPs were originally studied on the set of k-ary

words [109], and then studied on the set of compositions [88]. We will present

a sample of results that can be recovered by substituting A =[k], x =1and

y = x into the results of Section 5.4.2 to recover the results originally given

by Kitaev and Mansour [109].

Example 6.44 From Example 5.62, we obtain a simple formula for the gen-

erating function for the number of k-ary words that avoid 1



–2–1



,namely



–2–1



[k]

(x)=

(1 − x)

2k−1

−

k−1



j=1

(1 − x)

The main results for avoidance of shuﬄe patterns and multi-patterns in

words follow from Theorems 5.63 and 5.73.

Example 6.45 Let φ be the shuﬄe pattern τ––ν. Then for all k ≥ ,

[k]

(x)=

[k−1]

(x) − xAW

[k−1]

(x)AW

[k−1]

(x)

(1 − xAW

[k−1]

(x))(1 − xAW

[k−1]

(x))

Example 6.46 Let τ = τ

–τ

– ···–τ

be a multi-pattern. Then

[k]

(x)=



j=1

[k]

(x)

j−1



i=1

(kx − 1)AW

[k]

(x)+1

Finally, we state the result on the maximum number of nonoverlapping

patterns obtained from Theorem 5.80.

Example 6.47 Let τ be any subword pattern. Then for all k ≥ 1,



n≥0



w∈[k]

τ –nlap(w)

[k]

(x)

1 − q

)

(kx − 1)AW

[k]

(x)+1

Using Table 6.1 and setting q =0inW

[k]

(x, q), we can easily obtain

[k]

(x) for any 3-letter subword pattern, and therefore a result on the max-

imum number of nonoverlapping 3-letter subword patterns. Since the (sub-

sequence) pattern 123 has played so prominently in the previous section, we

will use the (subword) pattern 123 as an example (given originally by Kitaev

and Mansour [109]).

234 Combinatorics of Compositions and Words

Example 6.48 The distribution of the maximum number of nonoverlapping

occurrences of the subword pattern 123 is given by



n≥0



w∈[k]

123–nlap(w)



j=0





+ q

1 − kx −



j=0





where a

=1, a

3m+1

= −1 and a

3m+2

=0, for all m ≥ 0.

6.8 Exercises

Exercise 6.1 Use the formula given in Table 6.1 to compute the sequence

of values for the number of 5-ary words of length n that avoid the subword

pattern 123 for n =1, 2,...,10.

Exercise 6.2 Let w = w

···w

be any word on the alphabet [k].Wesay

that w

is a left-right-maximum in w if w

for all j =1, 2,...,i− 1.

(1) Find an explicit formula for the generating function for the number of

k-ary words of length n on the alphabet [k] according to the number of

left-right-maxima. (For more details see [43, 158].)

(2) Extend Part (1) to the case of compositions of n with m parts in [d]

according to the number of left-right-maxima.

Exercise 6.3 Show that the generating function for H

(n, k) is given by

(x, y)=

1 − 2x − (1 − x)y

where H

(n, k)=



m=0





m+k−2



Exercise 6.4 Show that the generating function H

(x, y) satisﬁes the recur-

rence relation given in (6.13),namely,

(1 −2x −(1 −x)y)H

I+1

(x, y) −(1 −x −y)H

(x, y)=(1−x)u

(x)(y −1)y

I+1

for all I ≥ 1.

Exercise 6.5 Give a proof of Lemma 6.30.

Exercise 6.6 Fill in the missing details of the proof of Theorem 6.31.