This article is cited in 17 papers

Research papers

On permutations generated by infinite binary words

M. A. Makarov

Novosibirsk State University

Abstract: 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)<R_w(j)$ 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.

UDC: 519.1

MSC: 68R05

Received November 23, 2005, published July 25, 2006

Bibliographic databases:

• 
•