|
Search: id:A027432
|
|
|
| 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. |
|
+0
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
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
Series reversion of g.f. A(x) is -A(-x) (if offset 1).
|
|
REFERENCES
|
M. Bousquet-Melou, 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
|
Index entries for sequences related to sorting
M. Bousquet-M\'{e}lou, Sorted or sortable permutations
|
|
FORMULA
|
G.f. is algebraic of degree 4.
If g.f. is A(x), y=xA(x) satisfies (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=0.
G.f. A(x) satisfies A(x) = x+B(xA(x)) where B(x) is g.f. for A000260 (offset 1). - Michael Somos Sep 07 2005
|
|
PROGRAM
|
(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: A124501 A124344 A049125 this_sequence A032128 A052829 A001998
Adjacent sequences: A027429 A027430 A027431 this_sequence A027433 A027434 A027435
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
Mireille BOUSQUET-MELOU (bousquet(AT)labri.u-bordeaux.fr)
|
|
|
Search completed in 0.002 seconds
|
