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

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

Avoidance of Nonsubword Patterns in Compositions 145

i<jand σ

<σ

i−1

, that is, an active descent is the “1” in an occurrence

of the pattern 31–2 of width j −i. An active descent can belong to more than

one occurrence of 31–2, and σ ∈AC

n,m

(31–2) cannot have an active descent.

For each occurrence of a pattern 31–2 we deﬁne the associated descent block

to be the maximal substring σ

i+1

···σ

such that σ



<σ

for  = i,...,k.

Figure 5.2 shows the structure of a descent block.

i−1

i i+1 k k+1 j

≥ 2

index

-. /

descent block

FIGURE 5.2: Structure of descent block.

Both the ascent and the descent block consist of parts that can play the

role of the “1” in the pattern. For a ﬁxed ascent/descent block, the innermost

pattern is the associated pattern of smallest width, while the outermost pattern

is the associated one of largest width.

We can now describe the map ρ:AC

n,m

(13–2) →AC

n,m

(31–2). Let σ ∈

n,m

(13–2) have r occurrences of the pattern 31–2. Let σ

(0)

= σ and σ

(j)

be the composition that results after j steps of the algorithm. Basically,

each step transforms one of the active descents and removes at least one of

its associated occurrences of the pattern 31–2, so that after at most r steps

we obtain a composition ρ(σ) ∈AC

n,m

(31–2). Note that if r =0,then

σ ∈AC

n,m

(31–2) and ρ(σ)=σ

(0)

= σ. Now assume that r>0. Then σ

(j)

is obtained from σ

(j−1)

as follows: Let σ

be the leftmost active descent in

(j−1)

and for i =1,...,m,letσ

denote the i-th part in σ

(j−1)

.Forthe

active descent σ

identify the associated innermost 31–2 pattern. Assume

that it occurs at σ

−1

j∗

. Since it has the smallest width, the descent

block consists of σ

···σ

j∗−1

. Furthermore, since σ avoids 13–2 we have that



≤ σ

j∗−1

≤ σ

or σ



≥ σ

j∗

for >j∗.

Next we cut out the descent block and move it to the left of σ

, inserting it

immediately after the rightmost part σ

i∗

with σ

i∗

≤ σ

j∗

, or at the beginning

of σ

(j−1)

if such a σ

i∗

does not exist. This insertion may create a descent if

i∗

>σ

, but the newly created descent cannot be active due to the deﬁnition

of i∗ and the consequences of the 13–2 avoidance. We have therefore reduced

the number of 31–2 patterns by at least one. Let the resulting composition

be σ

(j)

146 Combinatorics of Compositions and Words

Note that the movement of the descent block of the innermost pattern

modiﬁes other occurrences of 31–2 patterns associated with the active descent.

Sometimes several patterns are removed at once. If not, then the part that

previously played the role of the “2” for one of the associated patterns is

now playing the role of the “1”, and thus may become a new active descent.

However, it occurs to the right of the previous active descent, and the set

of values which can play the role of “2” for this potential active descent has

shrunk. Therefore, after a ﬁnite number of applications of the algorithm, all

occurrences of 31–2 have been removed from σ, and the resulting composition

ρ(σ)isinAC

n,m

(31–2). In addition, ρ(σ) has at least one active ascent

(created from the active descent in the last step). The resulting composition

ρ(σ) is unique, and if σ =˜σ,thenρ(σ) = ρ(˜σ). This gives |AC

n,m

(13–2)|≥

|AC

n,m

(31–2)|.

To compute the image ρ



(σ)ofσ ∈AC

n,m

(31–2), modify the algorithm

for ρ accordingly: in the j-th step identify the rightmost active ascent and

its associated outermost 13–2 pattern. Assume that this 13–2 pattern occurs

at σ

j∗

. Insert its ascent block immediately before σ

j∗

. Again, the

resulting composition ρ



(σ) is unique, and if σ =˜σ,thenρ



(σ) = ρ



(˜σ). This

gives |AC

n,m

(31–2)|≥|AC

n,m

(13–2)| and therefore the two sets have the same

number of compositions. 2

We give a few examples to illustrate the two algorithms. Note that in

each case, ρ



(ρ(σ)) = σ, even though the intermediate compositions are not

necessarily the same. In addition, the number of patterns associated with

active descents/ascents do not have to be the same in the composition and its

image, and not even the number of active ascents and descents have to be the

same. We will underline the active descent and ascent blocks and will show

in bold font the σ

that corresponds to the “2” of the pattern.

Example 5.20 Let σ = 59424511241 ∈AC

[9]

38,11

(13–2). Note that σ has two

active descents with associated 31–2 patterns 945, 512,and514.Itistrans-

formed as follows:

59424

511241 → 54249511241 → 54211495241 → 54211429541

corresponding to the movements of descent blocks (424) inserted after 5, (11)

inserted after 2,and(2) inserted after 4. On the other hand, starting with



= 54211429541 ∈AC

[9]

38,11

(31–2) (having two active ascents with associated

13–2 patterns 142, 295,and294) we obtain

5421142

9541 → 54211495241 → 594211452 41 → 59424511241

corresponding to the movements of ascent blocks (2) inserted before 4, (42114)

inserted before 5,and(11) inserted before 2.

Avoidance of Nonsubword Patterns in Compositions 147

As a second example, we consider σ = 9445421126718 ∈AC

[9]

54,13

(13–2)

with one active descent and associated 31–2 patterns 945, 946, 947, 948.This

composition is transformed as follows:

944

5421126718 → 4495421126718 → 4454211296718

→ 445421126971

8 → 4454211267198

corresponding to movement of the blocks (44) inserted before 9, (542112) in-

serted after 4, (6) inserted after 2,and(71) inserted after 6.Theresulting

composition 4454211267198 ∈AC

[9]

54,13

(31–2) has one active ascent, but only

a single associated 13–2 pattern, namely 198. The reverse map therefore has

only one intermediate step, where the block (44542112671) is inserted before

the 8:

44542112671

98 → 9445421126718.

Finally, we give an example where the image has fewer active ascents. Let

σ = 6244582418191 ∈AC

[9]

55,13

(13–2), which has two active descents with asso-

ciated 31–2 patterns 624, 624, 625,and824. The image is created as follows:

44582418191 → 2644582418191 → 2446582418191 → 2442658418191

corresponding to the movements of descent blocks (2) inserted before 6, (44)

inserted after 2,and(2) inserted after 4. The resulting composition has only

one active ascent with two associated 13–2 patterns 265 and 264. The reverse

map is given by

2442

658418191 → 2446582418191 → 6244582418191

corresponding to the movements of ascent blocks (2) inserted before 4 and

(244) inserted before 5.

So all together we have that 12–3 ∼ 21–3, 23–1 ∼ 32–1 and 13–2 ∼ 31–2.

In fact, these are all the Wilf classes for patterns of type (2, 1) because the

sequences for the number of compositions of n that avoid the respective pat-

terns are diﬀerent for n = 8 (see Examples 5.22, 5.24 and 5.26). Note that

this situation is quite diﬀerent from that for subsequence patterns, where all

permutation patterns of length 3 are Wilf-equivalent. We now derive the

corresponding generating functions for A =[d] for the three Wilf classes.

Theorem 5.21 The generating function for the number of compositions of n

with m parts in [d] that avoid 12–3 is given by

12–3

[d]

(x, y)=



i=1



1 −



i−1

j=1

(1 − x



−1

148 Combinatorics of Compositions and Words

Proof Separating how the composition begins we obtain

12–3

[d]

(i|x, y)

= x

y +



j=1

12–3

[d]

(ij|x, y)+



j=i+1

12–3

[d]

(ij|x, y)

= x

y + x

⎛

⎝



j=1

12–3

[d]

(j|x, y)+



j=i+1

yAC

12–3

[j]

(x, y)

⎞

⎠

Note that in the last sum the set of parts for the composition is restricted

from [d]to[j] to guarantee avoidance of 12–3. From this recursion we get

that the generating function G

(i)=AC

12–3

[d]

(i|x, y) −AC

12–3

[d−1]

(i|x, y)satisﬁes

(i)=x



j=1

(j)+x

y · x

yAC

12–3

[d]

(x, y).

Solving for G

(i)leadsto

(i)=

1 − x

⎛

⎝

i−1



j=1

(j)+x

yAC

12–3

[d]

(x, y)

⎞

⎠

. (5.4)

We can prove by induction on i that

(i)=

i+d

12–3

[d]

(x, y)



j=1

(1 − x

for all i =1, 2,...,d− 1. The induction step uses that

d−1



i=1



j=1

(1 − x



d−1

j=1

(1 − x

, (5.5)

which is also readily proved by induction. Also, for i = d, we obtain from the

deﬁnition that

(d)=AC

12–3

[d]

(d|x, y) − AC

12–3

[d−1]

(d|x, y)

= x

yAC

12–3

[d]

(x, y) − 0=x

yAC

12–3

[d]

(x, y).

Therefore, summing over i =1, 2,...,d we obtain

12–3

[d]

(x, y) − AC

12–3

[d−1]

(x, y)=x



d−1



i=1



j=1

(1 − x



12–3

[d]

(x, y),

Avoidance of Nonsubword Patterns in Compositions 149

which by (5.5) is equivalent to

12–3

[d]

(x, y) − AC

12–3

[d−1]

(x, y)=



d−1

j=1

(1 − x

12–3

[d]

(x, y).

Hence, for all d ≥ 1wehave

12–3

[d]

(x, y)=



1 −



d−1

j=1

(1 − x



−1

12–3

[d−1]

(x, y).

Iterating the above recurrence relation d times together with the initial con-

dition AC

12–3

∅

(x, y) = 1 we get the desired result. 2

Example 5.22 By taking the limit as d →∞in Theorem 5.21 we obtain

the generating function for the number of compositions of n that avoid the

generalized pattern 12–3 as

12–3

(x, 1) =



i≥1



1 −



i−1

j=1

(1 − x

)



−1

We evaluate this expression for d =20in Mathematica or Maple and obtain

the sequence of values for n =0to n =20as 1, 1, 2, 4, 8, 16, 31, 60, 114, 215,

402, 746, 1375, 2520, 4593, 8329, 15036, 27027, 48389, 86314 and 153432.

Theorem 5.23 The generating function for the number of compositions of n

with m parts in [d] that avoid 23–1 is given by

23–1

[d]

(x, y)=



i=1



1 −



j=i+1

(1 − x



−1

Proof Let σ be any composition of n with m parts in A =[d]thatavoids

23–1. Then σ either does not contain the part 1, or σ can be decomposed as

(1)

1σ

(2)

1 ···σ

(s)

1σ



where σ

(i)

and σ



have parts in

,eachσ

(i)

avoids 12 (why?) and σ



avoids

23–1. The generating function is given by

xyAC

(x, y)

23–1

(x, y)for

s ≥ 1. All together,

23–1

[d]

(x, y)=AC

23–1

(x, y)+

xyAC

(x, y)

1 − xyAC

(x, y)

23–1

(x, y),

150 Combinatorics of Compositions and Words

which is equivalent to

23–1

[d]

(x, y)=

23–1

(x, y)

1 − xyAC

(x, y)

Using the above recurrence d times we obtain that

23–1

[d]

(x, y)=



i=1

1 − x

yAC

(x, y)

Arguing as in Example 4.17 we obtain that AC

(x, y)=



j=i+1

(1 −x

−1

which completes the proof. 2

Notice the similarity in structure of AC

23–1

[d]

(x, y)andAC

12–3

[d]

(x, y), even

though their derivations are diﬀerent. The explanation for this phenomenon

is that 12–3 ∼ 21–3, and 21–3 and 23–1 are complementary patterns. Having

chosen to derive the generating function for the pattern 23–1 instead of the

pattern 21–3, we needed to use a somewhat diﬀerent method instead of doing a

“proof by replacement.” We intentionally gave the two diﬀerent proofs to make

the point that when deriving the generating function for a Wilf-equivalence

class with more than one pattern, it is very useful to think about which

pattern to use. Exercise 5.3 asks you to provide the simpler proof based on

complementary patterns.

Example 5.24 By taking the limit as d →∞and substituting y =1in Theo-

rem 5.23 we obtain that the generating function for the number of compositions

of n that avoid the generalized pattern 23–1 is given by

23–1

(x, 1) =



i≥1



1 −



j≥i+1

(1 − x

)



The sequence for the number of compositions of n that avoid 23–1 for n =0

to n =20is given by 1, 1, 2, 4, 8, 16, 31, 61, 118, 228, 440, 846, 1623, 3111,

5955, 11385, 21752, 41530, 79250, 151161 and 288224.

Finally, we ﬁnd the generating function for the compositions avoiding 13–2.

Using arguments similar to those in the proofs of Theorems 5.21 and 5.23

we obtain a recursive result for AC

13–2

[d]

(x, y). Finding an explicit expression

remains an open question (see Research Direction 5.1).

Lemma 5.25 The generating function AC

13–2

[d]

(x, y) for the number of com-

positions of n with m parts in [d] that avoid 13–2 satisﬁes

13–2

[d]

(x, y)=1+



i=1

13–2

[d]

(i|x, y),

Avoidance of Nonsubword Patterns in Compositions 151

where

13–2

[d]

(i|x, y)

= x

⎛

⎝

i+1



j=1

13–2

[d]

(j|x, y)+



j=i+2

13–2

{1,...,i,j,...,d}

(j|x, y)

⎞

⎠

Example 5.26 The expression in Lemma 5.25 is diﬃcult to evaluate. Mod-

ifying the Mathematica code of Example 5.14, we may enumerate the number

of compositions of n that avoid 13–2 directly and obtain the sequence for n =0

to n =15as 1, 1, 2, 4, 8, 16, 31, 60, 115, 218, 411, 770, 1434, 2656, 4897

and 8991 (see Exercise 5.1).

5.3.2 Patterns of type (2,1) with repeated letters

In this section we consider the three-letter generalized patterns of type (2, 1)

with repetitions, namely the patterns 11–1, 11–2, 12–1, 12–2, 21–1, 21–2 and

22–1. We start by determining the Wilf-equivalence classes. Since all patterns

in the same equivalence class must have the same letters, 11–1 forms its own

class. We will show that 12–2 ∼ 21–2 by giving an explicit bijection. Using

the complement map (see Deﬁnition 5.8) on this equivalence, we immediately

obtain that 21–1 ∼ 12–1. The remaining two patterns, 11–2 and 22–1, belong

to distinct classes because the sequences for the number of compositions of

n avoiding these two patterns are diﬀerent from each other and from those

for the patterns 12–2 and 21–1 (see Examples 5.42, 5.44 and 5.47). So all

together we have ﬁve diﬀerent Wilf classes.

To show that 12–2 ∼ 21–2, we start by determining the structure of the

compositions that avoid 12–2 and 21–2, respectively. We give a bijection

based on the structures of these compositions. To do so, we need some new

terminology.

Deﬁnition 5.27 For any composition σ ∈C

n,m

, we deﬁne

B(σ)=∪

i=1

{σ

} = {b

,...,b

that is, B(σ) is comprised of the parts of σ. The rightmost occurrence of each

∈ B(σ) in σ is called b

-critical, and the subsequence of critical parts

···σ

= κ

···κ

= κ(σ)

is called the core of σ.LetT

be the set of all compositions that have core

κ and whose values equal B, that is, T

= {σ|κ(σ)=κ, B(σ)=B},andlet

(τ) be the set of all compositions in T

that avoid τ.

Note that B(σ) ⊆ A,andthatκ(σ)isapermutationofB(σ).

152 Combinatorics of Compositions and Words

Example 5.28 For σ = 556632111233652, B(σ)={1, 2, 3, 5, 6}, the critical

parts of σ are σ

=1, σ

=3, σ

=6, σ

=5, σ

=2and κ(σ) = 13652.

Note that σ contains the pattern 12–2 three times (σ

= 566, σ

122,andσ

= 233).

Deﬁnition 5.29 A b

-block of σ is a subword σ

···σ

i+k−1

such that σ

i+1

= ··· = σ

i+k−1

= b

, σ

i−1

= b

,andσ

i+k

is either not equal to b

is b

-critical. A block K = σ

i+1

···σ

i+k−1

is to the left of a block K



···σ



−1

if i + k −1 <i



and we write K  K



. Likewise, K is to

the right of K



if i



+ k



− 1 <iand we write K  K



Example 5.30 The composition σ = 556632111233652 has the following

structure: blocks 55, 66, 3, 2 and 11,criticalpart1, blocks 2 and 3,and

critical parts 3, 6, 5,and2.Also,55  11 and 33  66.

We can visualize any composition in terms of its critical parts and its blocks

using a diagram like the one in Figure 5.3 for σ = 556632111233652, which

we will refer to as a block diagram. Each horizontal line corresponds to a

value of B(σ), ordered from smallest to biggest from bottom to top. On each

horizontal line we record the blocks and the critical parts for the respective b

Blocks are represented by rectangles and critical parts by dots, and they are

placed from left to right in the order in which they occur in the composition.

After the critical part b

has occurred, there can be no further occurrences of

and therefore the horizontal line is terminated. We emphasize the critical

parts by vertical (dotted) lines. We will use this type of diagram speciﬁcally

to visualize the underlying structure of 12–2 and 21–1-avoiding compositions

and to show the bijection between them. We are now ready to describe the

structure of any 12–2-avoiding compositions.

66 6

55 5

FIGURE 5.3: Block diagram for σ = 556632111233652.

Lemma 5.31 Let B = {b

,...,b

} be an ordered set and let κ be a permu-

tation of B.Ifσ ∈AT

(12–2), then for j =1,...,s, there is at most one

-block to the left of κ

, and also between any two consecutive critical parts.

Avoidance of Nonsubword Patterns in Compositions 153

Furthermore, the blocks occurring to the left of κ

or between consecutive crit-

ical parts, respectively, are in decreasing order, that is, if K is a b-block and



is a b



-block with b<b



,thenK  K



Proof We prove the statement by contradiction. Assume that there exist

two b

-blocks, K = σ

i+1

···σ

i+k−1

and K



= σ



···σ



−1

with K 



between two consecutive critical parts. If σ

i+k−1

<σ

i+k

, then there is

an occurrence of 12–2 at σ

i+k−1

i+k

i∗

,whereσ

i∗

is σ

i+k

-critical. (σ

i∗

exists

since σ

i+k

is not critical by assumption). If, on the other hand, σ

i+k−1

>σ

i+k

then there exists a minimal p with i + p ≤ i



(since σ



= b

) such that

i+k−1

>σ

i+k

≥··· ≥σ

i+p−1

<σ

i+p

.Thenσ

i+p−1

i+p

i∗

is an occurrence

of the pattern 12–2, where σ

i∗

is σ

i+p

-critical. This shows that there cannot

be two b

-blocks between consecutive critical parts.

What remains to be shown is that the blocks are in decreasing order. Let K

be a b-block and K



be a b



-block that occur between two consecutive critical

parts, with b<b



.IfK  K



,andσ

i+k

>b,thenσ

i+k−1

i+k

i∗

is an

occurrence of 12–2, where σ

i∗

is σ

i+k

-critical. If σ

i+k

<b, then there exists a

minimal p with i + p ≤ i



(because σ



= b



>b) such that σ

i+k−1

>σ

i+k

≥

··· ≥σ

i+p−1

<σ

i+p

and we get once more an occurrence of 12–2, where σ

i∗

is σ

i+p

-critical, a contradiction.

This proof uses only the fact that there are no critical parts between the

two blocks K and K



, therefore the argument also applies when the two blocks

are to the left of κ

. 2

Next we determine which blocks can actually occur for a given core κ.

Lemma 5.32 Let B = {b

,...,b

} be an ordered set and κ be a permutation

of B.Letσ ∈AT

(12–2) and let σ

= κ

,σ

= κ

i+1

, i =1,...,s− 1 be two

consecutive critical parts in σ.IfK is a b-block in σ

u+1

u+2

···σ

v−1

,then

b = κ

for all j =1, 2,...,iand b<κ

.IfK is a b-block in σ

···σ

u−1

,where

= κ

, then there are no restrictions on b.

Proof The deﬁnition of a critical part immediately gives that b = κ

,for

j =1, 2,...,i. The proof that b<κ

follows as in the proof of the second

part of Lemma 5.31, where the assumption that σ

i+k−1

<σ

i+k

leads to an

occurrence of 12–2, and therefore to a contradiction. If K  κ

, then no values

are excluded for reason of critical values occurring to the left of K (there are

none). By Lemma 5.31, all blocks occur in decreasing order, so they do not

create an occurrence of 12, and hence 12–2 does not occur. 2

Example 5.33 (Continuation of Example 5.28) We saw in Example 5.28 that

σ = 556632111233652 has three occurrences of 12–2. The ﬁrst and third

occurrences stem from the fact that the blocks to the left of κ

and those

154 Combinatorics of Compositions and Words

between κ

and κ

are not in decreasing order. The second pattern occurs

since there is a b-block with b ≥ κ

between κ

and κ

From Lemmas 5.31 and 5.32, we can derive the general structure for any

12–2 avoiding composition. Figure 5.4 shows the structure diagram for the

core 4512. In this diagram, an oval indicates the positions where a block is

allowed (but it may be empty), while an X indicates a position where such a

block cannot occur. We refer to the oval positions as allowable blocks and the

X positions as forbidden blocks.

FIGURE 5.4: Structure diagram for σ ∈AT

4512

(12–2).

Nowwecandeterminethenumberofb

-blocks that occur in a composition

σ ∈AT

(12–2).

Lemma 5.34 Let B = {b

,...,b

} be an ordered set and let κ be a permu-

tation of B.Forσ ∈AT

(12–2), the number of κ

-blocks in σ is at most

|{i|κ

<κ

and i<j}| +1.

Proof This follows immediately from Lemmas 5.31 and 5.32 and can be

visualized using Figure 5.4: a κ

-block can occur at most once between two

consecutive critical parts κ

and κ

i+1

only if i<jand κ

<κ

. In addition,

any b

-block can occur at most once to the left of κ

. 2

Lemma 5.34 will be the key to determining the generating function for the

number of 12–2-avoiding compositions. We now look at the structure of the

21–2-avoiding compositions. Since the behavior of blocks on the left of κ

is the same as that between two consecutive critical parts, we refer to the

section on the left of κ

as the section between κ

and κ

. This allows us to

give uniﬁed statements and simplify proofs. Using arguments similar to those

in the proofs of Lemmas 5.31, 5.32 and 5.34, we obtain the following results.

Lemma 5.35 Let B = {b

,...,b

} be an ordered set and let κ be a permu-

tation of B.Ifσ ∈AT

(21–2), then for j =1,...,s, there is at most one

-block between any two consecutive critical parts. Furthermore, the blocks