### On infinite permutations

*Dmitri G. Fon-Der-Flaass, Anna E. Frid*

#### Abstract

We define an infinite permutation as a sequence of reals taken up to the order, or, equivalently, as a linear ordering of a finite or countable set. Then we introduce and characterize periodic permutations; surprisingly, for each period t there is an infinite number of distinct t-periodic permutations. At last, we introduce a complexity notion for permutations analogous to subword complexity for words, and consider the problem of minimal complexity of non-periodic permutations. Its answer is different for the right infinite and the bi-infinite case.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page