login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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 (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

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

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, 2014  and J. Int. Seq. 18 (2015) 15.6.5.

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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 27 14:39 EST 2020. Contains 331295 sequences. (Running on oeis4.)