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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A111111 Number of simple permutations of degree n. 12
 1, 2, 0, 2, 6, 46, 338, 2926, 28146, 298526, 3454434, 43286526, 583835650, 8433987582, 129941213186, 2127349165822, 36889047574274, 675548628690430, 13030733384956418, 264111424634864638, 5612437196153963522, 124789500579376435198, 2897684052921851965442 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS A permutation is simple if the only intervals that are mapped onto intervals 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. REFERENCES Corteel, Sylvie; Louchard, Guy; and Pemantle, Robin, Common intervals of permutations. in Mathematics and Computer Science. III, 3--14, Trends Math., Birkhuser, Basel, 2004. S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7 Bridget Eileen Tenner, Interval posets of permutations, arXiv:2007.06142, Aug 2021. LINKS T. D. Noe, Table of n, a(n) for n = 1..100 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. Joerg Arndt, All simple permutations for n <= 6 Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016. M. Bouvel, M. Mishna, and C. Nicaud, Some simple varieties of trees arising in permutation analysis, FPSAC 2013 Paris, France DMTCS Proc. AS, 2013, 855-866. Robert Brignall, Sophie Huczynska, Vincent Vatter, Simple permutations and algebraic generating functions, arXiv:math/0608391 [math.CO], (2006). R. Brignall, S. Huczynska, and V. Vatter, Decomposing simple permutations with enumerative consequences, Combinatorica, 28 (2008) 384-400. Robert Brignall, A Survey of Simple Permutations, arXiv:0801.0963 [math.CO], (18-April-2008) Sylvie Corteel, Guy Louchard, and Robin Pemantle, Common intervals in permutations, Discrete Math. Theor. Comput. Sci. 8 (2006), no. 1, 189-216. Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015. V. Jelínek and P. Valtr, Splittings and Ramsey Properties of Permutation Classes, arXiv preprint arXiv:1307.0027 [math.CO], 2013. Djamila Oudrar, Sur l'énumération de structures discrètes, une approche par la théorie des relations, Thesis (in French), arXiv:1604.05839 [math.CO], 2016. Djamila Oudrar and Maurice Pouzet, Profile and hereditary classes of ordered relational structures, arXiv preprint arXiv:1409.1108 [math.CO], 2014. Djamila Oudrar, Maurice Pouzet, and Imed Zaguia, Minimal prime ages, words and permutation graphs Extended abstract, arXiv:2205.08992 [math.CO], 2022. FORMULA a(n) = -A059372(n)+2(-1)^(n+1). a(n) ~ n!*(1-4/n)/e^2. - Jon E. Schoenfield, Aug 05 2006 a(n) ~ n!*exp(-2)*(1 - 4/n + 2/(n*(n-1)) - (40/3)/(n*(n-1)*(n-2)) - ...). Coefficients are given by A280780(n)/A280781(n).- Gheorghe Coserea, Jan 23 2017 EXAMPLE G.f. = x + 2*x^2 + 2*x^4 + 6*x^5 + 46*x^6 + 338*x^7 + 2926*x^8 + ... The simple permutations of lowest degree are 1, 12, 21, 2413, 3142. MATHEMATICA nmax = 20; t[n_, k_] := t[n, k] = Sum[(m + 1)!*t[n - m - 1, k - 1], {m, 0, n - k}]; t[n_, 1] = n!; t[n_, n_] = 1; tnk = Table[t[n, k], {n, 1, nmax}, {k, 1, nmax}]; A111111 = -Inverse[tnk][[All, 1]] + 2*(-1)^Range[0, nmax - 1]; A111111[[2]] = 2; A111111 (* Jean-François Alcover, Jul 13 2016 *) PROG (PARI) simple(v)=for(i=1, #v-1, for(j=i+1, #v, my(u=vecsort(v[i..j])); if(u[#u]-u[1]==#u-1 && #u<#v, return(0)))); 1 a(n)=sum(i=0, n!-1, simple(numtoperm(n, i))) \\ Charles R Greathouse IV, Nov 05 2013 seq(N) = Vec(2 + 2*x^2 - 2/(1+x) - serreverse(x*Ser(vector(N, n, n!)))); \\ Gheorghe Coserea, Jan 22 2017 CROSSREFS Cf. A059372, A280780. Sequence in context: A057980 A242840 A081081 * A185343 A161014 A344768 Adjacent sequences: A111108 A111109 A111110 * A111112 A111113 A111114 KEYWORD nonn,nice AUTHOR N. J. A. Sloane, Oct 14 2005 EXTENSIONS Incorrect statement removed by Jay Pantone, Jul 16 2014 Word "fixed" removed by Franklin T. Adams-Watters, Jul 22 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 29 03:03 EST 2023. Contains 367422 sequences. (Running on oeis4.)