Picture of smart phone in human hand

World leading smartphone and mobile technology research at Strathclyde...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by University of Strathclyde researchers, including by Strathclyde researchers from the Department of Computer & Information Sciences involved in researching exciting new applications for mobile and smartphone technology. But the transformative application of mobile technologies is also the focus of research within disciplines as diverse as Electronic & Electrical Engineering, Marketing, Human Resource Management and Biomedical Enginering, among others.

Explore Strathclyde's Open Access research on smartphone technology now...

On square-free permutations

Avgustinovich, Sergey and Kitaev, Sergey and Pyatkin, Artem and Valyuzhenich, Alexander (2011) On square-free permutations. Journal of Automata, Languages and Combinatorics, 16 (1). pp. 3-10.

Full text not available in this repository. Request a copy from the Strathclyde author

Abstract

A permutation is square-free if it does not contain two consecutive factors of length more than one that coincide in the reduced form (as patterns). We prove that the number of square-free permutations of length n is nn(1􀀀"n) where "n ! 0 when n ! 1. A permutation of length n is crucial with respect to squares if it avoids squares but any extension of it to the right, to a permutation of length n+1, contains a square. A permutation is maximal with respect to squares if both the permutation and its reverse are crucial with respect to squares. We prove that there exist crucial permutations with respect to squares of any length at least 7, and there exist maximal permutations with respect to squares of odd lengths 8k+1; 8k+5; 8k+7 for k 1.