The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)



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. Right-crucial permutations with respect to squares exist of any length larger than 6.

A permutation is bicrucial with respect to squares if it is both right-crucial and left-crucial. 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.


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

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.


Cf. A221989, A221990.

Sequence in context: A125037 A101365 A022080 * A033688 A058283 A096510

Adjacent sequences:  A238932 A238933 A238934 * A238936 A238937 A238938




Alexander Konovalov et al., Mar 07 2014


a(21)-a(24) from Tom Johnston, Sep 02 2021



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 26 22:05 EST 2022. Contains 350601 sequences. (Running on oeis4.)