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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A221989 The number of squarefree permutations of 1,...,n. 4
 1, 2, 6, 12, 34, 104, 406, 1112, 3980, 15216, 68034, 312048, 1625968, 8771376, 53270068, 319218912, 2135312542, 14420106264, 109051882344, 815868128288, 6772099860398, 56501841264216, 519359404861294 (list; graph; refs; listen; history; text; internal format)
 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 For n>2, a(n) = 4*A238937(n) - 2*A238942(n). - Alexander Konovalov, Mar 07 2014 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 Cf. A221990, A238937, A238942. Sequence in context: A164099 A088808 A076278 * A204512 A099576 A303479 Adjacent sequences:  A221986 A221987 A221988 * A221990 A221991 A221992 KEYWORD nonn,nice,more AUTHOR Alexander Konovalov, May 12 2013 EXTENSIONS a(16) from Giovanni Resta, May 13 2013 a(17) and a(18) from Steve Linton, May 18 2013 a(19)-a(23) from Tom Johnston, Sep 02 2021 STATUS approved

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.

Last modified January 26 21:14 EST 2022. Contains 350600 sequences. (Running on oeis4.)