1,2

A permutation is simple if the only intervals that are fixed are the singletons and [1..n].

For example, the permutation

1234567

2647513

is not simple since it maps [2..5] onto [4..7].

In other words, a permutation [1 ... n] -> [p_1 p_2 ... p_n] is simple if there is no string of consecutive numbers [i_1 ... i_k] which is mapped onto a string of consecutive numbers [p_i_1 ... p_i_k] except for the strings of length k = 1 or n.

M. H. Albert and M. D. Atkinson, Simple permutations and pattern restricted permutations, Discr. Math., 300 (2005), 1-15.

M. H. Albert, M. D. Atkinson and M. Klazar, The enumeration of simple permutations, Journal of Integer Sequences 6 (2003), Article 03.4.4, 18 pages.

R. Brignall et al., Decomposing simple permutations with enumerative consequences, Combinatorica, 28 (2008), 385-400.

Corteel, Sylvie; Louchard, Guy; and Pemantle, Robin, Common intervals of permutations. in Mathematics and Computer Science. III, 3--14, Trends Math., Birkhuser, Basel, 2004.

Corteel, Sylvie; Louchard, Guy; and Pemantle, Robin, Common intervals in permutations, Discrete Math. Theor. Comput. Sci. 8 (2006), no. 1, 189-216.

T. D. Noe, Table of n, a(n) for n = 1..100

a(n)=-A059372(n)+2(-1)^(n+1) - assuming offset=1 in A059372

a(n) ~ n!*(1-4/n)/e^2 - Jon Schoenfield, Aug 05 2006

The simple permutations of lowest degree are 1, 12, 21, 2413, 3142.

Cf. A059372.

Sequence in context: A161803 A057980 A081081 this_sequence A161014 A154852 A088996

Adjacent sequences: A111108 A111109 A111110 this_sequence A111112 A111113 A111114

nonn,nice

N. J. A. Sloane (njas(AT)research.att.com), Oct 14 2005