The number of binary rotation words∗
Sobolev Institute of Mathematics SB RAS, Koptyug Av. 4, 630090,
Novosibirsk, Russia, and Université de Lorraine, 34 cours Léopold, CS 25233, 54052
2 LORIA, UMR 7503, Campus scientifique BP 239, 54506 Vandoeuvre-lès-Nancy cedex, France.
Received: 14 March 2014
Accepted: 18 March 2014
We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length n. We also give the precise asymptotics for it, which happens to be Θ(n4). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov [Problemy Kibernet. 39 (1982) 67–84], then independently by Mignosi [Theoret. Comput. Sci. 82 (1991) 71–84], and others.
Mathematics Subject Classification: 68R15 / 37B10
Key words: Rotation / rotation words / Sturmian words / subword complexity / total complexity
© EDP Sciences 2014