A221989 The number of squarefree permutations of 1,...,n.

1, 2, 6, 12, 34, 104, 406, 1112, 3980, 15216, 68034, 312048, 1625968, 8771376, 53270068, 319218912, 2135312542, 14420106264, 109051882344, 815868128288, 6772099860398, 56501841264216, 519359404861294

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

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

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). - Olexandr 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 * A349002 A204512 A099576

Adjacent sequences: A221986 A221987 A221988 * A221990 A221991 A221992

Keyword

nonn,nice,more

Author

Olexandr Konovalov, May 12 2013

Extensions

a(16) from Giovanni Resta, May 13 2013

a(17)-a(18) from Steve Linton, May 18 2013

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

Status

approved