Catalog Home Page

On a generalisation of trapezoidal words

Glen, A. and Levé, F. (2011) On a generalisation of trapezoidal words. In: 35th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (35ACCMCC), 5 December - 9 December, Melbourne, Australia.

PDF (Presentation)
Download (1MB)


The factor complexity function Cw(n) of a finite or infinite word w associates to each integer n ≥ 0 the number of distinct factors (i.e., blocks of consecutive letters) in w of length n. A finite word w of length │w│ is said to be trapezoidal if the graph of its factor complexity Cw(n) as a function of n (for 0 6 n 6 │w│) is that of a regular trapezoid (or possibly an isosceles triangle); that is, Cw(n) increases by 1 with each n on some interval of length r, then Cw(n) is constant on some interval of length s, and finally Cw(n) decreases by 1 with each n on an interval of the same length r. Necessarily Cw(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 A. 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 R2 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 - a new (wider) class of finite and infinite words characterised by containing the maximal number of palindromes { recently introduced by the speaker, together with J. Justin, S. Widmer, and L.Q. Zamboni (2009).

In this talk, I will introduce a natural generalisation of trapezoidal words over an arbitrary finite alphabet A consisting of at least two distinct letters, called generalised trapezoidal words (or GT-words for short). In particular, I will discuss some combinatorial properties of this new class of words when │A│ ≥ 3 and I will show that, unlike in the binary case (│A│ = 2), not all GT-words are rich in palindromes, but we do have a neat characterisation of those that are.

This work was inspired by a question of Ian Wanless at the 54th Annual Conference of the Australian Mathematical Society last year (2010).

Publication Type: Conference Item
Murdoch Affiliation: School of Chemical and Mathematical Science
Item Control Page Item Control Page


Downloads per month over past year