|
%I #92 Jan 28 2024 04:45:59
%S 1,2,0,2,6,46,338,2926,28146,298526,3454434,43286526,583835650,
%T 8433987582,129941213186,2127349165822,36889047574274,675548628690430,
%U 13030733384956418,264111424634864638,5612437196153963522,124789500579376435198,2897684052921851965442
%N Number of simple permutations of degree n.
%C A permutation is simple if the only intervals that are mapped onto intervals are the singletons and [1..n].
%C For example, the permutation
%C 1234567
%C 2647513
%C is not simple since it maps [2..5] onto [4..7].
%C 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 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 S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
%D Bridget Eileen Tenner, Interval posets of permutations, arXiv:2007.06142, Aug 2021.
%H T. D. Noe, <a href="/A111111/b111111.txt">Table of n, a(n) for n = 1..100</a>
%H M. H. Albert and M. D. Atkinson, <a href="http://dx.doi.org/10.1016/j.disc.2005.06.016">Simple permutations and pattern restricted permutations</a>, Discr. Math., 300 (2005), 1-15.
%H M. H. Albert, M. D. Atkinson and M. Klazar, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Albert/albert.html">The enumeration of simple permutations</a>, Journal of Integer Sequences 6 (2003), Article 03.4.4, 18 pages.
%H Joerg Arndt, <a href="/A111111/a111111.txt">All simple permutations for n <= 6</a>
%H Michael Borinsky, <a href="https://arxiv.org/abs/1603.01236">Generating asymptotics for factorially divergent sequences</a>, arXiv preprint arXiv:1603.01236 [math.CO], 2016.
%H M. Bouvel, M. Mishna, and C. Nicaud, <a href="https://doi.org/10.46298/dmtcs.2346">Some simple varieties of trees arising in permutation analysis</a>, FPSAC 2013 Paris, France DMTCS Proc. AS, 2013, 855-866.
%H Robert Brignall, Sophie Huczynska, and Vincent Vatter, <a href="http://arxiv.org/abs/math/0608391">Simple permutations and algebraic generating functions</a>, arXiv:math/0608391 [math.CO], (2006).
%H R. Brignall, S. Huczynska, and V. Vatter, <a href="http://dx.doi.org/10.1007/s00493-008-2314-0">Decomposing simple permutations with enumerative consequences</a>, Combinatorica, 28 (2008) 384-400.
%H Robert Brignall, <a href="http://arxiv.org/abs/0801.0963">A Survey of Simple Permutations</a>, arXiv:0801.0963 [math.CO], (18-April-2008)
%H Sylvie Corteel, Guy Louchard, and Robin Pemantle, <a href="https://doi.org/10.46298/dmtcs.362">Common intervals in permutations</a>, Discrete Math. Theor. Comput. Sci. 8 (2006), no. 1, 189-216.
%H Scott Garrabrant and Igor Pak, <a href="http://www.math.ucla.edu/~pak/papers/PatternAvoid10.pdf">Pattern Avoidance is Not P-Recursive</a>, preprint, 2015.
%H V. Jelínek and P. Valtr, <a href="http://arxiv.org/abs/1307.0027">Splittings and Ramsey Properties of Permutation Classes</a>, arXiv preprint arXiv:1307.0027 [math.CO], 2013.
%H Djamila Oudrar, <a href="http://arxiv.org/abs/1604.05839">Sur l'énumération de structures discrètes, une approche par la théorie des relations</a>, Thesis (in French), arXiv:1604.05839 [math.CO], 2016.
%H Djamila Oudrar and Maurice Pouzet, <a href="http://arxiv.org/abs/1409.1108">Profile and hereditary classes of ordered relational structures</a>, arXiv preprint arXiv:1409.1108 [math.CO], 2014.
%H Djamila Oudrar, Maurice Pouzet, and Imed Zaguia, <a href="https://arxiv.org/abs/2205.08992">Minimal prime ages, words and permutation graphs Extended abstract</a>, arXiv:2205.08992 [math.CO], 2022.
%F a(n) = -A059372(n)+2(-1)^(n+1).
%F a(n) ~ n!*(1-4/n)/e^2. - _Jon E. Schoenfield_, Aug 05 2006
%F 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
%e G.f. = x + 2*x^2 + 2*x^4 + 6*x^5 + 46*x^6 + 338*x^7 + 2926*x^8 + ...
%e The simple permutations of lowest degree are 1, 12, 21, 2413, 3142.
%t 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;
%t A111111 (* _Jean-François Alcover_, Jul 13 2016 *)
%o (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
%o a(n)=sum(i=0,n!-1, simple(numtoperm(n,i))) \\ _Charles R Greathouse IV_, Nov 05 2013
%o seq(N) = Vec(2 + 2*x^2 - 2/(1+x) - serreverse(x*Ser(vector(N, n, n!)))); \\ _Gheorghe Coserea_, Jan 22 2017
%Y Cf. A059372, A280780.
%K nonn,nice
%O 1,2
%A _N. J. A. Sloane_, Oct 14 2005
%E Incorrect statement removed by _Jay Pantone_, Jul 16 2014
%E Word "fixed" removed by _Franklin T. Adams-Watters_, Jul 22 2014
|
