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

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

Introduction 13

We now give a more detailed overview of the major research directions for

both compositions and words.

1.3 A more detailed look

In this section we will have a closer look at the ﬁve major research areas

for compositions and those for words, by giving relevant deﬁnitions and basic

examples, as well as an overview of the structure of this text.

1.3.1 Restricted compositions and words

Restrictions come in many ﬂavors, one of which is to restrict the parts of

the composition or word to a subset A of N. In the case of words this is not

interesting at all – all that matters is the total number of letters. Any set of n

elements can be mapped bijectively to the set [n]. However, for compositions,

this type of restriction leads to interesting results. This was the direction

taken by Alladi and Hoggatt [7], who considered A = {1, 2}, and enumerated,

among other things, the number of compositions, number of parts, and num-

ber of rises, levels and drops in compositions of n, exhibiting connections to

the Fibonacci sequence (see Chapter 3). Interest in the connection between

compositions and the Fibonacci sequence came from earlier studies by Hog-

gatt and Lind of weighted compositions [99, 100], who found connections to

identities for Fibonacci numbers.

Chinn, Grimaldi and Heubach [50, 51, 52, 76, 77] have recently revived

this research direction. They have generalized to A = {1,k}, A = N \{1},

A = N\{2}, A = N\{k},andA = {1, 3, 5,...} and have counted the number of

compositions, rises, levels and drops. For A = N\{ 1} and A = N\{ 2} they have

found combinatorial proofs for connections between the various sequences of

interest. At the same time, Srinivasa Rao and Agarwal [181] enumerated

compositions in which each part is bounded above and below, but did not

investigate the statistics considered by the other authors.

A second type of restriction is to place limitations on the arrangement of

the parts within the word or composition, the direction taken by Carlitz and

his various co-authors. It started with a paper by Carlitz [36] in which he

enumerated words according to the number of rises and falls, a reﬁnement of

the Simon Newcomb problem [60]. A natural extension is the study of up-

down sequences (words in which rises and falls alternate) by Carlitz [37] and by

Carlitz and Scoville [41], and, more generally, to the enumeration of words or

compositions that do not have levels [38]. This restriction on the placement of

the parts produces compositions that are “closest” to permutations. Carlitz

d his co-authors referred to these words or compositions as waves, while

14 Combinatorics of Compositions and Words

other authors have called them Smirnov sequences (see for example [75]).

Knopfmacher and Prodinger [119] introduced the name Carlitz compositions

in honor of Carlitz, which has become the name commonly used.

Deﬁnition 1.18 A Carlitz composition of n is a composition of n in which

no adjacent parts are the same.

Example 1.19 The Carlitz compositions of 5 are 131, 212, 32, 23, 41, 14

and 5.

Another example of a restriction on the arrangement of parts are palin-

dromic compositions. Hoggatt and Bicknell [98] investigated palindromic

compositions in N according to rises and falls, and various other authors

who studied compositions from restricted sets also considered palindromic

compositions from those restricted sets.

We will study restricted compositions, as well as other variations of com-

positions in Chapter 3.

1.3.2 Statistics on compositions in N

At the same time as Alladi and Hoggatt, Carlitz [38, 39, 40] and other au-

thors studied rises, levels and falls for compositions with parts from N,aswell

as other statistics. For example, Abramson [1, 2] enumerated compositions

according to longest runs and rises of a speciﬁc size. Carlitz and Vaughan [43]

derived the generating functions for the number of compositions according to

speciﬁcation (a list of counts for the occurrences of each integer), rises, falls

and maxima, while Carlitz et al. [42] enumerated pairs of sequences according

to rises, levels and falls. More recently, Rawlings [168] enumerated composi-

tions according to weak rises and falls (equality allowed) in connection with

restricted words by adjacencies. He also introduced the notion of ascent vari-

ation (the sum of the increases of the rises within a composition), which is

motivated by a connection to the perimeter of directed vertically convex poly-

ominoes. Knopfmacher and Mays enumerated compositions according to the

number of distinct parts [117] and gave results on the sum of distinct parts in

compositions and partitions [118]. Grimaldi, Chinn and Heubach enumerated

rises, falls, levels, “+” signs, as well as the number of parts in all compositions

[48, 87]. These results were generalized by Heubach and Mansour [89, 90] and

Merlini et al. [154], who provided a general framework for compositions with

parts from a set A, and derived generating functions for the number of parts,

rises, levels and falls.

Results on the statistics rise, level and fall can be extended by thinking of

them as two-letter subword patterns. To deﬁne what we mean by a pattern,

we need to introduce some terminology.

Deﬁnition 1.20 The reduced form of a sequence σ = σ

...σ

is given by

the sequence s

···s

,wheres

=  if σ

is -th smallest term.

Introduction 15

Example 1.21 The reduced form of the sequence 35237 is 23124,astheterms

of the sequence are in order 2 ≤ 3 ≤ 5 ≤ 7, and therefore, 2 is the smallest

element, 3 is the second smallest element, 5 is the third smallest element, and

7 is the fourth smallest element. The reduced form takes into account only

the relative size of the sequence terms and maps the sequence to the set [k],

where k is the number of distinct terms in the sequence.

Deﬁnition 1.22 Asequence(permutation, word, composition or partition)

σ contains a substring w if the word w occurs in σ. Otherwise, we say that σ

avoids the substring w or is w-avoiding.

Substring patterns are particularly relevant when the sequence consists of

letters or symbols that do not have an order relation associated with them. A

prime example is a DNA sequence, which can be considered a word from the

alphabet of nucleotides {A, C, G, T }. Since there is biological relevance to the

order in which the nucleotides occur, statistics on the number of substrings

in a DNA sequence has become an important area of research.

Example 1.23 The DNA sequence ACTGGATCTGAGA contains the sub-

string CT twice, the substring GA three times, and avoids the substring GGG.

Deﬁnition 1.24 Asequence(permutation, word, composition or partition) σ

contains a subword pattern τ = τ

...τ

if the reduced form of any subse-

quence of k consecutive terms of σ equals τ . Otherwise we say that σ avoids

the subword pattern τ or is τ-avoiding. A sequence avoids a set T of subword

patterns if it simultaneously avoids all subword patterns in T . We denote the

set of sequences with parts in a set F that avoid subword patterns from the

set T by F(T ).

Example 1.25 The sequence 1413364 avoids the substring 12, but has three

occurrences of the subword pattern 12 (namely 14, 13 and 36).Italsoavoids

the subword pattern 123.

For longer sequences, it is often useful to write the sequence in standard

short-hand notation as follows.

Deﬁnition 1.26 The notation k

in a sequence of nonnegative integers (per-

mutation, word, composition or partition) stands for a sequence of j consec-

utive occurrences of k.

Example 1.27 The sequence 1111234415333333 is written as 1

234

153

short-hand notation.

Now that we have deﬁned the notion of a subword pattern, it is easy to see

that a level corresponds to the subword pattern 11, while a rise corresponds

16 Combinatorics of Compositions and Words

to the subword pattern 12. Heubach and Mansour [92] enumerated compo-

sitions according to subword patterns of length three. Some of their results

were further generalized by Mansour and Sirhan [145] to enumerating com-

positions according to patterns from families of -letter patterns, for example

the pattern 1

−1

Having obtained very general results on the statistics rises, levels, parts

and order of compositions, we can look at special cases. Since partitions can

be thought of as the nonincreasing compositions, they can be enumerated as

compositions without rises. This allows us to obtain results for partitions

from our results for compositions. We will present these results in Chapter 4.

1.3.3 Pattern avoidance in compositions

In Chapter 5, we will change our focus from enumeration of compositions

and words according to the number of times a certain pattern occurs to the

avoidance of such patterns. Clearly, we can obtain results for pattern avoid-

ance of subword patterns from the previous chapter by looking at zero oc-

currences. In this chapter, we will look at more general patterns, namely

subsequence, generalized, and partially ordered patterns. Subsequence pat-

terns are those where the individual parts of the pattern do not have adjacency

requirements, while generalized patterns have some adjacency requirements.

Partially ordered patterns is a further generalization in the sense that some

of the letters of the pattern are not comparable.

Pattern avoidance was ﬁrst studied for S

, the set of permutations of [n],

avoiding a pattern τ ∈S

. Knuth [122] found that, for any τ ∈S

,thenumber

of permutations of [n] avoiding τ is given by the n-th Catalan number. Later,

Simion and Schmidt [179] determined |S

(T )|, the number of permutations

of [n] simultaneously avoiding any given set of patterns T ⊆S

.Burstein

[31] extended this to words of length n on the alphabet [k], determining the

number of words that avoid a set of patterns T ⊆S

. Burstein and Man-

sour [33, 34] considered forbidden patterns with repeated letters. Recently,

pattern avoidance has been studied for compositions. Savage and Wilf [176]

considered pattern avoidance in compositions for a single subsequence pattern

τ ∈S

, and showed that the number of compositions of n with parts in N

avoiding τ ∈S

is independent of τ. Heubach and Mansour answered the

same questions for subsequence patterns of length three with repeated letters

[91]. For longer subsequence patterns, the results by Jel´ınek and Mansour

[105] allow for a complete classiﬁcation according to avoidance in both words

and compositions.

We will also provide new results on the avoidance of generalized patterns of

length three in Section 5.3, both for permutation patterns and those that have

repeated letters, thereby giving results on the only three-letter patterns not

yet studied. Finally, Section 5.4 contains results on the number of composi-

tions that contain or avoid partially ordered patterns. Kitaev [108] originally

studied avoidance of partially ordered patterns in permutations, and he and

Introduction 17

Mansour [109] generalized to words. This was followed by a paper by Heubach

et al. [88] who gave the corresponding results for avoidance of partially or-

dered patterns in compositions. A somewhat diﬀerent approach was used by

Kitaev et al. [111] to enumerate compositions that contain partially ordered

patterns.

1.3.4 Pattern avoidance and enumeration in words

Historically, pattern avoidance in words has preceded pattern avoidance in

compositions. However, one can consider words as special cases of compo-

sitions (when only looking at a ﬁxed number of parts, not the order of the

composition) and therefore all results derived for compositions also apply for

words and we recover results for pattern avoidance in words [33, 35]. However,

there are some results on pattern avoidance in words that do not easily extend

to compositions. In Chapter 6 we will present the results on pattern avoidance

in words, both by stating the results that can be obtained via the results for

compositions, as well as approaches that are speciﬁc to words. In particular,

we will present the result on avoidance of the subsequence pattern 132, one

of the patterns studied in Burstein’s thesis [31] in 1998. The original result

was derived using the Noonan-Zeilberger algorithm. Since then, two diﬀer-

ent approaches, the block decomposition method and the scanning-element

algorithm, have been used to re-derive Burstein’s result in easier ways.

The block decomposition method was ﬁrst used by Mansour and Vainshtein

[147] to study the structure of 132-avoiding permutations, and permutations

containing a given number of occurrences of 132 [149]. Mansour [141] extended

the use of the block decomposition approach to pattern avoidance in words.

Besides providing a diﬀerent and simpler proof of Burstein’s result, the block

decomposition method reveals more of the structure of the 132-avoiding words,

and can also be used to derive generating functions for words that avoid

a set of patterns {132,τ} for families of patterns. Likewise, the scanning-

element algorithm was ﬁrst used for pattern avoidance and enumeration in

permutations by Firro and Mansour [64], and then extended to study the

number of k-ary words of length n that satisfy a certain set of conditions [65].

Not only does the approach work equally well for the patterns 123 and 132,

it can also be used more easily for the enumeration of patterns, especially for

the pattern 123.

1.3.5 Automata, generating trees and the ECO method

In Chapter 7 we will describe three approaches that are variations on the

same theme, namely deﬁning sequences recursively and then expressing the

recursive structures in an associated graph. The ﬁrst approach we discuss

is a ﬁnite automaton. Br¨and´en and Mansour [27] were the ﬁrst to use this

approach for pattern avoidance in words, using the transfer matrix method of

the automaton to count the number of words that avoid a subsequence pattern.

18 Combinatorics of Compositions and Words

Not only did they obtain exact enumeration results, but also the asymptotics

for the number of words of length n on k letters avoiding a pattern τ.In

addition, they gave the ﬁrst combinatorial proof of a formula for the number

of words of length n on k letters avoiding the pattern 123. This approach can

be easily extended to pattern avoidance in compositions.

The second approach, generating trees, consists of deﬁning recursive rules

that induce a tree, as the name suggests. Generating trees were introduced by

West [191] to enumerate permutations avoiding certain subsequence patterns.

Even though the two approaches look rather diﬀerent at ﬁrst, each generating

tree (which usually has inﬁnitely many vertices) can be mapped to a graph

with a ﬁnite number of vertices in the form of an automaton. Using several

examples, we describe how a recursive creation for the sequence translates

into recursive rules and labels for the vertices of the tree.

We conclude this chapter by discussing the ECO method, which is a gen-

eral framework that describes a process to obtain recurrences for enumerating

combinatorial objects. In essence, it is a road map that lays out the task to be

done, but does not give a formulaic description of the steps. The general idea

(but not with the name ECO method) was introduced in 1978 by Chung et

al. [54] who enumerated permutations avoiding a pair of generalized patterns

using a generating tree. In 1995, Barcucci et al. [14] enumerated Motzkin

paths and various other combinatorial objects using the ECO method. Soon

thereafter, these authors established a general methodology for plane tree enu-

meration [15], followed by a survey on the general theory [16] in which many

enumerative examples are considered in great detail. We refer the interested

reader to [16] and [63] for further details and results.

At roughly the same time, West [191, 192] used what is in principle the

ECO method in the form of generating trees and the associated directed

graphs for enumerating restricted permutations. In fact, most applications

of the ECO method to date reduce to generating trees, or equivalently, au-

tomata. Recently, the ECO method has been applied by Baril and Do [17]

to compositions and by Bernini et al. [23] to words. We will present the

general framework of the ECO method and the results of Bernini et al. [23]

for pattern avoidance of pairs of generalized patterns in words.

1.3.6 Asymptotics

In the study of statistics on compositions, sometimes one is not able to get

explicit results or nice generating functions. Then the question becomes what

can be said about the quantity of interest as n tends to inﬁnity. Tools to obtain

such asymptotic results come from probability theory and complex analysis,

or a combination of the two. In order to utilize the probability approach,

one considers the compositions to be random, with each composition of n

occurring equally likely. With this approach, several authors have derived

interesting asymptotic results.

Hitczenko and Savage [94, 95, 96] studied the probability that a randomly

Introduction 19

chosen part size in a random composition is unrepeated, and more generally,

gave results on the multiplicity of parts. Hitczenko and Stengle [97] presented

an asymptotic result for the expectation of the number of distinct part sizes

in a random composition of an integer, a result that has been obtained inde-

pendently and by an entirely diﬀerent method by Hwang and Yeh [102]. Gho,

Hitczenko, Louchard and Prodinger [73, 93, 133, 134] studied the distinctness

of a random composition, that is, the number of distinct parts, a natural

and important parameter in theoretical models for many applications. They

also studied a variant of distinctness, namely the number of distinct parts of

multiplicity m and other characteristics of random compositions and random

Carlitz compositions.

Knopfmacher and Robbins investigated asymptotics for compositions whose

parts are either powers of two or Fibonacci numbers [120], and for composi-

tions with parts that are constrained by the leading summand [121]. Bender

et al. [20] considered irreducible pairs of compositions, where the subsums of

the ﬁrst terms are all diﬀerent from each other. They enumerated the number

of irreducible ordered pairs of compositions of n into k parts, and approxi-

mated the probability of choosing an irreducible ordered composition of n.

Most recently, Knopfmacher and Mansour have investigated the asymptotic

behavior for record statistics in random compositions [115], while Brennan

and Knopfmacher [28] have investigated the distribution of the ascents of size

d or more in compositions. We will give an introduction to the tools from com-

plex analysis and probability theory and then present some of these results in

Chapter 8.

1.4 Exercises

Exercise 1.1

(1) List all partitions of 5.

(2) List all compositions of 5.

(3) Identify which of the compositions are palindromes.

(4) Associate each composition with its conjugate.

(5) Which of the compositions, if any, are reverse conjugate?

Exercise 1.2 List the reduced form of the following sequences:

(1) 3751293.

(2) 342615.

20 Combinatorics of Compositions and Words

(3) 34567.

(4) 12345.

(5) 333333.

Exercise 1.3 (1) List all words of length three on the alphabet [3].

(2) List the words of length three on the alphabet [3] that avoid the substring

12.

(3) List the words of length three on the alphabet [3] that avoid the subword

pattern 12.

Exercise 1.4 For the sequence 1342573264, determine

(1) whether it avoids the subword pattern 123;

(2) the number of occurrences of the subword pattern 21.

Exercise 1.5 Awordw = w

···w

is said to be a partition word if the ﬁrst

occurrence of i precedes the ﬁrst occurrence of j for any i<j (and therefore,

≤ i). For example, the partition words of length 3 are 111, 112, 121, 122

and 123. Partition words of length n provide an alternative representation for

the set partitions of [n], a well known combinatorial object enumerated by the

Bell (exponential) numbers (see Deﬁnition 2.59 and [180, A000110]).Listall

the partition words of length four.

Exercise 1.6 Which of the following types of compositions are closed under

conjugation (that is, the conjugate compositions are of the same type)?Either

give a proof that the conjugates are of the same type, or exhibit a counter

example.

(1) Compositions without 1s.

(2) Compositions with odd parts.

(3) Carlitz compositions.

Exercise 1.7

(1) Show that if a reverse conjugate composition of n has p parts, then

n =2p − 1. Thus, the reverse conjugate compositions of 2m +1 have

m +1 parts.

(2) Use the result of Part (1) to give a combinatorial argument that there

are 2

reverse conjugate compositions of 2m +1.

Introduction 21

Exercise 1.8 It can be shown that the total number of palindromic composi-

tions of 2m+1 is also 2

(see Theorem 3.4). Derive a bijection (see Deﬁnition

2.4) between the palindromic and the reverse conjugate compositions of 2m+1.

Show the correspondence between the reverse conjugate and the palindromic

compositions of 7 according to your bijection.

Exercise 1.9 The number of compositions of n in N is 2

n−1

, which is also

the number of subsets of [n −1]. Find a bijection (see Deﬁnition 2.4) between

the compositions of n and the subsets of [n − 1].

Exercise 1.10 Are there any proper subsets A of N such that the set of all

compositions of n with parts in A, denoted by C

(n), are closed under conjuga-

tion for n ≥ n

(A), that is, does there exist an n

(A) such that for n ≥ n

(A),

σ ∈ C

(n) implies conj(σ) ∈ C

(n)?

Exercise 1.11

(1) Find a composition with the fewest parts (in reduced form) that con-

tains all the subword patterns of length two on two letters, that is, a

composition that contains 11, 12 and 21.Isthisanswerunique?

(2) Find a composition with the fewest parts (in reduced form) that contains

all the subword patterns of length three on two letters, that is, a compo-

sition that contains 111, 112, 121, 211, 221, 212 and 122.Isthisanswer

unique?

(3) Are the respective compositions also the ones of smallest order? Is the

composition of smallest order unique?

Exercise 1.12 A composition of n is called smooth if the diﬀerence between

any two adjacent parts is either −1, 0,or1,andstrictly smooth if the dif-

ferences are −1 or 1. List the smooth compositions and the strictly smooth

compositions of 5.

Exercise 1.13 A zero-composition of n with m partsisacompositionofn

with m parts for which zero is an allowed part. List all the zero-compositions

of 4 with three parts.

Exercise 1.14 A k-ary circular word w = w

···w

of length n is a word

on n circular positions around a disk (but still written in linear form).For

example, as circular words, 123, 231 and 312 all denote the same word. List

all the circular words of lengths one, two, three, and four on the alphabet [2].

Exercise 1.15 A circular composition σ = σ

···σ

of n is a composition

of n on m circular positions around a disk (but still written in linear form).

(1) List all the circular compositions of 1, 2, 3,and4.

(2) Give an example of a circular composition that is not a partition.

Chapter 2

Basic Tools of the Trade

Combinatorics is the art of counting. Usually, we are interested in counting

objects that depend on a parameter (or two, or three...), for example the

number of compositions of n with only 1s and 2s. (Here the parameter is n.)

It is pretty straightforward to enumerate the number of such compositions for

small values of n by exhibiting all possibilities, but as n increases, the number

of compositions grows exponentially, and so we need to be smarter about

counting. In this chapter we will give an overview of some basic techniques

and ideas of combinatorics. We will illustrate important techniques such as

the use of recurrence relations and generating functions with basic examples,

which we will build upon and expand on in subsequent chapters.

2.1 Sequences

When we count combinatorial objects that depend on a parameter n,then

we obtain diﬀerent answers for each value of n, that is, we obtain a sequence

(in this case of nonnegative terms).

Deﬁnition 2.1 A sequence with values in B, in short a sequence in B,canbe

expressed formally as a function a : I → B,whereI ⊆ Z, the set of integers,

and, for the objects we are interested in, B ⊆ N

, the set of nonnegative

integers. The set I is called the index set,andthesetB consists of the values

of the sequence. If I =[k],thena is called a ﬁnite sequence of length k.

We will use a

and a(n) interchangeably to denote the value associated with

index n. The full sequence is usually given as an ordered list. For example,

when I = N,thena = {a

,...},ora = {a

}

∞

n=1

= {a

}

n≥1

for short. If

we select a subset of the terms of a sequence and preserve the order in which

they occur, then we obtain a subsequence of the original sequence.

Deﬁnition 2.2 Asequence{b

}

n∈I



is a subsequence of the sequence

}

n∈I

if for each index n there exists an index i

such that b

= a

where i

n−1

for n>1.