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.

1, 1, 1, 2, 4, 10, 25, 69, 192, 562, 1663, 5065, 15592, 48874, 154651, 495418, 1599816, 5212650, 17098590, 56473664, 187572584, 626430568, 2101977231, 7084963950, 23976649328, 81447876258, 277627821135, 949393445553, 3256266981128, 11199653726786, 38620292110925

Offset

0,4

Comments

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

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..500

M. Bousquet-Mélou, Sorted or sortable permutations, Discrete Math., 225 (2000), 25-50.

J. West, Sorting twice through a stack, Theoret. Comput. Sci. 117 (1993) 303-313.

Index entries for sequences related to sorting

Formula

G.f. is algebraic of degree 4.

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.

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

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

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

Mathematica

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 *)
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 *)

Prog

(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))}

Crossrefs

Cf. A027361.

Sequence in context: A124344 A049125 A191768 * A032128 A052829 A339295

Adjacent sequences: A027429 A027430 A027431 * A027433 A027434 A027435

Keyword

nonn,nice

Author

Mireille Bousquet-Mélou

Status

approved