Heubach S., Mansour T. Combinatorics of Compositions and Words
Подождите немного. Документ загружается.
104 Combinatorics of Compositions and Words
at least one occurrence, then we need to look at three cases for the first occur-
rence of a
d
. If the first occurrence is at the beginning of the composition, that
is, σ = a
d
σ
,whereσ
is a (possibly empty) composition with parts in A,then
no peak occurs, and the generating function is given by x
a
d
yC
peak
A
(x, y, q). If
the first (and only) occurrence of a
d
is at the end of the composition, that is,
σ =¯σa
d
,where¯σ is a nonempty composition with parts in A
d−1
, then the
generating function is given by x
a
d
y(C
peak
A
d−1
(x, y, q)−1). Finally, if the first oc-
currence of a
d
is in the interior of the composition, then σ = σ
(1)
a
d
σ
(2)
,where
σ
(1)
and σ
(2)
are nonempty compositions with parts in A
d−1
and A, respec-
tively. Furthermore, if σ
(2)
starts with a
d
,thenσ = σ
(1)
a
d
a
d
σ
(3)
,andboth
parts a
d
can be split off without decreasing the number of occurrences of peaks;
the generating function is given by (C
peak
A
d−1
(x, y, q) −1)x
2a
d
y
2
C
peak
A
(x, y, q). If
σ
(2)
does not start with a
d
, then a peak occurs and the generating function
is given by
(C
peak
A
d−1
(x, y, q) −1
,
-. /
σ
(1)
nonempty
)x
a
d
yq(C
peak
A
(x, y, q) −1
,
-. /
σ
(2)
nonempty
−x
a
d
yC
peak
A
(x, y, q)
,
-. /
does not start with a
d
).
Now, let C
A
= C
peak
A
(x, y, q). Combining the five cases above, we obtain
C
A
= C
A
d−1
+ x
a
d
yC
A
+ x
a
d
y (C
A
d−1
− 1) + x
2a
d
y
2
C
A
(C
A
d−1
− 1)
+ x
a
d
yq(C
A
− 1 − x
a
d
yC
A
)(C
A
d−1
− 1),
or, equivalently,
C
A
=
(1 + x
a
d
y(1 − q))C
A
d−1
− x
a
d
y(1 − q)
1 − x
a
d
y(1 − x
a
d
y)(1 − q) − x
a
d
y(x
a
d
y(1 − q)+q)C
A
d−1
=
1
1 − x
a
d
y −
C
A
d−1
− 1
(1 + x
a
d
y(1 − q))C
A
d−1
− x
a
d
y(1 − q)
=
1
1 − x
a
d
y −
1
[x
a
d
y(1 − q), 1 − 1/C
A
d−1
]
,
where [x
a
d
y(1 − q), 1 − 1/C
A
d−1
] is a finite continued fraction. Hence, by
induction on d and using the fact that C
A
1
=
1
1−x
a
1
y
, we obtain the desired
result for C
peak
A
(x, y, q). 2
Note that the proof given above assumes that d is finite. A similar continued
fraction expression can be obtained for C
valley
A
(x, y, q) (see Exercise 4.13).
Before we can state the explicit result for the respective generating functions
for the patterns peak and valley, we need some notation. For any set B ⊆ A
© 2010 by Taylor and Francis Group, LLC
Statistics on Compositions 105
and for s ≥ 1, we define
P
s
(B)={(i
1
,...,i
s
)|a
i
j
∈ B, j =1,...,s, and
i
2−1
<i
2
≤ i
2+1
for 1 ≤ ≤s/2},
Q
s
(B)={(i
1
,...,i
s
)|a
i
j
∈ B, j =1,...,s, and
i
2−1
≤ i
2
<i
2+1
for 1 ≤ ≤s/2},
M
s
(B)=
(i
1
,...,i
s
)∈P
s
(B)
s
j=1
b
i
j
and N
s
(B)=
(i
1
,...,i
s
)∈Q
s
(B)
s
j=1
b
i
j
,
where b
i
j
= x
a
i
j
y.
Theorem 4.26 Let A = {a
1
,...,a
d
},andletP
s
(A), Q
s
(A), M
s
(A),and
N
s
(A) be defined as above. Then
C
peak
A
(x, y, q)=
1+
j≥1
M
2j
(A)(1 − q)
j
1+
j≥1
M
2j
(A)(1 −q)
j
−
j≥0
M
2j+1
(A)(1 − q)
j
and
C
valley
A
(x, y, q)=
1+
j≥1
M
2j
(A)(1 −q)
j
1+
j≥1
M
2j
(A)(1 −q)
j
−
j≥0
N
2j+1
(A)(1 −q)
j
.
Proof We derive an explicit formula for C
peak
A
(x, y, q) based on recursions
for M
s
(A
d
)=M
s
(A) for odd and even s;ifs is odd, both the last and
second-to-last elements can equal a
d
,whereasforevens, the second-to-last
element can be at most a
d−1
. By separating the elements of P
s
(A) according
to whether the last element equals a
d
or is less than a
d
, we get the following
two recursions:
M
2s+1
(A)=b
d
M
2s
(A)+M
2s+1
(A
d−1
), (4.12)
M
2s
(A)=b
d
M
2s−1
(A
d−1
)+M
2s
(A
d−1
).
Let G
d
=1/[b
d
(1 − q),b
d−1
,b
d−1
(1 − q),...,b
2
,b
2
(1 − q),b
1
], that is, G
d
con-
sists of that portion of C
A
in the continued fraction expansion which has a
repeating pattern. Using induction, we first show that for d ≥ 2,
G
d
=
j≥0
M
2j+1
(A
d−1
)(1 − q)
j
1+
j≥1
M
2j
(A)(1 −q)
j
=
G
1
d−1
G
2
d
. (4.13)
For d =2,G
1
1
= b
1
(only the term j = 0 contributes), G
2
2
=1+b
1
b
2
(1 −q)
(only the term j = 1 contributes) and therefore, the induction hypothesis is
true. Now let d ≥ 3 and assume that the hypothesis holds for d − 1, that is,
G
d−1
=
G
1
d−2
G
2
d−1
. From the definition of G
d
it is easy to see that
G
d
=1/[b
d
(1 − q),b
d−1
+ G
d−1
].
© 2010 by Taylor and Francis Group, LLC
106 Combinatorics of Compositions and Words
Substituting the induction hypothesis for d −1intothisrecursionforG
d
and
simplifying yields
G
d
=
b
d−1
G
2
d−1
+ G
1
d−2
G
2
d−1
+ b
d
(1 − q)(b
d−1
G
2
d−1
+ G
1
d−2
)
.
Using the definitions for G
1
d−2
and G
2
d−1
in (4.13) together with (4.12) yields
b
d−1
G
2
d−1
+ G
1
d−2
= G
1
d−1
.
This result together with the definitions of G
1
d−2
and G
2
d−1
and another ap-
plication of (4.12) gives G
2
d−1
+ b
d
(1 − q)(b
d−1
G
2
d−1
+ G
1
d−2
)=G
2
d
,which
completes the proof of (4.13). Now we use (4.13) and C
A
=
1
1−b
d
−G
d
to get
(after simplification) that
C
A
=
1
1 − b
d
−
G
1
d−1
G
2
d
=
G
2
d
G
2
d
− (b
d
G
2
d
+ G
1
d−1
)
=
G
2
d
G
2
d
− G
1
d
=
1+
j≥1
M
2j
(A)(1 −q)
j
1+
j≥1
M
2j
(A)(1 −q)
j
−
j≥0
M
2j+1
(A)(1 −q)
j
.
This completes the proof for the pattern peak since the formula also holds
for the case d = ∞. The result for the pattern valley follows with minor
modifications, focusing on the smallest rather than the largest part, replacing
A
k
with
¯
A
k
, and using the recursions
M
s
(
¯
A
k
)=b
k+1
N
s−1
(
¯
A
k+1
)+M
s
(
¯
A
k+1
)
and
N
s
(
¯
A
k
)=b
k+1
M
s−1
(
¯
A
k
)+N
s
(
¯
A
k+1
),
which are obtained by separating the elements of P
s
(
¯
A
k
) according to whether
the first element equals a
k+1
or is greater than a
k+1
. 2
We now apply Theorem 4.26 to A = N.
Example 4.27 To determine the generating function for the compositions of
n, we first compute the specific expressions for M
s
(N) and N
s
(N) for s ≥ 1.
In each case, we have terms of the form
i
s−1
<i
s
x
i
s
or
i
s−1
≤i
s
x
i
s
which
we rewrite as
j≥1
x
i
s−1
+j
or
j≥0
x
i
s−1
+j
to successively reduce the sums.
© 2010 by Taylor and Francis Group, LLC
Statistics on Compositions 107
We obtain
M
2s
(N)=
1≤i
1
i
1
<i
2
···
i
2s−2
≤i
2s−1
i
2s−1
<i
2s
x
i
1
+···+i
2s
y
2s
=
x
1 − x
y
2s
1≤i
1
i
1
<i
2
···
i
2s−3
<i
2s−2
i
2s−2
≤i
2s−1
x
i
1
+···+i
2s−2
+2 i
2s−1
=
x
(1 − x)
1
(1 − x
2
)
y
2s
1≤i
1
i
1
<i
2
···
i
2s−3
<i
2s−2
x
i
1
+···+i
2s−3
+3 i
2s−2
= ···=
x
1+3+···+2s−3
y
2s
(1 − x)(1 −x
2
) ···(1 − x
2s−2
)
1≤i
1
i
1
<i
2
x
i
1
+(2s−1) i
2
=
x
1+3+···+(2s−3)+(2s−1)
y
2s
(1 − x)(1 −x
2
) ···(1 − x
2s−1
)
1≤i
1
x
2si
1
=
x
1+3+···+(2s−3)+(2s−1)
x
2s
y
2s
(1 − x)(1 −x
2
) ···(1 − x
2s
)
=
x
s(s+2)
y
2s
2s
i=1
(1 − x
i
)
.
Likewise, we obtain that
M
2s+1
(N)=
1≤i
1
i
1
<i
2
i
2
≤i
3
···
i
2s−1
<i
2s
i
2s
≤i
2s+1
x
i
1
+···+i
2s+1
y
2s+1
=
x
2+4+···+(2s−2)+(2s)
x
(2s+1)
y
2s+1
(1 − x)(1 −x
2
) ···(1 − x
2s+1
)
=
x
s
2
+3s+1
y
2s+1
2s+1
i=1
(1 − x
i
)
and
N
2s+1
(N)=
1≤i
1
i
1
≤i
2
i
2
<i
3
···
i
2s−1
≤i
2s
i
2s
<i
2s+1
x
i
1
+···+i
2s+1
y
2s+1
=
x
(s+1)
2
y
2s+1
2s+1
i=1
(1 − x
i
)
.
Substituting these expressions into Theorem 4.26 and setting y =1and
q =0gives the generating functions for the number of compositions of n
without peaks and without valleys, respectively, as
C
peak
N
(x, 1, 0) =
1+
j≥1
x
j(j+2)
2j
i=1
(1 − x
i
)
1+
j≥1
x
j(j+2)
2j
i=1
(1 − x
i
)
−
j≥0
x
j
2
+3j+1
2j+1
i=1
(1 − x
i
)
© 2010 by Taylor and Francis Group, LLC
108 Combinatorics of Compositions and Words
and
C
valley
N
(x, 1, 0) =
1+
j≥1
x
j(j+2)
2j
i=1
(1 − x
i
)
1+
j≥1
x
j(j+2)
2j
i=1
(1 − x
i
)
−
j≥0
x
(j+1)
2
2j+1
i=1
(1 − x
i
)
.
We approximate the respective generating function by using finite sums (up
to j = 20) in either the Mathematica function Series or the Maple function
taylor. The sequence for the number of peak-avoiding compositions with parts
in N for n =0to n =20is given by 1, 1, 2, 4, 7, 13, 22, 38, 64, 107, 177, 293,
481, 789, 1291, 2110, 3445, 5621, 9167, 14947 and 24366.Thecorresponding
sequence for valley-avoiding compositions is given by 1, 1, 2, 4, 8, 15, 28, 52,
96, 177, 326, 600, 1104, 2032, 3740, 6884, 12672, 23327, 42942, 79052 an
d
145528. Note that the first time a peak occurs is for n =4(as the composition
121), while the first time a valley can occur is for n =5(as the composition
212).
Even though the statistics peak and valley are in some sense symmetric, one
cannot obtain the number of valley-avoiding compositions from the number of
peak-avoiding compositions with parts in N. However there is a connection.
The number of valleys in compositions of n with m partsisequaltothe
number of peaks in compositions of m(n +1)− n with m parts. This can be
easily seen as follows: in each composition of n with m parts, replace each
part σ
i
by (n +1)− σ
i
, which results in a composition of
m(n +1)−
m
i=1
σ
i
= m(n +1)−n.
This connection will be important in Chapter 6 when we apply results derived
for various patterns in compositions to words on k letters.
4.3.2 The pattern 123
We now derive the generating function for the number of compositions of
n with m parts in A that contain the pattern 123 exactly r times. This is the
first type of pattern in which we have to employ a different method. Unlike
in the case of the pattern peak, where splitting up the composition according
to the largest part and checking whether both neighbors were smaller was
enough to produce a recursion, we will now have to keep a “memory” of the
parts to be split off. This situation, common for patterns of length three
or more, prompts us to define an auxiliary function that keeps track of the
number of occurrences of τ in an augmented sequence.
© 2010 by Taylor and Francis Group, LLC
Statistics on Compositions 109
Definition 4.28 Let A = {a
1
,...,a
d
} be any ordered subset of N and let
D
τ
A
(x, y, q)=
σ∈C
A
x
ord ( σ)
y
par( σ)
q
occ
τ
(ˆσ)
be the generating function for the number of compositions σ according to the
order and number of parts of σ and the number of occurrences of τ in the
augmented sequence ˆσ,whereˆσ is of the form aσ or σb for values of a and b
that depend on the specific pattern τ under consideration.
We first derive an explicit expression for D
123
A
(x, y, q).
Lemma 4.29 Let A = {a
1
,...,a
d
} be any ordered subset of N and let
t
p
(A)=
1≤i
1
<i
2
<···<i
p
≤d
y
p
p
j=1
x
a
i
j
for p =1,...,d.Then
D
123
A
=
1+
d
p=2
p−2
j=0
p−2
j
t
p+j
(A)(q − 1)
p−1
1 − t
1
(A) −
d
p=3
p−3
j=0
p−3
j
t
p+j
(A)(q − 1)
p−2
, (4.14)
where ˆσ = aσ for any integer a<a
1
.
Proof Let τ = 123. We derive an expression for D
τ
¯
A
1
(x, y, q) by considering
compositions σ with parts in
¯
A
1
such that a
1
σ contains the pattern τ exactly
r times. If σ does not contain the part a
2
, then the generating function for σ
is given by D
τ
¯
A
2
(x, y, q). Otherwise, we write
σ = σ
(1)
a
2
σ
(2)
a
2
σ
(3)
···a
2
σ
(+2)
with ≥ 0, where σ
(j)
is a (possibly empty) composition with parts in
¯
A
2
for
j =1,...,+ 2. There are four subcases, depending on whether σ
(1)
and σ
(2)
are empty compositions or not. If σ
(1)
and σ
(2)
are both empty compositions,
then a
1
σ = a
1
a
2
or a
1
σ = a
1
a
2
a
2
σ
(3)
···a
2
σ
(+2)
, ≥ 1. In either case we
can split off the first a
2
of σ, which results in one less part, but no reduction
in the number of occurrences of the pattern τ. Thus, the generating function
for σ is given by
x
a
2
y
≥0
(x
a
2
yD
τ
¯
A
2
(x, y, q))
=
x
a
2
y
1 − x
a
2
yD
τ
¯
A
2
(x, y, q)
.
If σ
(1)
is the empty composition and σ
(2)
is nonempty, then a
1
σ = a
1
a
2
σ
(2)
or a
1
σ = a
1
a
2
σ
(2)
a
2
σ
(3)
···a
2
σ
(+2)
, ≥ 1, and the generating function for σ
is given by
x
a
2
yq(D
τ
¯
A
2
(x, y, q) −1)
≥0
(x
a
2
yD
τ
¯
A
2
(x, y, q))
=
x
a
2
yq(D
τ
¯
A
2
(x, y, q) −1)
1 − x
a
2
yD
τ
¯
A
2
(x, y, q)
.
© 2010 by Taylor and Francis Group, LLC
110 Combinatorics of Compositions and Words
If σ
(1)
is nonempty and σ
(2)
is the empty composition, then σ = σ
(1)
a
2
or
σ = σ
(1)
a
2
a
2
σ
(3)
···a
2
σ
(+2)
, ≥ 1, and the generating function for σ is given
by
x
a
2
y(D
τ
¯
A
2
(x, y, q) −1)
≥0
(x
a
2
yD
τ
¯
A
2
(x, y, q))
=
x
a
2
y(D
τ
¯
A
2
(x, y, q) −1)
1 − x
a
2
yD
τ
¯
A
2
(x, y, q)
.
Finally, if both σ
(1)
and σ
(2)
are nonempty, then the generating function for
σ is given by
x
a
2
y(D
τ
¯
A
2
(x, y, q) −1)
2
1 − x
a
2
yD
τ
¯
A
2
(x, y, q)
.
Adding all four cases, using the shorthand D
A
for D
τ
A
(x, y, q), and solving for
D
¯
A
1
we obtain that
D
¯
A
1
=
(1 − x
a
2
y(1 − q))D
¯
A
2
+ x
a
2
y(1 − q)
1 − x
a
2
yD
¯
A
2
. (4.15)
From this recurrence relation for the generating functions D
¯
A
i
we want to
derive an explicit expression for D
A
. To do this, we give an interpretation of
t
p
(
¯
A
k
) as the generating function for the number of partitions with p distinct
parts from the set
¯
A
k
. These partitions either contain the part a
k+1
or not.
In the first case, the generating function is given by x
a
k+1
yt
p−1
(
¯
A
k+1
), and
in the second case, by t
p
(
¯
A
k+1
). Thus,
t
p
(
¯
A
k
)=t
p
(
¯
A
k+1
)+x
a
k+1
yt
p−1
(
¯
A
k+1
). (4.16)
We now prove (4.14) by induction on d, the number of elements in A.For
d =0andd =1wehaveD
∅
=1andD
{a
1
}
=
n≥0
x
n·a
1
y
n
=1/(1 − x
a
1
y),
respectively, and thus, (4.14) holds. Now assume that (4.14) holds for d − 1
and define s
A
(i, d)=
d
p=i
p−i
j=0
p−i
j
t
p+j
(A)(q − 1)
p−i+1
. Note that the
second parameter of s
A
(i, d) indicates the number of elements in the set A,
and that the powers of (q −1) range from 1 to d − i + 1. With this notation,
the induction hypothesis becomes D
A
=
1+s
A
(2,d)
1−t
1
(A)−s
A
(3,d)
. Using the recursion
(4.15) together with the induction hypothesis for the set
¯
A
1
gives
D
A
=
(1 − x
a
1
y(1 − q))D
¯
A
1
+ x
a
1
y(1 − q)
1 − x
a
1
yD
¯
A
1
=
(1 − x
a
1
y(1 − q))(1 + s
¯
A
1
(2,d− 1))
1 − t
1
(
¯
A
1
) − s
¯
A
1
(3,d− 1) − x
a
1
y(1 + s
¯
A
1
(2,d− 1))
+
x
a
1
y(1 − q)(1 − t
1
(
¯
A
1
) − s
¯
A
1
(3,d− 1))
1 − t
1
(
¯
A
1
) − s
¯
A
1
(3,d− 1) − x
a
1
y(1 + s
¯
A
1
(2,d− 1))
=
f
1
f
2
.
© 2010 by Taylor and Francis Group, LLC
Statistics on Compositions 111
We first expand the denominator and obtain that
f
2
=1− t
1
(
¯
A
1
) − x
a
1
y −
d−1
p=3
p−3
j=0
p−3
j
t
p+j
(
¯
A
1
)(q − 1)
p−2
−
d−1
p=2
p−2
j=0
p−2
j
x
a
1
yt
p+j
(
¯
A
1
)(q − 1)
p−1
.
Combining the two double sums by reindexing the second one, adding the
terms for p = d to the first one (note that t
d+j
(
¯
A
1
)=0forj ≥ 0) and
applying (4.16) twice gives f
2
=1− t
1
(A) − s
A
(3,d). Next we expand the
numerator and simplify to obtain that
f
1
=1+x
a
1
y(q − 1)t
1
(
¯
A
1
)+s
¯
A
1
(2,d− 1)
+ x
a
1
y(q − 1)(s
¯
A
1
(2,d− 1) + s
¯
A
1
(3,d− 1)).
We now collect terms according to powers of (q−1). For m = 0, the coefficient
is 1. If m =1,then[q − 1]f
1
is given by x
a
1
yt
1
(
¯
A
1
)+t
2
(
¯
A
1
)=t
2
(A)by
(4.16). If m =2, 3,...,d− 1, then the coefficient of (q −1)
m
is equal to
m−1
j=0
m−1
j
t
m+1+j
(
¯
A
1
)+x
a
1
y
m−2
j=0
m−2
j
(t
m+j
(
¯
A
1
)+t
m+1+j
(
¯
A
1
))
=
m−1
j=0
m−1
j
t
m+1+j
(
¯
A
1
)+x
a
1
y
m−1
j=0
%
m−2
j
+
m−2
j−1
&
t
m+j
(
¯
A
1
)
by reindexing the second term in the second sum and using that
m−2
−1
=
m−2
m−1
=0. Since
a
b−1
+
a
b
=
a+1
b
,wegetthat
[(q − 1)
m
]f
1
=
m−1
j=0
m−1
j
t
m+1+j
(
¯
A
1
)+x
a
1
y
m−1
j=0
m−1
j
t
m+j
(
¯
A
1
)
=
m−1
j=0
m−1
j
t
m+1+j
(
¯
A
1
)+x
a
1
yt
m+j
(
¯
A
1
)
=
m−1
j=0
m−1
j
t
m+j+1
(A),
where the last equality follows once more from using (4.16). Thus,
f
1
=1+t
2
(A)(q − 1) +
d−1
m=2
m−1
j=0
m−1
j
t
m+j+1
(A)(q − 1)
m
=1+s
A
(2,d)
© 2010 by Taylor and Francis Group, LLC
112 Combinatorics of Compositions and Words
after reindexing. Combining this result with the result for f
2
completes the
proof of the lemma. 2
We are now ready to derive an explicit expression for C
123
A
(x, y, q).
Theorem 4.30 Let A = {a
1
,...,a
d
} be any ordered subset of N.Then,
C
123
A
(x, y, q)=
1
1 − t
1
(A) −
d
p=3
p−3
j=0
p−3
j
t
p+j
(A)(q − 1)
p−2
,
where t
p
(A)=
1≤i
1
<i
2
<···<i
p
≤d
y
p
p
j=1
x
a
i
j
for p =1,...,d.
Proof Let σ be any composition of n with m parts in A = {a
1
,...,a
d
}
that contains the pattern τ = 123 exactly r times. For any composition σ
with parts in A, there are two possibilities: either σ does not contain a
1
,in
which case the generating function is given by C
τ
¯
A
1
(x, y, q), or the composition
contains at least one occurrence of a
1
,thatis,σ =¯σa
1
σ
,where¯σ is a
composition in
¯
A
1
and σ
has parts in A. In this case, the generating function
is given by
C
τ
¯
A
1
(x, y, q)C
τ
A
(a
1
|x, y, q).
All together, we have
C
τ
A
(x, y, q)=C
τ
¯
A
1
(x, y, q)+C
τ
¯
A
1
(x, y, q)C
τ
A
(a
1
|x, y, q). (4.17)
Now let us consider the compositions σ of n with m parts in A starting with a
1
that contain the pattern τ exactly r times. Again, there are two cases: either
σ contains exactly one occurrence of a
1
, or the part a
1
occurs at least twice
in σ. In the first case, the generating function is given by x
a
1
yD
τ
¯
A
1
(x, y, q).
If σ contains a
1
at least twice, then we decompose the composition according
to the second occurrence of a
1
,thatis,σ = a
1
¯σa
1
σ
,where¯σ is a (possibly
empty) composition with parts from
¯
A
1
. Splitting off the initial part a
1
results
in the generating function x
a
1
yD
τ
¯
A
1
(x, y, q) C
τ
A
(a
1
|x, y, q). Thus,
C
τ
A
(a
1
|x, y, q)=x
a
1
yD
τ
¯
A
1
(x, y, q)+x
a
1
yD
τ
¯
A
1
(x, y, q)C
τ
A
(a
1
|x, y, q).
Solving for C
τ
A
(a
1
|x, y, q) and substituting the result into (4.17), together with
Lemma 4.29 gives
C
τ
A
(x, y, q)=
C
τ
¯
A
1
(x, y, q)
1 − x
a
1
yD
τ
¯
A
1
(x, y, q)
=
C
τ
¯
A
1
(x, y, q)
1 − x
a
1
y
1+s
¯
A
1
(2,d− 1)
1 − t
1
(
¯
A
1
) − s
¯
A
1
(3,d− 1)
.
Using the same arguments as in the proof of Lemma 4.29 yields that
C
τ
A
(x, y, q)=C
τ
¯
A
1
(x, y, q)
1 − t
1
(
¯
A
1
) − s
¯
A
1
(3,d− 1)
1 − t
1
(A) − s
A
(3,d)
.
© 2010 by Taylor and Francis Group, LLC
Statistics on Compositions 113
Iterating this equation and using that C
τ
¯
A
d
(x, y, q)=C
τ
∅
(x, y, q)=1results
in
C
τ
A
(x, y, q)=
d−1
k=0
1 − t
1
(
¯
A
k+1
) − s
¯
A
k+1
(3,d− k − 1)
1 − t
1
(
¯
A
k
) − s
¯
A
k
(3,d− k)
.
Simplification together with t
p
(
¯
A
d
)=t
p
(∅) = 0 completes the proof. 2
Example 4.31 To apply Theorem 4.30 to A = N, we first show that
t
p
(N)=x
(
p+1
2
)
y
p
/(x; x)
p
,
where we use the customary notation (a; q)
n
=
n−1
j=0
(1−aq
j
). The derivation
of the expression for t
p
(N) is similar to the one in Example 4.27. However,
we now have only strict inequalities for the indices in the summation, and
therefore all powers, as opposed to only odd powers, occur in the numerator.
Clearly, the formula for t
p
(N) holds for p =0. Resolving the individual sums
and using a
i
= i for i ≥ 1 we get that
t
p
(N)=y
p
p
j=1
x
j
(1 − x
j
)
=
x
(
p+1
2
)
y
p
(x; x)
p
.
Setting y =1and q =0in Theorem 4.30 gives the generating function for the
number of compositions with parts in N that avoid 123 as
C
123
N
(x, 1, 0) =
1
1 −
x
1−x
−
p≥3
p−3
j=0
p−3
j
x
(
p+1+j
2
)
(x; x)
p+j
(−1)
p−2
,
and the sequence for the number of 123-avoiding compositions with parts in N
for n =0to n =20is given by 1, 1, 2, 4, 8, 16, 31, 61, 119, 232, 453, 883,
1721, 3354, 6536, 12735, 24813, 48344, 94189, 183506,and357518. Note that
the first time the pattern 123 can occur is for n =6, as the composition 123.
We will now generalize to the enumeration of compositions that contain -
letter subword patterns. For instance, we extend the question of counting the
occurrences of the subwords 11 (level) and 111 (level+level) to the question of
counting the occurrences of the pattern 1
=11···1 in the set of compositions
of n with m parts in A. Likewise, we will derive generating functions for
generalizations of the patterns 112 (level+rise) and 221 (level+drop).
4.3.3 The pattern τ =1
We start with the easiest pattern, namely τ =1
, which consists of 1s.
Note that for = 3, we obtain the result for the statistic level+level.
© 2010 by Taylor and Francis Group, LLC