Generalized trapezoidal words

The factor complexity function  Cw(n)Cw(n) of a finite or infinite word w counts the number of distinct factors of w of length n   for each n≥0n≥0. A finite word w of length  |w||w| is said to be trapezoidal   if the graph of its factor complexity Cw(n)Cw(n) as a function of n   (for 0≤n≤|w|0≤n≤|w|) is that of a regular trapezoid (or possibly an isosceles triangle); that is, Cw(n)Cw(n) increases by 1 with each n on some interval of length r  , then Cw(n)Cw(n) is constant on some interval of length s  , and finally Cw(n)Cw(n) decreases by 1 with each n on an interval of the same length r  . Necessarily Cw(1)=2Cw(1)=2 (since there is one factor of length 0, namely the empty word), so any trapezoidal word is on a binary alphabet. Trapezoidal words were first introduced by de Luca (1999) when studying the behaviour of the factor complexity of finite Sturmian words  , i.e., factors of infinite “cutting sequences”, obtained by coding the sequence of cuts in an integer lattice over the positive quadrant of R2R2 made by a line of irrational slope. Every finite Sturmian word is trapezoidal, but not conversely. However, both families of words (trapezoidal and Sturmian) are special classes of so-called rich words (also known as full words) – a wider family of finite and infinite words characterized by containing the maximal number of palindromes – studied in depth by the first author and others in 2009.In this paper, we introduce a natural generalization of trapezoidal words over an arbitrary finite alphabet AA, called generalized trapezoidal words (or GT-words   for short). In particular, we study combinatorial and structural properties of this new class of words, and we show that, unlike the binary case, not all GT-words are rich in palindromes when |A|≥3|A|≥3, but we can describe all those that are rich.