Heubach S., Mansour T. Combinatorics of Compositions and Words
Подождите немного. Документ загружается.
Avoidance of Nonsubword Patterns in Compositions 175
Therefore, the generating function for the number of compositions that have
exactly s nonoverlapping occurrences of the pattern τ is given by
AC
Φ
s+1
A
(x, y) − AC
Φ
s
A
(x, y)=AC
τ
A
(x, y)
y
a∈A
x
a
− 1
AC
τ
A
(x, y)+1
s
.
Hence,
n,m≥0
σ∈C
A
n,m
q
τ –nlap(σ)
x
n
y
m
=
s≥0
q
s
AC
τ
A
(x, y)
y
a∈A
x
a
− 1
AC
τ
A
(x, y)+1
s
=
AC
τ
A
(x, y)
1 − q
0
y
a∈A
x
a
− 1
AC
τ
A
(x, y)+1
1
,
which completes the proof. 2
We use Theorem 5.80 to obtain the distribution for MND,themaximum
number of nonoverlapping descents.
Example 5.81 For descents (the pattern 21) we modify the argument given
in Example 2.65 for a general set A to obtain that
AC
21
A
(x, y)=
a∈A
(1 − x
a
y)
−1
.
This implies that the distribution of MND is given by
1
a∈A
(1 − x
a
y)+q
1 − y
a∈A
x
a
−
a∈A
(1 − x
a
y)
.
5.5 Exercises
Exercise 5.1 Either modify the Mathematica code given in Example 5.14 or
write your own code in Maple or any other programming language to directly
enumerate the number of compositions that avoid 13–2. Give the sequence of
values for n =0, 1,...,10.
Exercise 5.2 Fill in the details of the proof of Theorem 5.21. That is, show
that
1+
d−1
i=1
x
i
y
i
j=1
(1 − x
j
y)
=
1
d−1
j=1
(1 − x
j
y)
(*)
© 2010 by Taylor and Francis Group, LLC
176 Combinatorics of Compositions and Words
and
G
d
(i)=
x
i+d
y
2
AC
12–3
[d]
(x, y)
i
j=1
(1 − x
j
y)
(**)
for i =1, 2,...,d− 1.
Exercise 5.3 Modify the proof of Theorem 5.23 to obtain
AC
21–3
[d]
(x, y)=
d
i=1
1 −
x
i
y
i−1
j=1
(1 − x
j
y)
−1
.
Exercise 5.4 Show that
det(U
(i)
i
)=β
i
i−1
j=1
(1 − α
j
)+α
i
i−1
j=1
β
j
j−1
k=1
(1 − α
k
)
for the matrix U
(i)
i
defined in the proof of Lemma 5.45.
Exercise 5.5 Find the generating function for the number of compositions of
n with m parts in A that simultaneously avoid 12–3 and 21–3.Thenusethe
generating function to compute the number of compositions of n that simulta-
neously avoid 12–3 and 21–3 for n =0,...,20.
Exercise 5.6 Prove Lemma 5.54.
Exercise 5.7 Use the generating functions for τ = 112 and ν = 221 given in
Theorem 4.35 to derive generating functions for the number of occurrences of
τ and ν, respectively, among all compositions of n, thereby deriving the results
of Example 5.58 in a different way.
Exercise 5.8 Prove Corollaries 5.65 and 5.66.
Exercise 5.9 Prove Theorem 5.73.
Exercise 5.10 Fill in the details of the proof of Corollary 5.77.
5.6 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.
© 2010 by Taylor and Francis Group, LLC
Avoidance of Nonsubword Patterns in Compositions 177
Research Direction 5.1 Throughout this chapter there were several enu-
meration problems for which we did not succeed to find an explicit formula for
the generating function. These lead us to ask the following questions:
(1) Derive an explicit expression for the generating function for the num-
ber of compositions avoiding the subsequence pattern 112,forwhicha
recursion was given in Theorem 5.13.
(2) Derive an explicit expression for the generating function for the num-
ber of compositions avoiding the subsequence pattern 221,forwhicha
recursion was given in Theorem 5.13.
(3) Derive an explicit expression for the generating function for the number
of compositions avoiding the pattern 13–2, for which a recursion was
given in Lemma 5.25.
(4) Find an explicit expression for the generating function for the number
of compositions avoiding the pattern 11–2, in terms of permutations if
possible. (A recursion for this generating function was given in Theo-
rem 5.41.)
(5) Derive an explicit expression for the generating function for the number
of compositions avoiding the pattern 11–1, for which a recursion was
given in Theorem 5.39.
(6) Find an explicit expression for the generating function for the number
of compositions avoiding the pattern 12–1, in terms of permutations if
possible. (A recursion for this generating function was given in Theo-
rem 5.46.)
Research Direction 5.2 In this chapter we completely classified the subse-
quence patterns of length three according to Wilf-equivalence, and gave explicit
expressions for their generating functions. Tables 5.2 and 5.3 show the Wilf-
equivalence classes for patterns of length four and five, respectively, but finding
expressions for the respective generating functions remains an open question.
Research Direction 5.3 In this chapter, we completely classified the 3-let-
ter patterns of type (1, 2), and gave explicit or recursive expressions for their
generating functions. Extending to 4-letter generalized patterns, we need to
consider four different types, namely
(3, 1), (2, 2), (1, 2, 1) and (1, 1, 2).
This leads to the following questions:
(1-a) Classify the 4-letter patterns of type (3, 1) ac
cording to Wilf-equivalence
by using the values of the sequence {AC
n
(τ)}
23
n=0
given in Table 5.4.
Either give a bijection for the patterns that have the same sequence of
© 2010 by Taylor and Francis Group, LLC
178 Combinatorics of Compositions and Words
values or show that they are not Wilf-equivalent by computing additional
sequence values and finding a value of n for which the sequences are
different.
(1-b) Find expressions for the generating functions for each Wilf-equivalence
class. As an example, we give the generating function AC
τ
[d]
(x, y) for any
type (3, 1) pattern in which the single letter is the largest one. That is,
τ = τ
–k is a pattern such that τ
is a 3-letter subword pattern on [k−1].
Then each composition σ of n with parts in [d] is either a composition
with parts in [d − 1] or σ can be written as σ
(1)
dσ
(2)
d ···σ
(s−1)
dσ
(s)
for s ≥ 2,whereσ
(i)
is a (potentially empty) composition with parts in
[d − 1] that avoids τ
. Therefore,
AC
τ
[d]
(x, y)=
AC
τ
[d−1]
(x, y)
1 − x
d
yAC
τ
[d−1]
(x, y)
,
which, when iterated d times yields
AC
τ
[d]
(x, y)=
AC
τ
[k−1]
(x, y)
d−1
j=k−1
(1 − x
j+1
yAC
τ
[j]
(x, y))
.
Since
AC
τ
[k−1]
(x, y)=C
[k−1]
(x, y)=
1
%
1 − y
k−1
i=1
x
i
&
(see Theorem 3.13), we obtain that
AC
τ
[d]
(x, y)=
1
%
1 − y
k−1
i=1
x
i
&
d−1
j=k−1
(1 − x
j+1
yAC
τ
[j]
(x, y))
.
Similar ideas lead to an expression for the generating function for avoid-
ance of τ = τ
–1,whereτ
is a three letter-subword on the letters
2, 3,...,k for k ≤ 4.
(2) Classify the 4-letter patterns of type (2, 2) according to Wilf-equivalence
by using the values of the sequence {AC
n
(τ)}
23
n=0
given in Table 5.5.
Give expressions for the respective generating functions.
(3) Classify the 4-letter patterns of type (1, 1, 2) according to Wilf-equiva-
lence by using the values of the sequence {AC
n
(τ)}
23
n=0
given in Table
5.6. Give expressions for the respective generating functions.
(4) Classify the 4-letter patterns of type (1, 2, 1) according to Wilf-equiva-
lence by using the values of the sequence {AC
n
(τ)}
23
n=0
given in Table
5.7. Give expressions for the respective generating functions.
© 2010 by Taylor and Francis Group, LLC
Avoidance of Nonsubword Patterns in Compositions 179
TABLE 5.4: {AC
n
(τ)}
23
n=0
for 4-letter patterns of type (3, 1)
τ {AC
n
(τ)}
23
n=0
for 4-letter patterns of type (3, 1)
112–1 11248 15
211–1
29 55 104 195 364 677
1257 2323 4282 7876 14459 26490
48460 88522 161512 294353 535932 974947
121–1 11248 15
29 55 105 199 377 713
1346 2533 4760 8931 16737 31328
58591 109488 204463 381573 711718 1326846
111–2 11248 15
29 56 108 207 397 761
1459 2794 5349 10237 19590 37477
71685 137098 262176 501313 958492 1832476
111–1 11247 15
28 55 105 203 391 752
1448 2778 5329 10225 19609 37575
71987 137849 263962 505241 966973 1850204
211–2 11248 16
31 61 119 232 449 869
1673 3215 6162 11784 22486 42816
81365 154331 292215 552368 1042501 1964645
112–2 11248 16
31 61 119 232 449 869
1674 3218 6170 11803 22531 42917
81589 154814 293244 554525 1046964 1973768
112–3 11248 16
211–3
32 63 124 242 471 912
1760 3386 6495 12425 23715 45161
85829 162816 308320 582919 1100431 2074464
121–2 11248 16
31 61 119 233 452 877
1694 3270 6298 12116 23263 44595
85358 163161 311514 594103 1131873 2154269
121–3 11248 16
32 63 124 242 472 916
1775 3430 6615 12731 24461 46918
89865 171887 328368 626586 1194381 2274451
113–2 11248 16
311–2
32 63 124 243 475 925
1799 3491 6764 13085 25285 48805
94115 181339 349151 671828 1291996 2483410
131–2 11248 16
32 63 124 243 475 926
1804 3508 6815 13225 25644 49685
96202 186161 360063 696105 1345251 2598854
© 2010 by Taylor and Francis Group, LLC
180 Combinatorics of Compositions and Words
τ {AC
n
(τ)}
23
n=0
for 4-letter patterns of type (3, 1)
122–1 11248 16
31 62 121 239 467 917
1793 3510 6860 13406 26181 51115
99761 194650 379711 740561 1444115 2815632
221–1 11248 16
31 62 121 239 467 917
1794 3512 6865 13418 26210 51178
99902 194950 380351 741894 1446886 2821316
212–1 11248 16
31 62 121 240 469 923
1808 3547 6944 13607 26628 52113
101952 199408 389942 762420 1490473 2913372
231–1 11248 16
132–1
32 63 125 246 485 952
1868 3659 7161 13999 27348 53387
104163 203128 395962 771583 1503089 2927366
123–1 11248 16
321–1
32 63 125 246 485 952
1868 3661 7168 14022 27412 53558
104593 204181 398460 777388 1516316 2957073
213–1 11248 16
32 63 125 246 485 952
1869 3662 7171 14029 27427 53587
104652 204288 398649 777691 1516756 2957547
312–1 11248 16
32 63 125 246 485 952
1869 3663 7174 14037 27447 53636
104765 204542 399204 778889 1519292 2962864
122–2 11248 16
221–2
32 63 125 248 490 967
1908 3760 7403 14563 28628 56241
110422 216677 424962 833074 1632425 3197516
122–3 11248 16
221–3
32 64 127 252 499 986
1945 3833 7544 14834 29144 57216
112253 220104 431352 844959 1654471 3238327
212–2 11248 16
32 63 125 248 491 970
1916 3780 7454 14687 28920 56914
111951 220099 432532 849648 1668392 3274977
212–3 11248 16
32 64 127 252 499 987
1949 3846 7580 14928 29378 57780
113574 223137 438194 860180 1687935 3311175
© 2010 by Taylor and Francis Group, LLC
Avoidance of Nonsubword Patterns in Compositions 181
τ {AC
n
(τ)}
23
n=0
for 4-letter patterns of type (3, 1)
132–2 11248 16
32 64 127 252 500 990
1957 3864 7621 15016 29559 58136
114250 224365 440320 863615 1692902 3316822
231–2 11248 16
32 64 127 252 500 990
1957 3864 7621 15017 29563 58148
114282 224445 440513 864069 1693941 3319151
312–2 11248 16
32 64 127 252 500 990
1957 3864 7621 15016 29561 58148
114293 224494 440676 864552 1695281 3322684
213–2 11248 16
32 64 127 252 500 990
1957 3864 7621 15017 29565 58159
114321 224562 440836 864919 1696102 3324483
123–2 11248 16
321–2
32 64 127 252 500 990
1957 3864 7621 15018 29569 58171
114354 224650 441064 865492 1697498 3327805
223–1 11248 16
322–1
32 64 127 253 503 999
1983 3936 7808 15486 30707 60879
120681 239199 474070 939499 1861764 3689208
232–1 11248 16
32 64 127 253 503 999
1983 3937 7812 15498 30741 60968
120903 239736 475331 942399 1868328 3703863
222–1 11248 16
32 63 126 251 498 990
1968 3910 7768 15430 30651 60880
120915 240142 476919 947132 1880906 3735216
231–3 11248 16
32 64 128 255 509 1014
2020 4020 7997 15898 31589 62731
124514 247020 489832 970872 1923487 3809194
132–3 11248 16
32 64 128 255 509 1014
2020 4020 7997 15898 31589 62732
124517 247030 489858 970940 1923653 3809592
312–3 11248 16
213–3
32 64 128 255 509 1014
2020 4020 7997 15898 31589 62731
124515 247027 489859 970961 1923753 3809941
© 2010 by Taylor and Francis Group, LLC
182 Combinatorics of Compositions and Words
τ {AC
n
(τ)}
23
n=0
for 4-letter patterns of type (3, 1)
321–3 11248 16
123–3
32 64 128 255 509 1014
2020 4020 7997 15898 31589 62733
124521 247047 489914 971110 1924135 3810897
231–4 11248 16
132–4
32 64 128 256 511 1020
2034 4053 8070 16058 31931 63455
126027 250162 496306 984150 1950595 3864361
213–4 11248 16
312–4
32 64 128 256 511 1020
2034 4053 8070 16058 31932 63460
126044 250214 496454 984548 1951621 3866921
321–4 11248 16
123–4
32 64 128 256 511 1020
2034 4053 8070 16059 31935 63469
126069 250280 496620 984951 1952577 3869147
412–3 11248 16
32 64 128 256 511 1020
2034 4054 8074 16073 31978 63594
126411 251179 498908 990629 1966371 3902068
214–3 11248 16
32 64 128 256 511 1020
2034 4054 8074 16073 31978 63594
126411 251179 498908 990630 1966375 3902082
124–3 11248 16
421–3
32 64 128 256 511 1020
2034 4054 8074 16073 31978 63594
126411 251179 498908 990631 1966379 3902096
142–3 11248 16
32 64 128 256 511 1020
2034 4054 8074 16073 31978 63594
126411 251180 498913 990648 1966430 3902235
241–3 11248 16
32 64 128 256 511 1020
2034 4054 8074 16073 31978 63594
126412 251183 498923 990676 1966505 3902426
133–2 11248 16
331–2
32 64 128 255 509 1015
2023 4030 8028 15986 31828 63354
126090 250912 499242 993233 1975835 3930185
313–2 11248 16
32 64 128 255 509 1015
2023 4031 8031 15994 31850 63410
126229 251246 500025 995040 1979944 3939409
© 2010 by Taylor and Francis Group, LLC
Avoidance of Nonsubword Patterns in Compositions 183
τ {AC
n
(τ)}
23
n=0
for 4-letter patterns of type (3, 1)
143–2 1124 8 16
32 64 128 256 511 1020
2035 4058 8088 16116 32102 63929
127280 253360 504244 1003410 1996449 3971801
341–2 1124 8 16
32 64 128 256 511 1020
2035 4058 8088 16116 32102 63929
127280 253360 504244 1003411 1996453 3971814
134–2 1124 8 16
431–2
32 64 128 256 511 1020
2035 4058 8088 16116 32102 63929
127280 253360 504244 1003412 1996459 3971838
314–2 1124 8 16
32 64 128 256 511 1020
2035 4058 8088 16116 32103 63933
127294 253402 504362 1003723 1997246 3973765
413–2 1124 8 16
32 64 128 256 511 1020
2035 4058 8088 16116 32103 63934
127297 253411 504386 1003785 1997398 3974126
332–1 1124 8 16
233–1
32 64 128 255 510 1017
2030 4049 8079 16113 32139 64098
127832 254928 508373 1013764 2021546 4031098
323–1 1124 8 16
32 64 128 255 510 1017
2030 4049 8080 16115 32145 64113
127871 255019 508590 1014260 2022672 4033616
243–1 1124 8 16
342–1
32 64 128 256 511 1021
2038 4068 8117 16196 32309 64448
128544 256373 511289 1019634 2033324 4054693
423–1 1124 8 16
324–1
32 64 128 256 511 1021
2038 4068 8117 16196 32309 64449
128548 256385 511323 1019724 2033551 4055247
234–1 1124 8 16
432–1
32 64 128 256 511 1021
2038 4068 8117 16197 32312 64458
128572 256447 511475 1020085 2034390 4057162
© 2010 by Taylor and Francis Group, LLC
184 Combinatorics of Compositions and Words
TABLE 5.5: {AC
n
(τ)}
23
n=0
for 4-letter patterns of type (2, 2)
τ {AC
n
(τ)}
23
n=0
for 4-letter patterns of type (2, 2)
11–12 11248 15
11–21
29 55 104 195 364 677
1256 2318 4268 7839 14361 26248
47889 87205 158545 287815 521754 944655
11–11 11247 15
28 54 104 198 379 721
1371 2599 4908 9278 17489 32877
61788 115892 216978 405878 758128 1414100
12–12 11248 16
31 61 118 230 443 853
1634 3118 5933 11247 21269 40065
75303 141041 263537 490969 912455 1691299
12–21 11248 16
21–12
31 61 118 230 443 853
1634 3120 5939 11273 21343 40277
75845 142395 266759 498485 929551 1729501
13–12 11248 16
12–13
32 63 124 242 471 911
1757 3374 6459 12321 23435 44440
84047 158533 298302 559967 1048824 1960242
21–13 11248 16
32 63 124 242 471 911
1757 3374 6459 12323 23444 44475
84161 158873 299242 562437 1055042 1975384
12–31 11248 16
32 63 124 242 471 911
1757 3375 6463 12337 23485 44587
84445 159565 300861 566123 1063231 1993229
11–32 11248 16
11–32
32 63 125 246 484 949
1857 3628 7076 13776 26785 52008
100856 195368 378048 730824 1411522 2723929
11–22 11248 16
31 62 122 240 470 923
1807 3534 6904 13471 26265 51165
99586 193693 376469 731246 1419538 2754174
12–32 11248 16
12–23
32 64 127 252 499 986
21–23
1944 3827 7520 14755 28909 56563
21–32
110527 215713 420517 818884 1593004 3095931
12–22 11248 16
21–22
32 63 125 248 490 967
1907 3755 7386 14512 28485 55860
109448 214261 419112 819191 1600033 3123029
© 2010 by Taylor and Francis Group, LLC