A221990 The number of right-crucial (with respect to squares) permutations of 1,...,n.

0, 0, 0, 0, 0, 0, 60, 140, 518, 1444, 8556, 31992, 220456, 984208, 7453080, 39692800, 289981136, 1467791790, 14316379108, 86001855074, 949804475890, 6494842788046, 73636377696714

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

Table of n, a(n) for n=1..23.

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

Cf. A221989.

Sequence in context: A336628 A336443 A252954 * A043478 A044311 A044692

Adjacent sequences: A221987 A221988 A221989 * A221991 A221992 A221993

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