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

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

84 Combinatorics of Compositions and Words

3.6 Exercises

Exercise 3.1 Let A(x, y, q)=



n≥0



σ∈C

n,m



∞

i=1

(σ)

be the gener-

ating function for the number of compositions of n with r

parts of size i and



= m. Prove that

A(x, y, q)=

1 − y



∞

i=1

Exercise 3.2 Let A(x, y, q)=



n≥0



σ∈P

n,m



∞

i=1

(σ)

be the gen-

erating function for the number of palindromic compositions of n with r

parts

of size i and



= m. Prove that

A(x, y, q)=

1+y



∞

i=1

1 − y



∞

i=1

Exercise 3.3

∗

Find an explicit formula for

N\{1}

(n)

and determine its limit

when n →∞.

Exercise 3.4 Find the generating function for the number of compositions of

n with m parts in N in which no part is unique (or equivalently, every part

appears at least twice). (Hint: use the exponential generating function for y,

that is, f(x, y)=



m≥0

f(m; x)

,wheref (m; x) is the ordinary generating

function for the number of compositions with m parts in which no part is

unique.)

Exercise 3.5 A composition σ is said to be odd-Carlitz (respectively, even-

Carlitz) if it is Carlitz and all its parts are odd (respectively, even) numbers.

Prove that

(1) the generating function for the number of odd-Carlitz compositions of n

with m parts in N is given by

1 −



i≥0

2i+1

1+x

2i+1

;

(2) the generating function for the number of even-Carlitz compositions of

n with m parts in N is given by

1 −



i≥0

2i+2

1+x

2i+2

Compositions 85

Exercise 3.6 Prove that the generating function for the number of palin-

dromic Carlitz compositions of n with m parts is given by

CP (x, y)=



m≥0

CP (m; x)y

=1+



i≥1

1+x

1 −



i≥1

1+x

Exercise 3.7

(1) Find an explicit formula for the number of times the summand k occurs

in all palindromic compositions of n with parts in N.

(2) More generally, for any ordered subset A of N, ﬁnd the generating func-

tion for the number of times that the coeﬃcient a

occurs in all palin-

dromic compositions with parts in A.

Exercise 3.8 Find an explicit formula for the number of Carlitz words (words

in which no two adjacent letters are the same) of length n on the alphabet [k].

Exercise 3.9 Derive the generating function for the number of rises in all

compositions with parts in {1, 2} from the recurrence relation given in Theo-

rem 3.11.

Exercise 3.10 Fill in the details of the proof of Part (2) of Theorem 3.12.

Exercise 3.11 Write a program that uses the recursive creation described in

Theorem 3.12 to create the compositions of n with odd parts.

Exercise 3.12 A composition σ = σ

···σ

of n with m parts is said to be

limited if 1 ≤ σ

≤ n

for all i =1, 2,...,n.

(1) Derive a formula for the generating function for the number of limited

compositions of n.

(2) Using Part (1), obtain a simple formula for the case n

= k for all i.

(3) Prove that the number of limited compositions of n is given by F

n+1

when n

=2for all i.

Exercise 3.13 Prove that the generating function for the number of compo-

sitions of n with exactly k odd parts is given by

(1 − x

)

(1 − 2x

)

k+1

Exercise 3.14 Let

CP (m, n) be the number of n-color palindromic composi-

tions of n with m parts. Show that

86 Combinatorics of Compositions and Words

(1)

CP (2m − 1, 2n − 1) =



n−1

i=1

(2i − 1)



n+m−2−i

2m−3



, for m>1.

(2)

CP (2m − 1, 2n)=



n−1

i=1



n+m−2−i

2m−3



, for m>1.

(3)

CP (2m, 2n)=



n+m−1

2m−1



Exercise 3.15 An odd-even partition of n is a partition in which the parts

alternate in parity, starting with the smallest odd part (see [9] ). For instance,

the odd-even partitions of 7 are 16, 34, 52,and7. Use either generating

function techniques or a combinatorial argument to show that the number of

compositions of n with an odd number of parts is the same as the number of

odd-even partitions with largest part n.

Exercise 3.16

∗

Awordw = w

···w

is said to be gap free if w contains all

the letters between the smallest and largest letter in w. For example, 342523

is gap free, but 154212 is not, as the letter 3 is missing. Find an explicit

formula for the generating function for the number of gap free words of length

n on the alphabet [k].

3.7 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.

Research Direction 3.1 In Exercise 3.16, we deﬁned the notion of a gap

free word. Obviously, this notion can be applied to compositions as well, and

can be generalized.

Deﬁnition 3.27 For a sequence (word, composition, partition) s = s

···s

we deﬁne

gap(s)=max

− min

+1−|{s

|i =1, 2,...,k}|,

which gives the number of parts missing in s between the minimal and maximal

parts of s. Note that if gap(s)=0, then the sequence is gap free.

Example 3.28 The word w = 13361755 has a gap of 2, which is easily deter-

mined by inspection as the letters 2 and 4 are missing. We can also obtain this

result from the above formula as gap(w)=7−1+1−|{1, 3, 5, 6, 7}| =7−5=2.

We can now formulate several research questions around this concept.

Compositions 87

(1) What is the explicit formula for the generating function for the number

of k-ary words w of length n such that gap(w)=? (Note that when

 =0, we obtain the generating function for the number of gap free

words of length n on [k].)

(2) More generally, can one ﬁnd an explicit formula for the generating

function for the number of compositions of n with m parts such that

gap(σ)=?

(3) A variation on the theme: Is there an explicit formula for the generating

function for the number of k-ary circular words of length n (see Exercise

1.14) such that gap(w)=?

(4) Generalize (3) to compositions, that is, ﬁnd an explicit formula for the

generating function for the number of circular compositions (see Exercise

1.15) of n with m parts such that gap(σ)=.

Research Direction 3.2 In Exercise 3.4 we investigated compositions in

which no part is unique, and derived an explicit formula for the mixed (expone-

ntial in y,ordinaryinx) generating function

f(x, y)=



m≥0

(m; x)

for the number of compositions of n with m parts in N in which no part is

unique. Here are some questions related to this concept.

(1) Is there an explicit formula for the ordinary generating function

f(x, y)=



m≥0

(m; x)y

for the number of compositions of n with m parts in N in which no part

is unique?

(2) What is the explicit formula for the number of compositions of n with

m parts in N such that if x is a part of σ,thenσ contains x at least 

times?

(3) Answer Part (2) for palindromic or Carlitz compositions.

Research Direction 3.3 A variation on the notion of circular words and

compositions is the notion of a cyclic word or composition, which we will

investigate in the context of Carlitz compositions and Carlitz words.

Deﬁnition 3.29 A cyclic Carlitz composition of n with m parts in A is a

Carlitz composition σ

···σ

of n with m parts in A such that σ

= σ

A cyclic Carlitz word of length n on the alphabet [k] is a Carlitz word (see

Exercise 2.6) w

···w

such that w

= w

88 Combinatorics of Compositions and Words

Note that for a cyclic composition, we look at the connection between the

ﬁrst and the last part, but we do not put the composition on a circle.

Example 3.30 1231 is a Carlitz composition of 7, but not a cyclic Carlitz

composition. The cyclic Carlitz compositions of n =1,...,5 are:

1; 2; 3, 12, 21; 4, 13, 31; 5, 41, 14, 32, 23.

ThecyclicCarlitzwordsoflength3 on [3] are 123, 132, 213, 231, 312,and

321.

The obvious questions to ask are:

(1) Find an explicit generating function for the number of k-ary cyclic Car-

litz words of length n.

(2) Find an explicit generating function for the number of cyclic Carlitz

compositions of n with m parts in N (or more generally, in a set A).

Research Direction 3.4 In Section 3.4 we have seen that there is a strong

connection between tilings and compositions. In particular, the number of n-

color compositions of n is given by F

(see Theorem 3.23). Recall that F

counts the number of tilings of a 1×(n−1) board with squares and dominoes, or

equivalently, compositions of n −1 with 1sand2s (see Example 3.18).Givea

bijection between the two types of compositions (or equivalently between tilings

with squares and dominoes and n-color tilings).

Chapter 4

Statistics on Compositions

4.1 History and connections

A statistic on a composition is a characteristic such as the numbers of parts,

levels, rises, odd summands, etc. In this chapter we will present some results

and techniques to obtain generating functions for statistics on compositions.

The earliest statistics to be considered, apart from the number of parts of

the composition, were rises, levels and drops, considered by Carlitz, Hoggatt

and their various co-authors [7, 36, 39, 42, 43]. Abramson considered longest

runs and rises of a given size [1, 2]. Rawlings investigated weak rises (level or

rise) and down-up alternating compositions [168].

Rises, levels and drops can be regarded as the simplest of patterns, namely

2-letter subword patterns (see Deﬁnition 1.24). A rise corresponds to the

subword pattern 12, a level to the subword pattern 11, and a drop to the

subword pattern 21. In this chapter we use the term pattern exclusively for

subword patterns, enumerating compositions which include or avoid them.

More general patterns will be discussed in Chapter 5.

In Section 4.2 we will present results on the enumeration of compositions

in an ordered set A with regard to the statistics parts, rises, levels, and drops

[90]. These results contain as special cases results on the sets considered in

[7, 50, 51, 76, 77, 87, 98], as well as results on Carlitz compositions [36, 39, 119]

and partitions. The approach we will take is to derive a generating function

for several statistics of interest simultaneously, and then obtain results for

individual statistics as special cases.

Following a line of research that arose from the study of permutation pat-

terns, Heubach and Mansour [92] enumerated compositions which contained

and/or avoided 2-letter and 3-letter patterns. Some of their results were fur-

ther generalized to families of -letter patterns by Mansour and Sirhan [145].

These results will be given in Section 4.3, starting with results that only exist

for 3-letter patterns or sets of 3-letter patterns, followed by the results for the

more general -letter patterns.

90 Combinatorics of Compositions and Words

4.2 Subword patterns of length 2: rises, levels and drops

Throughout the remainder of this chapter we let A be an ordered (ﬁnite or

inﬁnite) set of positive integers, say A = {a

,...,a

},wherea

< ··· <a

with the obvious modiﬁcations in the case |A| = ∞.Inthetheoremsand

proofs we will treat the two cases together if possible, and will note if the case

|A| = ∞ requires additional steps. We will derive general results involving a

number of statistics, which then can be applied to special cases.

Deﬁnition 4.1 For any ordered set A ⊆ N, we denote the set of all com-

positions (respectively palindromic compositions) of n with parts in A by C

(respectively P

). For any composition σ, we denote the number of rises,

levels, and drops by ris(σ), lev(σ),anddro(σ), respectively. Let

→

y =(y, r, ,d)

and

→

=(par(σ), ris(σ), lev (σ), dro(σ)). The generating functions for the

number of compositions (respectively palindromic compositions) of n with parts

in A according to the order of σ and the statistic

→

are given by

(x, y, r, , d)=



n≥0



σ∈C

par( σ)

ris ( σ)



lev( σ)

dro( σ)

and

(x, y, r, , d)=



n≥0



σ∈P

par( σ)

ris ( σ)



lev( σ)

dro( σ)

In the proofs, we also need to consider generating functions for compositions

that start with speciﬁed parts (as in the proof of Theorem 3.7).

Deﬁnition 4.2 We will denote the generating functions for the number of

compositions (respectively palindromic compositions) of n with parts in A ac-

cording to the order of σ and the statistic

→

that start with σ

···σ



(σ

···σ



|x, y, r, , d)=



n≥0



···σ





∈C

par( σ)

ris ( σ)



lev( σ)

dro( σ)

and

(σ

···σ



|x, y, r, , d)=



n≥0



···σ





∈P

par( σ)

ris ( σ)



lev( σ)

dro( σ)

From these deﬁnitions, it follows immediately that

(x, y, r, , d)=1+



i=1

|x, y, r, , d) (4.1)

Statistics on Compositions 91

and

(x, y, r, , d)=1+



i=1

|x, y, r, , d), (4.2)

where the summand 1 corresponds to the case n =0.

4.2.1 Results for compositions

We now state the results for subword patterns of length two for composi-

tions.

Theorem 4.3 The generating function for compositions according to order

and the statistic

→

=(par(σ), ris(σ), lev (σ), dro(σ)) for any ordered subset A

of N is given by

(x, y, r, , d)=

1+(1− d)



j=1



1 − x

y( − d)

j−1



i=1

1 − x

y( − r)

1 − x

y( − d)



1 − d



j=1



1 − x

y( − d)

j−1



i=1

1 − x

y( − r)

1 − x

y( − d)



Proof We start by deriving a recursion for C

|x, y, r, , d). Note that

the compositions of n starting with a

with at least two parts can be created

recursively by prepending a

to a composition of n − a

that starts with a

for some j. This either creates a rise (if i<j), a level (if i = j), or a drop (if

i>j), and in each case, results in one more part. Thus,

|x, y, r, , d)=

⎧

⎪

⎨

⎪

⎩

|x, y, r, , d),i<j

x

|x, y, r, , d),i= j

|x, y, r, , d),i>j.

Summing over j and accounting for the single composition with exactly one

part, namely a

,gives

|x, y, r, , d)=x

y + x

i−1



j=1

|x, y, r, , d)

yC

|x, y, r, , d)

+ x



j=i+1

|x, y, r, , d) (4.3)

for i =1, 2,...,k.Let

= C

(x, y, r, , d),t

= C

|x, y, r, , d), and b

= x

92 Combinatorics of Compositions and Words

for i =1, 2,...,k. Then (4.1) and (4.3) result in a system of k +1 equations

in k + 1 variables. By Cramer’s rule (see Theorem B.19), t

det(N

)

det(M

)

,where

is the (k +1)× (k + 1) matrix of the system of equations and N

is the

(k +1)×(k + 1) matrix which results from replacing the ﬁrst column in M

the vector of the right-hand side of the system. The next step is to derive a

recursion for det(M

) from which one can obtain the following explicit formula

(for details see [90]):

det(M

(

1 − b

 −b

r −b

r ··· −b

r −b

−b

d 1 −b

 −b

r ··· −b

r −b

−b

d −b

d 1 −b

 ··· −b

r −b

−b

k−1

d −b

k−1

d −b

k−1

··· 1 − b

k−1

 −b

k−1

−b

d −b

d ··· −b

d 1 − b



(



j=1

(1 − b

( − d)) − d



j=1

j−1



i=1

(1 − b

( − r))



i=j+1

(1 − b

( − d)).

A similar formula is obtained for det(N

), which completes the proof when

A is a ﬁnite set. Note that if |A| = ∞, then the result follows by taking limits

as k →∞. 2

We now apply Theorem 4.3 to speciﬁc sets, and also focus on individual

statistics by selectively setting some of the indeterminates y, r, ,andd to 1.

Example 4.4 Disregarding rises, levels and drops by setting r =  = d =

1 in Theorem 4.3, we recover the results of Theorem 3.13, namely that the

generating function for the number of compositions of n with m parts in A is

given by

(x, y, 1, 1, 1) =

1 − y



j=1



m≥0



j=1

. (4.4)

Moreover, setting y =1in (4.4) gives the generating function for the number

of compositions of n with parts in A as 1/(1−



j=1

). Additional examples

for speciﬁc choices of A can be found in [89].

Note that the number of rises equals the number of drops in all compositions

of n. For each nonpalindromic composition there exists a composition in re-

verse order, matching up rises and drops, while for palindromic compositions,

symmetry matches up rises and drops within the composition. Therefore, we

will derive results only for rises, and in the remainder of the chapter not men-

tion drops anymore. Any result that we derive for rises immediately gives the

identical result for drops.

Statistics on Compositions 93

Corolla ry 4.5 Let A = {a

,...,a

} and deﬁne

(x, y)=



n≥0



σ∈C

ris(σ)x

par( σ)

and

(x, y)=



n≥0



σ∈C

lev(σ)x

par( σ)

Then

(x, y)=



1≤i<j≤k



m≥0

(m +1)



j=1

m+2

(4.5)

and

(x, y)=



j=1



m≥0

(m +1)



j=1

m+2

Note that the generating functions given in Corollary 4.5 have the statistic

of interest as the coeﬃcient of x

par( σ)

. How can we obtain such a generating

function from the general result stated in Theorem 4.3? The obvious choice

is to take partial derivatives with respect to the relevant indeterminate, and

then set that indeterminate to 1, a common technique in enumerative com-

binatorics. We will illustrate this general technique in detail in the proof of

Corollary 4.5. The following rule for partial derivatives of products, which

holds whenever f

(r) = 0, will come in handy.

∂

∂r



i=1

(r)=



i=i

∂

∂r

(r)



j=i

(r)=





i=1

(r)





i=1

∂

∂r

(r)

. (4.6)

Proof We derive the expression for r

(x, y). Since we are only interested

in rises, we set  = d = 1 in Theorem 4.3 to obtain

(x, y, r, 1, 1) =

1 −



j=1

j−1



i=1

(1 − x

y(1 − r))

. (4.7)

Since



n≥0



σ∈C

ris(σ)x

par( σ)

∂

∂r

(x, y, r, 1, 1)

(

r=1