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

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

Words 215

Therefore, for I>1,

(k +1,I)+F

(k, I) − F

(k, I − 1) − F

(k +1,I+1)

=2F

n−1

(k +1,I) − F

n−1

(k, I − 1) − F

n−1

(k +1,I+1),

and for I =1,

(k+1, 1)−F

(k+1, 2) = 2F

n−1

(k+1, 1)−F

n−1

(k, 1)−F

n−1

(k+1, 2). (6.10)

Next, Burstein used the clever trick of recasting the recurrence for F

in a

diﬀerent form which results in a recurrence that can be solved. First, replace

I by k − I in the two recursions for F

(which replaces I>1byk>I+1),

andthenletH

(n, k)=F

(k, k − I). Thus, for k>I+1,I ≥ 1,

I+1

(n, k +1)− 2H

I+1

(n − 1,k+1)− H

I+1

(n, k)+H

I+1

(n − 1,k)

= H

(n, k +1)−H

(n − 1,k+1)− H

(n, k),

and for k = I +1,I ≥ 1,

I+1

(n, I +2)−2H

I+1

(n − 1,I+2)

= H

(n, I +2)− H

(n − 1,I+2)− H

(n − 1,I+1).

Let H

I,k

(x)=



n≥0

(n, k)x

with initial conditions H

(0,k) = 1 for all

I,k such that k ≥ I + 1. Then the above recurrence relations for k ≥ I +1

and I ≥ 1 become

(1 − 2x)H

I+1,k+1

(x) − (1 − x)H

I+1,k

(x)=(1−x)H

I,k+1

(x) − H

I,k

(x),

and

(1 − 2x)H

I+1,I+2

(x)=(1− x)H

I,I+2

(x) − xH

I,I+1

(x). (6.11)

Now deﬁne H

(x, y)=



k≥I+1

I,k

(x)y

, a generating function that keeps

track of the alphabet, and let u

(x)=H

I,I+1

(x). Since

(0; 1, 1,...,1) = F

(k, 1) = H

k−1

(n, k),

(x) is the function we really want, as it is the generating function for the

number of words on the alphabet [I + 1] that avoid the pattern 123 and that

have no restrictions with respect to the auxiliary patterns. So our goal is to

ﬁnd an explicit expression for u

(x)=AW

[I+1]

123

(x). In terms of u

(x), (6.11)

becomes

I,I+2

(x) = ((1 − 2x)u

I+1

− xu

)/(1 − x). (6.12)

From the recurrence for H

I,k

(x) together with (6.12) we obtain a recurrence

relation for H

(x, y)forI ≥ 1 (see Exercise 6.4):

((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

(6.13)

216 Combinatorics of Compositions and Words

Iterating this recurrence relation, we obtain that

(x, y)=H

(x, y)



1 − x − y

1 − 2x − (1 − x)y



I−1



j=1

(1 − x − y)

I−1−j

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

I−j

(1 − x)u

(x)(y − 1)y

j+1

To solve this recurrence relation, we need to ﬁnd H

(x, y). Note that H

(n, k)

= F

(k, k−1) is the number of words of length n that avoid 123 and where the

only occurrences of the pattern 12 are those containing the letter k.Wecan

obtain all such words by taking a nonincreasing (possibly empty) sequence of

letters from the alphabet [k − 1] of length m ≤ n and adding n − m letters k

with no restriction on position to obtain a word of length n. Therefore,

(n, k)=



m=0





m + k − 2



, (6.14)

and consequently (see Exercise 6.3) H

(x, y)=

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

. Hence,

(x, y)

(1 − x − y)

I−1

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

I−1



j=1

(1 − x − y)

I−1−j

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

I−j

(1 − x)(y − 1)y

j+1

(x, y).

(6.15)

Since u

(x)=[y

I+1

(x, y), we can turn (6.15) into a recurrence for u

(x).

To do so, we note that (see Exercise 2.23)

,m

(x)=[y



]



(1 − x − y)

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

m+1



(1 − x)

−m

(1 − 2x)

+1



i≥0



 + i





(1 − 2x)

. (6.16)

Taking coeﬃcients of y

I+1

on both sides of (6.15) and using (6.16) we obtain

the following recurrence relation for u

(x):

(x)=

(1 − 2x)



i≥0



I − 1+i



I − 1



(1 − 2x)

I−1



j=1

(1 − x)u

(x)

(1 − 2x)

I−j



i≥0



I − j − 1+i



I − j − 1



(1 − 2x)

−

I−1



j=1

(1 − x)

(x)

(1 − 2x)

I+1−j



i≥0



I − j + i



I − j



(1 − 2x)

Words 217

Since u

(x) is the generating function of words avoiding 123 on the alphabet

[2] (all 2

such words do), we obtain that u

(x)=

1−2x

. Using this initial

condition, one can ﬁnd an explicit formula for u

(x)=AW

132

[I+1]

(x), the gen-

erating function for the number of words on the alphabet [I +1]oflengthn

that avoid the pattern 123. 2

6.5.2 Block decomp osition for words

The block decomposition method was ﬁrst used by Mansour and Vainshtein

[147] to study the structure of 132-avoiding permutations and permutations

containing a given number of occurrences of 132 [149]. Mansour [141] extended

the use of the block decomposition approach for the set of permutations,

described in [148], to the set of words. We will describe this approach and use

it to provide a diﬀerent and simpler proof of Theorem 6.25. In addition, the

block decomposition method reveals more of the structure of the 132-avoiding

words and can also be used to derive generating functions for words that avoid

a set of patterns {132,τ} for families of patterns. To describe this approach,

we need some deﬁnitions.

Deﬁnition 6.26 Let w = w

···w

∈AW

[k]

(132) be a k-ary word of

length n that avoids the subsequence pattern 132. Then we can decompose

w as w = w

(1)

(2)

(3)

k ···kw

(s+1)

, where each of the w

(i)

is a possibly

empty word on the alphabet [k − 1],ands denotes the number of occurrences

of k in w. This representation of w is called the block decomposition of w.

Example 6.27 Let w = 34345523525121 ∈AW

[5]

(132), then the block de-

composition is given by w

(1)

= 3434, w

(2)

= ∅, w

(3)

=23, w

(4)

=2,and

(5)

= 121, and there are a total of s =4occurrences of 5 in w.Figure

6.3 shows the block decomposition for this particular word. The striped area

indicates values that cannot be taken in a word that avoids 132. Note that the

maximal value of w

j+1

)

determines the minimal value of w

)

and vice versa

for j =1, 2,...s.

FIGURE 6.3: The block decomposition of w = 34345523525121.

218 Combinatorics of Compositions and Words

Lemma 6.28, which follows immediately from Deﬁnition 6.26, is the basis

for all the enumeration results in [141].

Lemma 6.28 Let w = w

(1)

(2)

(3)

k ···kw

(s+1)

∈AW

[k]

(132) be the

block decomposition of w. Then one of the following assertions holds:

1. s =0, that is, w ∈AW

[k−1]

(132).

2. s ≥ 1; then there exist t

with 1 ≤ t

< ···<t

≤ s +1 such that

(a) w

)

= ∅ for j =1, 2,...,d;

(b) w

(j)

= ∅ for j ∈ [s +1]\{t

,...,t

};

)

is a word on the letters

+1,q

+2,...,q

j−1

that avoids 132 and in which the letter q

occurs at least once, where

k − 1=q

≥ q

≥···≥q

=1.

Note that the values q

mentioned in Lemma 6.28 refer either to the maximal

value of the word w

j+1

)

or the minimal value of w

)

for j =1, 2,...,d−1.

Neither q

nor q

have to be attained.

Example 6.29 (Continuation of Example 6.27) For w = 34345523525121 in

[5]

(132), the second case applies, with t

=1, t

=3, t

=4,andt

=5.

The values of q

are determined as follows: q

=4, q

=3(the maximal value

of w

(3)

), q

=2(the maximal value of w

(4)

), q

=2(the maximal value of

(5)

),andq

=1.

When proving Theorem 6.25 using the block decomposition method we will

rely on the following lemma which gives results for two generating functions

closely related to AW

132

(x, y).

Lemma 6.30 Let H(x; k)=AW

132

[k+1]

(x) − 1 be the generating function for

the number of (k +1)-ary nonempty words of length n that avoid 132,and

let M(x; k)=AW

132

[k+1]

(x) −AW

132

[k]

(x) denote the generating function for the

number of (k +1)-ary words of length n that avoid 132 and in which the

letter k +1 occurs at least once. Then for H(x, y)=



k≥0

H(x; k)y

and

M(x, y)=



k≥0

M(x; k)y

we have that

H(x, y)=

y(1 − y)

((1 − y)AW

132

(x, y) − 1)

and

M(x, y)=

((1 − y)AW

132

(x, y) − 1) .

Words 219

Proof See Exercise 6.5. 2

We are now ready to present the alternative derivation for the generating

function AW

132

(x, y) as given in [141].

Proof (of Theorem 6.25 using block decomposition method) By Lemma

6.28, there are exactly two possibilities for the block decomposition of an

arbitrary w ∈AW

[k]

(132). The contribution to AW

132

[k]

(x) for the case s =0

is AW

132

[k−1]

(x). Next we consider the case s ≥ 1and0≤ d ≤ s +1. If

d = 0, then the contribution to AW

132

[k]

(x)equalsx

since w = k ···k.For

1 ≤ d ≤ s +1,w

)

takes values in q

,...,q

j−1

,whereq

is deﬁned to be the

maximal value of w

j+1

)

for j =1,...,d− 1. Thus for counting purposes,

we can consider w

)

to be a word from the alphabet [q

j−1

− q

+1]. Note

that for w

)

the maximal value does not have to be taken, but for the other

subwords, the maximal value is achieved by deﬁnition of the q

. Deﬁning

= q

j−1

− q

, the contribution to AW

132

[k]

(x) for a given set of values t

given by



+···+a

=k−2

H(x; a

)



j=2

M(x; a

Taking into consideration that the t

can be selected in



s+1



ways, we obtain

that the contribution to AW

132

[k]

(x) for the case s ≥ 1isgivenby



s≥1

⎛

⎝

s+1



d=1



s +1





+···+a

=k−2

H(x; a

)



j=2

M(x; a

)

⎞

⎠

Adding the contributions from the two cases, multiplying by y

, summing

over all k ≥ 1, and accounting for the empty word yields

132

(x, y)=1+yAW

132

(x, y)



s≥1



1 − y

s+1



d=1



s +1



(M(x, y))

d−1

H(x, y)



=1+yAW

132

(x, y)+

(1 − y)(1 − x)



s≥1

H(x, y)

M(x, y)



(1 + M(x, y))

s+1

− 1



=1+yAW

132

(x, y)+

1 − x

x(1 −y)(AW

132

(x, y) − 1)

1 −

x(1−y)

(AW

132

(x, y) − 1)

where the last equality follows from Lemma 6.30. Letting AW = AW

132

(x, y),

this equation can be reduced to

x(1 −x)(1 − y)AW

+(1− y)(2x

− 2x −y)AW + x(1 − x)(1 − y)+y =0,

220 Combinatorics of Compositions and Words

from which we obtain the explicit formula, and if desired, a continued fraction

expansion for AW

132

(x, y) (see Example 2.62). 2

Note that the strength of the block decomposition method lies in the fact

that all the nonempty words w

(j)

have the same structure. This is in part

a result of the avoidance of the pattern 132. We already have encountered

block decomposition (without calling it that) for compositions in the proof of

Theorem 5.18, where it was used to derive a bijection to show Wilf-equivalence

of the patterns 12–3 and 21–3. In general, the block decomposition method

is more diﬃcult to use for compositions than it is for words. The main reason

is that for compositions we need to keep track of the order of the composition

and therefore there is a dependence between the blocks.

The derivation of AW

132

(x, y) can be easily modiﬁed to yield results for

{132,τ}

(x, y) as the core of the argument consists of the block decompo-

sition in conjunction with Lemma 6.30, which carries over to a more general

generating function AW

{132,τ}

(x, y).

Theorem 6.31 Let  ≥ 3 and let AW



(x, y)=AW

{132,12···}

(x, y).Thenwe

have the recurrence



(x, y)=1+

(1 − x)(1 −y)+

xy(1 − x)(1 − y)

x(1 − y)+

1 − AW

−1

(x, y)

with AW

(x, y)=

1−x

1−x−y

.Thus,AW



(x, y)−1 can be expressed as a continued

fraction with  levels

(1 − x)(1 − y) −

xy(1 − x)(1 − y)

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

xy(1 −x)(1 − y)

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

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

or in terms of Chebyshev polynomials of the second kind, as



(x, y)=1+

(1 − x)(1 − y)

αU

−2

(t)+βU

−3

(t)

αU

−3

(t)+βU

−4

(t)

where α =(1− 2x − y), β =

(1−x−y)

√

(1−x)(1−y)

,andt = −

1−2x

;

1−y

xy(1−x)

Proof Let H



(x; k)=AW

{132,12···}

[k+1]

(x) − 1, H



(x, y)=



k≥0



(x; k)y



(x; k)=AW

{132,1···}

[k+1]

(x) − AW

{132,1···}

[k]

(x), and ﬁnally,



(x, y)=



k≥0



(x; k)y

Words 221

The cases s =0ands ≥ 1withd = 0 follow as in the block decomposition

proof of Theorem 6.25. For s ≥ 1and0≤ d ≤ s + 1, we now have to consider

two cases, namely whether the block w

(s+1)

is empty or nonempty. Note that

this time we deﬁne q

to be the minimal value in w

)

for j =1, 2,...,d−1,

which all have to occur. Note that if w

(s+1)

is nonempty then the pattern

12 ··· has to be avoided, while in all other blocks, the pattern 12 ···( − 1)

has to be avoided. Therefore,

• if t

= s + 1, then the contribution for 1 ≤ d ≤ s is given by



+···+a

=k−2

−1

(x; a

)

d−1



j=1

−1

(x; a

• if t

= s + 1, then the contribution for 1 ≤ d ≤ s is given by



+···+a

=k−2



(x; a

)

d−1



j=1

−1

(x; a

Being careful about the number of ways the t

canbechosenandthenfol-

lowing the steps in the block decomposition proof of Theorem 6.25 gives the

recurrence



(x, y)=1+

(1 − x)(1 −y)+

xy(1 − x)(1 − y)

x(1 − y)+

1 − AW

−1

(x, y)

(6.17)

(see Exercise 6.6). To obtain an explicit formula we derive AW

(x, y). This is

the generating function for the number of words that simultaneously avoid

the subsequence patterns 132 and 12. However, since any occurrence of

132 automatically results in an occurrence of 12, we have that AW

(x, y)=

(x, y). From Theorem 5.5 we obtain that

(x, y)=



k≥0

[k]

(1,x)y



k≥0



j=1



1 − x





k≥0



1 − x



This gives the result for AW

(x, y) and the ﬁnite continued fraction. For the

expression involving the Chebyshev polynomials of the second kind, we write

the recurrence relation as



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

xy(1 − x)(1 − y)

x(1 −y) − f

−1

where f



(x, y)=y/(AW



(x, y) − 1). Using induction together with (C.2) as

in the proof of Proposition C.8 we obtain that



(x, y)=

(1 − x)(1 −y)

αU

−3

(t)+βU

−4

(t)

αU

−2

(t)+βU

−3

(t)

, (6.18)

222 Combinatorics of Compositions and Words

where

α =1− 2x − y, β =

xy(1 − x − y)

xy(1 − x)(1 − y)

, and t = −

1 − 2x

1 − y

xy(1 − x)

Substituting f





(x,y)−1

in (6.18) and solving for AW



(x, y)givesthe

desired expression for AW



(x, y) in terms of Chebyshev polynomials of the

second kind. 2

For additional examples of pattern avoidance in k-ary words of pairs of

patterns of the form {132,τ} for several interesting cases of τ see [141]. In

addition, the block decomposition approach as deﬁned in Lemma 6.28 can be

extended to describe the structure of k-ary words of length n that contain the

pattern 132 exactly once. For more details see [65].

We now turn our attention to the third approach, the scanning-element

algorithm. Again we will describe the approach and then use it to provide an

alternative proof for Theorem 6.25, followed by examples that showcase the

strength of the method. In fact we will present the proof for the pattern 123,

which is Wilf-equivalent to 132 but which is hard to deal with via the block

decomposition method.

6.5.3 Scanning-element algorithm

The scanning-element algorithm was ﬁrst used for pattern avoidance and

enumeration in permutations by Firro and Mansour [64], and then extended

to study the number of k-ary words of length n that satisfy a certain set of

conditions [65]. Not only does the approach work equally well for avoidance of

the patterns 123 and 132, it can also be used more easily for the enumeration

of patterns, especially for the pattern 123. To describe the algorithm we need

the following deﬁnition.

Deﬁnition 6.32 For n, k ≥ 0,letP (n, k) ⊆ [k]

,andletp(n, k) denote the

number of elements in P (n, k).Forb

,...,b

∈ [k],let

P (n, k; b

,...,b

)={w

···w

∈ P (n, k) | w

···w

= b

···b

}

denote the set of elements in P (n, k) that start with b

···b

,andlet

p(n, k; b

,...,b

)

denote the number of elements in P (n, k; b

,...,b

).WewilluseP (n, k) and

P (n, k; ∅) interchangeably, and likewise, p(n, k) and p(n, k; ∅).

The main goal of this section is to describe how to derive a recursive struc-

ture for the family {P (n, k)}

n,k≥0

. From Deﬁnition 6.32 we obtain immedi-

ately that

p(n, k; b

,...,b



j=1

p(n, k; b

,...,b

,j), (6.19)

Words 223

andinparticularthatp(n, k)=p(n, k;1)+···+ p(n, k; k). This suggests a

way to create a recursion for the sequence {p(n, k)}

n,k

Deﬁnition 6.33 Let 1 ≤ s ≤ m, 1 ≤ r ≤ k and c

,...,c

m−s

∈ [k].Ifthere

exists a bijection between the sets

P (n, k; b

,...,b

) and P (n − s, k − r; c

,...,c

m−s

then the set P (n − s, k − r; c

,...,c

m−s

) is said to be a reduction of the

set P (n, k; b

,...,b

). In this case we say that the set P (n, k; b

,...,b

) is

reducible (otherwise it is irreducible).Anelementb is said to be an (m +1)-

inactive element ((m + 1)-active element) of the set P (n, k; b

,...,b

) if the

set P (n, k; b

,...,b

,b) is reducible (irreducible).

Example 6.34 If P (n, k)=AW

1234

[k]

(n), then for 1 ≤ j

≤ k,

the set P (n − 1,j

; j

) is a reduction of the set P (n, k; j

), that is,

is an inactive 3-element of P (n, k; j

) in this case. Why? Because

for any word of the form w = j

···w

which avoids 1234,weknow

that j

has to be the maximal element in w. Thus, we can uniquely map w to

the word w



= j

···w

∈ [j

]

n−1

which also avoids 1234.Thisprocessis

reversible, therefore we have found the desired bijection.

In order to set up the system of recurrence relations, we need to deﬁne some

notation.

Deﬁnition 6.35 Let I(n, k; b

,...,b

) denote the set of (m +1)-active ele-

ments of P (n, k; b

,...,b

),and

I(n, k; b

,...,b

)=[k] − I(n, k; b

,...,b

)

the set of (m +1)-inactive elements of P(n, k; b

,...,b

). In addition, let

R(n, k; b

,...,b

) be the multi-set

⎧

⎨

⎩

(d, r, c

,...,c

m−d

)

(

P (n − d, k − r; c

,...,c

m−d

) is a reduction

of the set P (n, k; b

,...,b

,j), 1 ≤ d ≤ m,

1 ≤ r ≤ k, j ∈

I(n, k; b

,...,b

)

⎫

⎬

⎭

Note the fact that R(n, k; b

,...,b

) is a multi-set because reductions of

diﬀerent sets may lead to the same reduced set, creating multiple entries in

R(n, k; b

,...,b

We start with an overview of the algorithm before describing the step-by-

step procedure. The ﬁrst step is to determine the set of 1-inactive and 1-active

elements of P (n, k), that is,

I(n, k)andI(n, k), respectively. Using (6.19) and

Deﬁnition 6.35 we have

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

= |

I(n, k)|·p(n − 1,k)+



j∈I(n,k)

p(n, k; j) (6.20)

224 Combinatorics of Compositions and Words

for all n ≥ 1. The ﬁrst term accounts for the 1-inactive elements j,whichare

those that cannot be part of the pattern τ at the beginning of the word w.

These values of j can be split oﬀ, resulting in a word of length n − 1 without

restriction on the alphabet for the remaining letters, and therefore we obtain

a reduction to the set P (n − 1,k).

Equation 6.20 yields a recurrence relation for the sequence {p(n, k)}

n,k≥0

in terms of the sequences {p(n, k; j)}

n,k,j

. We now apply the same idea to the

sequence p(n, k; b

), and more generally, to p(n, k; b

,...,b

). To make the

resulting set of equations more readable, we adopt the following notation.

Deﬁnition 6.36 For any vector v

=(v

,...,v

) and scalars i

,...,i



(v

,...,i



)=(v

,...,v

,...,i



and likewise

,...,i



,v

)=(i

,...,i



,...,v

)

for s,  ≥ 1.

Now we are ready to proceed. Given a set P (n, k;



), we ﬁrst decide if it

is reducible or irreducible. If it is irreducible, then we determine the (m +1)-

inactive (active) elements of P (n, k;



). Using (6.19) again, we have for all

m ≥ 0that

p(n, k;



)



j∈I(n,k;



)

p(n, k;



,j)+



j∈I(n,k;



)

p(n, k;



,j) (6.21)



(d,r,c

(m−d)

)∈R(n,k;



)

p(n − d, k −r;c

(m−d)



j∈I(n,k;



)

p(n, k;



,j).

Equation (6.21) suggests an algorithm for deriving ﬁnite or inﬁnite systems

of recurrence relations in terms of p(n −d, k − r;



)withm, d, r ≥ 0. Let

q(n, k;



(d,r,c

(m−d)

)∈R(n,k;



)

p(n − d, k − r;c

(m−d)

Then,

⎧

⎪

⎨

⎪

⎩

0:p(n, k)=|

I(n, k)|·p(n − 1,k)+



∈I(n,k)

p(n, k; j

)

1:p(n, k; j

)=q(n, k; j



∈I(n,k;j

)

p(n, k;



)

2:p(n, k;



)=q(n, k;





∈I(n,k;



)

p(n, k;



)

(6.22)