OFFSET
1,2
COMMENTS
A permutation is squarefree if it does not contain two consecutive factors of length two or more that are in the same relative order. For example, the permutation 243156 is squarefree, while the permutation 631425 contains the square 3142 (indeed, 31 is order-isomorphic to 42). Squarefree permutations exist of any length.
LINKS
Sergey V. Avgustinovich, Sergey Kitaev, Artem V. Pyatkin and Alexandr Valyuzhenich, On Square-Free Permutations, Languages and Combinatorics 16(1): 3-10 (2011).
Ian Gent, Sergey Kitaev, Alexander Konovalov, Steve Linton and Peter Nightingale, S-crucial and bicrucial permutations with respect to squares, arXiv:1402.3582 [math.CO], 2014; and J. Int. Seq. 18 (2015) 15.6.5.
Carla Groenland and Tom Johnston, The lengths for which bicrucial square-free permutations exist, arXiv:2109.00502 [math.CO], 2021.
FORMULA
EXAMPLE
a(1)=1 [1]; a(2)=2 [12, 21]; a(3)=6 [123,132, 213, 231, 312, 321]; a(4)=12 [1243, 1342, 1432, 2341, 2431, 3421, 2134, 3124, 4123, 3214, 4213, 4312].
MATHEMATICA
noq[w_] := Length[w] < 4 || Catch[ Do[If[ Ordering@ Ordering@ Take[w, k] == Ordering@ Ordering@ Take[w, {k+1, 2*k}], Throw@False], {k, 2, Length[w]/2}]; True]; r[p_, f_] := Block[{w}, If[f == {}, 1, Sum[ If[noq[w = Prepend[p, f[[i]]]], r[w, Delete[f, i]], 0], {i, Length@f}]]]; a[n_] := r[{}, Range[n]]; Array[a, 9] (* Giovanni Resta, May 12 2013 *)
CROSSREFS
KEYWORD
nonn,nice,more
AUTHOR
Olexandr Konovalov, May 12 2013
EXTENSIONS
a(16) from Giovanni Resta, May 13 2013
a(17)-a(18) from Steve Linton, May 18 2013
a(19)-a(23) from Tom Johnston, Sep 02 2021
STATUS
approved