Journal of Integer Sequences, Vol. 18 (2015), Article 15.6.5 |

School of Computer Science

University of St Andrews

St Andrews, Fife KY16 9SX

United Kingdom

Sergey Kitaev

School of Computer and Information Sciences

University of Strathclyde

Glasgow, G1 1HX

United Kingdom

Alexander Konovalov, Steve Linton, and Peter Nightingale

School of Computer Science

University of St Andrews

St Andrews, Fife KY16 9SX

United Kingdom

**Abstract:**

A permutation is square-free if it does not contain two consecutive
factors of length two or more that are order-isomorphic. A permutation
is bicrucial with respect to squares if it is square-free but any
extension of it to the right or to the left by any element gives a
permutation that is not square-free.

Avgustinovich et al. studied bicrucial permutations with respect to
squares, and they proved that there exist bicrucial permutations of
lengths 8*k*+1, 8*k*+5, 8*k*+7 for *k* ≥ 1. It was left as open questions
whether bicrucial permutations of even length, or such permutations of
length 8*k*+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 8*k*+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 A221989 A221990 A238935 A238937 A238942.)

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.

Return to