×

zbMATH — the first resource for mathematics

A geometric proof of the enumeration formula for Sturmian words. (English) Zbl 0802.68099
The number of factors of length \(m\) of Sturmian words is known to be \(1 + \sum^ m_ 1 (m - i + 1) \varphi (i)\) where \(\varphi\) is the Euler function, i.e., \(\varphi (n)\) is the number of natural integers less than \(n\) and coprime to \(n\). We give a geometric proof of this formula, based on duality and on Euler’s relation for planar graphs.

MSC:
68R15 Combinatorics on words
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI