On permutations generated by infinite binary words

M. A. Makarov

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 3 (2006), pp. 304-311

Résumé

Let $w=w(1)w(2)\ldots w(n)\ldots$ be an arbitrary non-periodic infinite word on $\{0,1\}$. For every $i\in\mathbb{N}$ we may consider the binary real number $R_w(i)=0,w(i)w(i+1)\dots$. For all $n\in\mathbb{N}$ the numbers $R_w(1),\ldots,R_w(n)$ generate some permutation $\pi_w^n$ of length $n$ such that for all $i,j\in\{1,\ldots,n\}$ the inequalities $\pi_w^n(i)\pi_w^n(j)$ and $R_w(i)$ are equivalent. A permutation is said to be { it valid} if it is generated by some word. In this paper we investigate some properties of valid permutations. In particular, we prove a precise formula for the number of valid permutations of a given length. Also we consider a problem of continuability of valid permutations to the left.