OFFSET

1,7

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 square 3142 (indeed, 31 is order-isomorphic to 42). A permutation is right-crucial with respect to squares if it is squarefree but any extension of it to the right by an element results in a permutation (of one larger length) that is not squarefree. For example, the permutation 2136547 is right-crucial with respect to squares. For any length larger than 6, there exist right-crucial permutations with respect to squares.

LINKS

Sergey V. Avgustinovich, Sergey Kitaev, Artem V. Pyatkin, and Alexandr Valyuzhenich, On Square-Free Permutations, Journal of Automata, 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.

EXAMPLE

a(7) = 60 since all right-crucial permutations with respect to squares of length 7 are 2136547, 2137546, 2146537, 2147536, 2156437, 2157436, 2167435, 3146527, 3147526, 3156427, 3157426, 3167425, 3246517, 3247516, 3256417, 3257416, 3267415, 3421675, 3521674, 3621574, 3721564, 4156327, 4157326, 4167325, 4256317, 4257316, 4267315, 4356217, 4357216, 4367215, 4521673, 4531672, 4532671, 4621573, 4631572, 4632571, 4721563, 4731562, 4732561, 5167324, 5267314, 5367214, 5467213, 5621473, 5631472, 5632471, 5641372, 5642371, 5721463, 5731462, 5732461, 5741362, 5742361, 6721453, 6731452, 6732451, 6741352, 6742351, 6751342, 6752341.

CROSSREFS

KEYWORD

nonn,more

AUTHOR

Olexandr Konovalov, May 12 2013

EXTENSIONS

a(16) from Steve Linton, May 20 2013

a(17) from Ian P. Gent et al., Feb 17 2014

a(18)-a(23) from Tom Johnston, Sep 02 2021

STATUS

approved