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

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

Avoidance of Nonsubword Patterns in Compositions 185

τ {AC

(τ)}

n=0

for 4-letter patterns of type (2, 2)

13–22 11248 16

31–22

32 64 127 252 500 989

1953 3852 7586 14921 29312 57516

112739 220762 431884 844170 1648669 3217364

13–32 11248 16

32 64 128 255 509 1014

2019 4017 7988 15871 31515 62536

124017 245785 486825 963681 1906545 3769795

13–23 11248 16

23–13

32 64 128 255 509 1014

2019 4017 7988 15871 31515 62536

124018 245790 486842 963736 1906706 3770239

31–23 11248 16

32 64 128 255 509 1014

2019 4017 7988 15871 31515 62537

124020 245795 486853 963757 1906737 3770268

23–14 11248 16

14–23

32 64 128 256 511 1020

2034 4053 8069 16055 31920 63421

125927 249884 495560 982214 1945695 3852230

32–14 11248 16

32 64 128 256 511 1020

2034 4053 8069 16055 31920 63421

125927 249885 495565 982233 1945759 3852427

14–32 11248 16

32 64 128 256 511 1020

2034 4053 8069 16055 31920 63422

125931 249898 495604 982342 1946046 3853154

31–24 11248 16

13–42

32 64 128 256 511 1020

2034 4053 8070 16057 31927 63441

125981 250025 495921 983116 1947915 3857610

24–13 11248 16

13–24

32 64 128 256 511 1020

2034 4053 8070 16057 31927 63441

125982 250029 495936 983165 1948064 3858036

21–33 11248 16

12–33

32 64 128 255 509 1014

2021 4023 8008 15930 31683 62990

125198 248771 494194 981512 1948971 3869295

21–43 11248 16

12–34

32 64 128 256 511 1020

12–43

2034 4054 8074 16074 31982 63609

21–34

126458 251318 499290 991636 1968926 3908376

186 Combinatorics of Compositions and Words

TABLE 5.6: {AC

(τ)}

n=0

for 4-letter patterns of type (1, 1, 2)

τ {AC

(τ)}

n=0

for 4-letter patterns of type (1, 1, 2)

1–1–12 11248 15

1–1–21

29 54 101 185 336 603

1080 1906 3340 5813 10050 17220

29364 49698 83722 140091 233265 386112

1–2–11 11248 15

29 55 104 195 363 672

1242 2282 4176 7619 13860 25132

45465 82044 147749 265556 476419 853293

2–1–11 11248 15

29 55 104 195 363 672

1242 2282 4176 7619 13860 25132

45465 82044 147749 265556 476419 853293

1–1–11 11247 15

27 53 99 186 348 647

1212 2232 4095 7549 13838 25211

45962 83449 151345 273537 494147 890332

1–2–21 11248 16

1–2–12

31 61 118 229 438 836

1582 2981 5585 10414 19319 35654

65497 119732 217951 395021 713137 1282315

2–1–12 11248 16

2–1–21

31 61 118 229 438 836

1582 2981 5585 10414 19319 35654

65497 119733 217957 395043 713213 1282516

1–3–12 11248 16

32 63 124 241 467 896

1710 3241 6106 11436 21302 39469

72769 133534 243939 443746 803949 1450981

1–3–21 11248 16

32 63 124 241 467 896

1710 3242 6109 11447 21332 39550

72966 134005 245007 446117 809059 1461798

3–1–12 11248 16

3–1–21

32 63 124 241 467 896

1710 3242 6110 11450 21346 39592

73093 134349 245899 448310 814278 1473803

2–2–11 11248 16

31 61 119 231 443 848

1616 3066 5790 10878 20353 37942

70485 130511 240892 443257 813292 1488266

2–1–31 11248 16

2–1–13

32 63 124 242 470 907

1742 3327 6324 11962 22524 42224

78826 146574 271523 501195 922021 1690784

Avoidance of Nonsubword Patterns in Compositions 187

τ {AC

(τ)}

n=0

for 4-letter patterns of type (1, 1, 2)

2–3–11 11248 16

3–2–11

32 63 124 242 470 907

1741 3325 6320 11958 22533 42293

79092 147411 273872 507311 937130 1726623

1–2–13 11248 16

1–2–31

32 63 124 242 470 907

1742 3328 6329 11981 22586 42407

79324 147856 274676 508670 939209 1729308

2–2–12 11248 16

2–2–21

32 63 124 244 478 932

1810 3501 6745 12940 24725 47067

89281 168762 317883 596671 1116127 2080849

2–3–21 11248 16

2–3–12

32 64 127 251 494 968

3–2–21

1888 3666 7085 13632 26117 49831

3–2–12

94698 179267 338082 635270 1189487 2219620

2–2–13 11248 16

2–2–31

32 64 127 251 495 972

1900 3698 7166 13830 26586 50910

97119 184587 349582 659812 1241290 2327918

1–1–32 11248 16

1–1–23

32 63 125 245 481 938

1825 3543 6859 13247 25539 49154

94450 181276 347510 665526 1273449 2434942

1–1–22 11248 16

31 62 121 238 463 904

1760 3419 6634 12852 24889 48130

93039 179702 346925 669383 1291167 2489581

2–1–23 11248 16

1–2–23

32 64 127 252 499 985

2–1–32

1939 3809 7465 14601 28502 55535

1–2–32

108023 209788 406825 787862 1523868 2944030

1–2–22 11248 16

2–1–22

32 63 125 248 489 963

1895 3722 7299 14293 27956 54615

106581 207777 404680 787499 1531260 2975276

3–1–22 11248 16

1–3–22

32 64 127 252 499 985

1940 3814 7483 14657 28663 55973

109163 212648 413798 804455 1562573 3032783

3–3–12 11248 16

3–3–21

32 64 128 255 508 1009

2002 3962 7827 15425 30335 59523

116540 227673 443814 863278 1675600 3245434

188 Combinatorics of Compositions and Words

τ {AC

(τ)}

n=0

for 4-letter patterns of type (1, 1, 2)

2–3–13 11248 16

2–3–31

32 64 128 255 508 1010

2005 3973 7860 15521 30596 60202

118248 231847 453783 886622 1729357 3367413

3–2–13 11248 16

3–2–31

32 64 128 255 508 1010

2005 3973 7860 15521 30596 60203

118253 231868 453856 886854 1730038 3369304

3–4–12 11248 16

3–4–21

32 64 128 256 511 1019

4–3–12

2028 4029 7987 15802 31195 61454

4–3–21

120805 236983 463932 906402 1767403 3439723

2–4–31 11248 16

32 64 128 256 511 1019

2029 4033 8002 15849 31333 61831

121789 239454 469960 920748 1800855 3516374

2–4–13 11248 16

32 64 128 256 511 1019

2029 4033 8002 15849 31333 61831

121790 239460 469984 920828 1801096 3517049

4–2–13 11248 16

4–2–31

32 64 128 256 511 1019

2029 4033 8002 15849 31333 61832

121796 239486 470078 921134 1802016 3519658

3–2–14 11248 16

3–2–41

32 64 128 256 511 1019

2029 4034 8006 15864 31382 61979

122210 240598 472955 928353 1819675 3561937

2–3–14 11248 16

2–3–41

32 64 128 256 511 1019

2029 4034 8006 15864 31382 61980

122216 240623 473043 928633 1820504 3564257

3–1–32 11248 16

32 64 128 255 509 1013

2016 4005 7952 15767 31234 61808

122191 241330 476193 938771 1849100 3639108

3–1–23 11248 16

32 64 128 255 509 1013

2016 4005 7952 15767 31234 61809

122194 241341 476225 938860 1849333 3639699

1–3–23 11248 16

1–3–32

32 64 128 255 509 1013

2016 4005 7952 15767 31234 61809

122194 241344 476233 938895 1849433 3639995

Avoidance of Nonsubword Patterns in Compositions 189

τ {AC

(τ)}

n=0

for 4-letter patterns of type (1, 1, 2)

4–1–32 11248 16

32 64 128 256 511 1020

2033 4048 8050 15993 31734 62902

124547 246355 486806 961036 1895514 3735398

1–4–23 11248 16

32 64 128 256 511 1020

2033 4048 8050 15993 31734 62902

124547 246355 486806 961036 1895514 3735399

4–1–23 11248 16

32 64 128 256 511 1020

2033 4048 8050 15993 31734 62902

124547 246356 486810 961051 1895563 3735545

1–4–32 11248 16

32 64 128 256 511 1020

2033 4048 8050 15993 31734 62903

124550 246366 486839 961129 1895759 3736020

3–1–24 11248 16

32 64 128 256 511 1020

2033 4049 8054 16007 31779 63035

124917 247341 489348 967413 1911157 3773045

3–1–42 11248 16

32 64 128 256 511 1020

2033 4049 8054 16007 31779 63035

124918 247345 489363 967460 1911293 3773416

1–3–24 11248 16

1–3–42

32 64 128 256 511 1020

2033 4049 8054 16007 31779 63035

124918 247346 489367 967477 1911348 3773586

1–2–33 11248 16

2–1–33

32 64 128 255 509 1014

2020 4019 7995 15893 31583 62733

124564 247255 490660 973434 1930810 3829021

2–1–34 11248 16

2–1–43

32 64 128 256 511 1020

1–2–34

2034 4053 8069 16056 31926 63449

1–2–43

126029 250222 496592 985185 1953864 3873890

190 Combinatorics of Compositions and Words

TABLE 5.7: {AC

(τ)}

n=0

for 4-letter patterns of type (1, 2, 1)

τ {AC

(τ)}

n=0

for 4-letter patterns of type (1, 2, 1)

1–12–1 11248 15

29 54 101 185 336 603

1080 1906 3340 5813 10050 17220

29364 49698 83722 140091 233265 386112

1–11–2 11248 15

29 55 104 195 363 672

1242 2282 4176 7619 13860 25132

45465 82044 147749 265556 476419 853293

1–11–1 11247 15

27 53 99 186 348 647

1212 2232 4095 7549 13838 25211

45962 83449 151345 273537 494147 890332

1–12–2 11248 16

1–21–2

31 61 118 229 438 836

1582 2981 5583 10408 19298 35601

65358 119400 217167 393237 709158 1273657

2–11–2 11248 16

31 61 119 231 443 848

1614 3056 5760 10800 20155 37444

69265 127631 234310 428609 781378 1419850

1–21–3 11248 16

1–12–3

32 63 124 241 467 896

1710 3242 6110 11450 21344 39584

73062 134251 245617 447556 812367 1469172

1–31–2 11248 16

1–13–2

32 63 124 242 470 907

1742 3327 6324 11964 22533 42258

78931 146875 272318 503192 926820 1701939

2–11–3 11248 16

32 63 124 242 470 907

1741 3325 6319 11952 22511 42223

78887 146856 272451 503819 928843 1707517

2–12–2 11248 16

32 63 124 244 478 932

1810 3501 6745 12940 24725 47067

89281 168762 317883 596671 1116127 2080849

2–12–3 11248 16

2–21–3

32 64 127 251 494 968

1888 3666 7085 13632 26117 49831

94698 179267 338082 635270 1189487 2219620

2–13–2 11248 16

32 64 127 251 495 972

1900 3698 7166 13830 26586 50910

97119 184587 349582 659812 1241290 2327918

Avoidance of Nonsubword Patterns in Compositions 191

τ {AC

(τ)}

n=0

for 4-letter patterns of type (1, 2, 1)

1–23–1 11248 16

32 63 125 245 481 938

1825 3541 6853 13229 25489 49022

94128 180502 345718 661496 1264569 2415704

1–22–1 11248 16

31 62 121 238 463 904

1758 3415 6624 12824 24817 47962

92645 178808 344949 665095 1281951 2470037

1–23–2 11248 16

1–32–2

32 64 127 252 499 985

1939 3809 7465 14601 28502 55535

108023 209788 406825 787862 1523868 2944030

1–22–2 11248 16

32 63 125 248 489 963

1895 3722 7299 14293 27956 54615

106581 207777 404680 787499 1531260 2975276

1–22–3 11248 16

32 64 127 252 499 985

1940 3814 7483 14657 28663 55973

109163 212648 413798 804455 1562573 3032783

3–12–3 11248 16

32 64 128 255 508 1009

2002 3962 7827 15425 30335 59521

116530 227631 443674 862852 1674404 3242232

2–31–3 11248 16

2–13–3

32 64 128 255 508 1010

2005 3973 7860 15521 30596 60202

118248 231847 453785 886634 1729407 3367586

3–12–4 11248 16

3–21–4

32 64 128 256 511 1019

2028 4029 7987 15802 31195 61454

120805 236982 463926 906375 1767304 3439398

2–31–4 11248 16

2–13–4

32 64 128 256 511 1019

2029 4033 8002 15849 31333 61832

121796 239486 470078 921133 1802010 3519632

2–41–3 11248 16

2–14–3

32 64 128 256 511 1019

2029 4034 8006 15864 31382 61979

122210 240597 472950 928333 1819607 3561725

1–32–3 11248 16

1–23–3

32 64 128 255 509 1013

2016 4005 7952 15767 31234 61809

122194 241342 476227 938871 1849362 3639789

192 Combinatorics of Compositions and Words

τ {AC

(τ)}

n=0

for 4-letter patterns of type (1, 2, 1)

1–32–4 11248 16

1–23–4

32 64 128 256 511 1020

2033 4048 8050 15993 31734 62902

124547 246355 486806 961036 1895514 3735399

1–42–3 11248 16

1–24–3

32 64 128 256 511 1020

2033 4049 8054 16007 31779 63035

124918 247346 489368 967480 1911360 3773622

1–33–2 11248 16

32 64 128 255 509 1014

2020 4019 7995 15893 31582 62730

124553 247225 490576 973219 1930270 3827723

1–43–2 11248 16

1–34–2

32 64 128 256 511 1020

2034 4053 8069 16056 31926 63448

126025 250207 496546 985052 1953506 3872968

Chapter 6

Words

6.1 History and connections

Chronologically, enumeration of words according to the occurrence of a

pattern or a set of patterns grew out of the corresponding research questions

in permutations, and was followed by enumeration of compositions according

to the occurrence of a given (set of) pattern(s). In this book, we have presented

the more general results ﬁrst.

The main focus of this section will be pattern avoidance in words for dif-

ferent types of patterns: subword, subsequence, generalized, and partially

ordered patterns. A systematic investigation of this research area started in

the late 1990s. The ﬁrst paper on subsequence patterns was by Regev [169],

who found the asymptotic behavior of the number of k-ary words avoiding an

increasing subsequence of length . In 1999, Burstein [31] presented an explicit

formula for the generating functions for the number of k-ary words of length n

that avoid a set of permutation (subsequence) patterns T ⊂S

, together with

a complete classiﬁcation of the permutation patterns of length three. The

main technique used in his thesis is an extension of the Noonan-Zeilberger

algorithm [163] that was originally created for enumerating permutations sat-

isfying certain conditions. Burstein and Mansour [33] extended this line of

inquiry to the case of subsequence patterns with repetitions.

A diﬀerent generalization was given by Mansour [141], who derived the

generating function for the number of k-ary words of length n that avoid

both 132 and another pattern τ for several interesting cases of τ . Recently,

Firro and Mansour [64] recovered the results of Burstein for avoidance of

the subsequence pattern 123 by using a new technique, the scanning-element

algorithm, which allows for an easier proof. Moreover, they gave an explicit

formula for the number of k-ary words containing a subsequence pattern τ

exactly once. A third proof of Burstein’s result was given with yet another

approach by Mansour [141], who adapted the block decomposition method

used for permutations to words. Using ﬁnite automata theory, Br¨and´en and

Mansour [27] gave a combinatorial explanation for the number of k-ary words

of length n avoiding a subsequence pattern of length three (see Chapter 7).

Most recently, Jel´ınek and Mansour [105] classiﬁed the subsequence patterns

up to length six with regard to Wilf-equivalence.

193

194 Combinatorics of Compositions and Words

Several authors have considered other types of patterns besides subsequence

patterns. Burstein and Mansour [33, 34] enumerated words according to gen-

eralized patterns of length three as well as words containing a subword pattern

of length  exactly r times, while Kitaev and Mansour [109] studied partially

ordered generalized patterns.

In this chapter we sample some of the results. After deﬁning some notation

in Section 6.2, we give examples of how results for words can be recovered

from those for compositions in Section 6.3. We also summarize results for

subword patterns of length three and give a result for the pattern peak.

The focus of Sections 6.4 and 6.5 is on subsequence patterns. We start by

giving classiﬁcations of the patterns up to length ﬁve, based on the results by

Jel´ınek and Mansour [105], who connected Wilf-equivalence with equivalence

of ﬁllings of Ferrers diagrams by expressing words as matrices. The connec-

tion between the two types of equivalence gives surprisingly general results

using previously known results on ﬁllings of Ferrers diagrams [127]. Using sys-

tematic computer enumeration of small patterns we verify that these results,

together with the reversal and complement maps, are suﬃcient to describe all

Wilf-equivalence classes for patterns of length six or less.

Next, we give results for generating functions for subsequence permutation

and multi-permutation patterns of length three. One of the major results in

pattern avoidance of subsequence patterns was the derivation of the generating

function for the pattern 132. We give three diﬀerent proofs for this result.

The ﬁrst proof will illustrate the Noonan-Zeilberger algorithm as it applies to

words, the second one will utilize block decomposition, a very useful tool in

enumeration of words, and the third proof will showcase the scanning-element

algorithm. Each of these approaches has advantages and disadvantages, as

will become clear in this parallel treatment. We conclude the discussion of

permutation patterns of length three by giving results on avoidance of pairs

of patterns and their generalizations, as well as results for the generating

functions of words containing the patterns 123 and 132, respectively exactly

once.

In the last two sections we present results on generalized patterns and on

partially ordered patterns obtained from the results for compositions pre-

sented in Chapter 5.

6.2 Deﬁnitions and basic results

Before giving any results, we will state the basic notation, nearly identical

to that for compositions, for the generating functions of interest. Recall that

[k] denotes an ordered alphabet, and that [k]

denotes the set of k-ary words

of length n (see Deﬁnition 1.7).