|
| |
|
|
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
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Series reversion of g.f. A(x) is -A(-x) (if offset 1).
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
