|
| |
|
|
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, 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
(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).
|
|
|
REFERENCES
|
M. Bousquet-Mélou, Sorted or sortable permutations, Discrete Math., 225 (2000), 25-50.
J. West, Sorting twice through a stack, Theroret. Comput. Sci. 117 (1993) 303-313.
|
|
|
LINKS
|
Table of n, a(n) for n=0..28.
Index entries for sequences related to sorting
M. Bousquet-Mélou, Sorted or sortable permutations
|
|
|
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
|
|
|
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]]] (* From Jean-François Alcover, Nov 14 2011 *)
|
|
|
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 A001998
Adjacent sequences: A027429 A027430 A027431 * A027433 A027434 A027435
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
Mireille Bousquet-Mélou
|
|
|
STATUS
|
approved
|
| |
|
|
