236 Combinatorics of Compositions and Words
the partition of [7] into the four blocks {1, 4}, {2, 5, 7}, {3},and{6} has as-
sociated canonical sequence 1231242. We will refer to the canonical sequence
of a set partition of n as a partition word of length n.
Note that a word w on [d] represents a set partition with d blocks if and
only if it has the following properties:
(1) Each letter from the set [d] appears at least once in w.
(2) For each i, j such that 1 ≤ i<j≤ d, the first occurrence of i precedes
the first occurrence of j.
We remark that sequences satisfying these properties are also known as re-
stricted growth functions and they are often encountered in the study of set
partitions and related topics (see [175, 190] and references therein).LetP
n
de-
note the set of partition words of length n.ThenP
1
= {1}, P
2
= {11, 12} and
P
3
= {111, 112, 121, 122, 123}. Prove that the exponential generating function
for the number of partition words of length n is given by e
e
x
−1
.
Exercise 6.12
∗∗
Using the definitions of Exercise 6.11, determine
(1) the generating functions for the number of partition words of size n that
avoid a single pattern from the set P
3
= {111, 112, 121, 122, 123},and
(2) the generating functions for the number of partition words of size n that
avoid a single pattern from the set P
4
= {1111, 1112, 1121, 1122, 1123,
1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 1234}.
Note that a complete classification with regard to Wilf-equivalence for avoid-
ance of partition word patterns in partition words has been given up to n =7
in [104].
Exercise 6.13
∗
Combining the definitions in Exercises 6.9 and 6.11, prove
that the generating function for the number of smooth partition words of [n]
is given by
1+
x
1 − 3x
⎛
⎝
1 −
k≥1
1
U
k
1−x
2x
U
k−1
1−x
2x
⎞
⎠
,
where U
s
is the s-th Chebyshev polynomial of the second kind. Then, show
that the number of smooth partition words of [n] with k blocks is given by
2
k +1
k
j=1
(1 + (−1)
j+1
)cos
2
%
jπ
2(k +1)
&
1+2cos
%
jπ
k +1
&
n−1
−
2
k
k−1
j=1
(1 + (−1)
j+1
)cos
2
%
jπ
2k
&
1+2cos
%
jπ
k
&
n−1
.
© 2010 by Taylor and Francis Group, LLC