Combinatorics on words

Combinatorics on words studies finite and infinite sequences of symbols from an alphabet, especially repetition, ordering and occurrence of shorter words. A finite word is an element of the free monoid generated by its alphabet, with concatenation as its operation. For example, abab has two occurrences of ab and is the square of ab; aba is a palindrome. These questions connect algorithms on words with generating functions and symbolic descriptions of dynamical systems.

For a word $w=w_1\cdots w_n$ over a totally ordered alphabet, an inversion of a word is a pair of positions $i<j$ with $w_i>w_j$. Equal symbols contribute no inversion of a word. In baba, with $a<b$, the pairs are $(1,2),(1,4),(3,4)$, so the word inversion number is three. Counting these pairs records distance from sorted order even when letters repeat; replacing the letters by distinct ordered labels gives the inversion of a permutation case.

The number of inversions of a word: pairs of positions $i<j$ with $w_i>w_j$. Unlike an inversion of a permutation, this definition permits repeated letters in the word.

For slope $0\le \alpha \le 1$ and intercept $\rho$, the lower mechanical word has letters $w_n=\lfloor (n+1)\alpha +\rho \rfloor -\lfloor n\alpha +\rho \rfloor$. These letters are zero or one. Replacing floors by ceilings defines the upper mechanical word. An irrational slope gives a Sturmian word.

The floor-based mechanical word $w_n=\lfloor (n+1)\alpha +\rho \rfloor -\lfloor n\alpha +\rho \rfloor$.

A nonempty finite word that is strictly smaller in lexicographic order than each of its nontrivial cyclic rotations. For example, $001$ is a Lyndon word, whereas $010$ is not because its rotation $001$ is smaller.

A prefix of a word that is itself a Lyndon word. The longest Lyndon prefix is useful when ranking necklaces and substrings of a De Bruijn sequence.