A new geometric approach to Sturmian words (Q428857)

Sturmian words are one-way infinite sequences of symbols containing exactly \(n+1\) distinct factors of length \(n\geq 0\). Finite factors of Sturmian words are called finite Sturmian words. The paper describes a partition of the set of all finite Sturmian words of length \(n\) for which each part can be characterized by a specific straight line in an \(n\times n\) grid. Using this approach, the authors give new proofs of already known formulas enumerating finite Sturmian words and palindromic Sturmian words as well as a new proof of the fact that each factor of a Sturmian word \(\omega\) has exactly two return words in \(\omega\). A return word of a factor \(u\) in an infinite word \(\omega\) is a word \(v\) such that \(vu\) is a factor of \(\omega\) containing exactly two occurrences of \(u\): its prefix and its suffix.