Heubach S., Mansour T. Combinatorics of Compositions and Words
Подождите немного. Документ загружается.
Avoidance of Nonsubword Patterns in Compositions 165
of the alphabet. Since such letters are either smaller or larger than all other
letters (why? ), we use either 1 or for such a letter ( depends on the size of
the primed letters in T ).
Note that we always use ξ to refer to a pattern from a partially ordered set,
and τ for a pattern from an (ordered) alphabet. Furthermore, in this section
any pattern that does not contain dashes is a subword pattern. Before giving
a more formal definition of the occurrence of a POP in a composition, we give
an example.
Example 5.49 Let T = {1
, 1
, 2
}, where the only relation among the ele-
ments is 1
< 2
. Then an occurrence of the (subword ) pattern ξ =1
1
2
in σ means that there is a subword σ
i
σ
i+1
σ
i+2
with σ
i+1
<σ
i+2
and no
restrictions placed on σ
i
.Thus,thesequence31254 has two occurrences of
ξ =1
1
2
,namely312 and 125,whilethesequence113425 contains seven
occurrences of the (generalized ) pattern ξ =1
–1
2
,namely113, 134 twice,
125 twice, 325,and425.
What is the reason that these partially ordered patterns were introduced?
Just to see how far one can generalize and still get results? That in itself is
always a reason for mathematicians, but a second reason is that POPs allow
us to refer to a whole set of subword patterns via a single pattern.
Example 5.50 In Section 4.3, we studied occurrences of the pattern peak,
which is comprised of the patterns 121, 132 and 231. The pattern peak can
be described by a single POP as follows: let T = {1
, 1
, 2} and ξ =1
21
.
Likewise, the pattern valley = {212, 213, 312} can be described as a POP by
choosing T = {1, 2
, 2
} and ξ =2
12
. Thus, POPs are useful to describe
“shapes” of patterns; however, not every POP results in a particular shape
(see Example 5.52).
This connection between a POP and its associated subword patterns can
be used to give a formal definition of the occurrence of a POP.
Definition 5.51 For a given POP ξ = ξ
1
ξ
2
···ξ
k
, we say that a subword
pattern τ = τ
1
τ
2
···τ
k
is a linear extension of ξ if ξ
i
<ξ
j
implies that τ
i
<τ
j
.
A generalized pattern is a linear extension of a generalized POP if it has
the same adjacency requirements as the POP and obeys the rules for linear
extension of subwords. A POP ξ occurs in a sequence (permutation, word,
composition or partition) if any of its linear extensions occurs in the sequence.
Otherwise, the sequence avoids the POP.
Example 5.52 For T = {1
, 1
, 2} and ξ =1
21
, the linear extensions are
the patterns 121, 132 and 231.ForT = {1
, 1
, 2
} and ξ =1
1
2
, the linear
extensions are 112, 123, 212, 213,and312. The occurrences of ξ =1
1
2
in 31254 indicated in Example 5.49 result from the occurrences of the linear
extensions 312 and 125.
© 2010 by Taylor and Francis Group, LLC
166 Combinatorics of Compositions and Words
5.4.1 Enumeration of POPs
We will present the main result given by Kitaev et al. in [111]. Note that
in [111] the focus is on enumerating the number of occurrences of a given
POP ξ among all compositions of n, rather than enumeration of compositions
according to the number of occurrences of ξ within the composition. This
is the same focus as in [50, 51, 76, 77, 87] for the subword patterns 11, 12,
and 21. Kitaev et al. give additional results which we leave for the interested
reader to investigate. To present the results of Kitaev et al. we need the
following notation.
Definition 5.53 For a subword pattern τ from the alphabet [j],letμ
k
be the
number of parts of size k in τ.Thenμ
τ
=(μ
1
,μ
2
,...,μ
j
) is called the content
vector of τ. In addition, let λ
τ
(n) denote the number of compositions that are
order-isomorphic to τ, that is, the reduced form of these compositions equals
τ. The associated generating function is given by Λ
τ
(x)=
n≥0
λ
τ
(n)x
n
.
We will also make use of the following result.
Lemma 5.54 For τ ∈ [j] with content vector μ
τ
,
Λ
τ
(x)=
j
k=1
x
m
k
1 − x
m
k
,
where m
k
= μ
k
+ ···+ μ
j
for 1 ≤ k ≤ j.
Proof See Exercise 5.6. 2
In order to enumerate the number of occurrences of a given POP in all
compositions of n, we first compute a related generating function.
Definition 5.55 For a given POP ξ = ξ
1
ξ
2
···ξ
k
,letω
ξ
(n, , s) denote the
number of occurrences of ξ among the compositions of n with + k parts such
that the sum of the parts preceding the occurrence is s.LetΩ
ξ
(x, y, u) denote
the generating function for ω
ξ
(n, , s), that is,
Ω
ξ
(x, y, u)=
n,l,s≥0
ω
ξ
(n, , s)x
n
y
u
s
.
Theorem 5.56 [111, Theorem 2.1] Let ξ be a POP. Then
Ω
ξ
(x, y, u)=
(1 − x)(1 − xu)
(1 − x − xy)(1 − xu − xyu)
τ
Λ
τ
(x),
where the sum is over all linear extensions τ of ξ.
© 2010 by Taylor and Francis Group, LLC
Avoidance of Nonsubword Patterns in Compositions 167
Proof We first compute Ω
τ
(x, y, u) for a subword pattern τ. Each occur-
rence of τ determines a triple
σ
(1)
,σ
(2)
,σ
(3)
such that σ
(1)
comprises the
parts to the left of the occurrence of τ , the reduced form of σ
(2)
equals τ,
and σ
(3)
comprises the parts to the right of the occurrence. Hence, for given
n, , s ∈ N, ω
ξ
(n, , s) is the number of triples
σ
(1)
,σ
(2)
,σ
(3)
of compositions
such that ord
σ
(1)
+ ord
σ
(2)
+ ord
σ
(3)
= n, ord
σ
(1)
= s, σ
(2)
is order-
isomorphic to τ,andσ
(1)
and σ
(3)
together have parts. Recall that C(m; n)
denotes the number of compositions of n with m parts in N.Thus,
ω
τ
(n, , s)=
0≤j≤
0≤n
≤n−s
C(j; s)λ
τ
(n
)C(l −j; n − s − n
).
From Exercise 2.13, we have that
n≥0
C(m; n)x
n
= x
m
/(1 −x)
m
.Thuswe
can factor Ω
τ
(x, y, u) into a product of Λ
τ
(x) and two geometric series:
Ω
τ
(x, y, u)=
n,,s≥0
ω
τ
(n, , s)x
n
y
u
s
=Λ
τ
(x)
⎛
⎝
s,j≥0
C(j; s)(xu)
s
y
j
⎞
⎠
⎛
⎝
˜n,
˜
≥0
C(
˜
;˜n)x
˜n
y
˜
⎞
⎠
=Λ
τ
(x)
⎛
⎝
j≥0
(xu)
j
(1 − xu)
j
y
j
⎞
⎠
⎛
⎝
˜
≥0
x
˜
(1 − x)
˜
y
˜
⎞
⎠
=Λ
τ
(x)
(1 − xu)(1 − x)
(1 − xu − xyu)(1 − x − xy)
.
Note that for any POP ξ,Ω
ξ
(x, y, u)=
τ
Ω
τ
(x, y, u), where the sum is over
all linear extensions τ of ξ, which completes the proof. 2
Setting y = u = 1 in Theorem 5.56, we obtain a result for the number of
occurrences of a POP ξ in all compositions of n.
Corolla ry 5.57 [111, Corollary 2.2] Given a POP ξ, the number of occur-
rences of ξ among all compositions of n is given by
[x
n
]Ω
τ
(x, 1, 1) = [x
n
]
(1 − x)
2
(1 − 2x)
2
τ
Λ
τ
(x),
where the sum is over all linear extensions τ of ξ.
Example 5.58 We illustrate the use of Corollary 5.57 with two patterns that
we have considered before, namely τ = 112 and ν = 221. The content vector
© 2010 by Taylor and Francis Group, LLC
168 Combinatorics of Compositions and Words
for τ is given by μ
τ
=(2, 1), and the content vector for ν is μ
ν
=(1, 2).
Therefore, by Lemma 5.54,
Λ
τ
(x)=
x
4
(1 − x
3
)(1 − x)
and Λ
ν
(x)=
x
5
(1 − x
3
)(1 − x
2
)
.
The number of levels followed by a rise or drop, respectively, can then be
computed as
[x
n
]
(1 − x)
2
x
4
(1 − 2x)
2
(1 − x
3
)(1 − x)
and [x
n
]
(1 − x)
2
x
5
(1 − 2x)
2
(1 − x
3
)(1 − x
2
)
.
Using Mathematica or Maple, the sequences of values for the number of oc-
currences of either 112 or 221,forn =0, 1,...,20 are found to be 0, 0, 0, 0,
1, 3, 8, 21, 51, 120, 277, 627, 1400, 3093, 6771, 14712, 31765, 68211, 145784,
310293, 658035,and0, 0, 0, 0, 0, 1, 2, 6, 15, 36, 84, 193, 434, 966, 2127,
4644, 10068, 21697, 46514, 99270, 211023, respectively.
Note that we can recover many of the results in Chapter 4, for example, the
gen
erating function for the number of rises and levels given in Example 4.6, by
using Corollary 5.57. However those results just concern individual subword
patterns. To see the full power of POPs, we will now derive the generating
function for the number of peaks.
Example 5.59 A peak is represented by the POP ξ =1
21
, with linear ex-
tensions 121, 132 and 231. These patterns have content vectors (2, 1), (1, 1, 1)
and (1, 1, 1), respectively. We obtain
τ
Λ
τ
(x)=
x
4
(1 − x
3
)(1 − x)
+2
x
6
(1 − x
3
)(1 − x
2
)(1 − x)
,
where the sum is over the linear extensions of ξ. The number of peaks may
then be computed using Maple or Mathematica as 0, 0, 0, 0, 1, 3, 10, 27, 69,
168, 397, 915, 2074, 4635, 10245, 22440, 48781, 105363, 226330, 483867,and
1030149 for n =0, 1,...,20.
In Section 4.3 we derived generating functions for patterns of length ≥ 3
according to order, number of parts and occurrences of τ. We can exploit
these results to derive generating functions for the number of occurrences of
a given pattern τ by using the technique in the proof of Corollary 4.5 (see
Exercise 5.7).
5.4.2 Avoidance of POPs
We will present results on avoidance of two particular classes of POPs in
compositions. These types of patterns were considered for permutations in
[108] and for words in [109].
© 2010 by Taylor and Francis Group, LLC
Avoidance of Nonsubword Patterns in Compositions 169
Definition 5.60 Let {τ
0
,τ
1
,...,τ
s
} be a set of subword patterns. A multi-
pattern is of the form τ = τ
0
–τ
1
– ···–τ
s
and a shuffle pattern is of the form
τ = τ
0
–a
1
–τ
1
–a
2
– ···–τ
s−1
–a
s
–τ
s
, where each letter of τ
i
is incomparable with
any letter of τ
j
whenever i = j. In addition, the letters a
i
are either all greater
or all smaller than any letter of τ
j
for any i and j.
Example 5.61 Let T = {1
, 1
, 2}, that is 1
< 2, 1
< 2,and1
and 1
are
incomparable. Then 1
–2–1
is a shuffle pattern, and 1
–1
is a multi-pattern.
Clearly, we can get a multi-pattern from a shuffle pattern by removing the
letters a
i
.
We begin by deriving the generating function for the simplest shuffle pat-
tern, and then give a more general result.
Example 5.62 Let A = {a
1
,a
2
,...,a
d
} be any ordered set and let τ =
1
–2–1
. Then we have
AC
1
–2–1
A
(x, y)=
1
a∈A
(1 − x
a
y)
2
−
a∈A
x
a
y
a≤b∈A
(1 − x
b
y)
2
. (5.8)
This result follows from the specific structure of the compositions σ that
avoid τ =1
–2–1
.Ifσ avoids τ and contains s>0 copies of the letter a
d
,
then the letters a
d
can only appear as blocks on the left and right end of σ.If
σ contains no a
d
,thenσ ∈AC
A
d−1
n,m
(τ) where A
d−1
= A −{a
d
}. Therefore,
AC
τ
A
(m; x)=
m−1
i=0
(i +1)x
ia
d
AC
τ
A
d−1
(m − i; x)+x
ma
d
, (5.9)
for n ≥ 0,sincethereare(i +1) possibilities to separate i copies of a
d
into
two blocks when i<m, and there is exactly one composition when i = m.To
obtain a recurrence in the sets A
d
, we take second differences and substitute
the expression given in (5.9) for each term. Simplifying the result gives that
AC
τ
A
(m; x) − 2x
a
d
AC
τ
A
(m − 1; x)+x
2a
d
AC
τ
A
(m − 2; x)=AC
τ
A
d−1
(m; x).
Multiplying both sides of this recurrence by y
m
and summing over all m ≥ 2,
together with AC
τ
A
(0; x)=1and AC
τ
A
(1; x)=
a∈A
x
a
y, we obtain a recur-
rence in the generating functions. The stated result then follows by induction
on the number of elements of A, together with the fact that
AC
τ
{a
1
}
(x, y)=
1
1 − x
a
1
y
=
1
(1 − x
a
1
y)
2
−
x
a
1
y
(1 − x
a
1
y)
2
.
Now we look at the shuffle patterns τ––ν and τ –1–ν,where and 1 are
the greatest and smallest elements of the pattern, respectively.
© 2010 by Taylor and Francis Group, LLC
170 Combinatorics of Compositions and Words
Theorem 5.63 Let A = {a
1
,a
2
,...,a
d
} be any ordered set of positive inte-
gers.
1. Let φ be the shuffle pattern τ––ν. Then for all d ≥ ,
AC
φ
A
(x, y)=
AC
φ
A
d−1
(x, y) − x
a
d
yAC
τ
A
d−1
(x, y)AC
ν
A
d−1
(x, y)
(1 − x
a
d
yAC
τ
A
d−1
(x, y))(1 − x
a
d
yAC
ν
A
d−1
(x, y))
.
2. Let ψ be the shuffle pattern τ–1–ν. Then for all d ≥ ,
AC
ψ
A
(x, y)=
AC
ψ
¯
A
1
(x, y) − x
a
1
yAC
τ
¯
A
1
(x, y)AC
ν
¯
A
1
(x, y)
(1 − x
a
1
yAC
τ
¯
A
1
(x, y))(1 − x
a
1
yAC
ν
¯
A
1
(x, y))
.
Proof We derive a recurrence relation for AC
φ
A
(x, y)whereφ = τ––ν.Let
σ ∈AC
A
n,m
(φ)besuchthatitcontainsexactlys copies of the letter a
d
.If
s = 0, then the generating function for the number of such compositions is
AC
φ
A
d−1
(x, y). If s ≥ 1, then σ = σ
(0)
a
d
σ
(1)
a
d
···a
d
σ
(s)
,whereσ
(j)
is a φ-
avoiding composition with parts in A
d−1
for j =0, 1,...,s.Furthermore,
either σ
(j)
avoids τ for all j,orthereexistsaj
0
such that σ
(j
0
)
contains
τ, σ
(j)
avoids τ for all j =0, 1,...,j
0
− 1, and σ
(j)
avoids ν for any j =
j
0
+1,j
0
+2,...,s. In the first case, the generating function for the number
of such compositions is x
sa
d
y
s
%
AC
τ
A
d−1
(x, y)
&
s+1
. In the second case, the
generating function is given by
x
sa
d
y
s
s
j=0
AC
τ
A
d−1
(x, y)
j
%
AC
ν
A
d−1
(x, y)
&
s−j
(AC
φ
A
d−1
(x, y) − AC
τ
A
d−1
(x, y)).
Defining
H(x, y)=
s≥0
x
sa
d
y
s
s
j=0
AC
τ
A
d−1
(x, y)
j
%
AC
ν
A
d−1
(x, y)
&
s−j
,
we obtain that
AC
φ
A
(x, y)=AC
φ
A
d−1
(x, y)+
s≥1
x
sa
d
y
s
%
AC
τ
A
d−1
(x, y)
&
s+1
+(H(x, y) −1)(AC
φ
A
d−1
(x, y) − AC
τ
A
d−1
(x, y))
=
AC
τ
A
d−1
(x, y)
1 − x
a
d
yAC
τ
A
d−1
(x, y)
+ H(x, y)(AC
φ
A
d−1
(x, y) − AC
τ
A
d−1
(x, y)).
© 2010 by Taylor and Francis Group, LLC
Avoidance of Nonsubword Patterns in Compositions 171
Using the identity
n≥0
x
n
n
j=0
p
j
q
n−j
=
(1 − xp)(1 − xq)
−1
gives that
H(x, y)=
1
(1 − x
a
d
yAC
τ
A
d−1
(x, y))(1 − x
a
d
yAC
ν
A
d−1
(x, y))
,
and therefore,
AC
φ
A
(x, y)=
AC
φ
A
d−1
(x, y) − x
a
d
yAC
τ
A
d−1
(x, y)AC
ν
A
d−1
(x, y)
(1 − x
a
d
yAC
τ
A
d−1
(x, y))(1 − x
a
d
yAC
ν
A
d−1
(x, y))
,
which gives the first result. Replacing a
d
by a
1
and using similar arguments,
we obtain the second result. 2
Example 5.64 We can use Theorem 5.63 to recover the result of Example
5.62 for φ =1
–2–1
.SinceAC
1
A
(x, y)=1, the recurrence reduces to
AC
φ
A
(x, y)=
AC
φ
A
d−1
(x, y) − x
a
d
y
(1 − x
a
d
y)
2
,
which can be easily iterated and leads to the explicit formula given in (5.8).
We now give two corollaries to Theorem 5.63. The first one tells us that we
can reverse the letters within the two outside patterns, whereas the second
one allows for a swap of patterns. We therefore obtain Wilf-equivalence for a
whole family of patterns. (Note that the definition of Wilf-equivalence given
in Definition 5.2 also includes POPs.) The proofs are left as Exercise 5.8.
Corolla ry 5.65 Let φ = τ––ν (respectively φ = τ–1–ν) be a shuffle pat-
tern, and let f(φ)=f
1
(τ)––f
2
(ν)(respectively f(φ)=f
1
(τ)–1–f
2
(ν)),where
f
1
,f
2
∈{R, I} are any trivial bijections (the reversal map or the identity).
Then φ ∼ f(φ).
Corolla ry 5.66 For any shuffle pattern τ––ν (respectively τ–1–ν) we have
that
τ––ν ∼ ν––τ (respectively τ–1–ν ∼ ν–1–τ).
Example 5.67 Using these two corollaries, we obtain for example that
1
2
3
–4–2
1
1
∼ 1
2
3
–4–1
1
2
∼ 1
1
2
–4–1
2
3
.
We now look at the second class of patterns, multi-patterns. As before, the
generating function can be easily computed for simple multi-patterns, and we
give an example for the simplest such pattern.
© 2010 by Taylor and Francis Group, LLC
172 Combinatorics of Compositions and Words
Example 5.68 The simplest nontrivial example of a multi-pattern is the pat-
tern φ =1
–1
2
. Avoiding φ is the same as avoiding the patterns 1–12, 1–23,
2–12, 2–13,and3–12 simultaneously. To count the number of compositions
in AC
A
n,m
(1
–1
2
), we split up the composition: the first letter can be any-
thing, and the rest of the composition has to avoid 12. Using Example 2.65,
we obtain that
AC
1
–1
2
A
(x, y)=1+
y
a∈A
x
a
a∈A
(1 − x
a
y)
.
In order to prove general results for multi-patterns (and other POPs), it
is convenient to introduce the notion of quasi-avoidance, which embodies
what happens when creating compositions in a recursive manner. Specifi-
cally, adding a part at the end of a composition that avoids the pattern τ can
create an single occurrence of τ in the rightmost parts of the composition.
Definition 5.69 Let τ be a subword pattern. A sequence (composition, word,
or partition) σ quasi-avoids τ if σ has exactly one occurrence of τ and this oc-
currence consists of the |τ| rightmost parts of σ,where|τ| denotes the number
of letters in τ.
Example 5.70 The composition 4112234 quasi-avoids the pattern 1123,while
the compositions 5223411 and 1123346 do not.
Lemma 5.71 Let τ be a nonempty subword pattern. Let QC
τ
A
(x, y) denote
the generating function for the number of compositions in C
A
n,m
that quasi-
avoid τ.Then
QC
τ
A
(x, y)=1+AC
τ
A
(x, y)
y
a∈A
x
a
− 1
. (5.10)
Proof Adding the part a to the right end of a composition with m −1parts
that avoids τ creates either a composition with m parts that still avoids τ or
one that quasi-avoids τ.Thus,form ≥ 1,
QC
τ
A
(m; x)=
a∈A
x
a
AC
τ
A
(m − 1; x) − AC
τ
A
(m; x).
Multiplying both sides of this equality by y
m
and summing over all natural
numbers m we get the desired result. 2
We now obtain a general theorem that is a good auxiliary tool for calculating
the generating function for the number of compositions that avoid a given
POP, which we will apply specifically to shuffle patterns.
Theorem 5.72 Suppose τ = τ
–φ,whereφ is an arbitrary POP, and the
letters of τ
are incomparable with the letters of φ.Then
AC
τ
A
(x, y)=AC
τ
A
(x, y)+QC
τ
A
(x, y)AC
φ
A
(x, y).
© 2010 by Taylor and Francis Group, LLC
Avoidance of Nonsubword Patterns in Compositions 173
Proof In order to find AC
τ
A
(x, y), we observe that there are two possibilities:
either σ avoids τ
or σ does not avoid τ
. In the first case the generating
function is given by AC
τ
A
(x, y). If σ does not avoid τ
then we can write σ
in the form σ = σ
(1)
σ
(2)
σ
(3)
,whereσ
(1)
σ
(2)
quasi-avoids the pattern τ
and
σ
(2)
is order-isomorphic to τ
. Clearly, σ
(3)
must avoid φ. So the generating
function is equal to QC
τ
A
(x, y)AC
φ
A
(x, y) and we obtain the stated result. 2
Applying Lemma 5.71 and Theorem 5.72 to multi-patterns, we obtain the
following theorem. The proof is left as Exercise 5.9.
Theorem 5.73 Let τ = τ
1
–τ
2
– ···–τ
s
be a multi-pattern. Then
AC
τ
A
(x, y)=
s
j=1
AC
τ
j
A
(x, y)
j−1
i=1
y
a∈A
x
a
− 1
AC
τ
i
A
(x, y)+1
. (5.11)
Example 5.74 We can easily obtain the result of Example 5.68 from The-
orem 5.73. Since AC
12
A
(x, y)=
a∈A
(1 − x
a
y)
−1
and AC
1
A
(x, y)=1,the
result follows. For an example that is more difficult to obtain directly, let
τ = τ
1
–τ
2
– ···–τ
s
be a multi-pattern such that τ
j
is equal to either 12 or 21,
for j =1, 2,...,s. Then Theorem 5.73 gives
AC
τ
A
(x, y)=
1 −
1+
y
a∈A
x
a
− 1
a∈A
(1 − x
a
y)
s
1 − y
a∈A
x
a
.
We now give results for a whole family of patterns. The first result concerns
reversal of the individual patterns, while the second one gives Wilf-equivalence
for the permutations of the subword patterns that make up the multi-pattern.
Theorem 5.75 Let τ
0
and τ
1
be multi-patterns, τ = τ
0
–τ
1
,andf
1
and f
2
be
any trivial bijections. Then τ ∼ f
1
(τ
0
)–f
2
(τ
1
).
Proof We first show that τ
0
–τ
1
∼ τ
0
–f(τ
1
), where f is one of the trivial
bijections. If σ avoids τ
0
–τ
1
then either σ has no occurrence of τ
0
and therefore
σ also avoids τ
0
–f(τ
1
), or σ can be written as σ = σ
(1)
σ
(2)
σ
(3)
,whereσ
(1)
σ
(2)
has exactly one occurrence of τ
0
,namelyσ
(2)
.Thenσ
(3)
must avoid τ
1
,so
f(σ
(3)
)avoidsf (τ
1
), which implies that σ
f
= σ
(1)
σ
(2)
f(σ
(3)
)avoidsτ
0
-f(τ
1
).
The converse is also true, giving a bijection between the set of compositions
avoiding τ and the set of those avoiding τ
0
-f(τ
1
). This result and properties
of trivial bijections give the desired equivalence. 2
Repeated use of Theorem 5.75 allows us to show equivalence of multi-
patterns that are permutations of each other. Before stating the general
result, we will give an example. To avoid drowning in a sea of primes we
useˆand˜to mark letters that can be compared instead of using
and
.
© 2010 by Taylor and Francis Group, LLC
174 Combinatorics of Compositions and Words
Example 5.76 Consider the multi-pattern τ =1
2
–
˜
1
˜
2
˜
2–
ˆ
1
ˆ
2.Supposewe
want to switch the first and last parts of the multi-pattern. This can be
achieved by using the reversal operation on appropriate parts (shown in bold
font) of the multi-pattern:
τ =1
2
–
˜
1
˜
2
˜
2–
ˆ
1
ˆ
2 ∼ 1
2
–
ˆ
2
ˆ
1–
˜
2
˜
2
˜
1 ∼ 1
2
–
ˆ
2
ˆ
1–
˜
1
˜
2
˜
2
∼
˜
2
˜
2
˜
1–
ˆ
1
ˆ
2–2
1
∼
ˆ
2
ˆ
1–
˜
1
˜
2
˜
2–2
1
∼
ˆ
2
ˆ
1–
˜
1
˜
2
˜
2–1
2
∼
ˆ
1
ˆ
2–
˜
1
˜
2
˜
2–1
2
.
Corolla ry 5.77 Suppose we have multi-patterns τ = τ
1
–τ
2
– ···–τ
s
and φ =
φ
1
–φ
2
– ···–φ
s
,whereτ
1
τ
2
···τ
s
is a permutation of φ
1
φ
2
···φ
s
.Thenτ ∼ φ.
Proof See Exercise 5.10. 2
We conclude the section on POPs with an application of Theorem 5.73.
Definition 5.78 Let τ be an arbitrary subword pattern and let σ be a compo-
sition. We say that two patterns overlap in σ if they contain any of the same
letters of σ. Wedenotebyτ–nlap(σ) the maximum number of nonoverlapping
occurrences of τ in σ.
Example 5.79 The simplest subword pattern is a drop or descent in a com-
position, which occurs at position i if σ
i
>σ
i+1
. Clearly, two descents at
positions i and j overlap if j = i +1. In particular, we can define the statistic
maximum number of nonoverlapping descents,orMND, in a composition.
For example, MND(333211) = 1 whereas MND(13321111432111) = 3 (namely
either 32 or 21, together with 43 and 21).
Obviously, this statistic, maximum number of nonoverlapping patterns, can
be defined for any subword pattern τ. Using Theorem 5.73 for the multi-
pattern τ–τ – ···–τ allows us to obtain the generating function for the entire
distribution of the maximum number of nonoverlapping occurrences of a pat-
tern τ in compositions.
Theorem 5.80 For A = {a
1
,...,a
d
} andasubwordpatternτ, we have
n,m≥0
σ∈C
A
n,m
q
τ –nlap(σ)
x
n
y
m
=
AC
τ
A
(x, y)
1 − q
0
y
a∈A
x
a
− 1
AC
τ
A
(x, y)+1
1
.
Proof Let Φ
s
be the multi-pattern τ–τ – ···–τ consisting of s copies of τ.If
σ ∈AC
A
n,m
(Φ
s
), then it has at most s − 1 nonoverlapping occurrences of τ.
Theorem 5.73 yields
AC
Φ
s
A
(x, y)=
s
j=1
AC
τ
A
(x, y)
j−1
i=1
y
a∈A
x
a
− 1
AC
τ
A
(x, y)+1
.
© 2010 by Taylor and Francis Group, LLC