Enumeration of 2-Stack-Sortable Permutations By Shalosh B. Ekhad In this article, we will enumerate 2-Stack-Sortable Permutations by discovering (easily provable, once discovered!) an algebraic equation for\ the generating function of the enumerating sequence, and will also present the implied linear recurr\ ence equation with polynomial coefficients satisfied by the enumerating sequence We will do this by using as TRAINING DATA (so to speak!) the first , 20, terms, and admit failure otherwise According to the article Doron Zeilberger, A Proof of Julian West's Conjecture ... Discrete Math 102(1992), 85-93 Available from http://www.math.rutgers.edu/~zeilberg/mamarimY/julian.pdf The generating function, f(x,y),in the two variables (y being the so-called \ catalytic variable) satisfies the FUNCTIONAL EQUATION 1 x y (f(x, 1) - y f(x, y)) (f(x, 1) - f(x, y)) f(x, y) = ------- + --------------------------------------------- 1 - x y 2 (1 - y) we would be interested in the straight enumeration, whose generating functio\ n is f(x,1) -------------------------------------------------------- For the Enumeration of 2-stack-sortable permutations, we have Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation 1 x y (f(x, 1) - y f(x, y)) (f(x, 1) - f(x, y)) f(x, y) = ------- + --------------------------------------------- 1 - x y 2 (1 - y) Then P(x)=f(x,1) satisfies the following algebraic equation 2 2 2 2 3 -1 + 11 x + x + (1 - 14 x + 3 x ) P + x (2 + 3 x) P + x P = 0 and in Maple input notation -1+11*x+x^2+(1-14*x+3*x^2)*P+x*(2+3*x)*P^2+x^2*P^3 = 0 The first, 30, terms, for the sake of the OEIS are [1, 2, 6, 22, 91, 408, 1938, 9614, 49335, 260130, 1402440, 7702632, 42975796, 243035536, 1390594458, 8038677054, 46892282815, 275750636070, 1633292229030, 9737153323590, 58392041019795, 352044769046880, 2132866978427640, 12980019040145352, 79319075627675556, 486556845464525528, 2995168113638767536, 18498288730876090608, 114595331036190018936, 711933341625150895008] Furthermore, the sequence of coefficients, let's call them , A[n], satisfy: (3 n + 2) (3 n + 1) A[n] -3/2 ------------------------ + A[n + 1] = 0 (n + 2) (2 n + 3) and in Maple input format -3/2*(3*n+2)*(3*n+1)/(n+2)/(2*n+3)*A[n]+A[n+1] = 0 Just for fun, A[100], equals 409659766834989876832016504243771792550166593344529698897890119433008849645240 ---------------------------------------------------- This colcludes this article, that took, 1.360, seconds to generate.