On the number of factors in codings of three interval exchange. (English) Zbl 1283.68274

Ambrož, Petr; Frid, Anna; Masáková, Zuzana; Pelantová, Edita

Discrete Math. Theor. Comput. Sci. 13, No. 3, 51-66 (2011).

Summary: We consider exchange of three intervals with permutation \((3,2,1)\). The aim of this paper is to count the cardinality of the set \(3\mathrm{iet}(N)\) of all words of length \(N\) which appear as factors in infinite words coding such transformations. We use the strong relation of \(3\mathrm{iet}\) words and words coding exchange of two intervals, i.e., Sturmian words. The known asymptotic formula \[ \#2\mathrm{iet}(N)/N^{3}\sim 1/\pi ^{2} \] for the number of Sturmian factors allows us to find bounds \[ 1/3\pi ^{2} + o(1) \leq \# 3\mathrm{iet}(N)/N^{4} \leq 2/\pi ^{2} + o(1). \]

MSC:

68R15	Combinatorics on words
05A05	Permutations, words, matrices
37B10	Symbolic dynamics

Keywords:

interval exchange; enumeration of factors; Sturmian words