%I A111111
%S A111111 1,2,0,2,6,46,338,2926,28146,298526,3454434,43286526,583835650,
%T A111111 8433987582,129941213186,2127349165822,36889047574274,
%U A111111 675548628690430,13030733384956418,264111424634864638
%N A111111 Number of simple permutations of degree n.
%C A111111 A permutation is simple if the only intervals that are fixed are the 
               singletons and [1..n].
%C A111111 For example, the permutation
%C A111111 1234567
%C A111111 2647513
%C A111111 is not simple since it maps [2..5] onto [4..7].
%C A111111 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.
%D A111111 M. H. Albert and M. D. Atkinson, Simple permutations and pattern restricted 
               permutations, Discr. Math., 300 (2005), 1-15.
%D A111111 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.
%D A111111 R. Brignall et al., Decomposing simple permutations with enumerative 
               consequences, Combinatorica, 28 (2008), 385-400.
%D A111111 Corteel, Sylvie; Louchard, Guy; and Pemantle, Robin, Common intervals 
               of permutations. in Mathematics and Computer Science. III, 3--14, 
               Trends Math., Birkhuser, Basel, 2004.
%D A111111 Corteel, Sylvie; Louchard, Guy; and Pemantle, Robin, Common intervals 
               in permutations, Discrete Math. Theor. Comput. Sci. 8 (2006), no. 
               1, 189-216.
%H A111111 T. D. Noe, <a href="b111111.txt">Table of n, a(n) for n = 1..100</a>
%F A111111 a(n)=-A059372(n)+2(-1)^(n+1) - assuming offset=1 in A059372
%F A111111 a(n) ~ n!*(1-4/n)/e^2 - Jon Schoenfield, Aug 05 2006
%e A111111 The simple permutations of lowest degree are 1, 12, 21, 2413, 3142.
%Y A111111 Cf. A059372.
%Y A111111 Sequence in context: A161803 A057980 A081081 this_sequence A161014 A154852 
               A088996
%Y A111111 Adjacent sequences: A111108 A111109 A111110 this_sequence A111112 A111113 
               A111114
%K A111111 nonn,nice
%O A111111 1,2
%A A111111 N. J. A. Sloane (njas(AT)research.att.com), Oct 14 2005