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

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

124 Combinatorics of Compositions and Words

4.5 Research directions and open problems

We now suggest several research directions which are motivated both by

the results and exercises of this chapter. In later chapters we will revisit some

of these research directions and pose additional questions.

Research Direction 4.1 Lemma 4.25 gives that for a ﬁnite ordered set A =

,...,a

}, b

= x

y,andC

= C

peak

(x, y, q),

1 − b

−

(1 − q),b

d−1

(1 − q),...,b

(1 − q),b

]

By taking the limit d →∞wecanobtainacontinuedfractionalsoforthe

case when |A| = ∞, that is, A is a countably inﬁnite set A = {a

,...} :

= lim

d→∞

1 − b

−

(1 − q),b

d−1

(1 − q),...,b

(1 − q),b

]

Can this continued fraction expression (or any other approach) be used to

obtain a closed formula for the generating function C

peak

(x, y, q) when A is

countably inﬁnite?

Research Direction 4.2 We have completely classiﬁed the equivalence class-

es with respect to avoidance of 3-letter subword patterns (see Table 4.3).A

natural extension is to ﬁnd the equivalence classes for tight Wilf-equivalence

for larger values of n.

(1) Classiﬁcation of 4-letter patterns according to tight Wilf-equivalence:

Table 4.4 contains the values of the sequences {AC

(τ)}

n=0

(obtained

via an appropriate modiﬁcation of the program given in Appendix G)

for the 4-letter patterns τ up to the symmetry class of reversal which

suggests that the nontrivial tight Wilf-equivalence classes are given by

1322

∼ 1232, 2123

∼ 2213, 1342

∼ 1432, 3124

∼ 3214.

Prove that these are indeed the nontrivial Wilf-equivalence classes.

(Hint: To prove that τ

∼ ν, replace each occurrence of τ by an oc-

currence of ν).

(2) Use the steps of Part (1) (namely creating a table of sequence values

to obtain a conjecture about nontrivial classes and then to prove the

equivalence) to classify the subword patterns of lengths ﬁve and six ac-

cording to tight Wilf-equivalence.

Statistics on Compositions 125

(3) Let t

be the number of equivalence classes for k-letter patterns according

to tight Wilf-equivalence. Clearly, t

=1and t

=2. Table 4.3 shows

that t

=8,andPart(1) gives that t

=35.Part(2) gives two more

values, t

and t

. A very hard question is to ﬁnd properties of t

general.

Research Direction 4.3 Table 4.3 gives a complete list of (the theorems for)

the explicit formulas of the generating functions for the number of composi-

tions of n with m parts that avoid a given 3-letter subword pattern. A natural

extension in light of Research Direction 4.2 is to ask for a similar result for

4-letter subword patterns, namely a complete list of the respective generating

functions.

Research Direction 4.4 A third research direction is to look at a diﬀerent

type of pattern avoidance, namely a cyclic version. We say that a sequence

(composition, word, partition) s

···s

cyclicly avoids asubwordτ = τ

···τ



if s

···s

−1

avoids τ. For example, the composition 33412 avoids the

subword 123, but does not cyclicly avoid 123 (since 3341233 contains 123).A

natural research question is to ﬁnd the generating function for the number of

compositions of n that cyclicly avoid a subword pattern of length k.

TABLE 4.4: {AC

(τ)}

n=0

for 4-letter subword patterns τ

τ {AC

(τ)}

n=0

for 4-letter subword patterns τ

1112 1 1248 15

29 56 108 207 398 765

1471 2826 5431 10437 20058 38544

74070 142341 273538 525655 1010149 1941201

3730401

1121 1 1248 15

29 56 108 208 402 777

1502 2902 5608 10836 20937 40451

78154 150998 291738 563658 1089034 2104109

4065327

1111 1 1247 15

29 57 111 218 429 841

1651 3239 6355 12473 24475 48029

94249 184946 362932 712194 1397569 2742507

5381729

1122 1 1248 16

31 62 122 242 477 944

1866 3689 7293 14417 28504 56349

111402 220236 435401 860773 1701717 3364239

6650985

126 Combinatorics of Compositions and Words

τ {AC

(τ)}

n=0

for 4-letter subword patterns τ

1221 1 1248 16

31 62 122 242 477 945

1867 3694 7302 14442 28556 56470

111664 220810 436639 863426 1707375 3376228

6676294

2112 1 1248 16

31 62 122 242 478 946

1870 3700 7315 14470 28617 56598

111938 221385 437850 865960 1712665 3387243

6699164

1123 1 1248 16

32 63 125 247 489 966

1910 3774 7459 14738 29123 57543

113700 224654 443885 877044 1732898 3423912

6765071

1132 1 1248 16

32 63 125 247 489 966

1910 3774 7459 14738 29124 57547

113713 224689 443975 877264 1733420 3425118

6767805

1212 1 1248 16

31 62 122 243 479 949

1877 3715 7351 14548 28788 56965

112730 223072 441433 873532 1728602 3420658

6769015

2113 1 1248 16

32 63 125 247 489 966

1910 3775 7462 14748 29150 57612

113869 225054 444808 879135 1737559 3434179

6787449

1231 1 1248 16

32 63 125 247 489 966

1910 3775 7463 14752 29163 57650

113968 225300 445396 880500 1740663 3441114

6802743

1213 1 1248 16

32 63 125 247 489 966

1911 3777 7468 14762 29183 57687

114037 225423 445612 880868 1741271 3442075

6804169

1312 1 1248 16

32 63 125 247 489 966

1911 3777 7468 14762 29184 57691

114050 225458 445702 881087 1741789 3443266

6806859

Statistics on Compositions 127

τ {AC

(τ)}

n=0

for 4-letter subword patterns τ

1222 1124816

32 63 126 251 499 993

1977 3934 7830 15583 31014 61725

122847 244492 486595 968434 1927403 3835966

7634439

2122 1124816

32 63 126 251 499 993

1978 3936 7835 15595 31041 61787

122988 244802 487275 969912 1930591 3842805

7649034

1322 1124816

1232

32 64 127 253 504 1003

1996 3973 7907 15736 31317 62325

124035 246846 491255 977660 1945667 3872122

7706010

2123 1124816

2213

32 64 127 253 504 1003

1996 3973 7907 15736 31318 62329

124045 246871 491315 977800 1945988 3872846

7707618

1223 1124816

32 64 127 253 504 1003

1996 3973 7907 15737 31320 62333

124055 246893 491364 977909 1946224 3873353

7708703

2132 1124816

32 64 127 253 504 1003

1996 3973 7908 15741 31332 62365

124135 247086 491817 978947 1948562 3878547

7720116

1233 1124816

32 64 128 255 510 1018

2033 4059 8106 16185 32319 64533

128860 257304 513782 1025909 2048520 4090447

8167736

1332 1124816

32 64 128 255 510 1018

2033 4059 8106 16185 32319 64533

128860 257304 513783 1025911 2048527 4090463

8167777

1323 1124816

32 64 128 255 510 1018

2033 4059 8106 16185 32319 64533

128861 257306 513787 1025922 2048551 4090519

8167901

128 Combinatorics of Compositions and Words

τ {AC

(τ)}

n=0

for 4-letter subword patterns τ

2133 1124816

32 64 128 255 510 1018

2033 4059 8106 16185 32319 64533

128861 257307 513790 1025929 2048569 4090562

8168003

2313 1124816

32 64 128 255 510 1018

2033 4059 8106 16185 32319 64533

128862 257309 513795 1025942 2048600 4090634

8168167

3123 1124816

32 64 128 255 510 1018

2033 4059 8106 16186 32321 64538

128873 257336 513858 1026083 2048914 4091327

8169680

1243 1124816

32 64 128 256 511 1021

2039 4072 8131 16237 32422 64741

129274 258133 515435 1029210 2055101 4103574

8193908

2134 1124816

32 64 128 256 511 1021

2039 4072 8131 16237 32422 64741

129274 258133 515435 1029210 2055102 4103578

8193921

1342 1124816

1432

32 64 128 256 511 1021

2039 4072 8131 16237 32422 64741

129274 258133 515435 1029210 2055102 4103578

8193922

1423 1124816

32 64 128 256 511 1021

2039 4072 8131 16237 32422 64741

129274 258133 515435 1029211 2055104 4103583

8193932

2314 1124816

32 64 128 256 511 1021

2039 4072 8131 16237 32422 64741

129274 258133 515435 1029211 2055105 4103587

8193945

2143 1124816

32 64 128 256 511 1021

2039 4072 8131 16237 32422 64741

129274 258133 515436 1029216 2055121 4103632

8194062

Statistics on Compositions 129

τ {AC

(τ)}

n=0

for 4-letter subword patterns τ

1324 1124816

32 64 128 256 511 1021

2039 4072 8131 16237 32422 64741

129275 258136 515444 1029235 2055165 4103731

8194282

2413 1124816

32 64 128 256 511 1021

2039 4072 8131 16237 32422 64741

129275 258136 515445 1029240 2055182 4103780

8194412

3124 1124816

3214

32 64 128 256 511 1021

2039 4072 8131 16237 32422 64741

129275 258137 515448 1029246 2055196 4103812

8194484

1234 1124816

32 64 128 256 511 1021

2039 4072 8131 16238 32425 64750

129298 258194 515583 1029559 2055905 4105396

8197980

Chapter 5

Avoidance of Nonsubword Patterns

in Compositions

5.1 History and connections

In Chapter 4, we looked at enumeration of subword patterns. In this chapter

the focus will be on pattern avoidance rather than enumeration. In addition

we will consider diﬀerent types of patterns, namely subsequence patterns,

generalized patterns, and partially ordered patterns.

Research on avoiding (subsequence) permutation patterns has become an

important area of study in enumerative combinatorics, as evidenced by the

publication of a special volume of the Electronic Journal of Combinatorics on

permutation patterns (see http://www.combinatorics.org, volume 9:2) and

hundreds of articles elsewhere in journals (see [25] and references therein for

an overview). This area of research has applications to computer science

and algebraic geometry and has proved to be useful in a variety of seemingly

unrelated topics, including the theory of Kazhdan-Lusztig polynomials, sin-

gularities of Schubert varieties [128], Chebyshev polynomials [53, 126, 148],

rook polynomials for a rectangular board [146], various sorting algorithms

[123, Ch. 2.2.1], and sortable permutations [191].

Pattern avoidance was ﬁrst studied for S

, the set of permutations of [n],

avoiding a subsequence pattern τ ∈S

. Knuth [122] found that the number

of permutations of [n] avoiding any τ ∈S

is given by the n-th Catalan

number. Later, Simion and Schmidt [179] determined |S

(T )|,thenumber

of permutations of [n] simultaneously avoiding any given set of subsequence

patterns T ⊆S

. Burstein [31] extended this to words of length n on the

alphabet {1, 2,...,k}, determining the number of words that avoid a set of

subsequence patterns T ⊆S

. Burstein and Mansour [33, 34] considered

forbidden subsequence patterns with repeated letters.

Recently, subsequence pattern avoidance has been studied for compositions.

Savage and Wilf [176] considered subsequence pattern avoidance in composi-

tions for a single pattern τ ∈S

, and showed that the number of compositions

of n avoiding τ ∈S

is independent of τ . Heubach and Mansour [91] ﬁlled

in the missing pieces by investigating avoidance of multi-permutation subse-

quence patterns of length three. These results are the focus of Section 5.2.

131

132 Combinatorics of Compositions and Words

In Section 5.3 we present new results on generalized 3-letter patterns, those

that have some adjacency requirements. We derive results for permutation

and multi-permutation patterns of type (2, 1), which are the only general-

ized patterns not investigated in previous sections. Finally, in Section 5.4, we

discuss results on partially ordered patterns. Kitaev [108] introduced these

patterns in the context of permutations, extending the generalized permuta-

tion patterns deﬁned by Babson and Steingr´ımsson [11]. Later, Kitaev and

Mansour [109] investigated avoidance of partially ordered patterns in words,

and Heubach, Kitaev and Mansour [88] generalized to the case of composi-

tions. The majority of papers on partially ordered patterns are concerned

with pattern avoidance, but there are also some results on the enumeration

of these patterns in compositions [111].

Since we deal almost exclusively with pattern avoidance in this chapter, we

introduce notation for the set of compositions avoiding a certain pattern, the

number of such compositions and the corresponding generating function. To

highlight the fact that we talk about avoidance, we use AC instead of C –

think A for avoidance – for the relevant sets and generating functions.

Deﬁnition 5.1 For any ordered set A ⊆ N, we denote the set of compositions

of n with parts in A (respectively with m parts in A) that avoid the pattern τ by

(τ) and AC

n,m

(τ), respectively. We denote the number of compositions

in these two sets by AC

(n)(respectively AC

(m; n)).Thecorresponding

generating functions are given by AC

(x)=



n≥0

(n)x

and

(x, y)=



m,n≥0

(m; n)x



m≥0

(m; x)y

More generally, let AC

(σ

···σ



|n)(respectively AC

(σ

···σ



|m; n)) be the

number of compositions of n with parts in A (respectively with m parts in A)

that avoid τ and start with σ

,...,σ



. The corresponding generating functions

are given by

(σ

···σ



|x)=



n≥0

(σ

···σ



|n)x

and

(σ

···σ



|x, y)=



n,m≥0

(σ

···σ



|m; n)x



m≥0

(σ

···σ



|m; x)y

From the deﬁnitions, we immediately get that

(x, y)=1+



a∈A

(a|x, y). (5.1)

As before, we are interested in determining which patterns are equivalent

in the sense that they are avoided by the same number of compositions (and

Avoidance of Nonsubword Patterns in Compositions 133

therefore have the same generating functions). We follow the terminology in

the research literature and refer to this equivalence as Wilf-equivalence (as

distinguished from tight Wilf-equivalence which relates to subword patterns).

Deﬁnition 5.2 Two nonsubword patterns τ and ν are called Wilf-equivalent

if the number of compositions of n with m parts in A that avoid τ is the same

as the number of compositions of n with m parts in A that avoid ν, for all A,

n,andm. We denote two patterns that are Wilf-equivalent by τ ∼ ν.

Finally, note that in this chapter most of the results are given for A = N,

not only because that is the most interesting case, but also because results

for arbitrary sets A are much harder to derive for the more general patterns.

Likewise, enumeration for these more general patterns is more diﬃcult, and

in general does not lead to nice or even explicit formulas for the generating

functions. We will indicate when the results can be generalized to an arbitrary

ordered set A.

5.2 Avoidance of subsequence patterns

We now look at subsequence patterns that, unlike the subword patterns,

do not have any adjacency requirements. This type of pattern was originally

studied in the context of permutations, and is referred to in the literature as

classical pattern.

Deﬁnition 5.3 Asequence(permutation, word, composition or partition) σ

contains a subsequence pattern τ = τ

···τ

if the reduced form of any

k-term subsequence of σ equals τ. Otherwise we say that σ avoids the subse-

quence pattern τ or is τ-avoiding. The reversal map for subsequence patterns

generalizes in the obvious manner from that of subword patterns.

Example 5.4 The composition σ = 112532 contains the subsequence pattern

1123 twice (as the subsequences σ

= 1125 and σ

= 1123) and

avoids the subsequence pattern 1234. The reversal of the subsequence pattern

τ = 1243 is R(1243) = 3421.

In subsequent sections we introduce dashes into patterns to indicate the

positions in the pattern where there is no adjacency requirement. With

this notation, a subsequence pattern τ = τ

···τ

could be written as

τ = τ

–τ

– ··· −τ

, as there are no adjacency requirements at all. Since

this notation is somewhat cumbersome and conﬂicts with usage in the litera-

ture, and since we deal exclusively with subsequence patterns in this section,

we will omit the dashes.

134 Combinatorics of Compositions and Words

We start by deriving AC

(x, y), where τ is a pattern of length two. In this

case there are only two patterns to consider, namely 11 and 12.

Theorem 5.5 For patterns of length two we have

(x, y)=



j≥1

1 − x

and

(x, y)=



n,m≥0

m!p

n,m

where p

n,m

denotes the number of partitions of n with m distinct parts in N

with generating function



j≥1

(1 + x

y).

Proof To derive AC

(x, y) we just recognize that avoiding the subsequence

pattern 12 is the same as avoiding the subword pattern 12 (why?), and there-

fore obtain the result from Example 2.65. For the pattern 11, we have to

work a little. First observe that avoiding the subsequence pattern 11 means

that the composition consists of distinct parts. Furthermore, the number of

compositions of n with m distinct parts can be obtained by computing the

number of partitions of n with m distinct parts (for which we have derived

the generating function in Example 4.18), then multiplying by m!. 2

Example 5.6 If we want to compute the sequence of values for compositions

of n with distinct parts, then we cannot just set y =1in AC

(x, y) because

the coeﬃcients of x also depend on m. Rather, we have to compute the values

for p

n,m

from its generating function, then multiply by m!, and then sum over

all values of m for a given n. Obviously, this is a task for a computer algebra

system such as Mathematica or Maple. Below is the Maple code to compute

the values for n =0, 1,...,20.

N:=20:

s:=vector(N+1,[]):

F:=expand(product((1+x^j*y),j=1..N+1)):

for n from 0 to N do

s[n+1]:=0:

for m from 0 to n do

s[n+1]:=s[n+1]+m!*coeff(coeff(F,x,n),y,m):

od:

print(s);

The corresponding Mathematica code is given by

f[x_,y_]:= Series[Product[(1 + x^j y), {j, 1, 20}],

{x, 0, 21}, {y, 0, 21}]

co[n_,m_]:= If[n < m, 0, Coefficient[f[x, y], x^n y^m]];

Apply[Plus, Table[m! co[n, m], {n, 1, 20}, {m, 1, n}], 2]