|Journal of Integer Sequences, Vol. 18 (2015), Article 15.6.5|
School of Computer and Information Sciences
University of Strathclyde
Glasgow, G1 1HX
Alexander Konovalov, Steve Linton, and Peter Nightingale
School of Computer Science
University of St Andrews
St Andrews, Fife KY16 9SX
Avgustinovich et al. studied bicrucial permutations with respect to squares, and they proved that there exist bicrucial permutations of lengths 8k+1, 8k+5, 8k+7 for k ≥ 1. It was left as open questions whether bicrucial permutations of even length, or such permutations of length 8k+3 exist. In this paper, we provide an encoding of orderings which allows us, using the constraint solver Minion, to show that bicrucial permutations of even length exist, and the smallest such permutations are of length 32. To show that 32 is the minimum length in question, we establish a result on left-crucial (that is, not extendable to the left) square-free permutations which begin with three elements in monotone order. Also, we show that bicrucial permutations of length 8k+3 exist for k = 2,3 and they do not exist for k =1.
Further, we generalize the notions of right-crucial, left-crucial, and bicrucial permutations studied in the literature in various contexts, by introducing the notion of P-crucial permutations that can be extended to the notion of P-crucial words. In S-crucial permutations, a particular case of P-crucial permutations, we deal with permutations that avoid prohibitions, but whose extensions in any position contain a prohibition. We show that S-crucial permutations exist with respect to squares, and minimal such permutations are of length 17.
Finally, using our software, we generate relevant data showing, for example, that there are 162,190,472 bicrucial square-free permutations of length 19.
(Concerned with sequences
Received January 30 2015; revised version received April 12 2015; May 22 2015; June 2 2015. Published in Journal of Integer Sequences, June 3 2015.