login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A027432 Related to sorting procedure studied by West: number of permutations that are both sorted (i.e., obtainable as output of the sorting procedure) and one-stack sortable. 2

%I

%S 1,1,1,2,4,10,25,69,192,562,1663,5065,15592,48874,154651,495418,

%T 1599816,5212650,17098590,56473664,187572584,626430568,2101977231,

%U 7084963950,23976649328,81447876258,277627821135,949393445553,3256266981128,11199653726786,38620292110925

%N Related to sorting procedure studied by West: number of permutations that are both sorted (i.e., obtainable as output of the sorting procedure) and one-stack sortable.

%C Series reversion of g.f. A(x) is -A(-x) (if offset 1).

%H Vaclav Kotesovec, <a href="/A027432/b027432.txt">Table of n, a(n) for n = 0..500</a>

%H M. Bousquet-Mélou, <a href="http://dx.doi.org/10.1016/S0012-365X(00)00146-1">Sorted or sortable permutations</a>, Discrete Math., 225 (2000), 25-50.

%H J. West, <a href="http://dx.doi.org/10.1016/0304-3975(93)90321-J">Sorting twice through a stack</a>, Theoret. Comput. Sci. 117 (1993) 303-313.

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>

%F G.f. is algebraic of degree 4.

%F If g.f. is A(x), y = x*A(x) satisfies (x^4 - 3*x^3 + 3*x^2 - x) + y * (4*x^3 + 29*x^2 - 7*x + 1) + y^2 * (6*x^2 - 29*x + 3) + y^3 * (4*x + 3) + y^4 = 0.

%F G.f. A(x) satisfies A(x) = x + B(x*A(x)) where B(x) is g.f. for A000260 (offset 1). - _Michael Somos_, Sep 07 2005

%F Recurrence: 3*(n-1)*(n+1)*(3*n+1)*(3*n+2)*(24*n^2 - n - 90)*a(n) = 2*(1680*n^6 - 1294*n^5 - 10977*n^4 + 16676*n^3 - 3843*n^2 - 2602*n + 720)*a(n-1) + 4*(768*n^6 - 3872*n^5 + 3560*n^4 + 6195*n^3 - 11498*n^2 + 6887*n - 2520)*a(n-2) - 32*n*(2*n-5)*(4*n-11)*(4*n-9)*(24*n^2 + 47*n - 67)*a(n-3). - _Vaclav Kotesovec_, Mar 18 2014

%F a(n) ~ c * (1/r)^n / (sqrt(Pi) * n^(5/2)), where r = (2*sqrt(7)-1)/16 = 0.268218913883... and c = sqrt((9653 + 3619*sqrt(7))/1944) = 3.14498539342675985580088726043277778... - _Vaclav Kotesovec_, Jul 01 2014

%t max = 29; f[x_] = Sum[a[n]*x^n, {n, 0, max}]; a[0] = a[1] = 1; y = x*f[x]; coes = CoefficientList[ Series[(x^4-3x^3+3x^2-x) + y*(4x^3+29x^2-7x+1) + y^2*(6x^2-29x+3) + y^3*(4x+3) + y^4, {x, 0, max}], x]; Table[a[n], {n, 0, max-1}] /. First[ Solve[ Thread[coes == 0]]] (* _Jean-François Alcover_, Nov 14 2011 *)

%t a[0] = a[1] = a[2] = 1; a[3] = 2; a[n_] := a[n] = (1/(3*(n - 1)*(n + 1)* (3*n + 1)*(3*n + 2)*(n*(24*n - 1) - 90)))*(2*(n*(n*(n*(n*(1680*n^2 - 1294*n - 10977) + 16676) - 3843) - 2602) + 720)*a[n-1] + 4*(n*(n*(n* (768*n^3 - 3872*n^2 + 3560*n + 6195) - 11498) + 6887) - 2520)*a[n-2] - 32*n*(n*(2*n*(16*n*(n*(24*n - 133) + 29) + 16153) - 63331) + 33165)* a[n-3]); Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Apr 20 2018, after _Vaclav Kotesovec_ *)

%o (PARI) {a(n) = local(A); if( n<0, 0, n++; A = O(x); for( k=1, n, A = subst( x - 3*(x^2 + y^2) + 7*x*y + 3*(x^3 - y^3) - 29*x*y*(x - y) - (x^4 + y^4) - 4*x*y*(x^2 + y^2) - 6*x^2*y^2, y, A)); polcoeff(A, n))}

%Y Cf. A027361.

%K nonn,nice

%O 0,4

%A _Mireille Bousquet-Mélou_

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 March 20 19:23 EDT 2019. Contains 321349 sequences. (Running on oeis4.)