

A238935


The number of bicrucial (with respect to squares) permutations of 1,...,n.


0



0, 0, 0, 0, 0, 0, 0, 0, 54, 0, 0, 0, 69856, 0, 2930016, 0, 40654860, 0, 162190472, 0, 312348610684, 0, 29202730580288, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,9


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 orderisomorphic to 42).
A permutation is rightcrucial 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 rightcrucial with respect to squares. Rightcrucial permutations with respect to squares exist of any length larger than 6.
A permutation is bicrucial with respect to squares if it is both rightcrucial and leftcrucial. Such permutations are also called bicrucial squarefree permutations. For example, the permutation 143289756(14)(11)(10)(17)(19)(16)(13)(15)(18)(12) is bicrucial with respect to squares. Such permutations exist of any odd length 8k+1, 8k+5, 8k+7, where k>0. For the case 8k+3, there are no bicrucial squarefree permutations of length 11, while such permutations of lengths 19 and 27 exist. The shortest bicrucial squarefree permutation of even length is of length 32: (28)(30)(31)(23)(22)(24)(29)(27)(19)(25)(26)(17)(13)(18)(21)(20)(14)(16)(32)879(15)(12)5(10)(11)31462.


LINKS

Sergey V. Avgustinovich, Sergey Kitaev, Artem V. Pyatkin, and Alexandr Valyuzhenich, On SquareFree Permutations, Journal of Automata, Languages and Combinatorics 16(1): 310 (2011).


CROSSREFS



KEYWORD

nonn,more


AUTHOR



EXTENSIONS



STATUS

approved



